|
178
|
1 class Grammar:
|
|
|
2 def __init__(self, terminals):
|
|
|
3 self.terminals = terminals
|
|
|
4 self.nonterminals = []
|
|
|
5 self.productions = []
|
|
|
6 def add_production(self, name, symbols):
|
|
|
7 p = Production(name, symbols)
|
|
|
8 self.productions.append(p)
|
|
|
9 if not name in self.nonterminals:
|
|
|
10 self.nonterminals.append(name)
|
|
|
11 def productionsForName(self, name):
|
|
|
12 return [p for p in self.productions if p.name == name]
|
|
|
13 @property
|
|
|
14 def Symbols(self):
|
|
|
15 return self.nonterminals + self.terminals
|
|
|
16
|
|
|
17 class Production:
|
|
|
18 def __init__(self, name, symbols):
|
|
|
19 self.name = name
|
|
|
20 self.symbols = symbols
|
|
|
21 def __repr__(self):
|
|
|
22 return '{0} -> {1}'.format(self.name, self.symbols)
|
|
179
|
23
|
|
178
|
24 class Item:
|
|
|
25 def __init__(self, production, dotpos):
|
|
|
26 self.production = production
|
|
|
27 self.dotpos = dotpos
|
|
|
28 def __eq__(self, other):
|
|
|
29 if type(other) is type(self):
|
|
|
30 return (self.production, self.dotpos) == (other.production, other.dotpos)
|
|
|
31 return False
|
|
|
32 def __hash__(self):
|
|
|
33 return (self.production, self.dotpos).__hash__()
|
|
|
34 @property
|
|
|
35 def IsReduce(self):
|
|
|
36 return self.dotpos == len(self.production.symbols)
|
|
|
37 @property
|
|
|
38 def IsShift(self):
|
|
|
39 return not self.IsReduce
|
|
|
40 @property
|
|
|
41 def Next(self):
|
|
|
42 return self.production.symbols[self.dotpos]
|
|
|
43 def matches(self, symbol):
|
|
|
44 return self.Next == symbol
|
|
|
45 def __repr__(self):
|
|
179
|
46 return '{0} -> {1} _dot_ {2} {{}}'.format(self.production.name, ' '.join(self.production.symbols[0:self.dotpos]), ' '.join(self.production.symbols[self.dotpos:]))
|
|
|
47
|
|
|
48 class LRgenerator:
|
|
|
49 def __init__(self, g):
|
|
|
50 self.grammar = g
|
|
|
51 def e_closure(self, S):
|
|
|
52 """ Expand itemset by using epsilon moves """
|
|
|
53 something_changed = True
|
|
|
54 while something_changed:
|
|
|
55 something_changed = False
|
|
|
56 worklist = list(S)
|
|
|
57 for item in worklist:
|
|
|
58 if item.IsShift and item.Next in self.grammar.nonterminals:
|
|
|
59 n = item.Next
|
|
|
60 for add_p in self.grammar.productionsForName(n):
|
|
|
61 i = Item(add_p, 0)
|
|
|
62 if not i in S:
|
|
|
63 S.add(i)
|
|
|
64 something_changed = True
|
|
|
65 return frozenset(S)
|
|
|
66 def initialItemSet(self):
|
|
|
67 nis = set()
|
|
|
68 for p in self.grammar.productionsForName(self.grammar.start_symbol):
|
|
|
69 nis.add(Item(p, 0))
|
|
|
70 return self.e_closure(nis)
|
|
|
71 def nextItemSet(self, itemset, symbol):
|
|
|
72 nis = set()
|
|
|
73 for item in itemset:
|
|
|
74 if item.IsShift and item.Next == symbol:
|
|
|
75 nis.add(Item(item.production, item.dotpos + 1))
|
|
|
76 return self.e_closure(nis)
|
|
|
77 def genParser(self):
|
|
|
78 states = set()
|
|
|
79 goto_table = {}
|
|
|
80 action_table = {}
|
|
|
81 iis = self.initialItemSet()
|
|
|
82 worklist = [iis]
|
|
|
83 states.add(iis)
|
|
|
84 while len(worklist) > 0:
|
|
|
85 itemset = worklist.pop(0)
|
|
|
86 has_goto = False
|
|
|
87 for symbol in self.grammar.Symbols:
|
|
|
88 nis = self.nextItemSet(itemset, symbol)
|
|
|
89 if nis:
|
|
|
90 goto_table[(itemset, symbol)] = nis
|
|
|
91 has_goto = True
|
|
|
92 if not nis in states:
|
|
|
93 worklist.append(nis)
|
|
|
94 states.add(nis)
|
|
|
95 if has_goto:
|
|
|
96 action_table[itemset] = 'shift', 's'
|
|
|
97 for item in itemset:
|
|
|
98 assert item.IsShift, item
|
|
|
99 else:
|
|
|
100 # Check for reduce-reduce conflicts:
|
|
|
101 assert len(itemset) == 1
|
|
|
102 item = list(itemset)[0]
|
|
|
103 assert item.IsReduce
|
|
|
104 action_table[itemset] = 'reduce', item.production
|
|
|
105 for s, i in zip(states, range(len(states))):
|
|
|
106 print(i, ' || '.join(str(x) for x in s))
|
|
|
107 p = LRParser()
|
|
|
108 p.goto_table = goto_table
|
|
|
109 p.action_table = action_table
|
|
|
110 p.s0 = iis
|
|
|
111 return p
|
|
|
112
|
|
|
113 class LRParser:
|
|
|
114 def parse(self, toks):
|
|
|
115 stack = [self.s0]
|
|
|
116 while stack[-1] != 'input':
|
|
|
117 action, p = self.action_table[stack[-1]]
|
|
|
118 print(action, p)
|
|
|
119 if action == 'shift':
|
|
|
120 stack.append(toks.pop(0))
|
|
|
121 s, i = stack[-2:]
|
|
|
122 stack.append(self.goto_table[(s, i)])
|
|
|
123 elif action == 'reduce':
|
|
|
124 for s in p.symbols:
|
|
|
125 stack.pop()
|
|
|
126 stack.pop()
|
|
|
127 stack.append(p.name)
|
|
|
128 s, i = stack[-2:]
|
|
|
129 if stack[-1] == 'input':
|
|
|
130 break
|
|
|
131 stack.append(self.goto_table[(s, i)])
|
|
178
|
132
|
|
|
133 # Test it:
|
|
|
134 # 1. define a simple grammar:
|
|
179
|
135 g = Grammar(['EOF', 'identifier', '(', ')', '+', '*'])
|
|
178
|
136 g.add_production('input', ['expression', 'EOF'])
|
|
|
137 g.add_production('expression', ['term'])
|
|
|
138 g.add_production('expression', ['expression', '+', 'term'])
|
|
179
|
139 g.add_production('term', ['factor'])
|
|
|
140 #g.add_production('term', ['term', '*', 'factor'])
|
|
178
|
141 g.add_production('term', ['(', 'expression', ')'])
|
|
179
|
142 g.add_production('factor', ['identifier'])
|
|
|
143 g.start_symbol = 'input'
|
|
178
|
144 # 2. define input:
|
|
179
|
145 tokens = ['identifier', '+', 'identifier', '+', 'identifier', 'EOF']
|
|
|
146 # 3. build parser:
|
|
|
147 p = LRgenerator(g).genParser()
|
|
|
148 # 4. feed input:
|
|
|
149 p.parse(tokens)
|
|
178
|
150
|
