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) = `{/, *, +, –, ), $}`.