lcfOS: python/pyyacc.py annotate

annotate python/pyyacc.py @ 191:6b2bec5653f1

Added assembler testset

author	Windel Bouwman
date	Sun, 26 May 2013 15:28:07 +0200
parents	46d62dadd61b
children	6cd6260789a1

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

Mercurial > lcfOS

annotate python/pyyacc.py @ 191:6b2bec5653f1