01. Give the translation scheme that converts infix to postfix notation.
Generate the annotated
parse tree for input string 3-5+4.
Translation Scheme for Infix to Postfix Conversion
1. Operands: Directly add to the output.
2. Operators: Use a stack to handle operators by precedence.
3. Parentheses: Push ( onto the stack, pop until ) is found.
Example: Convert 3 - 5 + 4 (Infix) to Postfix
1. Initialize:
o Stack: []
o Output: []
2. Process:
o 3: Output → 3
o -: Push onto stack → [-]
o 5: Output → 3 5
o +: Pop - to output, then push + → Output: 3 5 -, Stack: [+]
o 4: Output → 3 5 - 4
o Pop + to output → 3 5 - 4 +
Final Postfix Expression: 3 5 - 4 +
(+)
/ \
(-) 4
/ \
3 5
First, 3 - 5 is evaluated, then the result is added to 4.
02. Check given grammer is LL(1) but not SLR(1).
S->AaAb | BbBa
A->€
B->€
Check if Grammar is LL(1) but not SLR(1)
Grammar:
1. S→AaAb ∣ BbBaS \to AaAb \ | \ BbBaS→AaAb ∣ BbBa
2. A→ϵA \to \epsilonA→ϵ
3. B→ϵB \to \epsilonB→ϵ
Step 1: LL(1) Check
FIRST Sets:
o FIRST(AaAb)={a}\text{FIRST}(AaAb) = \{ a \}FIRST(AaAb)={a}
o FIRST(BbBa)={b}\text{FIRST}(BbBa) = \{ b \}FIRST(BbBa)={b}
No conflicts (disjoint FIRST sets).
Grammar is LL(1).
Step 2: SLR(1) Check
Reduce/Reduce Conflict:
A→ϵA \to \epsilonA→ϵ and B→ϵB \to \epsilonB→ϵ can be reduced in the same
lookahead context, causing a reduce/reduce conflict.
The grammar is LL(1) but not SLR(1) due to conflicts in the SLR(1) parsing table.
03. what is the important of intermediate code? Discuss various representations of three address
code using the given expression. a=b*-c+b*-c or a+a*(b-c)+(b-c)*d
Importance of Intermediate Code
Intermediate code is vital in compilers because it provides:
Platform Independence: It allows the compiler to generate code for multiple platforms.
Simplified Optimization: Easier application of optimizations.
Modularity: Enables separation of front-end (source to intermediate) and back-end
(intermediate to machine code).
Improved Code Generation: Simplifies the translation from high-level languages to
machine code.
Representations of Three-Address Code
For the given expressions, we'll generate three-address code (TAC) in different forms.
Expression 1: a=b∗−c+b∗−ca = b * -c + b * -ca=b∗−c+b∗−c
Three-Address Code Representation:
1. t1 = -c
2. t2 = b * t1
3. t3 = -c
4. t4 = b * t3
5. a = t2 + t4
Expression 2: a+a∗(b−c)+(b−c)∗da + a * (b - c) + (b - c) * da+a∗(b−c)+(b−c)∗d
Three-Address Code Representation:
1. t1 = b - c
2. t2 = a * t1
3. t3 = b - c
4. t4 = t3 * d
5. a = a + t2 + t4
These TAC representations help optimize and translate complex expressions efficiently by breaking them
into smaller, manageable steps.
04. Draw syntax tree and DAG for the statement x=(a+b)*(a+b+c)*(a+b+c+d) Draw a DAG for
expression: a+a*(b-c)+(b-c)*d or d: = b*c e: = a+b b: = b*c a: = e-d
Syntax Tree and DAG for the Statement:
x = (a + b) * (a + b + c) * (a + b + c + d)
Syntax Tree:
/\
x *
/ \
* (a + b + c + d)
/ \
(a + b) (a + b + c)
DAG (Directed Acyclic Graph):
/ \
* +
/ \ /|\
+ +abcd
|\ |
ab ab
DAG for Expression:
a + a * (b - c) + (b - c) * d
/\
+ *
/\ /\
a * - d
/\/\
a -b c
/\
b c
DAG for Statements:
d=b*c
e=a+b
b=b*c
a=e–d
DAG:
e d
| |
+ *
/\ /\
a b b c
/\
b c
d = b * c
e = a + b
b = b * c (reuses the previous multiplication)
a = e - d
