Mercurial > lcfOS

comparison python/pyyacc.py @ 218:494828a7adf1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
added some sort of cache to assembler
author Windel Bouwman
date Fri, 05 Jul 2013 15:30:22 +0200
parents 37ac6c016e0f
children 6259856841a0
comparison
equal deleted inserted replaced
217:8b2e5f3cd579 218:494828a7adf1
1 """ 1 """
2 Parser generator script 2 Parser generator script
3 """ 3 """
4 4
5 import shelve
6 import hashlib
5 from ppci import Token 7 from ppci import Token
6 8
7 EPS = 'EPS' 9 EPS = 'EPS'
8 EOF = 'EOF' 10 EOF = 'EOF'
9 SHIFT = 1 11 SHIFT = 1
158 for production in self.productions: 160 for production in self.productions:
159 for symbol in production.symbols: 161 for symbol in production.symbols:
160 if symbol not in self.Symbols + [EPS]: 162 if symbol not in self.Symbols + [EPS]:
161 raise ParserGenerationException('Symbol {0} undefined'.format(symbol)) 163 raise ParserGenerationException('Symbol {0} undefined'.format(symbol))
162 164
163 165 def getSignature(self):
166 m = hashlib.md5()
167 m.update((str(self.productions) + str(self.start_symbol)).encode('ascii'))
168 signature = m.hexdigest()
169
164 def genParser(self): 170 def genParser(self):
165 """ Generates a parser from the grammar """ 171 """ Generates a parser from the grammar (using a caching algorithm) """
172 signature = self.getSignature()
173 cache = shelve.open('__grammar_cache__.shelve')
174 # TODO: fix caching.
175 if ('signature1' in cache) and cache['signature'] == signature:
176 goto_table = cache['goto_table']
177 action_table = cache['action_table']
178 else:
179 action_table, goto_table = self.doGenerate()
180 cache['goto_table'] = goto_table
181 cache['action_table'] = action_table
182 cache['signature'] = signature
183 cache.close()
184 p = LRParser(action_table, goto_table, self.start_symbol)
185 p.grammar = self
186 return p
187
188 def doGenerate(self):
166 self.checkSymbols() 189 self.checkSymbols()
167 action_table = {} 190 action_table = {}
168 goto_table = {} 191 goto_table = {}
169 iis = self.initialItemSet() 192 iis = self.initialItemSet()
170 193
179 return 'Reduce {0}'.format(p) 202 return 'Reduce {0}'.format(p)
180 return 'Other' 203 return 'Other'
181 204
182 def setAction(state, t, action): 205 def setAction(state, t, action):
183 key = (state, t) 206 key = (state, t)
207 assert type(state) is int
208 assert type(t) is str
184 if key in action_table: 209 if key in action_table:
185 action2 = action_table[key] 210 action2 = action_table[key]
186 if action != action2: 211 if action != action2:
187 if (action2[0] == REDUCE) and (action[0] == SHIFT): 212 if (action2[0] == REDUCE) and (action[0] == SHIFT):
188 # Automatically resolve and do the shift action! 213 # Automatically resolve and do the shift action!
207 nextstate = transitions[(states.index(state), item.Next)] 232 nextstate = transitions[(states.index(state), item.Next)]
208 setAction(states.index(state), item.Next, (SHIFT, nextstate)) 233 setAction(states.index(state), item.Next, (SHIFT, nextstate))
209 if item.IsReduce: 234 if item.IsReduce:
210 if item.production.name == self.start_symbol and item.look_ahead == EOF: 235 if item.production.name == self.start_symbol and item.look_ahead == EOF:
211 # Rule 3: accept: 236 # Rule 3: accept:
212 setAction(states.index(state), item.look_ahead, (ACCEPT, item.production)) 237 setAction(states.index(state), item.look_ahead, (ACCEPT, self.productions.index(item.production)))
213 else: 238 else:
214 # Rule 2, reduce item: 239 # Rule 2, reduce item:
215 setAction(states.index(state), item.look_ahead, (REDUCE, item.production)) 240 setAction(states.index(state), item.look_ahead, (REDUCE, self.productions.index(item.production)))
216 for nt in self.nonterminals: 241 for nt in self.nonterminals:
217 key = (states.index(state), nt) 242 key = (states.index(state), nt)
218 if key in transitions: 243 if key in transitions:
219 goto_table[key] = transitions[key] 244 goto_table[key] = transitions[key]
220 245 return action_table, goto_table
221 return LRParser(action_table, goto_table, self.start_symbol)
222 246
223 247
224 class Production: 248 class Production:
225 """ Production rule for a grammar """ 249 """ Production rule for a grammar """
226 def __init__(self, name, symbols, f=None): 250 def __init__(self, name, symbols, f=None):
322 if not key in self.action_table: 346 if not key in self.action_table:
323 raise ParserException('Error parsing at character {0}'.format(look_ahead)) 347 raise ParserException('Error parsing at character {0}'.format(look_ahead))
324 action, param = self.action_table[key] 348 action, param = self.action_table[key]
325 if action == REDUCE: 349 if action == REDUCE:
326 f_args = [] 350 f_args = []
351 param = self.grammar.productions[param]
327 for s in param.symbols: 352 for s in param.symbols:
328 stack.pop() 353 stack.pop()
329 stack.pop() 354 stack.pop()
330 f_args.append(r_data_stack.pop()) 355 f_args.append(r_data_stack.pop())
331 f_args.reverse() 356 f_args.reverse()
346 look_ahead = Token(EOF, EOF) 371 look_ahead = Token(EOF, EOF)
347 assert type(look_ahead) is Token 372 assert type(look_ahead) is Token
348 elif action == ACCEPT: 373 elif action == ACCEPT:
349 # Pop last rule data off the stack: 374 # Pop last rule data off the stack:
350 f_args = [] 375 f_args = []
376 param = self.grammar.productions[param]
351 for s in param.symbols: 377 for s in param.symbols:
352 stack.pop() 378 stack.pop()
353 stack.pop() 379 stack.pop()
354 f_args.append(r_data_stack.pop()) 380 f_args.append(r_data_stack.pop())
355 f_args.reverse() 381 f_args.reverse()