Compiler-Design-Lab/Q6firstnfollow.py at master · ankgitk/Compiler-Design-Lab · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import re

def follow(s, productions, ans):
	if len(s)!=1 :
		return {}

	for key in productions:
		for value in productions[key]:
			f = value.find(s)
			if f!=-1:
				if f==(len(value)-1):
					if key!=s:
						if key in ans:
							temp = ans[key]
						else:
							ans = follow(key, productions, ans)
							temp = ans[key]
						ans[s] = ans[s].union(temp)
				else:
					first_of_next = first(value[f+1:], productions)
					if '@' in first_of_next:
						if key!=s:
							if key in ans:
								temp = ans[key]
							else:
								ans = follow(key, productions, ans)
								temp = ans[key]
							ans[s] = ans[s].union(temp)
							ans[s] = ans[s].union(first_of_next) - {'@'}
					else:
						ans[s] = ans[s].union(first_of_next)
	return ans

def first(s, productions):
	c = s[0]
	ans = set()
	if c.isupper():
		for st in productions[c]:
			if st == '@' :
				if len(s)!=1 :
					ans = ans.union( first(s[1:], productions) )
				else :
					ans = ans.union('@')
			else :
				f = first(st, productions)
				ans = ans.union(x for x in f)
	else:
		ans = ans.union(c)
	return ans

if __name__=="__main__":
	productions=dict()
	grammar = open("firstnfollow.txt", "r")
	first_dict = dict()
	follow_dict = dict()
	flag = 1
	start = ""
	for line in grammar:
		l = re.split("( |->|\n|\||)*", line)
		lhs = l[0]
		rhs = set(l[1:-1])-{''}
		if flag :
			flag = 0
			start = lhs
		productions[lhs] = rhs

	print '\nFirst\n'
	for lhs in productions:
		first_dict[lhs] = first(lhs, productions)
	for f in first_dict:
		print str(f) + " : " + str(first_dict[f])
	print ""

	print '\nFollow\n'

	for lhs in productions:
		follow_dict[lhs] = set()

	follow_dict[start] = follow_dict[start].union('$')

	for lhs in productions:
		follow_dict = follow(lhs, productions, follow_dict)

	for lhs in productions:
		follow_dict = follow(lhs, productions, follow_dict)

	for f in follow_dict:
		print str(f) + " : " + str(follow_dict[f])