Compiler Design and Construction Question Bank Solution 2081

Explore comprehensive solutions to Compiler Design and Construction questions, updated for the year 2081. Customize this content for different subjects and years to enhance your SEO.

Explain different phases of compiler in brief.

fig: Block diagram of phases of compiler

Following are the phases of compiler:

1. Lexical Anlysis :
   Lexical analysis is the process where rge source program is read from left to right and grouped into tokens. In this initial stage, the source code is read and transformed into tokens. Tokens, which include operators, symbols, identifiers, and keywords, are the fundamental units of the language. After eliminating comments and whitespace, the lexical analyzer (lexer) produces a stream of tokens for the following stage.
2. Syntatic Anlysis :
   Here, it checks if arrangement of tokens follows grammar rules of programming language. It creates the syntatic structure of the given source program.eg: new_val = old_val + 12.
3. Semantic Anlysis :
   It performs a very importantrole to check the semantic rules of the expression according to the source language. It is required when the compilee may require performing some additional checks.
4. Intermediate Code generator :
   It generates a simple machine independent intermediate language. It should be generated in such a way that it can be easily translated into target machine code.eg:      A =b+c*d/f
   intermediate code for above expression will be:T1 = c*d
   T2 = T1/f
   T3 = b+T2
   A = T3
5. Code Optimization:
   It is the process of removing unnecessary part of a code. It decreases the time ad space complexity of program.
   eg:Before code optimization
   b = 0
   T1 = a+b
   T2= c*T1
   a = T2After code optimization
   b = 0
   a = c*a
6. Code generator:
   It generates the assembly code for the target CPU from an optimized intermediate representation of program.
   eg:
   A = b+c*d/f
   MOV c,R1
   MULT d,R1
   DIV f,R1
   ADD b,R1
   MOV R1,A

Give an example of reduce-reduce conflict. Construct the SLR parsing table for the following grammar.

E→ (L) | a
L → L, E | E

Reduce- Reduce conflict :
The reduce-reduce conflict arises when the parser is not able to decide  which sentential form to use for reduction.

For example:
A → bc
B → abc
and stack contains $ abc, the parser cannot decide whether to reduce it $aA, or to $B

Given grammer.

• E→ (L) | a
• L → L, E | E

step 1: Augment the grammar

• E’→ E
• E → (L) | a
• L → L, E | E

Step 2: Find FIRST and FOLLOW sets.

First sets:

• FIRST (E) = {C, a}
• FIRST (L) = {C, a}

Follow sets:

• FOLLOW(E’) = {$}
• FOLLOW(E) = {$, , , )}
• FOLLOW(L) = {)}

step 3: Construct canonical LR(0) collection for the grammar.

State I₀:

• E’→ .E
• E → .(L)
• E → .a
• L → .L, E
• L → .E

State I₁:

• E’→ E.

State I₂:

• E → (.L)
• L → .L, E
• L → .E
• E → .(L)
• E → .a

State I₃:

• E →a.

State I₄:

• E → (L.)
• L → L., E

State I₅:

• E → (L).

State I₆:

• L → L,. E
• E → .(L)
• E → .a

State I₇:

• L → L,E.

step 4: Now let’s create SLR Parsing Table

What are the significances of intermediate code? Differentiate between DAG and Syntax tree. Represent the instruction A = B + C − D * E + G using quadruple and triple.

Significance of intermediate are as:

• Enhances portability between different machines.
• Optimizes code before final generation.
• Makes semantic analysis easy.

Feature	DAG (Directed Acyclic Graph)	Syntax Tree
Definition	A compact representation of an expression where common subexpressions are merged to eliminate redundancy.	A hierarchical tree structure representing the syntactic structure of an expression.
Redundancy	Eliminates redundant computations by merging duplicate subexpressions.	May contain subexpressions, leading to inefficiencies.
Storage Efficiency	More memory efficient due to elimination of repeated computations.	Less memory efficient as it stores redundant subexpressions separately.

Solution:

Given instruction,
A = B + C – D * E + G

Quadruple Representation:

t₁ = D * E
t₂ = B + C
t₃ = t₂ – t₁
A = t₃ + G

