ASSIGNMENT NO 2

PARSERS
IMPLEMENTATION

Department of Computer Science

University of Engineering & Technology, Taxila

Jan 14, 2023

Submitted by
Aleeza Anjum(20-CS-101)
Moaz Ali(20-CS-69)

Submitted to
Dr. Abid Rauf
Question: Implement all the bottom up parsers we studied in the class. 
Ans:

Parsers Implementation:
We have implemented parsers LR(0), CLR, SLR and LALR(1) here.
As we know that LR Parsers are divided into four categories:

LR(0) CLR(1) SLR LALR(1)

LR(0) – LR parser:
 Works on the complete set of LR(0) Grammars.
 It generates a table of action and goto.
 LR(0) grammars is a CFG such that it produces a table without conflicts.
SLR(1) - Simple LR parser:
 It is working on the smallest grammar class.
 Few number of states, therefore a very small table.
 Simple and quick construction.
LALR(1) – Look-Ahead LR Parser:
 Works on a medium sized grammar.
 The number of states is the same as SLR(1).
CLR(1) – LR Parser:
 Canonical collection of LR(1) items.
 Makes more number of states as compared to SLR(1).
 It can find the reduce nodes only in lookahead.

We used LR (0) canonical items to generate LR and SLR parser

And LR(1) canonical items to generate CLR and LALR.
Our parsers take input of grammar via txt file, and generate the respective parser.
After generating it, we check for a string to know whether it accept this string or not.
Each parser have its own file specified below.
Implementation Language:
Whole project is implemented in python

Code:
CLR Parser:
from pprint import pprint
from random import randint
from threading import Thread,Lock
mutex = Lock()
def import_grammar(fileHandle):
G,T,Nt = [],[],[]
for lines in fileHandle:
production = lines.split(' -> ')
if production[0] not in Nt: Nt.append(production[0])
listStr = list(production[1])
del listStr[-1]
production[1] = ''.join(i for i in listStr)
for char in production[1]:
if 65<=ord(char) and ord(char)<= 90:
if char not in Nt: Nt.append(char)
else:
if char not in T: T.append(char)
if production not in G: G.append((production[0],production[1]))
T.append('$')
return G,T,Nt
def closure(I,G,Nt):
J = [p for p in I]
while True:
J1 = [x for x in J]
for x in J1:
handle = list(x[1])
a = x[2]
k = handle.index('.')
if k+1!=len(handle):
if handle[k+1] in Nt:
for p in G:
 beta = ''.join(handle[m] for m in range(k+2,len(handle)))
b = list(beta+a)[0]
if p[0] == handle[k+1]:
new_p = (p[0],'.'+p[1],b)
if new_p not in J1: J1.append(new_p)
flag = True
for x in J1:
if x not in J:
flag = False
J.append(x)
if flag: break
return J
def goto(I,G,X,Nt):
W = []
for x in I:
handle = list(x[1])
k = handle.index('.')
if k != len(handle)-1:
if handle[k+1] == X:
S1 = ''.join([handle[i] for i in range(k)])
S2 = ''.join([handle[i] for i in range(k+2,len(handle))])
W.append((x[0],S1+X+'.'+S2,x[2]))
return closure(W,G,Nt)
def items(G,T,Nt):
C = [ closure([(G[0][0],'.'+G[0][1],'$')],G,Nt) ]
action = {}
goto_k = {}
reduction_states = {}
while True:
C1 = [ I for I in C ]
for I in C1:
for X in T:
goto_list = goto(I,G,X,Nt)
if len(goto_list)!=0 and goto_list not in C1:
C1.append(goto_list)
if C1.index(I) not in action: action[C1.index(I)] = {}
if X not in action[C1.index(I)]:
action[C1.index(I)][X] = C1.index(goto_list)
elif goto_list in C1:
 if C1.index(I) not in action: action[C1.index(I)] = {}
