Question.
1 (a) – Label the following table with the phases of Compilation in the first row
and complete the table. Please be careful and avoid over writing and striking –
Name Input(s) Output(s)
Lexical Analysis Char stream Lexeme
1. Symbol
Table
Syntax Analysis Lexeme Parse Tree
Symbol Table
2.
CFG
Semantic Analysis Parse Tree Synthesized
3. Symbol Table Tree
SDD
Intermediate Semantic Tree Intermediate
4. Representation Symbol Table Representation
5. Intermediate Code Intermediate Optimized IR
(Optional Phase) Optimization Representation
Code Generation Optimized IR Machine Code
6.
Machine code Machine Code Optimized
7. Optimization Machine Code
Question no. 2. Consider the following source program is to be compiled by a ‘Turbo C’ Compiler –
#include<stdio.h>
void main() {
int a, b, sum;
printf("\nEnter two no: ");
scanf("%d %d", &a, &b);
sum = a + b;
printf("Sum : %d", sum);
}
A. Perform Lexical Analysis on your answer book. Identify all Tokens, Lexemes and Attribute
Values, with respect to the code. Furthermore, construct the corresponding Symbol Table.
Lexeme Token Attribute Value
void Void -
main Id 1
( ( -
) ) -
{ { -
int Int -
a Id 2
, , -
b Id 3
, , -
sum Id 4
; ; -
printf Id 5
( ( -
Enter two no: Enter two no: -
) ) -
; ; -
scanf Id 6
( ( -
%d %d %d %d -
, , -
& & -
a Id 2
, , -
& & -
b Id 3
) ) -
; ; -
sum Id 4
= = -
a Id 2
+ + -
b Id 3
) ) -
; ; -
printf Id 5
( ( -
Sum = %d Sum = %d -
, , -
sum Id 4
) ) -
; ; -
} } -
Symbol Table
1 Method main
2 Int a
3 Int b
4 Int sum
5 Method printf
6 Method scanf
B. Illustrate the each form of the above code will take during compilation, till it reaches an
intermediate representation
<void> <id,1> <(> <)> <{><int> <id,2><,> <id,3><,> <id,4> <;><id,5><(> <Lt,\nEnter two no: > <)> <;>
<id,6> <(> <Lt,%d %d> <,> <&><id,2><,><&> <id,3> <)> <;> <id,4> <=> <id,2><+> <id,3><;> <id,5><(>
<Lt,Sum: %d><,> <id,4> <id,3> <)> <;> <}>
• Syntax tree is a
main()
void
{ stmts }
int id,id,id; stmts
printf(LT) stmts
scanf(LT,IDlist) stmts
id=id+id stmts
printf(LT,IDlist) stmts
epsilon
Intermediate Code Generation
t1 = id2
t2 =id3
t3 = t1 + t 2
id4 = t3
id4 = id3+ id2
LDF R2, id3
LDF R1, id2
ADDF R1, R2
STF id4, R1
Question no. 3. Consider the following Context Free Grammar G1 and statement stmt:
G1: S S / S | S * S | S+S | S – S | (S)
S 0|1|2|3|4|5|6|7|8|9
string: (5 - 2) ∗ 3 / (8 + 1)
1. Arithmetic expression of digits [0-9] and operators [+-/*] that may or may not be
enclosed with parenthesis(’s)
2. Prove that G1 is ambiguous using, string
3. Rewrite G1 as an unambiguous grammar
Expr Expr + Term | Expr - Term | Term
Term Term / Factor | Term * Factor | Factor
Factor 0|2|1|3|4|5|6|7|8|9 | (Expr)
4. Rewrite G1 as a non deterministic grammar
S S X | (S)
S 0|1|2|3|4|5|6|7|8|9
X / S | * S | +S | – S
5. Rewrite G1 as a left factored grammar
S 0 A | 1 A | 2 A | 3 A | 4 A | 5 A | 6 A | 7 A| 8 A | 9 A | (S)
A / SA | * SA | +SA | – SA | epsilon
6. Convert given into postfix expression.
52-3*81+/
7. RDP
class Parser:
def __init__(self, input_string):
self.input = input_string # The input string to parse
self.position = 0 # The current position in the string
def current_char(self):
"""Returns the current character or None if at the end of input."""
if self.position < len(self.input):
return self.input[self.position]
return None
def advance(self):
"""Moves to the next character in the input string."""
self.position += 1
def match(self, expected_char):
"""Matches the current character with the expected character."""
if self.current_char() == expected_char:
self.advance()
return True
return False
def S(self):
"""Handles the non-terminal S."""
current = self.current_char()
if current is None:
return False
if current in '0123456789': # Match digit
self.advance() # Move past the digit
return self.A() # After the digit, parse A
elif current == '(': # Match '(' followed by S and ')'
self.advance() # Move past '('
if self.S() and self.match(')'):
return True
return False
return False
def A(self):
"""Handles the non-terminal A."""
current = self.current_char()
if current is None:
return True # epsilon (empty production)
if current in '/*+-': # Match operators '/', '*', '+', '-'
self.advance() # Move past the operator
if self.S(): # After operator, expect S
return self.A() # After S, expect A recursively
return False
# epsilon (empty production), which is valid
return True
def parse(self):
"""Starts parsing from the start symbol S."""
if self.S() and self.position == len(self.input):
return True
return False
# Example usage:
parser = Parser("3+5")
if parser.parse():
print("The input is valid according to the grammar.")
else:
print("The input is not valid according to the grammar.")
8. LL1 Parsing Table
**First Sets**:
- First(S) = `{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, (}`.
- First(X) = `{/, *, +, –}`.
**Follow Sets**:
- Follow(S) = `{/, *, +, –, ), $}`.
- Follow(X) = `{/, *, +, –, ), $}`.
