annotate python/pyyacc.py @ 357:818be710e13d

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