where t₁,  t₂ , t₃ are temporary variable

Op	Arg 1	Arg 2	Result
*	D	E	t1
+	B	C	t2
–	t2	t1	t3
+	t3	G	A

Triple representation

	Op	arg 1	arg 2
(1)	*	D	E
(2)	+	B	C
(3)	–	(2)	(1)
(4)	+	(3)	G
(5)	=	(4)	A

Illustrate the concept of backpatching with an example. Convert the regular expression a(a + b)a# to DFA.

Backpatching:

Backpatching is a technique used in compiler design to resolve forward references. It is used when we need to generate code but don’t yet know the target address. It is common in control structures like if-then-else, while loops, etc.

Eg.:

If (a > b) then
x = 10
end if.

Step1: Initial quadruples generated (with blank jump targets)

100: (>, a, b, t1)
101: (if, t1, _, ?)
102: (=, 10, _, x)
103: (next instruction)

Step2: After backpatching

100: (>, a, b, t1)
101: (if, t1, _, 103)
102: (=, 10, _, x)
103: (next instruction)

given regulat expression,

a(a + b)a#

syntax tree of above RE

 

compute follow pos of

 

What types of information are stored in a symbol table? Discuss the activation record.

A symbol table is a data structure used by a compiler to store information about program identifiers such as variables, functions, classes, and objects.

Information stored in symbol table:

1. Identifier Name: The name of a variable, function, or object
2. Type information: Data type (e.g., int, float, char, etc.)
3. Scope: The block/function where identifier is declared
4. Memory location: Address where the variable is stored in memory

Activation Record:

An activation record is a data structure used during function calls to store important execution information.

Components of activation record:

1. Return Address: Address to resume execution after function completion.
2. Control Link: Pointer to activation record of the calling function.

3. Access Link: Pointer to non-local data in nested function.

4. Local variables: Space allocated for variables declared in the function.

5.  Save of Register Values: Stores registers that must be restored after function execution.

Compute the FIRST and FOLLOW of the non-terminals in the following grammar:
S → (L) ∣ 1
L → LS ∣∗S

Given grammar:

• S → (L) ∣ 1
• L → LS ∣∗S

Removing the left recursion from above grammar as:

• S → (L) ∣ 1
• L → *SL’
• L’ → SL’| ε

Step 1: Compute FIRST of Non-terminals

• FIRST(S) = { (, 1}
• FIRST(L) = { * }
• FIRST(L’) = {(, 1, ε}

Step 2: Compute FOLLOW of Non-terminals

• FOLLOW(S) = { $, ) }
• FOLLOW(L) = { ) }
• FOLLOW(L’) = { ) }

Write the code generation algorithm for the instruction a = b op c.

Given instruction:

a = b op c

Code Generation Algorithm:

MOV b, R1
OP c, R1
MOV R1, a

Here, R1 is the register.

Lets take an eg for a = b + c (here, op is +)

MOV b, R1
ADD c, R1
MOV R1, a

Define core item. Compute the LR(1) item sets for the following grammar:
S → AA
A → aA ∣ b

Core item: A core item in a LR parsing table refers to an item that does not include lookahead symbols.

Given grammar
S → AA
A → aA | b

Step1: Augment the Grammar

• S’ → S
• S → AA
• A → aA
• A → b

Step2: Compute LR(1) items

• S’ → .S, $
• S → .AA, $
• A → .aA, a|b
• A → .b, a|b

I₀ state:

I₀ = closure (S’ → .S)

• S’ → .S, $
• S → .AA, $
• A → .aA, a|b
• A → .b, a|b

I₁ = Goto (I₀, S) = closure (S → S., $)

• S’ → S., $

I₂ = Goto (I₀, A) = closure (S → A.A, $)

• S → A.A, $
• A → .aA,$
• A → .b, $

I₃ = Goto (I₀ , a) = closure (A → .aA, a|b)

• A → a.A, a|b
• A → .b, a|b

= Goto (I₃ , a) = closure (A → .aA, a|b) (Same as I₃)

I₄ = Goto (I₀ , b) = closure (A → .b , a|b)

• A → b. , a|b

