Introduction To Compiler Design For CSE

Compiler is a program which translates a program written in one language (the source language) to an equivalent program in other language (the target language). Usually the source language is a high level language like Java, C, Fortran etc. whereas the target language is machine code or "code" that a computer's processor understands.
The source language is optimized for humans. It is more user-friendly, to some extent platform-independent. They are easier to read, write, and maintain and hence it is easy to avoid errors. Ultimately, programs written in a high-level language must be translated into machine language by a compiler. The target machine language is efficient for hardware but lacks readability.

Compilers

. Translates from one representation of the program to another

. Typically from high level source code to low level machine code or object code

. Source code is normally optimized for human readability

- Expressive: matches our notion of languages (and application?!)

- Redundant to help avoid programming errors

. Machine code is optimized for hardware

- Redundancy is reduced

- Information about the intent is lost

How to translate?

The high level languages and machine languages differ in level of abstraction. At machine level we deal with memory locations, registers whereas these resources are never accessed in high level languages. But the level of abstraction differs from language to language and some languages are farther from machine code than others

. Goals of translation

- Good performance for the generated code

Good performance for generated code : The metric for the quality of the generated code is the ratio between the size of handwritten code and compiled machine code for same program. A better compiler is one which generates smaller code. For optimizing compilers this ratio will be lesser.

- Good compile time performance

Good compile time performance : A handwritten machine code is more efficient than a compiled code in terms of the performance it produces. In other words, the program handwritten in machine code will run faster than compiled code. If a compiler produces a code which is 20-30% slower than the handwritten code then it is considered to be acceptable. In addition to this, the compiler itself must run fast (compilation time must be proportional to program size).

- Maintainable code

- High level of abstraction

. Correctness is a very important issue.

Correctness : A compiler's most important goal is correctness - all valid programs must compile correctly. How do we check if a compiler is correct i.e. whether a compiler for a programming language generates correct machine code for programs in the language. The complexity of writing a correct compiler is a major limitation on the amount of optimization that can be done.

Can compilers be proven to be correct? Very tedious!

. However, the correctness has an implication on the development cost 

Many modern compilers share a common 'two stage' design. The "front end" translates the source language or the high level program into an intermediate representation. The second stage is the "back end", which works with the internal representation to produce code in the output language which is a low level code. The higher the abstraction a compiler can support, the better it is.

The Big picture

• Compiler is part of program development environment
• The other typical components of this environment are editor, assembler, linker, loader, debugger, profiler etc.
• The compiler (and all other tools) must support each other for easy program development

All development systems are essentially a combination of many tools. For compiler, the other tools are debugger, assembler, linker, loader, profiler, editor etc. If these tools have support for each other than the program development becomes a lot easier.

This is how the various tools work in coordination to make programming easier and better. They all have a specific task to accomplish in the process, from writing a code to compiling it and running/debugging it. If debugged then do manual correction in the code if needed, after getting debugging results. It is the combined contribution of these tools that makes programming a lot easier and efficient. 

How to translate easily?

In order to translate a high level code to a machine code one needs to go step by step, with each step doing a particular task and passing out its output for the next step in the form of another program representation. The steps can be parse tree generation, high level intermediate code generation, low level intermediate code generation, and then the machine language conversion. As the translation proceeds the representation becomes more and more machine specific, increasingly dealing with registers, memory locations etc.

 

. Translate in steps. Each step handles a reasonably simple, logical, and well defined task

. Design a series of program representations

. Intermediate representations should be amenable to program manipulation of various kinds (type checking, optimization, code generation etc.)

. Representations become more machine specific and less language specific as the translation proceeds