Compiler Design and Construction - Unit Wise Questions

A compiler is a program that takes a program written in a source language and translates it into an equivalent program in a target language. As an important part of a compiler is error showing to the programmer.

Analysis phase breaks up the source program into constituent pieces and creates an intermediate representation of the source program. Analysis of source program includes: lexical analysis, syntax analysis and semantic analysis.

1. Lexical Analysis:

In this phase, lexical analyzer reads the source program and returns the tokens of the source program. Token is a sequence of characters that can be treated as a single logical entity (such as identifier, operators, keywords, constants etc.).

2. Syntax Analysis:

In this phase, the syntax analyzer takes the token produced by lexical analyzer as input and generates a parse tree as output. In syntax analysis phase, the parser checks that the expression made by the token is syntactically correct or not, according to the rules that define the syntax of the source language.

3. Semantic Analysis:

In this phase, the semantic analyzer checks the source program for semantic errors and collects the type information for the code generation. Semantic analyzer checks whether they form a sensible set of instructions in the programming language or not. Type-checking is an important part of semantic analyzer.

Example of Analysis phase:

Given RE:

0 +(1+ 0)*00

Converting into NFA using Thomson's method:

For 0,

For 1,

For 1+0

For (1+0)*

For (1+0)*00

For 0+(1+0)*00

Which is the required NFA. Now converting it into a DFA:

The initial state of the NFA is {A}.

Therefore, the initial state of the DFA is:

S₀ = ∈-closure({A}) = {A, B, C, D, E, F, J}

Here,

Σ = {0, 1)

Now,

Dtran[S₀, 0] = ∈-closure(move(S₀, 0)) = ∈-closure({H, K, M}) = {D, E, F, H, I, J, K, M, N} = S₁ (say)

Dtran[S₀, 1] = ∈-closure(move(S₀, 1)) = ∈-closure({G}) = {D, E, F, G, I, J} = S₂

Dtran[S₁, 0] = ∈-closure(move(S₁, 0)) = ∈-closure({H, K, L}) = {D, E, F, H, I, J, L, N} = S₃

Dtran[S₁, 1] = ∈-closure(move(S₁, 1)) = ∈-closure({G}) = {D, E, F, G, I, J} = S₂

Dtran[S₂, 0] = ∈-closure(move(S₂, 0)) = ∈-closure({H, K}) = {D, E, F, H, I, J, K} = S₄

Dtran[S₂, 1] = ∈-closure(move(S₂, 1)) = ∈-closure({G}) = {D, E, F, G, I, J} = S₂

Dtran[S₃, 0] = ∈-closure(move(S₃, 0)) = ∈-closure({H, K}) = {D, E, F, H, I, J, K} = S₄

Dtran[S₃, 1] = ∈-closure(move(S₃, 1)) = ∈-closure({G}) = {D, E, F, G, I, J} = S₂

Dtran[S₄, 0] = ∈-closure(move(S₄, 0)) = ∈-closure({H, K, L}) = {D, E, F, H, I, J, L, N} = S₃

Dtran[S₄, 1] = ∈-closure(move(S₄, 1)) = ∈-closure({G}) = {D, E, F, G, I, J} = S₂

Here, S₁ & S₃ are the accepting state of DFA, since N is a member of both S₁ & S₃ states.

The equivalent DFA is;

Symbol Table is an important data structure created and maintained by the compiler in order to keep track of semantics of variable i.e. it stores information about scope and binding information about names, information about instances of various entities such as variable and function names, classes, objects, etc. It is built in lexical and syntax analysis phases. The information is collected by the analysis phases (front end) of compiler and is used by synthesis phases (back end) of compiler to generate code. It is used by compiler to achieve compile time efficiency.

A symbol table may have the following roles/functions depending upon the language in hand:

• To store the names of all entities in a structured form at one place.
• To verify if a variable has been declared or not.
• To determine the scope of a name (scope resolution).
• To access information associated with a given name.
• To add new information with a given name.
• To delete a name or group of names from the table.
• To implement type checking, by verifying assignments and expressions in the source code are semantically correct.