= Goto (I₃ , b) = closure (A → b., a|b) (Same as I₄)

I₅ = Goto (I₂ , A) = closure (S → AA., $)

• S → AA. , $

I₆ = Goto (I₂ , a) = closure (A → a.A, $)

• A → a.A, $
• A → .aA, $
• A → .b, $

= Goto (I₆ , a) = closure (A → a.A, $) (Same as I₆)

I₇ = Goto (I₂ , b) = closure (A → b. , $)

• A → b. , a|b

= Goto (I₆ , b) = closure (A → b., $) (Same as I₇)

I₈ = Goto (I₃ , A) = closure (A → aA., a|b)

• A → aA., a|b

I₉ = Goto (I₆ , A) = closure (A → aA., $)

• A → aA., $

Above are the LR(1) item sets for the given grammar.

How do you represent recursion in an activation tree? Generate the three-address code for the following instruction:

n = (a + b) * (c - d);
for(i = 0; i < n; i++) {
    for(j = 0; j < n; j++) {
        x = n + i + j;
    }
}

 

An Activation tree is a tree structure used to represent function calls and their activation during program execution.

When a function calls itself, i.e., recursion, the activation tree shows multiple instances of the function at different levels.

Given instruction:

n = (a + b) * (c – d)
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
n = n + i + j;
}
}

Three address code representation:

t1 = a + b;
t2 = c – d;
n = t1 * t2;
L1: j = 0;
if j >= n goto L2;
i = 0;
L3: if j >= n goto L4;
x = a + i + j
j = j + 1
goto L3
L4: i = i + 1
goto L1
L2:

What are the techniques for compiler optimization? Explain.

Code Optimization: Code optimization is the process of improving the efficiency of code by making it run faster, consume less memory, or use fewer resources while preserving the original functionality and output. The goal is to enhance the performance of the code without altering its expected behavior.

Common Code optimization techniques:

1. Constant Folding:
   In this technique, it involves folding the constants. The expressions that contain the operands having constant values at compile time are evaluated. These expressions are then replaced with their respective results.
   E.g., circumference of circle = (22/7) x Diameter. Here, this technique evaluates the expression 22/7 at compile time. The expression is then replaced with its result 3.14. This saves time at run time.
2. Dead Code Elimination:
   In this technique, it involves eliminating the dead code. The statements are the codes which either never executes or are unreachable, or their output is never used are eliminated.
   Eg: Code before optimization Code after optimization
   i = 0;
   if (i == 1)
   a = x + 5;
   y = 7;

   i = 0;

3. Strength Reduction:
   Here, it involves reducing the strength of expression. This technique replaces the expensive and costly operators with simple and cheaper ones.
   Eg: Code before optimization Code after optimization
   B = A * 2;

   B = A + A;

Describe the synthesized attribute and inherited attribute with an example.

Synthesized attribute:

Synthesized attributes are those attributes which are computed using child nodes in a parse tree. Here, the direction of information flows upward from a child to parent. It is commonly used for value computation and type checking. The dependency is only on attributes of children.

For e.g. E → E1 + T

E.val = E1.val + T.val

Inherited attribute:

Inherited attributes are those attributes which are computed using parent and/or sibling nodes. Here, the information flows downward from parent to child or sideways between siblings. These are useful in enforcing contextual constraints (e.g. type compatibility). The dependency is on the attributes of parents or siblings.

For e.g. S → A B

A.type = S.type

What is a type expression? List the properties of LL(1) grammar.

Type expression:

A type expression is a symbolic representation of a data type in a programming language, commonly used in type checking and semantic analysis.

A type expression can be:

• A basic type:
  • A primitive data type such as int, real, bool etc.
• A type name:
  • A name can be used to denote a type expression.
• A type constructor:
  • arrays
  • products
  • pointers
  • functions

Properties of LL(1) grammar:

1. No Left Recursion
2. No Ambiguity
3. Non-conflicting FIRST and FOLLOW sets
4. Deterministic Parsing Table
5. Top-down Parsable

For more detailed insights on Compiler Design and Construction and additional subjects, stay tuned for regular updates and expanded question bank solutions.