lcfOS: python/pyyacc.py annotate

annotate python/pyyacc.py @ 192:6cd6260789a1

Added more tests for parser generator

author	Windel Bouwman
date	Sun, 26 May 2013 23:19:27 +0200
parents	6b2bec5653f1
children	b01429a5d695

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

Mercurial > lcfOS

annotate python/pyyacc.py @ 192:6cd6260789a1