if X not in action[C1.index(I)]:
action[C1.index(I)][X] = C1.index(goto_list)
for I in C1:
for X in Nt:
goto_list = goto(I,G,X,Nt)
if len(goto_list)!=0 and goto_list not in C1:
C1.append(goto_list)
if C1.index(I) not in goto_k: goto_k[C1.index(I)] = {}
if X not in goto_k[C1.index(I)]:
goto_k[C1.index(I)][X] = C1.index(goto_list)
elif goto_list in C1:
if C1.index(I) not in goto_k: goto_k[C1.index(I)] = {}
if X not in goto_k[C1.index(I)]:
goto_k[C1.index(I)][X] = C1.index(goto_list)
flag = True
for x in C1:
if x not in C:
flag = False
C.append(x)
if flag: break
for state in range(len(C)):
reduction_states[state] = {}
for production in C[state]:
if production[1][len(production[1])-1] == '.':
rhs = list(production[1])
del rhs[-1]
rhsStr = ''.join(i for i in rhs)
Pp = (production[0],rhsStr)
reduction_states[state][production[2]] = Pp
accept_state = 0
for x in reduction_states:
if '$' in reduction_states[x]:
if reduction_states[x]['$'] == G[0]:
accept_state = x
break
return C,action,goto_k,reduction_states,accept_state
def driver():
txt = input('Enter the name of the file. ') + '.txt'
fileHandle = open(txt)
G,T,Nt = import_grammar(fileHandle)
print (T,Nt)
C,action_list,goto_list,reduction_states,accept_state = items(G,T,Nt)
print ('Canonical states')
for i in range(len(C)): print (i,C[i])
print ('Action list')
pprint(action_list)
print ('Goto list')
pprint(goto_list)
print ('Reduction states')
pprint(reduction_states)
print ('Accept state',accept_state)
stack = [0]
symbol_stack=['$']
input_str = input('Enter some string ')+'$'
i,top = 0,0
# LR(1) AUTOMATON PARSING
def automatonThread(symbol_stack,stack,input_str,i,top):
global mutex
mutex.acquire()
print ('STATE','INPUT','SYMBOL_STACK','ACTION')
while True:
print ('Input string',input_str)
s = stack[top]
try:
print (s,input_str[i]) if i != len(input_str) else 'Finish',symbol_stack,
if s == accept_state:
print ('accept')
mutex.release()
break
elif len(reduction_states[s]) != 0 and input_str[i] in reduction_states[s]:
A,beta = reduction_states[s][input_str[i]]
print ('reduce',A,'->',beta)
for j in range(len(beta)):
del stack[top]
del symbol_stack[top]
t = stack[top]
 stack.insert(top,goto_list[t][A])
symbol_stack.insert(top,A)
else:
a = input_str[i]
stack.insert(top,action_list[s][a])
symbol_stack.insert(top,a)
print ('shift',action_list[s][a])
i=i+1
except:
print ('\nSyntax error detected')
print ('Expected any of the following')
errors = []
if s in action_list:
for prod in action_list[s]: errors.append(prod)
elif s in reduction_states:
for prod in reduction_states[s]: errors.append(prod)
for j in range(len(errors)): print (j+1,')',errors[j]) if errors[j] != '$' else 'End of line'
threadList = [None for j in range(len(errors))]

print ('Got',input_str[i],'at position',i)

mutex.release()
for k in range(len(errors)):
r = errors[k]
e = input_str[i]
buffer_str = ''.join(input_str[j] for j in range(i))+r+''.join(input_str[j] for j in
range(i+1,len(input_str)))
if i == len(buffer_str) - 1 and e == '$': buffer_str = buffer_str + '$'
print ('Current adjusted input',buffer_str)
threadList[k] =
Thread(target=automatonThread,args=(symbol_stack,stack,buffer_str,i,top,))
for k in range(len(errors)): threadList[k].start()
for k in range(len(errors)): threadList[k].join()
break
automatonThread(symbol_stack,stack,input_str,i,top)
driver()
LALR Parser:
# with user-defined error recovery
from pprint import pprint
from random import randint
from threading import Thread,Lock
mutex = Lock()
def import_grammar(fileHandle):
G,T,Nt = [],[],[]
for lines in fileHandle:
production = lines.split(' -> ')
if production[0] not in Nt: Nt.append(production[0])
listStr = list(production[1])
del listStr[-1]
production[1] = ''.join(i for i in listStr)
for char in production[1]:
if 65<=ord(char) and ord(char)<= 90:
if char not in Nt: Nt.append(char)
else:
if char not in T: T.append(char)
if production not in G: G.append((production[0],production[1]))
T.append('$')
return G,T,Nt
def closure(I,G,Nt):
J = [p for p in I]

