8.
First and Follow:
gram = {
"E":["E+T","T"],
"T":["T*F","F"],
"F":["(E)","i"]
}
result={'E': [['T', "E'"]], 'T': [['F', "T'"]], 'F': [['(', 'E', ')'], ['i']],
"E'": [['+', 'T', "E'"], ['e']], "T'": [['*', 'F', "T'"], ['e']]}
def first(gram, term):
a = []
if term not in gram:
return [term]
for i in gram[term]:
if i[0] not in gram:
a.append(i[0])
elif i[0] in gram:
a += first(gram, i[0])
return a
def follow(gram, term):
a = []
for rule in gram:
for i in gram[rule]:
if term in i:
temp = i
indx = i.index(term)
if indx+1!=len(i):
if i[-1] in firsts:
a+=firsts[i[-1]]
else:
a+=[i[-1]]
else:
a+=["e"]
if rule != term and "e" in a:
a+= follow(gram,rule)
return a
firsts = {}
for i in result:
firsts[i] = first(result,i)
print(f'First({i}):',firsts[i])
print(f"Firsts are {firsts}")
follows = {}
for i in result:
follows[i] = list(set(follow(result,i)))
if "e" in follows[i]:
follows[i].pop(follows[i].index("e"))
follows[i]+=["$"]
print(f'Follow({i}):',follows[i])
o/p:
First(E): ['(', 'i']
First(T): ['(', 'i']
First(F): ['(', 'i']
First(E'): ['+', 'e']
First(T'): ['*', 'e']
Firsts are {'E': ['(', 'i'], 'T': ['(', 'i'], 'F': ['(', 'i'], "E'": ['+', 'e'], "T'": ['*', 'e']}
Follow(E): [')', '$']
Follow(T): [')', '+', '$']
Follow(F): [')', '+', '*', '$']
Follow(E'): [')', '$']
Follow(T'): [')', '+', '$']
EXP NO 9: Predictive parsing table
#predictive parsing table
terminals=['+', '*', 'i', ')', '(', 'e']
result={'E': [['T', "E'"]], 'T': [['F', "T'"]], 'F': [['(', 'E', ')'], ['i']],
"E'": [['+', 'T', "E'"], ['e']], "T'": [['*', 'F', "T'"], ['e']]}
firsts={'E': ['(', 'i'], 'T': ['(', 'i'], 'F': ['(', 'i'], "E'": ['+', 'e'],
"T'": ['*', 'e']}
resMod={'E': ["TE'"], 'T': ["FT'"], 'F': ['(E)', 'i'], "E'": ["+TE'", 'e'],
"T'": ["*FT'", 'e']}
follows={'E': [')', '$'], 'T': [')', '+', '$'], 'F': ['+', ')', '*', '$'],
"E'": [')', '$'], "T'": [')', '+', '$']}
tterm = list(terminals)
tterm.pop(tterm.index("e"))
tterm+=["$"]
pptable = {}
for i in result:
for j in tterm:
if j in firsts[i]:
pptable[(i,j)]=resMod[i][0]
else:
pptable[(i,j)]=""
if "e" in firsts[i]:
for j in tterm:
if j in follows[i]:
pptable[(i,j)]="e"
pptable[("F","i")] = "i"
toprint = f'{"": <10}'
for i in tterm:
toprint+= f'|{i: <10}'
print(toprint)
for i in result:
toprint = f'{i: <10}'
for j in tterm:
if pptable[(i,j)]!="":
toprint+=f'|{i+"->"+pptable[(i,j)]: <10}'
else:
toprint+=f'|{pptable[(i,j)]: <10}'
print(f'{"-":-<76}')
print(toprint)
o/p:
Stack Input Buffer Parsing Action
--------------------------------------------------
$a +a$ Shift
$E +a$ Reduce E->a
$E+ a$ Shift
$E+a $ Shift
$E+E $ Reduce E->a
$E $ Reduce E->E+E
$E $ Accepted
EXP NO 12: Generation of 3 address code:
def generate_temp():
global temp_count
temp_count += 1
return f"t{temp_count}"
def three_address_code(expression):
global temp_count
temp_count = 0
tokens = expression.split()
stack = []
result = []
for token in tokens:
if token.isalnum():
stack.append(token)
else:
if token in ['*', '/']:
op1 = stack.pop()
op2 = stack.pop()
temp = generate_temp()
result.append(f"{temp} = {op2} {token} {op1}")
stack.append(temp)
else:
stack.append(token)
while len(stack) > 1:
op1 = stack.pop()
op2 = stack.pop()
temp = generate_temp()
result.append(f"{temp} = {op2} {stack.pop()} {op1}")
stack.append(temp)
return result
expression = "(a+b)/d*(a+b*c)"
result = three_address_code(expression)
for step in result:
print(step)
O/p:
Three Address Code for expression: ( a * b ) + ( c + d ) && ( x + y )
temp1 = a * b
temp2 = c + d
temp3 = temp1 + temp2
temp4 = x + y
temp5 = temp3 && temp4
temp5
EXP NO 13: Implementation of 3 address code:
class Triple:
def __init__(self, op, arg1, arg2, result):
self.op = op
self.arg1 = arg1
self.arg2 = arg2
self.result = result
def __str__(self):
return f"({self.op}, {self.arg1}, {self.arg2}, {self.result})"
class Quadruple:
def __init__(self, op, arg1, arg2, result):
self.op = op
self.arg1 = arg1
self.arg2 = arg2
self.result = result
def __str__(self):
return f"{{op: {self.op}, arg1: {self.arg1}, arg2: {self.arg2},
result: {self.result}}}"
class CodeGeneration:
def __init__(self):
self.triples = []
self.quadruples = []
def gen_triple(self, op, arg1, arg2, result):
triple = Triple(op, arg1, arg2, result)
self.triples.append(triple)
def gen_quadruple(self, op, arg1, arg2, result):
quadruple = Quadruple(op, arg1, arg2, result)
self.quadruples.append(quadruple)
def display_triples(self):
print("Generated Triples:")
for index, triple in enumerate(self.triples):
print(f"Triple {index + 1}: {triple}")
def display_quadruples(self):
print("Generated Quadruples:")
for index, quadruple in enumerate(self.quadruples):
print(f"Quadruple {index + 1}: {quadruple}")
def main():
generator = CodeGeneration()
num_statements = int(input("Enter the number of statements: "))
for i in range(num_statements):
op = input(f"Enter operation for Statement {i+1}: ")
arg1 = input("Enter arg1: ")
arg2 = input("Enter arg2: ")
result = input("Enter result: ")
generator.gen_triple(op, arg1, arg2, result)
generator.gen_quadruple(op, arg1, arg2, result)
generator.display_triples()
print()
generator.display_quadruples()
if __name__ == "__main__":
main()
O/p:
Enter the number of statements: 2
Enter operation for Statement 1: add
Enter arg1: 2
Enter arg2: 3
Enter result: 5
Enter operation for Statement 2: sub
Enter arg1: 5
Enter arg2: 3
Enter result: 2
Generated Triples:
Triple 1: (add, 2, 3, 5)
Triple 2: (sub, 5, 3, 2)
EXP NO 14: Implementation of optimization techniques:
def main():
op = []
pr = []
n = int(input("Enter number of values: "))
for i in range(n):
left = input("Left: \t")
right = input("Right: ")
op.append({'l': left, 'r': right})
print("Intermediate Code:")
for item in op:
print(f"{item['l']}={item['r']}")
z = 0
for i in range(n-1):
temp = op[i]['l']
for j in range(n):
if temp in op[j]['r']:
pr.append({'l': op[i]['l'], 'r': op[i]['r']})
z += 1
pr.append({'l': op[n-1]['l'], 'r': op[n-1]['r']})
z += 1
print("\nAfter dead code elimination:")
for item in pr:
print(f"{item['l']}={item['r']}")
for m in range(z):
tem = pr[m]['r']
for j in range(m+1, z):
if pr[j]['r'] in tem:
t = pr[j]['l']
pr[j]['l'] = pr[m]['l']
for i in range(z):
if t in pr[i]['r']:
a = pr[i]['r'].index(t)
pr[i]['r'] = pr[i]['r'][:a] + pr[m]['l'] +
pr[i]['r'][a+1:]
print("After eliminating common expressions:")
for item in pr:
print(f"{item['l']}={item['r']}")
for i in range(z):
for j in range(i+1, z):
if pr[i]['l'] == pr[j]['l'] and pr[i]['r'] == pr[j]['r']:
pr[i]['l'] = None
pr[i]['r'] = None
print("Optimized code:")
for item in pr:
if item['l'] is not None:
print(f"{item['l']}={item['r']}")
if __name__ == "__main__":
main()
O/p:
Enter number of values: 5
Left: a
Right: 9
Left: b
Right: c+d
Left: c
Right: d+f
Left: g
Right: h+i
Left: v
Right: g
Intermediate Code:
a=9
b=c+d
c=d+f
g=h+i
v=g
After dead code elimination:
c=d+f
g=h+i
v=g
After eliminating common expressions:
c=d+f
g=h+i
...
Optimized code:
c=d+f
g=h+i
v=g
EXP NO 10:Shift reducing parser
# shift reduce parsing-Exp 10
gram = {
"E":["E+E","E*E","(E)","a"]
}
S = "E"
inp = "a+a$"
stack = "$"
print(f'{"Stack": <15}'+f'{"Input Buffer": <15}'+f'Parsing Action')
print(f'{"-":-<50}')
while True:
action = True
i = 0
while i<len(gram[S]):
if gram[S][i] in stack:
stack = stack.replace(gram[S][i],S)
print(f'{stack: <15}'+f'{inp: <15}'+f'Reduce E->{gram[S][i]}')
i=-1
action = False
i+=1
if len(inp)>1:
stack+=inp[0]
inp=inp[1:]
print(f'{stack: <15}'+f'{inp: <15}'+f'Shift')
action = False
if inp == "$" and stack == ("$"+S):
print(f'{stack: <15}'+f'{inp: <15}'+f'Accepted')
break
if action:
print(f'{stack: <15}'+f'{inp: <15}'+f'Rejected')
break
EXP NO 15: Generation of target code:
s=int(input('Enter number of inputs:'))
e=[]
r=1
for i in range(s):
e.append(input(f'Enter the {i} expession:'))
for i in range(s):
l=len(e[i])
for j in range(1,l):
if ord(e[i][j])>=97 and ord(e[i][j])<=122:
r=r+1
print(f'LOAD R{r-1},{e[i][j]}')
if j == l-1 and e[i][l-j] =='=':
j=3
if e[i][j]=='+':
print(f'ADD R{r-2},R{r-1}')
print(f'STORE {e[i][0]},R{r-2}')
elif e[i][j]=='-':
print(f'SUB R{r-2},R{r-1}')
print(f'STORE {e[i][0]},R{r-2}')
elif e[i][j]=='*':
print(f'MUL R{r-2},R{r-1}')
print(f'STORE {e[i][0]},R{r-2}')
elif e[i][j]=='/':
print(f'DIV R{r-2},R{r-1}')
print(f'STORE {e[i][0]},R{r-2}')
break
O/P:
Enter number of inputs:2
Enter the 0 expession:a=a+b
Enter the 1 expession:c=c+d
LOAD R1,a
LOAD R2,b
ADD R1,R2
STORE a,R1
LOAD R3,c
LOAD R4,d
ADD R3,R4
STORE c,R3
