lcfOS: python/pyyacc.py annotate

annotate python/pyyacc.py @ 186:46d62dadd61b

Improved testsuite

author	Windel Bouwman
date	Sat, 25 May 2013 14:26:25 +0200
parents	51a6440d6398
children	6b2bec5653f1

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

Mercurial > lcfOS

annotate python/pyyacc.py @ 186:46d62dadd61b