while True:
J1 = [x for x in J]
for x in J1:
handle = list(x[1])
a = x[2]
k = handle.index('.')
if k+1!=len(handle):
if handle[k+1] in Nt:
for p in G:
beta = ''.join(handle[m] for m in range(k+2,len(handle)))
b = list(beta+a)[0]
 if p[0] == handle[k+1]:
new_p = (p[0],'.'+p[1],b)
if new_p not in J1: J1.append(new_p)
flag = True
for x in J1:
if x not in J:
flag = False
J.append(x)
if flag: break
return J
def goto(I,G,X,Nt):
W = []
for x in I:
handle = list(x[1])
k = handle.index('.')
if k != len(handle)-1:
if handle[k+1] == X:
S1 = ''.join([handle[i] for i in range(k)])
S2 = ''.join([handle[i] for i in range(k+2,len(handle))])
W.append((x[0],S1+X+'.'+S2,x[2]))
return closure(W,G,Nt)
def items(G,T,Nt):
C = [ closure([(G[0][0],'.'+G[0][1],'$')],G,Nt) ]
action = {}
goto_k = {}
reduction_states = {}
while True:
C1 = [ I for I in C ]
for I in C1:
for X in T:
goto_list = goto(I,G,X,Nt)
if len(goto_list)!=0 and goto_list not in C1:
C1.append(goto_list)
if C1.index(I) not in action: action[C1.index(I)] = {}
if X not in action[C1.index(I)]:
 action[C1.index(I)][X] = C1.index(goto_list)
elif goto_list in C1:
if C1.index(I) not in action: action[C1.index(I)] = {}
if X not in action[C1.index(I)]:
action[C1.index(I)][X] = C1.index(goto_list)
for I in C1:
for X in Nt:
goto_list = goto(I,G,X,Nt)
if len(goto_list)!=0 and goto_list not in C1:
C1.append(goto_list)
if C1.index(I) not in goto_k: goto_k[C1.index(I)] = {}
if X not in goto_k[C1.index(I)]:
goto_k[C1.index(I)][X] = C1.index(goto_list)
elif goto_list in C1:
if C1.index(I) not in goto_k: goto_k[C1.index(I)] = {}
if X not in goto_k[C1.index(I)]:
goto_k[C1.index(I)][X] = C1.index(goto_list)
flag = True
for x in C1:
if x not in C:
flag = False
C.append(x)
if flag: break
for state in range(len(C)):
reduction_states[state] = {}
for production in C[state]:
if production[1][len(production[1])-1] == '.':
rhs = list(production[1])
del rhs[-1]
rhsStr = ''.join(i for i in rhs)
Pp = (production[0],rhsStr)
reduction_states[state][production[2]] = Pp
accept_state = 0
for x in reduction_states:
if '$' in reduction_states[x]:
 if reduction_states[x]['$'] == G[0]:
accept_state = x

break
return C,action,goto_k,reduction_states,accept_state
def driver():
txt = input('Enter the name of the file. ') + '.txt'
fileHandle = open(txt)
G, T, Nt = import_grammar(fileHandle)
print (T,Nt)

