Mercurial > lcfOS

annotate python/pyyacc.py @ 185:51a6440d6398

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixed LR(1) parser
author Windel Bouwman
date Fri, 24 May 2013 20:45:03 +0200
parents fe2b72381a83
children 46d62dadd61b
rev   line source
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
1 """
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
2 Parser generator script
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
3 """
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
4
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
5 EPS = 'EPS'
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
6 EOF = 'EOF'
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
7 SHIFT = 1
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
8 REDUCE = 2
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
9 ACCEPT = 3
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
10
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
11 class ParserGenerationException(Exception):
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
12 pass
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
13
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
14
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
15 class ParserException(Exception):
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
16 pass
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
17
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
18
178
c694ec551f34 Added lex yacc test scripts
Windel Bouwman
parents:
diff changeset
19 class Grammar:
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
20 """ Defines a grammar of a language """
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
21 def __init__(self, terminals):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
22 self.terminals = terminals
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
23 self.nonterminals = []
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
24 self.productions = []
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
25 self._first = None # Cached first set
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
26
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
27 def add_production(self, name, symbols):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
28 """ Add a production rule to the grammar """
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
29 production = Production(name, symbols)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
30 self.productions.append(production)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
31 assert not name in self.terminals, "Cannot redefine terminal"
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
32 if not name in self.nonterminals:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
33 self.nonterminals.append(name)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
34
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
35 def productionsForName(self, name):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
36 """ Retrieve all productions for a non terminal """
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
37 return [p for p in self.productions if p.name == name]
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
38
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
39 @property
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
40 def Symbols(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
41 """ Get all the symbols defined by this grammar """
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
42 return self.nonterminals + self.terminals
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
43
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
44 @property
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
45 def first(self):
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
46 if not self._first:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
47 self._first = self.calcFirstSets()
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
48 return self._first
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
49
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
50 def calcFirstSets(self):
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
51 """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
52 Calculate first sets for each grammar symbol
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
53 This is a dictionary which maps each grammar symbol
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
54 to a set of terminals that can be encountered first
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
55 when looking for the symbol.
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
56 """
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
57 first = {}
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
58 for t in self.terminals + [EOF, EPS]:
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
59 first[t] = set([t])
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
60 for nt in self.nonterminals:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
61 first[nt] = set()
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
62 epsset = {EPS}
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
63 while True:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
64 some_change = False
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
65 for p in self.productions:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
66 rhs = set()
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
67 for beta in p.symbols:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
68 rhs = rhs | (first[beta] - epsset)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
69 if not EPS in first[beta]:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
70 break
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
71 else:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
72 if EPS in first[beta]:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
73 rhs.add(EPS)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
74 if rhs - first[p.name]:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
75 first[p.name] |= rhs
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
76 some_change = True
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
77 if not some_change:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
78 break
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
79 return first
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
80
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
81 def closure(self, itemset):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
82 """ Expand itemset by using epsilon moves """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
83 worklist = list(itemset)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
84 def addIt(itm):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
85 if not itm in itemset:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
86 itemset.add(itm)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
87 worklist.append(itm)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
88 def first2(itm, la):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
89 # When using the first sets, create a copy:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
90 f = set(self.first[item.NextNext])
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
91 if EPS in f:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
92 f.discard(EPS)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
93 f.add(item.look_ahead)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
94 return f
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
95 # Start of algorithm:
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
96 while worklist:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
97 item = worklist.pop(0)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
98 if not item.IsShift:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
99 continue
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
100 if not (item.Next in self.nonterminals):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
101 continue
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
102 C = item.Next
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
103 for add_p in self.productionsForName(C):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
104 for b in first2(item, item.look_ahead):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
105 addIt(Item(add_p, 0, b))
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
106 return frozenset(itemset)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
107
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
108 def initialItemSet(self):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
109 """ Calculates the initial item set """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
110 iis = set()
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
111 for p in self.productionsForName(self.start_symbol):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
112 iis.add(Item(p, 0, EOF))
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
113 return self.closure(iis)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
114
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
115 def nextItemSet(self, itemset, symbol):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
116 """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
117 Determines the next itemset for the current set and a symbol
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
118 This is the goto procedure
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
119 """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
120 next_set = set()
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
121 for item in itemset:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
122 if item.can_shift_over(symbol):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
123 next_set.add(item.shifted())
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
124 return self.closure(next_set)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
125
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
126 def genCanonicalSet(self, iis):
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
127 states = []
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
128 worklist = []
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
129 transitions = {}
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
130 def addSt(s):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
131 if not (s in states):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
132 worklist.append(s)
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
133 states.append(s)
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
134 addSt(iis)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
135 while len(worklist) > 0:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
136 itemset = worklist.pop(0)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
137 for symbol in self.Symbols:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
138 nis = self.nextItemSet(itemset, symbol)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
139 if not nis:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
140 continue
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
141 addSt(nis)
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
142 transitions[(states.index(itemset), symbol)] = states.index(nis)
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
143 return states, transitions
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
144
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
145 def genParser(self):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
146 """ Generates a parser from the grammar """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
147 action_table = {}
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
148 goto_table = {}
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
149 iis = self.initialItemSet()
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
150
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
151 # First generate all item sets by using the nextItemset function:
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
152 states, transitions = self.genCanonicalSet(iis)
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
153
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
154 def setAction(state, t, action):
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
155 key = (state, t)
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
156 if key in action_table:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
157 action2 = action_table[key]
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
158 if action != action2:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
159 raise ParserGenerationException('LR construction conflict')
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
160 else:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
161 action_table[key] = action
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
162
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
163 # Fill action table:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
164 for state in states:
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
165 # Detect conflicts:
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
166 for item in state:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
167 if item.IsShift and item.Next in self.terminals:
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
168 # Rule 1, a shift item:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
169 nextstate = transitions[(states.index(state), item.Next)]
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
170 setAction(states.index(state), item.Next, (SHIFT, nextstate))
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
171 if item.IsReduce:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
172 if item.production.name == self.start_symbol and item.look_ahead == EOF:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
173 # Rule 3: accept:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
174 setAction(states.index(state), item.look_ahead, (ACCEPT, None))
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
175 else:
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
176 # Rule 2, reduce item:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
177 setAction(states.index(state), item.look_ahead, (REDUCE, item.production))
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
178 for nt in self.nonterminals:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
179 key = (states.index(state), nt)
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
180 if key in transitions:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
181 goto_table[key] = transitions[key]
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
182
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
183 return LRParser(action_table, goto_table)
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
184
178
c694ec551f34 Added lex yacc test scripts
Windel Bouwman
parents:
diff changeset
185
c694ec551f34 Added lex yacc test scripts
Windel Bouwman
parents:
diff changeset
186 class Production:
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
187 """ Production rule for a grammar """
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
188 def __init__(self, name, symbols):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
189 self.name = name
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
190 self.symbols = symbols
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
191
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
192 def __repr__(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
193 return '{0} -> {1}'.format(self.name, self.symbols)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
194
179
0f3b1adfd416 LR(0) parser
Windel Bouwman
parents: 178
diff changeset
195
178
c694ec551f34 Added lex yacc test scripts
Windel Bouwman
parents:
diff changeset
196 class Item:
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
197 def __init__(self, production, dotpos, look_ahead):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
198 self.production = production
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
199 self.dotpos = dotpos
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
200 assert self.dotpos <= len(self.production.symbols)
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
201 self.look_ahead = look_ahead
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
202
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
203 def getdata(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
204 """ Gets the members as a tuple """
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
205 return (self.production, self.dotpos, self.look_ahead)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
206
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
207 def __eq__(self, other):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
208 if type(other) is type(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
209 return self.getdata() == other.getdata()
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
210 return False
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
211
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
212 def __hash__(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
213 return self.getdata().__hash__()
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
214
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
215 @property
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
216 def IsReduce(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
217 return self.dotpos == len(self.production.symbols)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
218
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
219 @property
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
220 def IsShift(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
221 return not self.IsReduce
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
222
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
223 @property
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
224 def Next(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
225 return self.production.symbols[self.dotpos]
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
226
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
227 def can_shift_over(self, symbol):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
228 """ Determines if this item can shift over the given symbol """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
229 return self.IsShift and self.Next == symbol
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
230
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
231 def shifted(self):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
232 """ Creates a new item that is shifted one position """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
233 return Item(self.production, self.dotpos + 1, self.look_ahead)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
234
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
235 @property
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
236 def NextNext(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
237 if self.dotpos + 1 >= len(self.production.symbols):
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
238 return EPS
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
239 else:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
240 return self.production.symbols[self.dotpos + 1]
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
241
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
242 def __repr__(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
243 prod = self.production
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
244 predot = ' '.join(prod.symbols[0:self.dotpos])
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
245 postdot = ' '.join(prod.symbols[self.dotpos:])
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
246 nt = prod.name
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
247 args = (nt, predot, postdot, self.look_ahead)
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
248 return '[{0} -> {1} . {2} -> {3}]'.format(*args)
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
249
179
0f3b1adfd416 LR(0) parser
Windel Bouwman
parents: 178
diff changeset
250
0f3b1adfd416 LR(0) parser
Windel Bouwman
parents: 178
diff changeset
251 class LRParser:
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
252 """ LR parser """
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
253 def __init__(self, action_table, goto_table):
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
254 self.action_table = action_table
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
255 self.goto_table = goto_table
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
256
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
257 def parse(self, toks):
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
258 stack = [0]
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
259 look_ahead = toks.pop(0)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
260 while True:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
261 state = stack[-1] # top of stack
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
262 key = (state, look_ahead)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
263 if not key in self.action_table:
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
264 print(key)
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
265 raise Exception('Error parsing')
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
266 action, param = self.action_table[(state, look_ahead)]
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
267 if action == REDUCE:
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
268 for s in param.symbols:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
269 stack.pop()
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
270 stack.pop()
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
271 state = stack[-1]
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
272 stack.append(param.name)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
273 stack.append(self.goto_table[(state, param.name)])
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
274 elif action == SHIFT:
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
275 stack.append(look_ahead)
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
276 stack.append(param)
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
277 look_ahead = toks.pop(0)
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
278 elif action == ACCEPT:
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
279 break
178
c694ec551f34 Added lex yacc test scripts
Windel Bouwman
parents:
diff changeset
280
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
281 def testSimpleGrammar():
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
282 # 1. define a simple grammar:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
283 g = Grammar(['EOF', 'identifier', '(', ')', '+', '*'])
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
284 g.add_production('input', ['expression'])
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
285 g.add_production('expression', ['term'])
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
286 g.add_production('expression', ['expression', '+', 'term'])
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
287 g.add_production('term', ['factor'])
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
288 g.add_production('term', ['term', '*', 'factor'])
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
289 g.add_production('factor', ['(', 'expression', ')'])
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
290 g.add_production('factor', ['identifier'])
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
291 g.start_symbol = 'input'
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
292 # 2. define input:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
293 tokens = ['identifier', '+', 'identifier', '+', 'identifier', 'EOF']
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
294 # 3. build parser:
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
295 p = g.genParser()
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
296 # 4. feed input:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
297 p.parse(tokens)
178
c694ec551f34 Added lex yacc test scripts
Windel Bouwman
parents:
diff changeset
298
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
299
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
300 if __name__ == '__main__':
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
301 testSimpleGrammar()