annotate python/pyyacc.py @ 239:63bb40758066

added check
author Windel Bouwman
date Mon, 22 Jul 2013 17:57:25 +0200
parents 494828a7adf1
children 6259856841a0
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
218
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
5 import shelve
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
6 import hashlib
191
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents: 186
diff changeset
7 from ppci import Token
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents: 186
diff changeset
8
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
9 EPS = 'EPS'
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
10 EOF = 'EOF'
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
11 SHIFT = 1
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
12 REDUCE = 2
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
13 ACCEPT = 3
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
14
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
15 class ParserGenerationException(Exception):
186
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
16 """ Raised when something goes wrong during parser generation """
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
17 pass
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
18
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
19
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
20 class ParserException(Exception):
186
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
21 """ Raised during a failure in the parsing process """
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
22 pass
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
23
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
24
178
c694ec551f34 Added lex yacc test scripts
Windel Bouwman
parents:
diff changeset
25 class Grammar:
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
26 """ Defines a grammar of a language """
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
27 def __init__(self, terminals):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
28 self.terminals = terminals
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
29 self.nonterminals = []
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
30 self.productions = []
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
31 self._first = None # Cached first set
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
32
194
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
33 def add_production(self, name, symbols, f=None):
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
34 """ Add a production rule to the grammar """
194
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
35 production = Production(name, symbols, f)
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
36 self.productions.append(production)
192
6cd6260789a1 Added more tests for parser generator
Windel Bouwman
parents: 191
diff changeset
37 if name in self.terminals:
6cd6260789a1 Added more tests for parser generator
Windel Bouwman
parents: 191
diff changeset
38 raise ParserGenerationException("Cannot redefine terminal {0}".format(name))
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
39 if not name in self.nonterminals:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
40 self.nonterminals.append(name)
194
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
41 self._first = None # Invalidate cached version
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
42
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
43 def productionsForName(self, name):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
44 """ Retrieve all productions for a non terminal """
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
45 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
46
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
47 @property
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
48 def Symbols(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
49 """ Get all the symbols defined by this grammar """
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
50 return self.nonterminals + self.terminals
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
51
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
52 @property
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
53 def first(self):
186
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
54 """
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
55 The first set is a mapping from a grammar symbol to a set of
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
56 set of all terminal symbols that can be the first terminal when
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
57 looking for the grammar symbol
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
58 """
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
59 if not self._first:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
60 self._first = self.calcFirstSets()
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
61 return self._first
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
62
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
63 def calcFirstSets(self):
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
64 """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
65 Calculate first sets for each grammar symbol
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
66 This is a dictionary which maps each grammar symbol
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
67 to a set of terminals that can be encountered first
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
68 when looking for the symbol.
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
69 """
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
70 first = {}
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
71 for t in self.terminals + [EOF, EPS]:
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
72 first[t] = set([t])
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
73 for nt in self.nonterminals:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
74 first[nt] = set()
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
75 epsset = {EPS}
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
76 while True:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
77 some_change = False
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
78 for p in self.productions:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
79 rhs = set()
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
80 for beta in p.symbols:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
81 rhs = rhs | (first[beta] - epsset)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
82 if not EPS in first[beta]:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
83 break
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
84 else:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
85 if EPS in first[beta]:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
86 rhs.add(EPS)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
87 if rhs - first[p.name]:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
88 first[p.name] |= rhs
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
89 some_change = True
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
90 if not some_change:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
91 break
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
92 return first
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
93
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
94 def closure(self, itemset):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
95 """ Expand itemset by using epsilon moves """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
96 worklist = list(itemset)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
97 def addIt(itm):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
98 if not itm in itemset:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
99 itemset.add(itm)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
100 worklist.append(itm)
186
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
101 def first2(itm):
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
102 # When using the first sets, create a copy:
186
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
103 f = set(self.first[itm.NextNext])
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
104 if EPS in f:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
105 f.discard(EPS)
186
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
106 f.add(itm.look_ahead)
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
107 return f
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
108 # Start of algorithm:
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
109 while worklist:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
110 item = worklist.pop(0)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
111 if not item.IsShift:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
112 continue
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
113 if not (item.Next in self.nonterminals):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
114 continue
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
115 C = item.Next
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
116 for add_p in self.productionsForName(C):
186
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
117 for b in first2(item):
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
118 addIt(Item(add_p, 0, b))
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
119 return frozenset(itemset)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
120
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
121 def initialItemSet(self):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
122 """ Calculates the initial item set """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
123 iis = set()
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
124 for p in self.productionsForName(self.start_symbol):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
125 iis.add(Item(p, 0, EOF))
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
126 return self.closure(iis)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
127
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
128 def nextItemSet(self, itemset, symbol):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
129 """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
130 Determines the next itemset for the current set and a symbol
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
131 This is the goto procedure
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
132 """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
133 next_set = set()
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
134 for item in itemset:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
135 if item.can_shift_over(symbol):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
136 next_set.add(item.shifted())
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
137 return self.closure(next_set)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
138
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
139 def genCanonicalSet(self, iis):
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
140 states = []
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
141 worklist = []
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
142 transitions = {}
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
143 def addSt(s):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
144 if not (s in states):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
145 worklist.append(s)
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
146 states.append(s)
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
147 addSt(iis)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
148 while len(worklist) > 0:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
149 itemset = worklist.pop(0)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
150 for symbol in self.Symbols:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
151 nis = self.nextItemSet(itemset, symbol)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
152 if not nis:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
153 continue
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
154 addSt(nis)
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
155 transitions[(states.index(itemset), symbol)] = states.index(nis)
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
156 return states, transitions
192
6cd6260789a1 Added more tests for parser generator
Windel Bouwman
parents: 191
diff changeset
157
6cd6260789a1 Added more tests for parser generator
Windel Bouwman
parents: 191
diff changeset
158 def checkSymbols(self):
6cd6260789a1 Added more tests for parser generator
Windel Bouwman
parents: 191
diff changeset
159 """ Checks no symbols are undefined """
6cd6260789a1 Added more tests for parser generator
Windel Bouwman
parents: 191
diff changeset
160 for production in self.productions:
6cd6260789a1 Added more tests for parser generator
Windel Bouwman
parents: 191
diff changeset
161 for symbol in production.symbols:
194
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
162 if symbol not in self.Symbols + [EPS]:
192
6cd6260789a1 Added more tests for parser generator
Windel Bouwman
parents: 191
diff changeset
163 raise ParserGenerationException('Symbol {0} undefined'.format(symbol))
6cd6260789a1 Added more tests for parser generator
Windel Bouwman
parents: 191
diff changeset
164
218
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
165 def getSignature(self):
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
166 m = hashlib.md5()
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
167 m.update((str(self.productions) + str(self.start_symbol)).encode('ascii'))
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
168 signature = m.hexdigest()
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
169
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
170 def genParser(self):
218
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
171 """ Generates a parser from the grammar (using a caching algorithm) """
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
172 signature = self.getSignature()
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
173 cache = shelve.open('__grammar_cache__.shelve')
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
174 # TODO: fix caching.
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
175 if ('signature1' in cache) and cache['signature'] == signature:
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
176 goto_table = cache['goto_table']
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
177 action_table = cache['action_table']
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
178 else:
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
179 action_table, goto_table = self.doGenerate()
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
180 cache['goto_table'] = goto_table
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
181 cache['action_table'] = action_table
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
182 cache['signature'] = signature
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
183 cache.close()
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
184 p = LRParser(action_table, goto_table, self.start_symbol)
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
185 p.grammar = self
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
186 return p
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
187
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
188 def doGenerate(self):
192
6cd6260789a1 Added more tests for parser generator
Windel Bouwman
parents: 191
diff changeset
189 self.checkSymbols()
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
190 action_table = {}
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
191 goto_table = {}
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
192 iis = self.initialItemSet()
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
193
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
194 # First generate all item sets by using the nextItemset function:
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
195 states, transitions = self.genCanonicalSet(iis)
194
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
196
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
197 def action_str(act):
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
198 a, p = act
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
199 if a is SHIFT:
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
200 return 'Shift {0}'.format(0)
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
201 elif a is REDUCE:
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
202 return 'Reduce {0}'.format(p)
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
203 return 'Other'
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
204
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
205 def setAction(state, t, action):
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
206 key = (state, t)
218
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
207 assert type(state) is int
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
208 assert type(t) is str
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
209 if key in action_table:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
210 action2 = action_table[key]
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
211 if action != action2:
194
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
212 if (action2[0] == REDUCE) and (action[0] == SHIFT):
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
213 # Automatically resolve and do the shift action!
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
214 # Simple, but almost always what you want!!
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
215 action_table[key] = action
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
216 else:
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
217 if (action2[0] == SHIFT) and (action[0] == REDUCE):
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
218 pass
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
219 else:
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
220 a1 = action_str(action)
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
221 a2 = action_str(action2)
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
222 raise ParserGenerationException('LR construction conflict {0} vs {1}'.format(a1, a2))
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
223 else:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
224 action_table[key] = action
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
225
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
226 # Fill action table:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
227 for state in states:
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
228 # Detect conflicts:
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
229 for item in state:
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
230 if item.IsShift and item.Next in self.terminals:
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
231 # Rule 1, a shift item:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
232 nextstate = transitions[(states.index(state), item.Next)]
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
233 setAction(states.index(state), item.Next, (SHIFT, nextstate))
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
234 if item.IsReduce:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
235 if item.production.name == self.start_symbol and item.look_ahead == EOF:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
236 # Rule 3: accept:
218
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
237 setAction(states.index(state), item.look_ahead, (ACCEPT, self.productions.index(item.production)))
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
238 else:
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
239 # Rule 2, reduce item:
218
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
240 setAction(states.index(state), item.look_ahead, (REDUCE, self.productions.index(item.production)))
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
241 for nt in self.nonterminals:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
242 key = (states.index(state), nt)
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
243 if key in transitions:
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
244 goto_table[key] = transitions[key]
218
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
245 return action_table, goto_table
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
246
178
c694ec551f34 Added lex yacc test scripts
Windel Bouwman
parents:
diff changeset
247
c694ec551f34 Added lex yacc test scripts
Windel Bouwman
parents:
diff changeset
248 class Production:
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
249 """ Production rule for a grammar """
194
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
250 def __init__(self, name, symbols, f=None):
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
251 self.name = name
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
252 self.symbols = symbols
194
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
253 self.f = f
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
254
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
255 def __repr__(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
256 return '{0} -> {1}'.format(self.name, self.symbols)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
257
179
0f3b1adfd416 LR(0) parser
Windel Bouwman
parents: 178
diff changeset
258
178
c694ec551f34 Added lex yacc test scripts
Windel Bouwman
parents:
diff changeset
259 class Item:
186
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
260 """
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
261 Represents a partially parsed item
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
262 It has a production it is looking for, a position
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
263 in this production called the 'dot' and a look ahead
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
264 symbol that must follow this item.
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
265 """
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
266 def __init__(self, production, dotpos, look_ahead):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
267 self.production = production
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
268 self.dotpos = dotpos
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
269 assert self.dotpos <= len(self.production.symbols)
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
270 self.look_ahead = look_ahead
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
271
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
272 def getdata(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
273 """ Gets the members as a tuple """
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
274 return (self.production, self.dotpos, self.look_ahead)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
275
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
276 def __eq__(self, other):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
277 if type(other) is type(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
278 return self.getdata() == other.getdata()
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
279 return False
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
280
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
281 def __hash__(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
282 return self.getdata().__hash__()
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
283
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
284 @property
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
285 def IsReduce(self):
186
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
286 """ Check if this item has the dot at the end """
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
287 return self.dotpos == len(self.production.symbols)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
288
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
289 @property
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
290 def IsShift(self):
186
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
291 """ Check if this item is a shift item, i.e. the dot can proceed """
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
292 return not self.IsReduce
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
293
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
294 @property
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
295 def Next(self):
186
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
296 """ Returns the symbol after the dot """
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
297 return self.production.symbols[self.dotpos]
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
298
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
299 def can_shift_over(self, symbol):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
300 """ Determines if this item can shift over the given symbol """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
301 return self.IsShift and self.Next == symbol
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
302
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
303 def shifted(self):
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
304 """ Creates a new item that is shifted one position """
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
305 return Item(self.production, self.dotpos + 1, self.look_ahead)
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
306
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
307 @property
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
308 def NextNext(self):
186
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
309 """ Gets the symbol after the next symbol, or EPS if at the end """
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
310 if self.dotpos + 1 >= len(self.production.symbols):
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
311 return EPS
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
312 else:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
313 return self.production.symbols[self.dotpos + 1]
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
314
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
315 def __repr__(self):
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
316 prod = self.production
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
317 predot = ' '.join(prod.symbols[0:self.dotpos])
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
318 postdot = ' '.join(prod.symbols[self.dotpos:])
186
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
319 name = prod.name
46d62dadd61b Improved testsuite
Windel Bouwman
parents: 185
diff changeset
320 args = (name, predot, postdot, self.look_ahead)
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
321 return '[{0} -> {1} . {2} -> {3}]'.format(*args)
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
322
179
0f3b1adfd416 LR(0) parser
Windel Bouwman
parents: 178
diff changeset
323
0f3b1adfd416 LR(0) parser
Windel Bouwman
parents: 178
diff changeset
324 class LRParser:
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
325 """ LR parser """
195
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
326 def __init__(self, action_table, goto_table, start_symbol):
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
327 self.action_table = action_table
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
328 self.goto_table = goto_table
195
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
329 self.start_symbol = start_symbol
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
330
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
331 def parse(self, toks):
191
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents: 186
diff changeset
332 """ Parse an iterable with tokens """
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents: 186
diff changeset
333 assert hasattr(toks, '__iter__'), '{0} not iter type'.format(type(toks))
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
334 stack = [0]
195
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
335 r_data_stack = []
194
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
336 try:
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
337 look_ahead = toks.__next__()
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
338 except StopIteration:
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
339 look_ahead = Token(EOF, EOF)
191
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents: 186
diff changeset
340 assert type(look_ahead) is Token
195
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
341 # TODO: exit on this condition:
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
342 while stack != [0, self.start_symbol, 2222]:
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
343 #print(stack)
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
344 state = stack[-1] # top of stack
191
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents: 186
diff changeset
345 key = (state, look_ahead.typ)
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
346 if not key in self.action_table:
194
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
347 raise ParserException('Error parsing at character {0}'.format(look_ahead))
191
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents: 186
diff changeset
348 action, param = self.action_table[key]
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
349 if action == REDUCE:
194
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
350 f_args = []
218
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
351 param = self.grammar.productions[param]
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
352 for s in param.symbols:
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
353 stack.pop()
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
354 stack.pop()
195
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
355 f_args.append(r_data_stack.pop())
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
356 f_args.reverse()
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
357 r_data = None
194
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
358 if param.f:
195
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
359 r_data = param.f(*f_args)
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
360 state = stack[-1]
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
361 stack.append(param.name)
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
362 stack.append(self.goto_table[(state, param.name)])
195
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
363 r_data_stack.append(r_data)
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
364 elif action == SHIFT:
191
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents: 186
diff changeset
365 stack.append(look_ahead.typ)
185
51a6440d6398 Fixed LR(1) parser
Windel Bouwman
parents: 184
diff changeset
366 stack.append(param)
195
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
367 r_data_stack.append(look_ahead.val)
191
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents: 186
diff changeset
368 try:
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents: 186
diff changeset
369 look_ahead = toks.__next__()
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents: 186
diff changeset
370 except StopIteration:
194
b01429a5d695 Fixed test
Windel Bouwman
parents: 192
diff changeset
371 look_ahead = Token(EOF, EOF)
191
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents: 186
diff changeset
372 assert type(look_ahead) is Token
184
fe2b72381a83 Added testset for pyy
Windel Bouwman
parents: 181
diff changeset
373 elif action == ACCEPT:
195
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
374 # Pop last rule data off the stack:
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
375 f_args = []
218
494828a7adf1 added some sort of cache to assembler
Windel Bouwman
parents: 195
diff changeset
376 param = self.grammar.productions[param]
195
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
377 for s in param.symbols:
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
378 stack.pop()
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
379 stack.pop()
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
380 f_args.append(r_data_stack.pop())
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
381 f_args.reverse()
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
382 if param.f:
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
383 param.f(*f_args)
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
384 # Break out!
181
216da5e46efc Changed indent to 4 spaces to comply to convention
Windel Bouwman
parents: 180
diff changeset
385 break
195
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
386 # At exit, the stack must be 1 long
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
387 # TODO: fix that this holds:
37ac6c016e0f Expanded asm subsystem
Windel Bouwman
parents: 194
diff changeset
388 #assert len(stack) == 1, 'stack {0} not totally reduce'.format(stack)
178
c694ec551f34 Added lex yacc test scripts
Windel Bouwman
parents:
diff changeset
389