C,action_list,goto_list,reduction_states,accept_state = items(G,T,Nt)
print ('Canonical states')
for i in range(len(C)): print (i,C[i])
print ('Action list')
pprint(action_list)
print ('Goto list')
pprint(goto_list)
print ('Reduction states')
pprint(reduction_states)
print ('Accept state',accept_state)
stack = [0]
symbol_stack=['$']
input_str = input('Enter some string ')+'$'
i,top = 0,0
# LR(1) AUTOMATON PARSING
def automatonThread(symbol_stack,stack,input_str,i,top):
global mutex
mutex.acquire()
print ('STATE','INPUT','SYMBOL_STACK','ACTION')
while True:
print ('Input string',input_str)
s = stack[top]
try:
print (s,input_str[i]) if i != len(input_str) else 'Finish',symbol_stack,
if s == accept_state:
print ('accept')
mutex.release()
break
 elif len(reduction_states[s]) != 0 and input_str[i] in reduction_states[s]:
A,beta = reduction_states[s][input_str[i]]

print ('reduce',A,'->',beta)
for j in range(len(beta)):
del stack[top]
del symbol_stack[top]
t = stack[top]
stack.insert(top,goto_list[t][A])
symbol_stack.insert(top,A)
else:
a = input_str[i]
stack.insert(top,action_list[s][a])
symbol_stack.insert(top,a)
print ('shift',action_list[s][a])
i=i+1
except:
print ('\nSyntax error detected')
print ('Expected any of the following')
errors = []

