COMPILER DESIGN FAQ

Q. What do you mean by compilers? What are the parts of compilation?

Ans: Compiler: A compiler is a program that reads a program written in one language – the source language – and translates it into an equivalent program in another language – the target language.

The compiler reports to its user the presence of errors in the source program. Compilers are sometime classified as single – pass, multi – pass, load and go, debugging or optimizing, depending on how they have been constructed or on what function they are supposed to perform.

Compilation parts: There are two parts to compilation which are as follows: --

• Analysis


• Synthesis

Analysis: The analysis part breaks up the source program into consistent pieces and creates an intermediate representation of the source program. During analysis, the operations implied by the source program are determined and recorded in a hierarchical structure called a tree. Often a special kind of tree called a syntax tree is used, in which each node represents an operation and the children of a node represent the arguments of the operation.

Example: The syntax tree for an assignment operation as follows:

Synthesis: The synthesis part constructs the desired target program from the intermediate representation of the two parts; synthesis requires the most specialized techniques.

Q. What are the phases of analysis and describe them.

Ans: Analysis of the source program: In compiling, analysis consists of three phases: --

• Linear analysis (Lexical Analysis)


• Hierarchical analysis (Syntax Analysis)


• Semantic analysis

Linear (Lexical) analysis: In a compiler, linear analysis is called lexical analysis or scanning. In this case, the stream of characters which make the source program is read from left to right and generates the tokens which are sequences of characters having a collective meaning.

Example: In lexical analysis, the characters in the assignment statement

position:= initial + rate * 60

would be grouped into the following token ---

• The identifier position


• The assignment symbol :=


• The identifier initial


• The plus sign


• The identifier rate


• The multiplication sign


• The number 60

The blanks separating the characters of these tokens would normally be eliminated during lexical analysis.

Hierarchical analysis / Parsing / Syntax analysis: Hierarchical analysis is called parsing or syntax analysis. In this case the tokens of the source program are grouped hierarchically into grammatical parses that are used by the compiler to synthesize output. Usually, the grammatical phrases of the source program are represented by a parse tree as follows:

The hierarchical structure of a program is usually expressed by recursive rules. The rules of expression are as follows:--

• Any identification is an expression.


• Any number is an expression


• If expression1 and expression2 are expressions then so are

expression1 + expression2

expression1 * expression2

(expression1)

Semantic analysis: The semantic analysis phase checks the source program for semantic errors and gathers type information for the subsequent code – generation phase. It uses the hierarchical structure determined by the syntax analysis phase to identify the operators and operands of expressions and statements. An important component of semantic analysis is type checking.

Q. What is symbol table? What are the functions of symbol table?

Ans: Symbol table: A symbol table is a data structure containing a record for each identifier with fields for the attributes of the identifier. It is generally used to store information about various source language constructs. The information is collected by the analysis phases of the compiler and used by the synthesis phases to generate the target code.

Q. Derive the parse tree from the statement “position: = initial + rate * 60”.

Ans: At first the defined statement should be grouped into tokens as above and then derive the parse tree as follows: --

Q. What are the phases of a compiler?

Ans: The phases of compiler: A compiler operates in phases each of which transforms the source program from one representation to another. A typical decomposition of a compiler is as follows: --

The first three phases from the bulk of the Analysis portion of a compiler were introduced in the last section. Two other activities, symbol table management and error handling are shown interacting with the six phases of lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code optimization and code generation.

• Lexical analysis: In lexical analysis the stream of character making up the source program is read from left to right and grouped into tokens that are sequence of characters having a collective meaning. The phase that makes this analysis portion is called lexical analyzer.


• Syntax analysis: Syntax analysis involves grouping the tokens of the source program into grammatical phrases that are used by the compiler to synthesize output. The phase that makes this analysis portion is called syntax analyzer.


• Semantic analysis: The semantic analyzer makes the semantic analysis portion. The semantics analysis phase checks the source program for semantic error and gathers type information or the subsequent code generation phase4. It uses the hierarchical structure determines by the syntax tree.


• Intermediate code generation: After syntax and semantics analysis some compilers generate an explicit intermediate representation of the source program. We can think of this intermediate representation as a program for an abstract machine. This intermediate representation should have two important properties.

• It should be easy to produce


• It should be easy to translate into the target program.

• Code optimization: The code optimizer phase attempts to improve the intermediate code, so that faster running machine code will result.


• Code generation: The final phase of the compiler is the generation of target code. Consisting normally o relocate able machine code or assembly code. Memory locations are selected for each of the variables used by the program. Then intermediate instructions are each translated into a sequence of machine instructions that perform the same task. A crucial aspect is the assignment of variables to registers.