Topics in compiler implementation

Some compiler-related ideas & problems (Appel : Modern compiler implementation in Java):
- Instruction selection : Machine instructions are represented by tree pattern. The optimal code is generated by selecting tree patterns which form the minimum tree. Thus, instruction selection becomes a task of tiling the tree with minimal set of tree patterms. There is a number of approaches to this problem, most notably, the Maximal Munch algorithm and Dynamic Programming.
In pratice, tree pattern - based approach can be a problem when optimizing for cics, rather than risc machine...
- Liveness Analysis : In order to optimize the register allocation, the compiler must analyze which variables are used ("alive") during every segment of program (for example, we can observe every basic block as one segment). Variables which are not used at the same time can be allocated in the same register. We observe the control-flow-graph of the program and determine the "live" variables at every edge of the graph. Then, we can perform graph partitioning in order to divide the program into segments with a number of alive variables which correspond to number of system registers. Again, we should do this in a optimal manner (every segment should allocate all registers, but among segments there should be minimum needed transfer of data between registers and memory).

Notes on automata theory

Remarks from Motwani, Hopcroft & Ullman : Introduction to Automata Theory, Languages and Computation (during 45min reading) :
Chapter 2 : Finite Automata
- Give an example of practical communication/transaction protocol which can only be analyzed via automata model
- Examples of structural patterns which require formal verification of correctness ?
- Complexity bound for automata which require formal verification?
(even in the case of 2 simple, say 4-state automata, their single interconnection yields a product of automata resulting in 16-state automata )

- Optimal representation of DFA ? (space-efficient Transition Tables). Alternative methods of representation ?
- Algorithm-efficient representations ? (ex. finding all loops in automation by observing transition table -> can we speedup the algoritm by using structure other than table)

A NFA models the ability of input to "guess" the right state. Actually this can be seen as increasing complexity in order to simplify the description. The automata can reduce complexity of the problem by increasing the description. However, there are problems that cannot be treated in this manner.

A NFA is more descriptive than DFA, while there should be a 1-1 mapping NFA <-> DFA (Using a Tompson's algorithm , we can efficiently construct the DFA corresponding to NFA). Still, a NFA of size N corresponds to a DFA of size N+K . How do we prove the 1-1 mapping then ?

- [Offtopic] -> how can we efficiently create a program for automata generation via feeding it with a list of input examples and accept/reject results for each example ?

& stuff.....

Here it is... I will be typing some random stuff on development, cs & stuff...