if s in action_list
for prod in action_list[s]: errors.append(prod)
elif s in reduction_states:
for prod in reduction_states[s]: errors.append(prod)
for j in range(len(errors)): print (j+1,')',errors[j] if errors[j] != '$' else 'End of
line')
threadList = [None for j in range(len(errors))]
print ('Got',input_str[i],'at position',i)
mutex.release()
for k in range(len(errors)):
r = errors[k]
e = input_str[i]
buffer_str = ''.join(input_str[j] for j in range(i))+r+''.join(input_str[j] for j in
range(i+1,len(input_str)))
if i == len(buffer_str) - 1 and e == '$': buffer_str = buffer_str + '$'
print ('Current adjusted input',buffer_str)
threadList[k] =
Thread(target=automatonThread,args=(symbol_stack,stack,buffer_str,i,top,))
for k in range(len(errors)): threadList[k].start()
for k in range(len(errors)): threadList[k].join()

break
automatonThread(symbol_stack,stack,input_str,i,top)
driver()

LR(0) Parser:
from pprint import pprint
def import_grammar(fileHandle):
G,T,Nt = [],[],[]
for lines in fileHandle:
production = lines.split(' -> ')
if production[0] not in Nt: Nt.append(production[0])
listStr = list(production[1])
del listStr[-1]
production[1] = ''.join(i for i in listStr)
for char in production[1]:
if 65<=ord(char) and ord(char)<= 90:
if char not in Nt: Nt.append(char)
else:
if char not in T: T.append(char)
if production not in G: G.append((production[0],production[1]))
T.append('#')
return G,T,Nt
def closure(I,G,Nt):
J = [p for p in I]
while True:
J1 = [x for x in J]
for x in J1:
handle = list(x[1])
k = handle.index('.')
if k+1!=len(handle):
if handle[k+1] in Nt:
for p in G:
if p[0] == handle[k+1]:
 new_p = (p[0],'.'+p[1])
if new_p not in J1: J1.append(new_p)
flag = True

for x in J1:
if x not in J:
flag = False
J.append(x)
if flag: break
return J
def goto(I,X,Nt):
W = []
for x in I:
handle = list(x[1])
k = handle.index('.')
if k != len(handle)-1:
if handle[k+1] == X:
S1 = ''.join([handle[i] for i in range(k)])
S2 = ''.join([handle[i] for i in range(k+2,len(handle))])
W.append((x[0],S1+X+'.'+S2))
return closure(W,G,Nt)
def items(G,T,Nt):
C = [ closure([(G[0][0],'.'+G[0][1])],G,Nt) ]
action = {}
goto_k = {}
reduction_states = {}
while True:
C1 = [ I for I in C ]
for I in C1:
for X in T:
goto_list = goto(I,X,Nt)
if len(goto_list)!=0 and goto_list not in C1:
C1.append(goto_list)
if C1.index(I) not in action: action[C1.index(I)] = {}
if X not in action[C1.index(I)]: action[C1.index(I)][X] = C1.index(goto_list)
elif goto_list in C1:
if C1.index(I) not in action: action[C1.index(I)] = {}
if X not in action[C1.index(I)]: action[C1.index(I)][X] = C1.index(goto_list)
 for I in C1:
for X in Nt:
goto_list = goto(I,X,Nt)
if len(goto_list)!=0 and goto_list not in C1:
C1.append(goto_list)

if C1.index(I) not in goto_k: goto_k[C1.index(I)] = {}

if X not in goto_k[C1.index(I)]: goto_k[C1.index(I)][X] = C1.index(goto_list)
elif goto_list in C1:
if C1.index(I) not in goto_k: goto_k[C1.index(I)] = {}
if X not in goto_k[C1.index(I)]: goto_k[C1.index(I)][X] = C1.index(goto_list)
flag = True
for x in C1:
if x not in C:
flag = False
C.append(x)
if flag: break
for P in G:
Pp = (P[0],P[1]+'.')
for state in range(len(C)):
if Pp in C[state]: reduction_states[state] = P
accept_state = 0
for x in reduction_states:
if reduction_states[x] == G[0]: accept_state = x
return C,action,goto_k,reduction_states,accept_state
txt = input('Enter the name of the file. ')+'.txt'
fileHandle = open(txt)
G,T,Nt = import_grammar(fileHandle)
print (T,Nt)
C,action_list,goto_list,reduction_states,accept_state = items(G,T,Nt)
print ('Action list')
pprint(action_list)
print ('Goto list')
pprint(goto_list)
print ('Reduction states')
pprint(reduction_states)
print ('Accept state',accept_state)
stack = [0]
input_str = input('Enter some string ')+'#'
i,top = 0,0
# LR(0) AUTOMATON PARSING
while True:
s = stack[top]
try:

print (s,stack,input_str[i]) if i != len(input_str) else 'Finish',

if s == accept_state:
print ('accept')
break
elif s in reduction_states:
A,beta = reduction_states[s]
print ('reduce',A,'->',beta)
for j in range(len(beta)): del stack[top]
t = stack[top]
stack.insert(top,goto_list[t][A])
else:
a = input_str[i]
stack.insert(top,action_list[s][a])
print ('shift',action_list[s][a])
i=i+1
except:
print ('Syntax error')
break

SLR Parser:
from pprint import pprint
def add(listA,x):
if x not in listA: listA.append(x)
def first_set(G,T,Nt):
firstA = {}
tempA = {}
for NonT in Nt: firstA[NonT] = []
while True:
for NonT in firstA:
tempA[NonT] = [i for i in firstA[NonT]]
for i in range(len(G)):
 if G[i][1] == '': add(tempA[G[i][0]],'')
elif G[i][1][0] in Nt:
if '' not in firstA[G[i][1][0]]:
for k in firstA[G[i][1][0]]: add(tempA[G[i][0]],k)
else:

listA = [ k for k in firstA[G[i][1][0]] ]

r = listA.index('')
del listA[r]
for k in listA: add(tempA[G[i][0]],k)
add(tempA[G[i][0]],'')
elif G[i][1][0] in T: add(tempA[G[i][0]],G[i][1][0])
flag = True
for NonT in Nt: flag = flag and (tempA[NonT] == firstA[NonT])
if flag: break
for NonT in Nt: firstA[NonT] = [i for i in tempA[NonT]]
return firstA
def follow_set(G,S,T,Nt):
followA = {}
tempA = {}
for NonT in Nt: followA[NonT] = ['$'] if NonT == S else []
first_set_list = first_set(G,T,Nt)
while True:
for NonT in followA:
tempA[NonT] = [i for i in followA[NonT]]
for production in G:
Aj,rhs = production[0],list(production[1])
for i in range(len(rhs)):
Ai = rhs[i]
if Ai in Nt:
if i+1 == len(rhs): w = ''
else: w = rhs[i+1]
if w == '' or (w in Nt and '' in first_set_list[w]):
for k in followA[Aj]: add(tempA[Ai],k)
if w in T: add(tempA[Ai],w)
if w in Nt:
for k in first_set_list[w]: add(tempA[Ai],k) if k!='' else add(tempA[Ai],'$')
flag = True
 for NonT in Nt: flag = flag and (tempA[NonT] == followA[NonT])
if flag: break
for NonT in Nt: followA[NonT] = [i for i in tempA[NonT]]
return followA
def import_grammar(fileHandle):
G,T,Nt = [],[],[]

for lines in fileHandle:

production = lines.split(' -> ')
if production[0] not in Nt: Nt.append(production[0])
listStr = list(production[1])
del listStr[-1]
production[1] = ''.join(i for i in listStr)
for char in production[1]:
if 65<=ord(char) and ord(char)<= 90:
if char not in Nt: Nt.append(char)
else:
if char not in T: T.append(char)
if production not in G: G.append((production[0],production[1]))
T.append('#')
return G,T,Nt
def closure(I,G,Nt):
J = [p for p in I]
while True:
J1 = [x for x in J]
for x in J1:
handle = list(x[1])
k = handle.index('.')
if k+1!=len(handle):
if handle[k+1] in Nt:
for p in G:
if p[0] == handle[k+1]:
new_p = (p[0],'.'+p[1])
if new_p not in J1: J1.append(new_p)
flag = True
for x in J1:
if x not in J:
flag = False
 J.append(x)
if flag: break
return J
def goto(I,X,Nt):
W = []
for x in I:
handle = list(x[1])

k = handle.index('.')
if k != len(handle)-1:
if handle[k+1] == X:
S1 = ''.join([handle[i] for i in range(k)])
S2 = ''.join([handle[i] for i in range(k+2,len(handle))])
W.append((x[0],S1+X+'.'+S2))
return closure(W,G,Nt)
def items(G,T,Nt):
C = [ closure([(G[0][0],'.'+G[0][1])],G,Nt) ]
action = {}
goto_k = {}
reduction_states = {}
while True:
C1 = [ I for I in C ]
for I in C1:
for X in T:
goto_list = goto(I,X,Nt)
if len(goto_list)!=0 and goto_list not in C1:
C1.append(goto_list)
if C1.index(I) not in action: action[C1.index(I)] = {}
if X not in action[C1.index(I)]: action[C1.index(I)][X] = C1.index(goto_list)
elif goto_list in C1:
if C1.index(I) not in action: action[C1.index(I)] = {}
if X not in action[C1.index(I)]: action[C1.index(I)][X] = C1.index(goto_list)
for I in C1:
for X in Nt:
goto_list = goto(I,X,Nt)
if len(goto_list)!=0 and goto_list not in C1:
C1.append(goto_list)
if C1.index(I) not in goto_k: goto_k[C1.index(I)] = {}
 if X not in goto_k[C1.index(I)]: goto_k[C1.index(I)][X] = C1.index(goto_list)
elif goto_list in C1:
if C1.index(I) not in goto_k: goto_k[C1.index(I)] = {}
if X not in goto_k[C1.index(I)]: goto_k[C1.index(I)][X] = C1.index(goto_list)
flag = True
for x in C1:
if x not in C:

flag = False
C.append(x)
if flag: break
for P in G:
Pp = (P[0],P[1]+'.')
for state in range(len(C)):
if Pp in C[state]: reduction_states[state] = P
accept_state = 0
for x in reduction_states:
if reduction_states[x] == G[0]: accept_state = x
return C,action,goto_k,reduction_states,accept_state
txt = input('Enter the name of the file. ')+'.txt'
fileHandle = open(txt)
G,T,Nt = import_grammar(fileHandle)
print (T,Nt)
C,action_list,goto_list,reduction_states,accept_state = items(G,T,Nt)
follow_set_list = follow_set(G,G[0][0],T,Nt)
print (follow_set_list)
print ('Action list')
pprint(action_list)
print ('Goto list')
pprint(goto_list)
print ('Reduction states')
pprint(reduction_states)
print ('Accept state',accept_state)
stack = [0]
input_str = input('Enter some string ')+'#'
i,top = 0,0
# SLR(1) AUTOMATON PARSING
while True:
s = stack[top]
try:
print (s,input_str[i]) if i != len(input_str) else 'Finish',
if input_str[i] in action_list[s] and s in reduction_states:
print ('THE INPUT GRAMMAR IS NOT IN SLR(1).')
break
elif s == accept_state:
print ('accept')

break
elif s in reduction_states:
A,beta = reduction_states[s]
if input_str[i] in follow_set_list[A]:
print ('reduce',A,'->',beta)
for j in range(len(beta)): del stack[top]
t = stack[top]
stack.insert(top,goto_list[t][A])
else:
a = input_str[i]
stack.insert(top,action_list[s][a])
print ('shift',action_list[s][a])
i=i+1
except:
print ('Syntax error')
break

First and Follow:

from pprint import pprint
def add(listA,x):
if x not in listA: listA.append(x)
def first_set(G,T,Nt):
firstA = {}
tempA = {}
for NonT in Nt: firstA[NonT] = []
while True:
 for NonT in firstA:
tempA[NonT] = [i for i in firstA[NonT]]
for i in range(len(G)):
if G[i][1] == '': add(tempA[G[i][0]],'')
elif G[i][1][0] in Nt:
if '' not in firstA[G[i][1][0]]:
for k in firstA[G[i][1][0]]: add(tempA[G[i][0]],k)
else:
listA = [ k for k in firstA[G[i][1][0]] ]
r = listA.index('')

del listA[r]
for k in listA: add(tempA[G[i][0]],k)
add(tempA[G[i][0]],'')
elif G[i][1][0] in T: add(tempA[G[i][0]],G[i][1][0])
flag = True
for NonT in Nt: flag = flag and (tempA[NonT] == firstA[NonT])
if flag: break
else: print (tempA); print (firstA); print ('---------------')
for NonT in Nt: firstA[NonT] = [i for i in tempA[NonT]]
return firstA
def follow_set(G,S,T,Nt):
followA = {}
tempA = {}
for NonT in Nt: followA[NonT] = ['$'] if NonT == S else []
first_set_list = first_set(G,T,Nt)
while True:
for NonT in followA:
tempA[NonT] = [i for i in followA[NonT]]
for production in G:
Aj,rhs = production[0],list(production[1])
for i in range(len(rhs)):
Ai = rhs[i]
if Ai in Nt:
if i+1 == len(rhs): w = ''
else: w = rhs[i+1]
if w == '' or (w in Nt and '' in first_set_list[w]):
for k in followA[Aj]: add(tempA[Ai],k)
 if w in T: add(tempA[Ai],w)
if w in Nt:
for k in first_set_list[w]: add(tempA[Ai],k) if k!='' else add(tempA[Ai],'$')
flag = True
for NonT in Nt: flag = flag and (tempA[NonT] == followA[NonT])
if flag: break
else: print (tempA); print (followA); print ('//////////////')
for NonT in Nt: followA[NonT] = [i for i in tempA[NonT]]
return followA
def import_grammar(fileHandle):
G,T,Nt = [],[],[]

for lines in fileHandle:

production = lines.split(' -> ')
if production[0] not in Nt: Nt.append(production[0])
listStr = list(production[1])
del listStr[-1]
production[1] = ''.join(i for i in listStr)
for char in production[1]:
if 65<=ord(char) and ord(char)<= 90:
if char not in Nt: Nt.append(char)
else:
if char not in T: T.append(char)
if production not in G: G.append((production[0],production[1]))
T.append('$')
return G,T,Nt
filename = input('Enter the file name ')+'.txt'
fileHandle = open(filename)
G,T,Nt = import_grammar(fileHandle)
pprint(G)
print (T,Nt)
print ('First set calculated')
first_set_list = first_set(G,T,Nt)
print ('Follow set calculated')
follow_set_list = follow_set(G,G[0][0],T,Nt)
print ('First')
print (first_set_list)
print ('Follow')
pprint(follow_set_list)