Mercurial > repo
comparison ply-3.8/build/lib.linux-x86_64-2.7/ply/yacc.py @ 7268:a1845676eaa0
<ais523> ` (cd ply-3.8; python setup.py build)
author | HackBot |
---|---|
date | Wed, 23 Mar 2016 02:43:21 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
7267:343ff337a19b | 7268:a1845676eaa0 |
---|---|
1 # ----------------------------------------------------------------------------- | |
2 # ply: yacc.py | |
3 # | |
4 # Copyright (C) 2001-2015, | |
5 # David M. Beazley (Dabeaz LLC) | |
6 # All rights reserved. | |
7 # | |
8 # Redistribution and use in source and binary forms, with or without | |
9 # modification, are permitted provided that the following conditions are | |
10 # met: | |
11 # | |
12 # * Redistributions of source code must retain the above copyright notice, | |
13 # this list of conditions and the following disclaimer. | |
14 # * Redistributions in binary form must reproduce the above copyright notice, | |
15 # this list of conditions and the following disclaimer in the documentation | |
16 # and/or other materials provided with the distribution. | |
17 # * Neither the name of the David Beazley or Dabeaz LLC may be used to | |
18 # endorse or promote products derived from this software without | |
19 # specific prior written permission. | |
20 # | |
21 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
22 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
23 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
24 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
25 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
26 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
27 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
28 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
29 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
30 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
31 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
32 # ----------------------------------------------------------------------------- | |
33 # | |
34 # This implements an LR parser that is constructed from grammar rules defined | |
35 # as Python functions. The grammer is specified by supplying the BNF inside | |
36 # Python documentation strings. The inspiration for this technique was borrowed | |
37 # from John Aycock's Spark parsing system. PLY might be viewed as cross between | |
38 # Spark and the GNU bison utility. | |
39 # | |
40 # The current implementation is only somewhat object-oriented. The | |
41 # LR parser itself is defined in terms of an object (which allows multiple | |
42 # parsers to co-exist). However, most of the variables used during table | |
43 # construction are defined in terms of global variables. Users shouldn't | |
44 # notice unless they are trying to define multiple parsers at the same | |
45 # time using threads (in which case they should have their head examined). | |
46 # | |
47 # This implementation supports both SLR and LALR(1) parsing. LALR(1) | |
48 # support was originally implemented by Elias Ioup (ezioup@alumni.uchicago.edu), | |
49 # using the algorithm found in Aho, Sethi, and Ullman "Compilers: Principles, | |
50 # Techniques, and Tools" (The Dragon Book). LALR(1) has since been replaced | |
51 # by the more efficient DeRemer and Pennello algorithm. | |
52 # | |
53 # :::::::: WARNING ::::::: | |
54 # | |
55 # Construction of LR parsing tables is fairly complicated and expensive. | |
56 # To make this module run fast, a *LOT* of work has been put into | |
57 # optimization---often at the expensive of readability and what might | |
58 # consider to be good Python "coding style." Modify the code at your | |
59 # own risk! | |
60 # ---------------------------------------------------------------------------- | |
61 | |
62 import re | |
63 import types | |
64 import sys | |
65 import os.path | |
66 import inspect | |
67 import base64 | |
68 import warnings | |
69 | |
70 __version__ = '3.8' | |
71 __tabversion__ = '3.8' | |
72 | |
73 #----------------------------------------------------------------------------- | |
74 # === User configurable parameters === | |
75 # | |
76 # Change these to modify the default behavior of yacc (if you wish) | |
77 #----------------------------------------------------------------------------- | |
78 | |
79 yaccdebug = True # Debugging mode. If set, yacc generates a | |
80 # a 'parser.out' file in the current directory | |
81 | |
82 debug_file = 'parser.out' # Default name of the debugging file | |
83 tab_module = 'parsetab' # Default name of the table module | |
84 default_lr = 'LALR' # Default LR table generation method | |
85 | |
86 error_count = 3 # Number of symbols that must be shifted to leave recovery mode | |
87 | |
88 yaccdevel = False # Set to True if developing yacc. This turns off optimized | |
89 # implementations of certain functions. | |
90 | |
91 resultlimit = 40 # Size limit of results when running in debug mode. | |
92 | |
93 pickle_protocol = 0 # Protocol to use when writing pickle files | |
94 | |
95 # String type-checking compatibility | |
96 if sys.version_info[0] < 3: | |
97 string_types = basestring | |
98 else: | |
99 string_types = str | |
100 | |
101 MAXINT = sys.maxsize | |
102 | |
103 # This object is a stand-in for a logging object created by the | |
104 # logging module. PLY will use this by default to create things | |
105 # such as the parser.out file. If a user wants more detailed | |
106 # information, they can create their own logging object and pass | |
107 # it into PLY. | |
108 | |
109 class PlyLogger(object): | |
110 def __init__(self, f): | |
111 self.f = f | |
112 | |
113 def debug(self, msg, *args, **kwargs): | |
114 self.f.write((msg % args) + '\n') | |
115 | |
116 info = debug | |
117 | |
118 def warning(self, msg, *args, **kwargs): | |
119 self.f.write('WARNING: ' + (msg % args) + '\n') | |
120 | |
121 def error(self, msg, *args, **kwargs): | |
122 self.f.write('ERROR: ' + (msg % args) + '\n') | |
123 | |
124 critical = debug | |
125 | |
126 # Null logger is used when no output is generated. Does nothing. | |
127 class NullLogger(object): | |
128 def __getattribute__(self, name): | |
129 return self | |
130 | |
131 def __call__(self, *args, **kwargs): | |
132 return self | |
133 | |
134 # Exception raised for yacc-related errors | |
135 class YaccError(Exception): | |
136 pass | |
137 | |
138 # Format the result message that the parser produces when running in debug mode. | |
139 def format_result(r): | |
140 repr_str = repr(r) | |
141 if '\n' in repr_str: | |
142 repr_str = repr(repr_str) | |
143 if len(repr_str) > resultlimit: | |
144 repr_str = repr_str[:resultlimit] + ' ...' | |
145 result = '<%s @ 0x%x> (%s)' % (type(r).__name__, id(r), repr_str) | |
146 return result | |
147 | |
148 # Format stack entries when the parser is running in debug mode | |
149 def format_stack_entry(r): | |
150 repr_str = repr(r) | |
151 if '\n' in repr_str: | |
152 repr_str = repr(repr_str) | |
153 if len(repr_str) < 16: | |
154 return repr_str | |
155 else: | |
156 return '<%s @ 0x%x>' % (type(r).__name__, id(r)) | |
157 | |
158 # Panic mode error recovery support. This feature is being reworked--much of the | |
159 # code here is to offer a deprecation/backwards compatible transition | |
160 | |
161 _errok = None | |
162 _token = None | |
163 _restart = None | |
164 _warnmsg = '''PLY: Don't use global functions errok(), token(), and restart() in p_error(). | |
165 Instead, invoke the methods on the associated parser instance: | |
166 | |
167 def p_error(p): | |
168 ... | |
169 # Use parser.errok(), parser.token(), parser.restart() | |
170 ... | |
171 | |
172 parser = yacc.yacc() | |
173 ''' | |
174 | |
175 def errok(): | |
176 warnings.warn(_warnmsg) | |
177 return _errok() | |
178 | |
179 def restart(): | |
180 warnings.warn(_warnmsg) | |
181 return _restart() | |
182 | |
183 def token(): | |
184 warnings.warn(_warnmsg) | |
185 return _token() | |
186 | |
187 # Utility function to call the p_error() function with some deprecation hacks | |
188 def call_errorfunc(errorfunc, token, parser): | |
189 global _errok, _token, _restart | |
190 _errok = parser.errok | |
191 _token = parser.token | |
192 _restart = parser.restart | |
193 r = errorfunc(token) | |
194 try: | |
195 del _errok, _token, _restart | |
196 except NameError: | |
197 pass | |
198 return r | |
199 | |
200 #----------------------------------------------------------------------------- | |
201 # === LR Parsing Engine === | |
202 # | |
203 # The following classes are used for the LR parser itself. These are not | |
204 # used during table construction and are independent of the actual LR | |
205 # table generation algorithm | |
206 #----------------------------------------------------------------------------- | |
207 | |
208 # This class is used to hold non-terminal grammar symbols during parsing. | |
209 # It normally has the following attributes set: | |
210 # .type = Grammar symbol type | |
211 # .value = Symbol value | |
212 # .lineno = Starting line number | |
213 # .endlineno = Ending line number (optional, set automatically) | |
214 # .lexpos = Starting lex position | |
215 # .endlexpos = Ending lex position (optional, set automatically) | |
216 | |
217 class YaccSymbol: | |
218 def __str__(self): | |
219 return self.type | |
220 | |
221 def __repr__(self): | |
222 return str(self) | |
223 | |
224 # This class is a wrapper around the objects actually passed to each | |
225 # grammar rule. Index lookup and assignment actually assign the | |
226 # .value attribute of the underlying YaccSymbol object. | |
227 # The lineno() method returns the line number of a given | |
228 # item (or 0 if not defined). The linespan() method returns | |
229 # a tuple of (startline,endline) representing the range of lines | |
230 # for a symbol. The lexspan() method returns a tuple (lexpos,endlexpos) | |
231 # representing the range of positional information for a symbol. | |
232 | |
233 class YaccProduction: | |
234 def __init__(self, s, stack=None): | |
235 self.slice = s | |
236 self.stack = stack | |
237 self.lexer = None | |
238 self.parser = None | |
239 | |
240 def __getitem__(self, n): | |
241 if isinstance(n, slice): | |
242 return [s.value for s in self.slice[n]] | |
243 elif n >= 0: | |
244 return self.slice[n].value | |
245 else: | |
246 return self.stack[n].value | |
247 | |
248 def __setitem__(self, n, v): | |
249 self.slice[n].value = v | |
250 | |
251 def __getslice__(self, i, j): | |
252 return [s.value for s in self.slice[i:j]] | |
253 | |
254 def __len__(self): | |
255 return len(self.slice) | |
256 | |
257 def lineno(self, n): | |
258 return getattr(self.slice[n], 'lineno', 0) | |
259 | |
260 def set_lineno(self, n, lineno): | |
261 self.slice[n].lineno = lineno | |
262 | |
263 def linespan(self, n): | |
264 startline = getattr(self.slice[n], 'lineno', 0) | |
265 endline = getattr(self.slice[n], 'endlineno', startline) | |
266 return startline, endline | |
267 | |
268 def lexpos(self, n): | |
269 return getattr(self.slice[n], 'lexpos', 0) | |
270 | |
271 def lexspan(self, n): | |
272 startpos = getattr(self.slice[n], 'lexpos', 0) | |
273 endpos = getattr(self.slice[n], 'endlexpos', startpos) | |
274 return startpos, endpos | |
275 | |
276 def error(self): | |
277 raise SyntaxError | |
278 | |
279 # ----------------------------------------------------------------------------- | |
280 # == LRParser == | |
281 # | |
282 # The LR Parsing engine. | |
283 # ----------------------------------------------------------------------------- | |
284 | |
285 class LRParser: | |
286 def __init__(self, lrtab, errorf): | |
287 self.productions = lrtab.lr_productions | |
288 self.action = lrtab.lr_action | |
289 self.goto = lrtab.lr_goto | |
290 self.errorfunc = errorf | |
291 self.set_defaulted_states() | |
292 self.errorok = True | |
293 | |
294 def errok(self): | |
295 self.errorok = True | |
296 | |
297 def restart(self): | |
298 del self.statestack[:] | |
299 del self.symstack[:] | |
300 sym = YaccSymbol() | |
301 sym.type = '$end' | |
302 self.symstack.append(sym) | |
303 self.statestack.append(0) | |
304 | |
305 # Defaulted state support. | |
306 # This method identifies parser states where there is only one possible reduction action. | |
307 # For such states, the parser can make a choose to make a rule reduction without consuming | |
308 # the next look-ahead token. This delayed invocation of the tokenizer can be useful in | |
309 # certain kinds of advanced parsing situations where the lexer and parser interact with | |
310 # each other or change states (i.e., manipulation of scope, lexer states, etc.). | |
311 # | |
312 # See: http://www.gnu.org/software/bison/manual/html_node/Default-Reductions.html#Default-Reductions | |
313 def set_defaulted_states(self): | |
314 self.defaulted_states = {} | |
315 for state, actions in self.action.items(): | |
316 rules = list(actions.values()) | |
317 if len(rules) == 1 and rules[0] < 0: | |
318 self.defaulted_states[state] = rules[0] | |
319 | |
320 def disable_defaulted_states(self): | |
321 self.defaulted_states = {} | |
322 | |
323 def parse(self, input=None, lexer=None, debug=False, tracking=False, tokenfunc=None): | |
324 if debug or yaccdevel: | |
325 if isinstance(debug, int): | |
326 debug = PlyLogger(sys.stderr) | |
327 return self.parsedebug(input, lexer, debug, tracking, tokenfunc) | |
328 elif tracking: | |
329 return self.parseopt(input, lexer, debug, tracking, tokenfunc) | |
330 else: | |
331 return self.parseopt_notrack(input, lexer, debug, tracking, tokenfunc) | |
332 | |
333 | |
334 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
335 # parsedebug(). | |
336 # | |
337 # This is the debugging enabled version of parse(). All changes made to the | |
338 # parsing engine should be made here. Optimized versions of this function | |
339 # are automatically created by the ply/ygen.py script. This script cuts out | |
340 # sections enclosed in markers such as this: | |
341 # | |
342 # #--! DEBUG | |
343 # statements | |
344 # #--! DEBUG | |
345 # | |
346 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
347 | |
348 def parsedebug(self, input=None, lexer=None, debug=False, tracking=False, tokenfunc=None): | |
349 #--! parsedebug-start | |
350 lookahead = None # Current lookahead symbol | |
351 lookaheadstack = [] # Stack of lookahead symbols | |
352 actions = self.action # Local reference to action table (to avoid lookup on self.) | |
353 goto = self.goto # Local reference to goto table (to avoid lookup on self.) | |
354 prod = self.productions # Local reference to production list (to avoid lookup on self.) | |
355 defaulted_states = self.defaulted_states # Local reference to defaulted states | |
356 pslice = YaccProduction(None) # Production object passed to grammar rules | |
357 errorcount = 0 # Used during error recovery | |
358 | |
359 #--! DEBUG | |
360 debug.info('PLY: PARSE DEBUG START') | |
361 #--! DEBUG | |
362 | |
363 # If no lexer was given, we will try to use the lex module | |
364 if not lexer: | |
365 from . import lex | |
366 lexer = lex.lexer | |
367 | |
368 # Set up the lexer and parser objects on pslice | |
369 pslice.lexer = lexer | |
370 pslice.parser = self | |
371 | |
372 # If input was supplied, pass to lexer | |
373 if input is not None: | |
374 lexer.input(input) | |
375 | |
376 if tokenfunc is None: | |
377 # Tokenize function | |
378 get_token = lexer.token | |
379 else: | |
380 get_token = tokenfunc | |
381 | |
382 # Set the parser() token method (sometimes used in error recovery) | |
383 self.token = get_token | |
384 | |
385 # Set up the state and symbol stacks | |
386 | |
387 statestack = [] # Stack of parsing states | |
388 self.statestack = statestack | |
389 symstack = [] # Stack of grammar symbols | |
390 self.symstack = symstack | |
391 | |
392 pslice.stack = symstack # Put in the production | |
393 errtoken = None # Err token | |
394 | |
395 # The start state is assumed to be (0,$end) | |
396 | |
397 statestack.append(0) | |
398 sym = YaccSymbol() | |
399 sym.type = '$end' | |
400 symstack.append(sym) | |
401 state = 0 | |
402 while True: | |
403 # Get the next symbol on the input. If a lookahead symbol | |
404 # is already set, we just use that. Otherwise, we'll pull | |
405 # the next token off of the lookaheadstack or from the lexer | |
406 | |
407 #--! DEBUG | |
408 debug.debug('') | |
409 debug.debug('State : %s', state) | |
410 #--! DEBUG | |
411 | |
412 if state not in defaulted_states: | |
413 if not lookahead: | |
414 if not lookaheadstack: | |
415 lookahead = get_token() # Get the next token | |
416 else: | |
417 lookahead = lookaheadstack.pop() | |
418 if not lookahead: | |
419 lookahead = YaccSymbol() | |
420 lookahead.type = '$end' | |
421 | |
422 # Check the action table | |
423 ltype = lookahead.type | |
424 t = actions[state].get(ltype) | |
425 else: | |
426 t = defaulted_states[state] | |
427 #--! DEBUG | |
428 debug.debug('Defaulted state %s: Reduce using %d', state, -t) | |
429 #--! DEBUG | |
430 | |
431 #--! DEBUG | |
432 debug.debug('Stack : %s', | |
433 ('%s . %s' % (' '.join([xx.type for xx in symstack][1:]), str(lookahead))).lstrip()) | |
434 #--! DEBUG | |
435 | |
436 if t is not None: | |
437 if t > 0: | |
438 # shift a symbol on the stack | |
439 statestack.append(t) | |
440 state = t | |
441 | |
442 #--! DEBUG | |
443 debug.debug('Action : Shift and goto state %s', t) | |
444 #--! DEBUG | |
445 | |
446 symstack.append(lookahead) | |
447 lookahead = None | |
448 | |
449 # Decrease error count on successful shift | |
450 if errorcount: | |
451 errorcount -= 1 | |
452 continue | |
453 | |
454 if t < 0: | |
455 # reduce a symbol on the stack, emit a production | |
456 p = prod[-t] | |
457 pname = p.name | |
458 plen = p.len | |
459 | |
460 # Get production function | |
461 sym = YaccSymbol() | |
462 sym.type = pname # Production name | |
463 sym.value = None | |
464 | |
465 #--! DEBUG | |
466 if plen: | |
467 debug.info('Action : Reduce rule [%s] with %s and goto state %d', p.str, | |
468 '['+','.join([format_stack_entry(_v.value) for _v in symstack[-plen:]])+']', | |
469 goto[statestack[-1-plen]][pname]) | |
470 else: | |
471 debug.info('Action : Reduce rule [%s] with %s and goto state %d', p.str, [], | |
472 goto[statestack[-1]][pname]) | |
473 | |
474 #--! DEBUG | |
475 | |
476 if plen: | |
477 targ = symstack[-plen-1:] | |
478 targ[0] = sym | |
479 | |
480 #--! TRACKING | |
481 if tracking: | |
482 t1 = targ[1] | |
483 sym.lineno = t1.lineno | |
484 sym.lexpos = t1.lexpos | |
485 t1 = targ[-1] | |
486 sym.endlineno = getattr(t1, 'endlineno', t1.lineno) | |
487 sym.endlexpos = getattr(t1, 'endlexpos', t1.lexpos) | |
488 #--! TRACKING | |
489 | |
490 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
491 # The code enclosed in this section is duplicated | |
492 # below as a performance optimization. Make sure | |
493 # changes get made in both locations. | |
494 | |
495 pslice.slice = targ | |
496 | |
497 try: | |
498 # Call the grammar rule with our special slice object | |
499 del symstack[-plen:] | |
500 del statestack[-plen:] | |
501 p.callable(pslice) | |
502 #--! DEBUG | |
503 debug.info('Result : %s', format_result(pslice[0])) | |
504 #--! DEBUG | |
505 symstack.append(sym) | |
506 state = goto[statestack[-1]][pname] | |
507 statestack.append(state) | |
508 except SyntaxError: | |
509 # If an error was set. Enter error recovery state | |
510 lookaheadstack.append(lookahead) | |
511 symstack.pop() | |
512 statestack.pop() | |
513 state = statestack[-1] | |
514 sym.type = 'error' | |
515 lookahead = sym | |
516 errorcount = error_count | |
517 self.errorok = False | |
518 continue | |
519 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
520 | |
521 else: | |
522 | |
523 #--! TRACKING | |
524 if tracking: | |
525 sym.lineno = lexer.lineno | |
526 sym.lexpos = lexer.lexpos | |
527 #--! TRACKING | |
528 | |
529 targ = [sym] | |
530 | |
531 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
532 # The code enclosed in this section is duplicated | |
533 # above as a performance optimization. Make sure | |
534 # changes get made in both locations. | |
535 | |
536 pslice.slice = targ | |
537 | |
538 try: | |
539 # Call the grammar rule with our special slice object | |
540 p.callable(pslice) | |
541 #--! DEBUG | |
542 debug.info('Result : %s', format_result(pslice[0])) | |
543 #--! DEBUG | |
544 symstack.append(sym) | |
545 state = goto[statestack[-1]][pname] | |
546 statestack.append(state) | |
547 except SyntaxError: | |
548 # If an error was set. Enter error recovery state | |
549 lookaheadstack.append(lookahead) | |
550 symstack.pop() | |
551 statestack.pop() | |
552 state = statestack[-1] | |
553 sym.type = 'error' | |
554 lookahead = sym | |
555 errorcount = error_count | |
556 self.errorok = False | |
557 continue | |
558 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
559 | |
560 if t == 0: | |
561 n = symstack[-1] | |
562 result = getattr(n, 'value', None) | |
563 #--! DEBUG | |
564 debug.info('Done : Returning %s', format_result(result)) | |
565 debug.info('PLY: PARSE DEBUG END') | |
566 #--! DEBUG | |
567 return result | |
568 | |
569 if t is None: | |
570 | |
571 #--! DEBUG | |
572 debug.error('Error : %s', | |
573 ('%s . %s' % (' '.join([xx.type for xx in symstack][1:]), str(lookahead))).lstrip()) | |
574 #--! DEBUG | |
575 | |
576 # We have some kind of parsing error here. To handle | |
577 # this, we are going to push the current token onto | |
578 # the tokenstack and replace it with an 'error' token. | |
579 # If there are any synchronization rules, they may | |
580 # catch it. | |
581 # | |
582 # In addition to pushing the error token, we call call | |
583 # the user defined p_error() function if this is the | |
584 # first syntax error. This function is only called if | |
585 # errorcount == 0. | |
586 if errorcount == 0 or self.errorok: | |
587 errorcount = error_count | |
588 self.errorok = False | |
589 errtoken = lookahead | |
590 if errtoken.type == '$end': | |
591 errtoken = None # End of file! | |
592 if self.errorfunc: | |
593 if errtoken and not hasattr(errtoken, 'lexer'): | |
594 errtoken.lexer = lexer | |
595 tok = call_errorfunc(self.errorfunc, errtoken, self) | |
596 if self.errorok: | |
597 # User must have done some kind of panic | |
598 # mode recovery on their own. The | |
599 # returned token is the next lookahead | |
600 lookahead = tok | |
601 errtoken = None | |
602 continue | |
603 else: | |
604 if errtoken: | |
605 if hasattr(errtoken, 'lineno'): | |
606 lineno = lookahead.lineno | |
607 else: | |
608 lineno = 0 | |
609 if lineno: | |
610 sys.stderr.write('yacc: Syntax error at line %d, token=%s\n' % (lineno, errtoken.type)) | |
611 else: | |
612 sys.stderr.write('yacc: Syntax error, token=%s' % errtoken.type) | |
613 else: | |
614 sys.stderr.write('yacc: Parse error in input. EOF\n') | |
615 return | |
616 | |
617 else: | |
618 errorcount = error_count | |
619 | |
620 # case 1: the statestack only has 1 entry on it. If we're in this state, the | |
621 # entire parse has been rolled back and we're completely hosed. The token is | |
622 # discarded and we just keep going. | |
623 | |
624 if len(statestack) <= 1 and lookahead.type != '$end': | |
625 lookahead = None | |
626 errtoken = None | |
627 state = 0 | |
628 # Nuke the pushback stack | |
629 del lookaheadstack[:] | |
630 continue | |
631 | |
632 # case 2: the statestack has a couple of entries on it, but we're | |
633 # at the end of the file. nuke the top entry and generate an error token | |
634 | |
635 # Start nuking entries on the stack | |
636 if lookahead.type == '$end': | |
637 # Whoa. We're really hosed here. Bail out | |
638 return | |
639 | |
640 if lookahead.type != 'error': | |
641 sym = symstack[-1] | |
642 if sym.type == 'error': | |
643 # Hmmm. Error is on top of stack, we'll just nuke input | |
644 # symbol and continue | |
645 #--! TRACKING | |
646 if tracking: | |
647 sym.endlineno = getattr(lookahead, 'lineno', sym.lineno) | |
648 sym.endlexpos = getattr(lookahead, 'lexpos', sym.lexpos) | |
649 #--! TRACKING | |
650 lookahead = None | |
651 continue | |
652 | |
653 # Create the error symbol for the first time and make it the new lookahead symbol | |
654 t = YaccSymbol() | |
655 t.type = 'error' | |
656 | |
657 if hasattr(lookahead, 'lineno'): | |
658 t.lineno = t.endlineno = lookahead.lineno | |
659 if hasattr(lookahead, 'lexpos'): | |
660 t.lexpos = t.endlexpos = lookahead.lexpos | |
661 t.value = lookahead | |
662 lookaheadstack.append(lookahead) | |
663 lookahead = t | |
664 else: | |
665 sym = symstack.pop() | |
666 #--! TRACKING | |
667 if tracking: | |
668 lookahead.lineno = sym.lineno | |
669 lookahead.lexpos = sym.lexpos | |
670 #--! TRACKING | |
671 statestack.pop() | |
672 state = statestack[-1] | |
673 | |
674 continue | |
675 | |
676 # Call an error function here | |
677 raise RuntimeError('yacc: internal parser error!!!\n') | |
678 | |
679 #--! parsedebug-end | |
680 | |
681 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
682 # parseopt(). | |
683 # | |
684 # Optimized version of parse() method. DO NOT EDIT THIS CODE DIRECTLY! | |
685 # This code is automatically generated by the ply/ygen.py script. Make | |
686 # changes to the parsedebug() method instead. | |
687 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
688 | |
689 def parseopt(self, input=None, lexer=None, debug=False, tracking=False, tokenfunc=None): | |
690 #--! parseopt-start | |
691 lookahead = None # Current lookahead symbol | |
692 lookaheadstack = [] # Stack of lookahead symbols | |
693 actions = self.action # Local reference to action table (to avoid lookup on self.) | |
694 goto = self.goto # Local reference to goto table (to avoid lookup on self.) | |
695 prod = self.productions # Local reference to production list (to avoid lookup on self.) | |
696 defaulted_states = self.defaulted_states # Local reference to defaulted states | |
697 pslice = YaccProduction(None) # Production object passed to grammar rules | |
698 errorcount = 0 # Used during error recovery | |
699 | |
700 | |
701 # If no lexer was given, we will try to use the lex module | |
702 if not lexer: | |
703 from . import lex | |
704 lexer = lex.lexer | |
705 | |
706 # Set up the lexer and parser objects on pslice | |
707 pslice.lexer = lexer | |
708 pslice.parser = self | |
709 | |
710 # If input was supplied, pass to lexer | |
711 if input is not None: | |
712 lexer.input(input) | |
713 | |
714 if tokenfunc is None: | |
715 # Tokenize function | |
716 get_token = lexer.token | |
717 else: | |
718 get_token = tokenfunc | |
719 | |
720 # Set the parser() token method (sometimes used in error recovery) | |
721 self.token = get_token | |
722 | |
723 # Set up the state and symbol stacks | |
724 | |
725 statestack = [] # Stack of parsing states | |
726 self.statestack = statestack | |
727 symstack = [] # Stack of grammar symbols | |
728 self.symstack = symstack | |
729 | |
730 pslice.stack = symstack # Put in the production | |
731 errtoken = None # Err token | |
732 | |
733 # The start state is assumed to be (0,$end) | |
734 | |
735 statestack.append(0) | |
736 sym = YaccSymbol() | |
737 sym.type = '$end' | |
738 symstack.append(sym) | |
739 state = 0 | |
740 while True: | |
741 # Get the next symbol on the input. If a lookahead symbol | |
742 # is already set, we just use that. Otherwise, we'll pull | |
743 # the next token off of the lookaheadstack or from the lexer | |
744 | |
745 | |
746 if state not in defaulted_states: | |
747 if not lookahead: | |
748 if not lookaheadstack: | |
749 lookahead = get_token() # Get the next token | |
750 else: | |
751 lookahead = lookaheadstack.pop() | |
752 if not lookahead: | |
753 lookahead = YaccSymbol() | |
754 lookahead.type = '$end' | |
755 | |
756 # Check the action table | |
757 ltype = lookahead.type | |
758 t = actions[state].get(ltype) | |
759 else: | |
760 t = defaulted_states[state] | |
761 | |
762 | |
763 if t is not None: | |
764 if t > 0: | |
765 # shift a symbol on the stack | |
766 statestack.append(t) | |
767 state = t | |
768 | |
769 | |
770 symstack.append(lookahead) | |
771 lookahead = None | |
772 | |
773 # Decrease error count on successful shift | |
774 if errorcount: | |
775 errorcount -= 1 | |
776 continue | |
777 | |
778 if t < 0: | |
779 # reduce a symbol on the stack, emit a production | |
780 p = prod[-t] | |
781 pname = p.name | |
782 plen = p.len | |
783 | |
784 # Get production function | |
785 sym = YaccSymbol() | |
786 sym.type = pname # Production name | |
787 sym.value = None | |
788 | |
789 | |
790 if plen: | |
791 targ = symstack[-plen-1:] | |
792 targ[0] = sym | |
793 | |
794 #--! TRACKING | |
795 if tracking: | |
796 t1 = targ[1] | |
797 sym.lineno = t1.lineno | |
798 sym.lexpos = t1.lexpos | |
799 t1 = targ[-1] | |
800 sym.endlineno = getattr(t1, 'endlineno', t1.lineno) | |
801 sym.endlexpos = getattr(t1, 'endlexpos', t1.lexpos) | |
802 #--! TRACKING | |
803 | |
804 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
805 # The code enclosed in this section is duplicated | |
806 # below as a performance optimization. Make sure | |
807 # changes get made in both locations. | |
808 | |
809 pslice.slice = targ | |
810 | |
811 try: | |
812 # Call the grammar rule with our special slice object | |
813 del symstack[-plen:] | |
814 del statestack[-plen:] | |
815 p.callable(pslice) | |
816 symstack.append(sym) | |
817 state = goto[statestack[-1]][pname] | |
818 statestack.append(state) | |
819 except SyntaxError: | |
820 # If an error was set. Enter error recovery state | |
821 lookaheadstack.append(lookahead) | |
822 symstack.pop() | |
823 statestack.pop() | |
824 state = statestack[-1] | |
825 sym.type = 'error' | |
826 lookahead = sym | |
827 errorcount = error_count | |
828 self.errorok = False | |
829 continue | |
830 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
831 | |
832 else: | |
833 | |
834 #--! TRACKING | |
835 if tracking: | |
836 sym.lineno = lexer.lineno | |
837 sym.lexpos = lexer.lexpos | |
838 #--! TRACKING | |
839 | |
840 targ = [sym] | |
841 | |
842 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
843 # The code enclosed in this section is duplicated | |
844 # above as a performance optimization. Make sure | |
845 # changes get made in both locations. | |
846 | |
847 pslice.slice = targ | |
848 | |
849 try: | |
850 # Call the grammar rule with our special slice object | |
851 p.callable(pslice) | |
852 symstack.append(sym) | |
853 state = goto[statestack[-1]][pname] | |
854 statestack.append(state) | |
855 except SyntaxError: | |
856 # If an error was set. Enter error recovery state | |
857 lookaheadstack.append(lookahead) | |
858 symstack.pop() | |
859 statestack.pop() | |
860 state = statestack[-1] | |
861 sym.type = 'error' | |
862 lookahead = sym | |
863 errorcount = error_count | |
864 self.errorok = False | |
865 continue | |
866 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
867 | |
868 if t == 0: | |
869 n = symstack[-1] | |
870 result = getattr(n, 'value', None) | |
871 return result | |
872 | |
873 if t is None: | |
874 | |
875 | |
876 # We have some kind of parsing error here. To handle | |
877 # this, we are going to push the current token onto | |
878 # the tokenstack and replace it with an 'error' token. | |
879 # If there are any synchronization rules, they may | |
880 # catch it. | |
881 # | |
882 # In addition to pushing the error token, we call call | |
883 # the user defined p_error() function if this is the | |
884 # first syntax error. This function is only called if | |
885 # errorcount == 0. | |
886 if errorcount == 0 or self.errorok: | |
887 errorcount = error_count | |
888 self.errorok = False | |
889 errtoken = lookahead | |
890 if errtoken.type == '$end': | |
891 errtoken = None # End of file! | |
892 if self.errorfunc: | |
893 if errtoken and not hasattr(errtoken, 'lexer'): | |
894 errtoken.lexer = lexer | |
895 tok = call_errorfunc(self.errorfunc, errtoken, self) | |
896 if self.errorok: | |
897 # User must have done some kind of panic | |
898 # mode recovery on their own. The | |
899 # returned token is the next lookahead | |
900 lookahead = tok | |
901 errtoken = None | |
902 continue | |
903 else: | |
904 if errtoken: | |
905 if hasattr(errtoken, 'lineno'): | |
906 lineno = lookahead.lineno | |
907 else: | |
908 lineno = 0 | |
909 if lineno: | |
910 sys.stderr.write('yacc: Syntax error at line %d, token=%s\n' % (lineno, errtoken.type)) | |
911 else: | |
912 sys.stderr.write('yacc: Syntax error, token=%s' % errtoken.type) | |
913 else: | |
914 sys.stderr.write('yacc: Parse error in input. EOF\n') | |
915 return | |
916 | |
917 else: | |
918 errorcount = error_count | |
919 | |
920 # case 1: the statestack only has 1 entry on it. If we're in this state, the | |
921 # entire parse has been rolled back and we're completely hosed. The token is | |
922 # discarded and we just keep going. | |
923 | |
924 if len(statestack) <= 1 and lookahead.type != '$end': | |
925 lookahead = None | |
926 errtoken = None | |
927 state = 0 | |
928 # Nuke the pushback stack | |
929 del lookaheadstack[:] | |
930 continue | |
931 | |
932 # case 2: the statestack has a couple of entries on it, but we're | |
933 # at the end of the file. nuke the top entry and generate an error token | |
934 | |
935 # Start nuking entries on the stack | |
936 if lookahead.type == '$end': | |
937 # Whoa. We're really hosed here. Bail out | |
938 return | |
939 | |
940 if lookahead.type != 'error': | |
941 sym = symstack[-1] | |
942 if sym.type == 'error': | |
943 # Hmmm. Error is on top of stack, we'll just nuke input | |
944 # symbol and continue | |
945 #--! TRACKING | |
946 if tracking: | |
947 sym.endlineno = getattr(lookahead, 'lineno', sym.lineno) | |
948 sym.endlexpos = getattr(lookahead, 'lexpos', sym.lexpos) | |
949 #--! TRACKING | |
950 lookahead = None | |
951 continue | |
952 | |
953 # Create the error symbol for the first time and make it the new lookahead symbol | |
954 t = YaccSymbol() | |
955 t.type = 'error' | |
956 | |
957 if hasattr(lookahead, 'lineno'): | |
958 t.lineno = t.endlineno = lookahead.lineno | |
959 if hasattr(lookahead, 'lexpos'): | |
960 t.lexpos = t.endlexpos = lookahead.lexpos | |
961 t.value = lookahead | |
962 lookaheadstack.append(lookahead) | |
963 lookahead = t | |
964 else: | |
965 sym = symstack.pop() | |
966 #--! TRACKING | |
967 if tracking: | |
968 lookahead.lineno = sym.lineno | |
969 lookahead.lexpos = sym.lexpos | |
970 #--! TRACKING | |
971 statestack.pop() | |
972 state = statestack[-1] | |
973 | |
974 continue | |
975 | |
976 # Call an error function here | |
977 raise RuntimeError('yacc: internal parser error!!!\n') | |
978 | |
979 #--! parseopt-end | |
980 | |
981 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
982 # parseopt_notrack(). | |
983 # | |
984 # Optimized version of parseopt() with line number tracking removed. | |
985 # DO NOT EDIT THIS CODE DIRECTLY. This code is automatically generated | |
986 # by the ply/ygen.py script. Make changes to the parsedebug() method instead. | |
987 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
988 | |
989 def parseopt_notrack(self, input=None, lexer=None, debug=False, tracking=False, tokenfunc=None): | |
990 #--! parseopt-notrack-start | |
991 lookahead = None # Current lookahead symbol | |
992 lookaheadstack = [] # Stack of lookahead symbols | |
993 actions = self.action # Local reference to action table (to avoid lookup on self.) | |
994 goto = self.goto # Local reference to goto table (to avoid lookup on self.) | |
995 prod = self.productions # Local reference to production list (to avoid lookup on self.) | |
996 defaulted_states = self.defaulted_states # Local reference to defaulted states | |
997 pslice = YaccProduction(None) # Production object passed to grammar rules | |
998 errorcount = 0 # Used during error recovery | |
999 | |
1000 | |
1001 # If no lexer was given, we will try to use the lex module | |
1002 if not lexer: | |
1003 from . import lex | |
1004 lexer = lex.lexer | |
1005 | |
1006 # Set up the lexer and parser objects on pslice | |
1007 pslice.lexer = lexer | |
1008 pslice.parser = self | |
1009 | |
1010 # If input was supplied, pass to lexer | |
1011 if input is not None: | |
1012 lexer.input(input) | |
1013 | |
1014 if tokenfunc is None: | |
1015 # Tokenize function | |
1016 get_token = lexer.token | |
1017 else: | |
1018 get_token = tokenfunc | |
1019 | |
1020 # Set the parser() token method (sometimes used in error recovery) | |
1021 self.token = get_token | |
1022 | |
1023 # Set up the state and symbol stacks | |
1024 | |
1025 statestack = [] # Stack of parsing states | |
1026 self.statestack = statestack | |
1027 symstack = [] # Stack of grammar symbols | |
1028 self.symstack = symstack | |
1029 | |
1030 pslice.stack = symstack # Put in the production | |
1031 errtoken = None # Err token | |
1032 | |
1033 # The start state is assumed to be (0,$end) | |
1034 | |
1035 statestack.append(0) | |
1036 sym = YaccSymbol() | |
1037 sym.type = '$end' | |
1038 symstack.append(sym) | |
1039 state = 0 | |
1040 while True: | |
1041 # Get the next symbol on the input. If a lookahead symbol | |
1042 # is already set, we just use that. Otherwise, we'll pull | |
1043 # the next token off of the lookaheadstack or from the lexer | |
1044 | |
1045 | |
1046 if state not in defaulted_states: | |
1047 if not lookahead: | |
1048 if not lookaheadstack: | |
1049 lookahead = get_token() # Get the next token | |
1050 else: | |
1051 lookahead = lookaheadstack.pop() | |
1052 if not lookahead: | |
1053 lookahead = YaccSymbol() | |
1054 lookahead.type = '$end' | |
1055 | |
1056 # Check the action table | |
1057 ltype = lookahead.type | |
1058 t = actions[state].get(ltype) | |
1059 else: | |
1060 t = defaulted_states[state] | |
1061 | |
1062 | |
1063 if t is not None: | |
1064 if t > 0: | |
1065 # shift a symbol on the stack | |
1066 statestack.append(t) | |
1067 state = t | |
1068 | |
1069 | |
1070 symstack.append(lookahead) | |
1071 lookahead = None | |
1072 | |
1073 # Decrease error count on successful shift | |
1074 if errorcount: | |
1075 errorcount -= 1 | |
1076 continue | |
1077 | |
1078 if t < 0: | |
1079 # reduce a symbol on the stack, emit a production | |
1080 p = prod[-t] | |
1081 pname = p.name | |
1082 plen = p.len | |
1083 | |
1084 # Get production function | |
1085 sym = YaccSymbol() | |
1086 sym.type = pname # Production name | |
1087 sym.value = None | |
1088 | |
1089 | |
1090 if plen: | |
1091 targ = symstack[-plen-1:] | |
1092 targ[0] = sym | |
1093 | |
1094 | |
1095 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
1096 # The code enclosed in this section is duplicated | |
1097 # below as a performance optimization. Make sure | |
1098 # changes get made in both locations. | |
1099 | |
1100 pslice.slice = targ | |
1101 | |
1102 try: | |
1103 # Call the grammar rule with our special slice object | |
1104 del symstack[-plen:] | |
1105 del statestack[-plen:] | |
1106 p.callable(pslice) | |
1107 symstack.append(sym) | |
1108 state = goto[statestack[-1]][pname] | |
1109 statestack.append(state) | |
1110 except SyntaxError: | |
1111 # If an error was set. Enter error recovery state | |
1112 lookaheadstack.append(lookahead) | |
1113 symstack.pop() | |
1114 statestack.pop() | |
1115 state = statestack[-1] | |
1116 sym.type = 'error' | |
1117 lookahead = sym | |
1118 errorcount = error_count | |
1119 self.errorok = False | |
1120 continue | |
1121 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
1122 | |
1123 else: | |
1124 | |
1125 | |
1126 targ = [sym] | |
1127 | |
1128 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
1129 # The code enclosed in this section is duplicated | |
1130 # above as a performance optimization. Make sure | |
1131 # changes get made in both locations. | |
1132 | |
1133 pslice.slice = targ | |
1134 | |
1135 try: | |
1136 # Call the grammar rule with our special slice object | |
1137 p.callable(pslice) | |
1138 symstack.append(sym) | |
1139 state = goto[statestack[-1]][pname] | |
1140 statestack.append(state) | |
1141 except SyntaxError: | |
1142 # If an error was set. Enter error recovery state | |
1143 lookaheadstack.append(lookahead) | |
1144 symstack.pop() | |
1145 statestack.pop() | |
1146 state = statestack[-1] | |
1147 sym.type = 'error' | |
1148 lookahead = sym | |
1149 errorcount = error_count | |
1150 self.errorok = False | |
1151 continue | |
1152 # !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | |
1153 | |
1154 if t == 0: | |
1155 n = symstack[-1] | |
1156 result = getattr(n, 'value', None) | |
1157 return result | |
1158 | |
1159 if t is None: | |
1160 | |
1161 | |
1162 # We have some kind of parsing error here. To handle | |
1163 # this, we are going to push the current token onto | |
1164 # the tokenstack and replace it with an 'error' token. | |
1165 # If there are any synchronization rules, they may | |
1166 # catch it. | |
1167 # | |
1168 # In addition to pushing the error token, we call call | |
1169 # the user defined p_error() function if this is the | |
1170 # first syntax error. This function is only called if | |
1171 # errorcount == 0. | |
1172 if errorcount == 0 or self.errorok: | |
1173 errorcount = error_count | |
1174 self.errorok = False | |
1175 errtoken = lookahead | |
1176 if errtoken.type == '$end': | |
1177 errtoken = None # End of file! | |
1178 if self.errorfunc: | |
1179 if errtoken and not hasattr(errtoken, 'lexer'): | |
1180 errtoken.lexer = lexer | |
1181 tok = call_errorfunc(self.errorfunc, errtoken, self) | |
1182 if self.errorok: | |
1183 # User must have done some kind of panic | |
1184 # mode recovery on their own. The | |
1185 # returned token is the next lookahead | |
1186 lookahead = tok | |
1187 errtoken = None | |
1188 continue | |
1189 else: | |
1190 if errtoken: | |
1191 if hasattr(errtoken, 'lineno'): | |
1192 lineno = lookahead.lineno | |
1193 else: | |
1194 lineno = 0 | |
1195 if lineno: | |
1196 sys.stderr.write('yacc: Syntax error at line %d, token=%s\n' % (lineno, errtoken.type)) | |
1197 else: | |
1198 sys.stderr.write('yacc: Syntax error, token=%s' % errtoken.type) | |
1199 else: | |
1200 sys.stderr.write('yacc: Parse error in input. EOF\n') | |
1201 return | |
1202 | |
1203 else: | |
1204 errorcount = error_count | |
1205 | |
1206 # case 1: the statestack only has 1 entry on it. If we're in this state, the | |
1207 # entire parse has been rolled back and we're completely hosed. The token is | |
1208 # discarded and we just keep going. | |
1209 | |
1210 if len(statestack) <= 1 and lookahead.type != '$end': | |
1211 lookahead = None | |
1212 errtoken = None | |
1213 state = 0 | |
1214 # Nuke the pushback stack | |
1215 del lookaheadstack[:] | |
1216 continue | |
1217 | |
1218 # case 2: the statestack has a couple of entries on it, but we're | |
1219 # at the end of the file. nuke the top entry and generate an error token | |
1220 | |
1221 # Start nuking entries on the stack | |
1222 if lookahead.type == '$end': | |
1223 # Whoa. We're really hosed here. Bail out | |
1224 return | |
1225 | |
1226 if lookahead.type != 'error': | |
1227 sym = symstack[-1] | |
1228 if sym.type == 'error': | |
1229 # Hmmm. Error is on top of stack, we'll just nuke input | |
1230 # symbol and continue | |
1231 lookahead = None | |
1232 continue | |
1233 | |
1234 # Create the error symbol for the first time and make it the new lookahead symbol | |
1235 t = YaccSymbol() | |
1236 t.type = 'error' | |
1237 | |
1238 if hasattr(lookahead, 'lineno'): | |
1239 t.lineno = t.endlineno = lookahead.lineno | |
1240 if hasattr(lookahead, 'lexpos'): | |
1241 t.lexpos = t.endlexpos = lookahead.lexpos | |
1242 t.value = lookahead | |
1243 lookaheadstack.append(lookahead) | |
1244 lookahead = t | |
1245 else: | |
1246 sym = symstack.pop() | |
1247 statestack.pop() | |
1248 state = statestack[-1] | |
1249 | |
1250 continue | |
1251 | |
1252 # Call an error function here | |
1253 raise RuntimeError('yacc: internal parser error!!!\n') | |
1254 | |
1255 #--! parseopt-notrack-end | |
1256 | |
1257 # ----------------------------------------------------------------------------- | |
1258 # === Grammar Representation === | |
1259 # | |
1260 # The following functions, classes, and variables are used to represent and | |
1261 # manipulate the rules that make up a grammar. | |
1262 # ----------------------------------------------------------------------------- | |
1263 | |
1264 # regex matching identifiers | |
1265 _is_identifier = re.compile(r'^[a-zA-Z0-9_-]+$') | |
1266 | |
1267 # ----------------------------------------------------------------------------- | |
1268 # class Production: | |
1269 # | |
1270 # This class stores the raw information about a single production or grammar rule. | |
1271 # A grammar rule refers to a specification such as this: | |
1272 # | |
1273 # expr : expr PLUS term | |
1274 # | |
1275 # Here are the basic attributes defined on all productions | |
1276 # | |
1277 # name - Name of the production. For example 'expr' | |
1278 # prod - A list of symbols on the right side ['expr','PLUS','term'] | |
1279 # prec - Production precedence level | |
1280 # number - Production number. | |
1281 # func - Function that executes on reduce | |
1282 # file - File where production function is defined | |
1283 # lineno - Line number where production function is defined | |
1284 # | |
1285 # The following attributes are defined or optional. | |
1286 # | |
1287 # len - Length of the production (number of symbols on right hand side) | |
1288 # usyms - Set of unique symbols found in the production | |
1289 # ----------------------------------------------------------------------------- | |
1290 | |
1291 class Production(object): | |
1292 reduced = 0 | |
1293 def __init__(self, number, name, prod, precedence=('right', 0), func=None, file='', line=0): | |
1294 self.name = name | |
1295 self.prod = tuple(prod) | |
1296 self.number = number | |
1297 self.func = func | |
1298 self.callable = None | |
1299 self.file = file | |
1300 self.line = line | |
1301 self.prec = precedence | |
1302 | |
1303 # Internal settings used during table construction | |
1304 | |
1305 self.len = len(self.prod) # Length of the production | |
1306 | |
1307 # Create a list of unique production symbols used in the production | |
1308 self.usyms = [] | |
1309 for s in self.prod: | |
1310 if s not in self.usyms: | |
1311 self.usyms.append(s) | |
1312 | |
1313 # List of all LR items for the production | |
1314 self.lr_items = [] | |
1315 self.lr_next = None | |
1316 | |
1317 # Create a string representation | |
1318 if self.prod: | |
1319 self.str = '%s -> %s' % (self.name, ' '.join(self.prod)) | |
1320 else: | |
1321 self.str = '%s -> <empty>' % self.name | |
1322 | |
1323 def __str__(self): | |
1324 return self.str | |
1325 | |
1326 def __repr__(self): | |
1327 return 'Production(' + str(self) + ')' | |
1328 | |
1329 def __len__(self): | |
1330 return len(self.prod) | |
1331 | |
1332 def __nonzero__(self): | |
1333 return 1 | |
1334 | |
1335 def __getitem__(self, index): | |
1336 return self.prod[index] | |
1337 | |
1338 # Return the nth lr_item from the production (or None if at the end) | |
1339 def lr_item(self, n): | |
1340 if n > len(self.prod): | |
1341 return None | |
1342 p = LRItem(self, n) | |
1343 # Precompute the list of productions immediately following. | |
1344 try: | |
1345 p.lr_after = Prodnames[p.prod[n+1]] | |
1346 except (IndexError, KeyError): | |
1347 p.lr_after = [] | |
1348 try: | |
1349 p.lr_before = p.prod[n-1] | |
1350 except IndexError: | |
1351 p.lr_before = None | |
1352 return p | |
1353 | |
1354 # Bind the production function name to a callable | |
1355 def bind(self, pdict): | |
1356 if self.func: | |
1357 self.callable = pdict[self.func] | |
1358 | |
1359 # This class serves as a minimal standin for Production objects when | |
1360 # reading table data from files. It only contains information | |
1361 # actually used by the LR parsing engine, plus some additional | |
1362 # debugging information. | |
1363 class MiniProduction(object): | |
1364 def __init__(self, str, name, len, func, file, line): | |
1365 self.name = name | |
1366 self.len = len | |
1367 self.func = func | |
1368 self.callable = None | |
1369 self.file = file | |
1370 self.line = line | |
1371 self.str = str | |
1372 | |
1373 def __str__(self): | |
1374 return self.str | |
1375 | |
1376 def __repr__(self): | |
1377 return 'MiniProduction(%s)' % self.str | |
1378 | |
1379 # Bind the production function name to a callable | |
1380 def bind(self, pdict): | |
1381 if self.func: | |
1382 self.callable = pdict[self.func] | |
1383 | |
1384 | |
1385 # ----------------------------------------------------------------------------- | |
1386 # class LRItem | |
1387 # | |
1388 # This class represents a specific stage of parsing a production rule. For | |
1389 # example: | |
1390 # | |
1391 # expr : expr . PLUS term | |
1392 # | |
1393 # In the above, the "." represents the current location of the parse. Here | |
1394 # basic attributes: | |
1395 # | |
1396 # name - Name of the production. For example 'expr' | |
1397 # prod - A list of symbols on the right side ['expr','.', 'PLUS','term'] | |
1398 # number - Production number. | |
1399 # | |
1400 # lr_next Next LR item. Example, if we are ' expr -> expr . PLUS term' | |
1401 # then lr_next refers to 'expr -> expr PLUS . term' | |
1402 # lr_index - LR item index (location of the ".") in the prod list. | |
1403 # lookaheads - LALR lookahead symbols for this item | |
1404 # len - Length of the production (number of symbols on right hand side) | |
1405 # lr_after - List of all productions that immediately follow | |
1406 # lr_before - Grammar symbol immediately before | |
1407 # ----------------------------------------------------------------------------- | |
1408 | |
1409 class LRItem(object): | |
1410 def __init__(self, p, n): | |
1411 self.name = p.name | |
1412 self.prod = list(p.prod) | |
1413 self.number = p.number | |
1414 self.lr_index = n | |
1415 self.lookaheads = {} | |
1416 self.prod.insert(n, '.') | |
1417 self.prod = tuple(self.prod) | |
1418 self.len = len(self.prod) | |
1419 self.usyms = p.usyms | |
1420 | |
1421 def __str__(self): | |
1422 if self.prod: | |
1423 s = '%s -> %s' % (self.name, ' '.join(self.prod)) | |
1424 else: | |
1425 s = '%s -> <empty>' % self.name | |
1426 return s | |
1427 | |
1428 def __repr__(self): | |
1429 return 'LRItem(' + str(self) + ')' | |
1430 | |
1431 # ----------------------------------------------------------------------------- | |
1432 # rightmost_terminal() | |
1433 # | |
1434 # Return the rightmost terminal from a list of symbols. Used in add_production() | |
1435 # ----------------------------------------------------------------------------- | |
1436 def rightmost_terminal(symbols, terminals): | |
1437 i = len(symbols) - 1 | |
1438 while i >= 0: | |
1439 if symbols[i] in terminals: | |
1440 return symbols[i] | |
1441 i -= 1 | |
1442 return None | |
1443 | |
1444 # ----------------------------------------------------------------------------- | |
1445 # === GRAMMAR CLASS === | |
1446 # | |
1447 # The following class represents the contents of the specified grammar along | |
1448 # with various computed properties such as first sets, follow sets, LR items, etc. | |
1449 # This data is used for critical parts of the table generation process later. | |
1450 # ----------------------------------------------------------------------------- | |
1451 | |
1452 class GrammarError(YaccError): | |
1453 pass | |
1454 | |
1455 class Grammar(object): | |
1456 def __init__(self, terminals): | |
1457 self.Productions = [None] # A list of all of the productions. The first | |
1458 # entry is always reserved for the purpose of | |
1459 # building an augmented grammar | |
1460 | |
1461 self.Prodnames = {} # A dictionary mapping the names of nonterminals to a list of all | |
1462 # productions of that nonterminal. | |
1463 | |
1464 self.Prodmap = {} # A dictionary that is only used to detect duplicate | |
1465 # productions. | |
1466 | |
1467 self.Terminals = {} # A dictionary mapping the names of terminal symbols to a | |
1468 # list of the rules where they are used. | |
1469 | |
1470 for term in terminals: | |
1471 self.Terminals[term] = [] | |
1472 | |
1473 self.Terminals['error'] = [] | |
1474 | |
1475 self.Nonterminals = {} # A dictionary mapping names of nonterminals to a list | |
1476 # of rule numbers where they are used. | |
1477 | |
1478 self.First = {} # A dictionary of precomputed FIRST(x) symbols | |
1479 | |
1480 self.Follow = {} # A dictionary of precomputed FOLLOW(x) symbols | |
1481 | |
1482 self.Precedence = {} # Precedence rules for each terminal. Contains tuples of the | |
1483 # form ('right',level) or ('nonassoc', level) or ('left',level) | |
1484 | |
1485 self.UsedPrecedence = set() # Precedence rules that were actually used by the grammer. | |
1486 # This is only used to provide error checking and to generate | |
1487 # a warning about unused precedence rules. | |
1488 | |
1489 self.Start = None # Starting symbol for the grammar | |
1490 | |
1491 | |
1492 def __len__(self): | |
1493 return len(self.Productions) | |
1494 | |
1495 def __getitem__(self, index): | |
1496 return self.Productions[index] | |
1497 | |
1498 # ----------------------------------------------------------------------------- | |
1499 # set_precedence() | |
1500 # | |
1501 # Sets the precedence for a given terminal. assoc is the associativity such as | |
1502 # 'left','right', or 'nonassoc'. level is a numeric level. | |
1503 # | |
1504 # ----------------------------------------------------------------------------- | |
1505 | |
1506 def set_precedence(self, term, assoc, level): | |
1507 assert self.Productions == [None], 'Must call set_precedence() before add_production()' | |
1508 if term in self.Precedence: | |
1509 raise GrammarError('Precedence already specified for terminal %r' % term) | |
1510 if assoc not in ['left', 'right', 'nonassoc']: | |
1511 raise GrammarError("Associativity must be one of 'left','right', or 'nonassoc'") | |
1512 self.Precedence[term] = (assoc, level) | |
1513 | |
1514 # ----------------------------------------------------------------------------- | |
1515 # add_production() | |
1516 # | |
1517 # Given an action function, this function assembles a production rule and | |
1518 # computes its precedence level. | |
1519 # | |
1520 # The production rule is supplied as a list of symbols. For example, | |
1521 # a rule such as 'expr : expr PLUS term' has a production name of 'expr' and | |
1522 # symbols ['expr','PLUS','term']. | |
1523 # | |
1524 # Precedence is determined by the precedence of the right-most non-terminal | |
1525 # or the precedence of a terminal specified by %prec. | |
1526 # | |
1527 # A variety of error checks are performed to make sure production symbols | |
1528 # are valid and that %prec is used correctly. | |
1529 # ----------------------------------------------------------------------------- | |
1530 | |
1531 def add_production(self, prodname, syms, func=None, file='', line=0): | |
1532 | |
1533 if prodname in self.Terminals: | |
1534 raise GrammarError('%s:%d: Illegal rule name %r. Already defined as a token' % (file, line, prodname)) | |
1535 if prodname == 'error': | |
1536 raise GrammarError('%s:%d: Illegal rule name %r. error is a reserved word' % (file, line, prodname)) | |
1537 if not _is_identifier.match(prodname): | |
1538 raise GrammarError('%s:%d: Illegal rule name %r' % (file, line, prodname)) | |
1539 | |
1540 # Look for literal tokens | |
1541 for n, s in enumerate(syms): | |
1542 if s[0] in "'\"": | |
1543 try: | |
1544 c = eval(s) | |
1545 if (len(c) > 1): | |
1546 raise GrammarError('%s:%d: Literal token %s in rule %r may only be a single character' % | |
1547 (file, line, s, prodname)) | |
1548 if c not in self.Terminals: | |
1549 self.Terminals[c] = [] | |
1550 syms[n] = c | |
1551 continue | |
1552 except SyntaxError: | |
1553 pass | |
1554 if not _is_identifier.match(s) and s != '%prec': | |
1555 raise GrammarError('%s:%d: Illegal name %r in rule %r' % (file, line, s, prodname)) | |
1556 | |
1557 # Determine the precedence level | |
1558 if '%prec' in syms: | |
1559 if syms[-1] == '%prec': | |
1560 raise GrammarError('%s:%d: Syntax error. Nothing follows %%prec' % (file, line)) | |
1561 if syms[-2] != '%prec': | |
1562 raise GrammarError('%s:%d: Syntax error. %%prec can only appear at the end of a grammar rule' % | |
1563 (file, line)) | |
1564 precname = syms[-1] | |
1565 prodprec = self.Precedence.get(precname) | |
1566 if not prodprec: | |
1567 raise GrammarError('%s:%d: Nothing known about the precedence of %r' % (file, line, precname)) | |
1568 else: | |
1569 self.UsedPrecedence.add(precname) | |
1570 del syms[-2:] # Drop %prec from the rule | |
1571 else: | |
1572 # If no %prec, precedence is determined by the rightmost terminal symbol | |
1573 precname = rightmost_terminal(syms, self.Terminals) | |
1574 prodprec = self.Precedence.get(precname, ('right', 0)) | |
1575 | |
1576 # See if the rule is already in the rulemap | |
1577 map = '%s -> %s' % (prodname, syms) | |
1578 if map in self.Prodmap: | |
1579 m = self.Prodmap[map] | |
1580 raise GrammarError('%s:%d: Duplicate rule %s. ' % (file, line, m) + | |
1581 'Previous definition at %s:%d' % (m.file, m.line)) | |
1582 | |
1583 # From this point on, everything is valid. Create a new Production instance | |
1584 pnumber = len(self.Productions) | |
1585 if prodname not in self.Nonterminals: | |
1586 self.Nonterminals[prodname] = [] | |
1587 | |
1588 # Add the production number to Terminals and Nonterminals | |
1589 for t in syms: | |
1590 if t in self.Terminals: | |
1591 self.Terminals[t].append(pnumber) | |
1592 else: | |
1593 if t not in self.Nonterminals: | |
1594 self.Nonterminals[t] = [] | |
1595 self.Nonterminals[t].append(pnumber) | |
1596 | |
1597 # Create a production and add it to the list of productions | |
1598 p = Production(pnumber, prodname, syms, prodprec, func, file, line) | |
1599 self.Productions.append(p) | |
1600 self.Prodmap[map] = p | |
1601 | |
1602 # Add to the global productions list | |
1603 try: | |
1604 self.Prodnames[prodname].append(p) | |
1605 except KeyError: | |
1606 self.Prodnames[prodname] = [p] | |
1607 | |
1608 # ----------------------------------------------------------------------------- | |
1609 # set_start() | |
1610 # | |
1611 # Sets the starting symbol and creates the augmented grammar. Production | |
1612 # rule 0 is S' -> start where start is the start symbol. | |
1613 # ----------------------------------------------------------------------------- | |
1614 | |
1615 def set_start(self, start=None): | |
1616 if not start: | |
1617 start = self.Productions[1].name | |
1618 if start not in self.Nonterminals: | |
1619 raise GrammarError('start symbol %s undefined' % start) | |
1620 self.Productions[0] = Production(0, "S'", [start]) | |
1621 self.Nonterminals[start].append(0) | |
1622 self.Start = start | |
1623 | |
1624 # ----------------------------------------------------------------------------- | |
1625 # find_unreachable() | |
1626 # | |
1627 # Find all of the nonterminal symbols that can't be reached from the starting | |
1628 # symbol. Returns a list of nonterminals that can't be reached. | |
1629 # ----------------------------------------------------------------------------- | |
1630 | |
1631 def find_unreachable(self): | |
1632 | |
1633 # Mark all symbols that are reachable from a symbol s | |
1634 def mark_reachable_from(s): | |
1635 if s in reachable: | |
1636 return | |
1637 reachable.add(s) | |
1638 for p in self.Prodnames.get(s, []): | |
1639 for r in p.prod: | |
1640 mark_reachable_from(r) | |
1641 | |
1642 reachable = set() | |
1643 mark_reachable_from(self.Productions[0].prod[0]) | |
1644 return [s for s in self.Nonterminals if s not in reachable] | |
1645 | |
1646 # ----------------------------------------------------------------------------- | |
1647 # infinite_cycles() | |
1648 # | |
1649 # This function looks at the various parsing rules and tries to detect | |
1650 # infinite recursion cycles (grammar rules where there is no possible way | |
1651 # to derive a string of only terminals). | |
1652 # ----------------------------------------------------------------------------- | |
1653 | |
1654 def infinite_cycles(self): | |
1655 terminates = {} | |
1656 | |
1657 # Terminals: | |
1658 for t in self.Terminals: | |
1659 terminates[t] = True | |
1660 | |
1661 terminates['$end'] = True | |
1662 | |
1663 # Nonterminals: | |
1664 | |
1665 # Initialize to false: | |
1666 for n in self.Nonterminals: | |
1667 terminates[n] = False | |
1668 | |
1669 # Then propagate termination until no change: | |
1670 while True: | |
1671 some_change = False | |
1672 for (n, pl) in self.Prodnames.items(): | |
1673 # Nonterminal n terminates iff any of its productions terminates. | |
1674 for p in pl: | |
1675 # Production p terminates iff all of its rhs symbols terminate. | |
1676 for s in p.prod: | |
1677 if not terminates[s]: | |
1678 # The symbol s does not terminate, | |
1679 # so production p does not terminate. | |
1680 p_terminates = False | |
1681 break | |
1682 else: | |
1683 # didn't break from the loop, | |
1684 # so every symbol s terminates | |
1685 # so production p terminates. | |
1686 p_terminates = True | |
1687 | |
1688 if p_terminates: | |
1689 # symbol n terminates! | |
1690 if not terminates[n]: | |
1691 terminates[n] = True | |
1692 some_change = True | |
1693 # Don't need to consider any more productions for this n. | |
1694 break | |
1695 | |
1696 if not some_change: | |
1697 break | |
1698 | |
1699 infinite = [] | |
1700 for (s, term) in terminates.items(): | |
1701 if not term: | |
1702 if s not in self.Prodnames and s not in self.Terminals and s != 'error': | |
1703 # s is used-but-not-defined, and we've already warned of that, | |
1704 # so it would be overkill to say that it's also non-terminating. | |
1705 pass | |
1706 else: | |
1707 infinite.append(s) | |
1708 | |
1709 return infinite | |
1710 | |
1711 # ----------------------------------------------------------------------------- | |
1712 # undefined_symbols() | |
1713 # | |
1714 # Find all symbols that were used the grammar, but not defined as tokens or | |
1715 # grammar rules. Returns a list of tuples (sym, prod) where sym in the symbol | |
1716 # and prod is the production where the symbol was used. | |
1717 # ----------------------------------------------------------------------------- | |
1718 def undefined_symbols(self): | |
1719 result = [] | |
1720 for p in self.Productions: | |
1721 if not p: | |
1722 continue | |
1723 | |
1724 for s in p.prod: | |
1725 if s not in self.Prodnames and s not in self.Terminals and s != 'error': | |
1726 result.append((s, p)) | |
1727 return result | |
1728 | |
1729 # ----------------------------------------------------------------------------- | |
1730 # unused_terminals() | |
1731 # | |
1732 # Find all terminals that were defined, but not used by the grammar. Returns | |
1733 # a list of all symbols. | |
1734 # ----------------------------------------------------------------------------- | |
1735 def unused_terminals(self): | |
1736 unused_tok = [] | |
1737 for s, v in self.Terminals.items(): | |
1738 if s != 'error' and not v: | |
1739 unused_tok.append(s) | |
1740 | |
1741 return unused_tok | |
1742 | |
1743 # ------------------------------------------------------------------------------ | |
1744 # unused_rules() | |
1745 # | |
1746 # Find all grammar rules that were defined, but not used (maybe not reachable) | |
1747 # Returns a list of productions. | |
1748 # ------------------------------------------------------------------------------ | |
1749 | |
1750 def unused_rules(self): | |
1751 unused_prod = [] | |
1752 for s, v in self.Nonterminals.items(): | |
1753 if not v: | |
1754 p = self.Prodnames[s][0] | |
1755 unused_prod.append(p) | |
1756 return unused_prod | |
1757 | |
1758 # ----------------------------------------------------------------------------- | |
1759 # unused_precedence() | |
1760 # | |
1761 # Returns a list of tuples (term,precedence) corresponding to precedence | |
1762 # rules that were never used by the grammar. term is the name of the terminal | |
1763 # on which precedence was applied and precedence is a string such as 'left' or | |
1764 # 'right' corresponding to the type of precedence. | |
1765 # ----------------------------------------------------------------------------- | |
1766 | |
1767 def unused_precedence(self): | |
1768 unused = [] | |
1769 for termname in self.Precedence: | |
1770 if not (termname in self.Terminals or termname in self.UsedPrecedence): | |
1771 unused.append((termname, self.Precedence[termname][0])) | |
1772 | |
1773 return unused | |
1774 | |
1775 # ------------------------------------------------------------------------- | |
1776 # _first() | |
1777 # | |
1778 # Compute the value of FIRST1(beta) where beta is a tuple of symbols. | |
1779 # | |
1780 # During execution of compute_first1, the result may be incomplete. | |
1781 # Afterward (e.g., when called from compute_follow()), it will be complete. | |
1782 # ------------------------------------------------------------------------- | |
1783 def _first(self, beta): | |
1784 | |
1785 # We are computing First(x1,x2,x3,...,xn) | |
1786 result = [] | |
1787 for x in beta: | |
1788 x_produces_empty = False | |
1789 | |
1790 # Add all the non-<empty> symbols of First[x] to the result. | |
1791 for f in self.First[x]: | |
1792 if f == '<empty>': | |
1793 x_produces_empty = True | |
1794 else: | |
1795 if f not in result: | |
1796 result.append(f) | |
1797 | |
1798 if x_produces_empty: | |
1799 # We have to consider the next x in beta, | |
1800 # i.e. stay in the loop. | |
1801 pass | |
1802 else: | |
1803 # We don't have to consider any further symbols in beta. | |
1804 break | |
1805 else: | |
1806 # There was no 'break' from the loop, | |
1807 # so x_produces_empty was true for all x in beta, | |
1808 # so beta produces empty as well. | |
1809 result.append('<empty>') | |
1810 | |
1811 return result | |
1812 | |
1813 # ------------------------------------------------------------------------- | |
1814 # compute_first() | |
1815 # | |
1816 # Compute the value of FIRST1(X) for all symbols | |
1817 # ------------------------------------------------------------------------- | |
1818 def compute_first(self): | |
1819 if self.First: | |
1820 return self.First | |
1821 | |
1822 # Terminals: | |
1823 for t in self.Terminals: | |
1824 self.First[t] = [t] | |
1825 | |
1826 self.First['$end'] = ['$end'] | |
1827 | |
1828 # Nonterminals: | |
1829 | |
1830 # Initialize to the empty set: | |
1831 for n in self.Nonterminals: | |
1832 self.First[n] = [] | |
1833 | |
1834 # Then propagate symbols until no change: | |
1835 while True: | |
1836 some_change = False | |
1837 for n in self.Nonterminals: | |
1838 for p in self.Prodnames[n]: | |
1839 for f in self._first(p.prod): | |
1840 if f not in self.First[n]: | |
1841 self.First[n].append(f) | |
1842 some_change = True | |
1843 if not some_change: | |
1844 break | |
1845 | |
1846 return self.First | |
1847 | |
1848 # --------------------------------------------------------------------- | |
1849 # compute_follow() | |
1850 # | |
1851 # Computes all of the follow sets for every non-terminal symbol. The | |
1852 # follow set is the set of all symbols that might follow a given | |
1853 # non-terminal. See the Dragon book, 2nd Ed. p. 189. | |
1854 # --------------------------------------------------------------------- | |
1855 def compute_follow(self, start=None): | |
1856 # If already computed, return the result | |
1857 if self.Follow: | |
1858 return self.Follow | |
1859 | |
1860 # If first sets not computed yet, do that first. | |
1861 if not self.First: | |
1862 self.compute_first() | |
1863 | |
1864 # Add '$end' to the follow list of the start symbol | |
1865 for k in self.Nonterminals: | |
1866 self.Follow[k] = [] | |
1867 | |
1868 if not start: | |
1869 start = self.Productions[1].name | |
1870 | |
1871 self.Follow[start] = ['$end'] | |
1872 | |
1873 while True: | |
1874 didadd = False | |
1875 for p in self.Productions[1:]: | |
1876 # Here is the production set | |
1877 for i, B in enumerate(p.prod): | |
1878 if B in self.Nonterminals: | |
1879 # Okay. We got a non-terminal in a production | |
1880 fst = self._first(p.prod[i+1:]) | |
1881 hasempty = False | |
1882 for f in fst: | |
1883 if f != '<empty>' and f not in self.Follow[B]: | |
1884 self.Follow[B].append(f) | |
1885 didadd = True | |
1886 if f == '<empty>': | |
1887 hasempty = True | |
1888 if hasempty or i == (len(p.prod)-1): | |
1889 # Add elements of follow(a) to follow(b) | |
1890 for f in self.Follow[p.name]: | |
1891 if f not in self.Follow[B]: | |
1892 self.Follow[B].append(f) | |
1893 didadd = True | |
1894 if not didadd: | |
1895 break | |
1896 return self.Follow | |
1897 | |
1898 | |
1899 # ----------------------------------------------------------------------------- | |
1900 # build_lritems() | |
1901 # | |
1902 # This function walks the list of productions and builds a complete set of the | |
1903 # LR items. The LR items are stored in two ways: First, they are uniquely | |
1904 # numbered and placed in the list _lritems. Second, a linked list of LR items | |
1905 # is built for each production. For example: | |
1906 # | |
1907 # E -> E PLUS E | |
1908 # | |
1909 # Creates the list | |
1910 # | |
1911 # [E -> . E PLUS E, E -> E . PLUS E, E -> E PLUS . E, E -> E PLUS E . ] | |
1912 # ----------------------------------------------------------------------------- | |
1913 | |
1914 def build_lritems(self): | |
1915 for p in self.Productions: | |
1916 lastlri = p | |
1917 i = 0 | |
1918 lr_items = [] | |
1919 while True: | |
1920 if i > len(p): | |
1921 lri = None | |
1922 else: | |
1923 lri = LRItem(p, i) | |
1924 # Precompute the list of productions immediately following | |
1925 try: | |
1926 lri.lr_after = self.Prodnames[lri.prod[i+1]] | |
1927 except (IndexError, KeyError): | |
1928 lri.lr_after = [] | |
1929 try: | |
1930 lri.lr_before = lri.prod[i-1] | |
1931 except IndexError: | |
1932 lri.lr_before = None | |
1933 | |
1934 lastlri.lr_next = lri | |
1935 if not lri: | |
1936 break | |
1937 lr_items.append(lri) | |
1938 lastlri = lri | |
1939 i += 1 | |
1940 p.lr_items = lr_items | |
1941 | |
1942 # ----------------------------------------------------------------------------- | |
1943 # == Class LRTable == | |
1944 # | |
1945 # This basic class represents a basic table of LR parsing information. | |
1946 # Methods for generating the tables are not defined here. They are defined | |
1947 # in the derived class LRGeneratedTable. | |
1948 # ----------------------------------------------------------------------------- | |
1949 | |
1950 class VersionError(YaccError): | |
1951 pass | |
1952 | |
1953 class LRTable(object): | |
1954 def __init__(self): | |
1955 self.lr_action = None | |
1956 self.lr_goto = None | |
1957 self.lr_productions = None | |
1958 self.lr_method = None | |
1959 | |
1960 def read_table(self, module): | |
1961 if isinstance(module, types.ModuleType): | |
1962 parsetab = module | |
1963 else: | |
1964 exec('import %s' % module) | |
1965 parsetab = sys.modules[module] | |
1966 | |
1967 if parsetab._tabversion != __tabversion__: | |
1968 raise VersionError('yacc table file version is out of date') | |
1969 | |
1970 self.lr_action = parsetab._lr_action | |
1971 self.lr_goto = parsetab._lr_goto | |
1972 | |
1973 self.lr_productions = [] | |
1974 for p in parsetab._lr_productions: | |
1975 self.lr_productions.append(MiniProduction(*p)) | |
1976 | |
1977 self.lr_method = parsetab._lr_method | |
1978 return parsetab._lr_signature | |
1979 | |
1980 def read_pickle(self, filename): | |
1981 try: | |
1982 import cPickle as pickle | |
1983 except ImportError: | |
1984 import pickle | |
1985 | |
1986 if not os.path.exists(filename): | |
1987 raise ImportError | |
1988 | |
1989 in_f = open(filename, 'rb') | |
1990 | |
1991 tabversion = pickle.load(in_f) | |
1992 if tabversion != __tabversion__: | |
1993 raise VersionError('yacc table file version is out of date') | |
1994 self.lr_method = pickle.load(in_f) | |
1995 signature = pickle.load(in_f) | |
1996 self.lr_action = pickle.load(in_f) | |
1997 self.lr_goto = pickle.load(in_f) | |
1998 productions = pickle.load(in_f) | |
1999 | |
2000 self.lr_productions = [] | |
2001 for p in productions: | |
2002 self.lr_productions.append(MiniProduction(*p)) | |
2003 | |
2004 in_f.close() | |
2005 return signature | |
2006 | |
2007 # Bind all production function names to callable objects in pdict | |
2008 def bind_callables(self, pdict): | |
2009 for p in self.lr_productions: | |
2010 p.bind(pdict) | |
2011 | |
2012 | |
2013 # ----------------------------------------------------------------------------- | |
2014 # === LR Generator === | |
2015 # | |
2016 # The following classes and functions are used to generate LR parsing tables on | |
2017 # a grammar. | |
2018 # ----------------------------------------------------------------------------- | |
2019 | |
2020 # ----------------------------------------------------------------------------- | |
2021 # digraph() | |
2022 # traverse() | |
2023 # | |
2024 # The following two functions are used to compute set valued functions | |
2025 # of the form: | |
2026 # | |
2027 # F(x) = F'(x) U U{F(y) | x R y} | |
2028 # | |
2029 # This is used to compute the values of Read() sets as well as FOLLOW sets | |
2030 # in LALR(1) generation. | |
2031 # | |
2032 # Inputs: X - An input set | |
2033 # R - A relation | |
2034 # FP - Set-valued function | |
2035 # ------------------------------------------------------------------------------ | |
2036 | |
2037 def digraph(X, R, FP): | |
2038 N = {} | |
2039 for x in X: | |
2040 N[x] = 0 | |
2041 stack = [] | |
2042 F = {} | |
2043 for x in X: | |
2044 if N[x] == 0: | |
2045 traverse(x, N, stack, F, X, R, FP) | |
2046 return F | |
2047 | |
2048 def traverse(x, N, stack, F, X, R, FP): | |
2049 stack.append(x) | |
2050 d = len(stack) | |
2051 N[x] = d | |
2052 F[x] = FP(x) # F(X) <- F'(x) | |
2053 | |
2054 rel = R(x) # Get y's related to x | |
2055 for y in rel: | |
2056 if N[y] == 0: | |
2057 traverse(y, N, stack, F, X, R, FP) | |
2058 N[x] = min(N[x], N[y]) | |
2059 for a in F.get(y, []): | |
2060 if a not in F[x]: | |
2061 F[x].append(a) | |
2062 if N[x] == d: | |
2063 N[stack[-1]] = MAXINT | |
2064 F[stack[-1]] = F[x] | |
2065 element = stack.pop() | |
2066 while element != x: | |
2067 N[stack[-1]] = MAXINT | |
2068 F[stack[-1]] = F[x] | |
2069 element = stack.pop() | |
2070 | |
2071 class LALRError(YaccError): | |
2072 pass | |
2073 | |
2074 # ----------------------------------------------------------------------------- | |
2075 # == LRGeneratedTable == | |
2076 # | |
2077 # This class implements the LR table generation algorithm. There are no | |
2078 # public methods except for write() | |
2079 # ----------------------------------------------------------------------------- | |
2080 | |
2081 class LRGeneratedTable(LRTable): | |
2082 def __init__(self, grammar, method='LALR', log=None): | |
2083 if method not in ['SLR', 'LALR']: | |
2084 raise LALRError('Unsupported method %s' % method) | |
2085 | |
2086 self.grammar = grammar | |
2087 self.lr_method = method | |
2088 | |
2089 # Set up the logger | |
2090 if not log: | |
2091 log = NullLogger() | |
2092 self.log = log | |
2093 | |
2094 # Internal attributes | |
2095 self.lr_action = {} # Action table | |
2096 self.lr_goto = {} # Goto table | |
2097 self.lr_productions = grammar.Productions # Copy of grammar Production array | |
2098 self.lr_goto_cache = {} # Cache of computed gotos | |
2099 self.lr0_cidhash = {} # Cache of closures | |
2100 | |
2101 self._add_count = 0 # Internal counter used to detect cycles | |
2102 | |
2103 # Diagonistic information filled in by the table generator | |
2104 self.sr_conflict = 0 | |
2105 self.rr_conflict = 0 | |
2106 self.conflicts = [] # List of conflicts | |
2107 | |
2108 self.sr_conflicts = [] | |
2109 self.rr_conflicts = [] | |
2110 | |
2111 # Build the tables | |
2112 self.grammar.build_lritems() | |
2113 self.grammar.compute_first() | |
2114 self.grammar.compute_follow() | |
2115 self.lr_parse_table() | |
2116 | |
2117 # Compute the LR(0) closure operation on I, where I is a set of LR(0) items. | |
2118 | |
2119 def lr0_closure(self, I): | |
2120 self._add_count += 1 | |
2121 | |
2122 # Add everything in I to J | |
2123 J = I[:] | |
2124 didadd = True | |
2125 while didadd: | |
2126 didadd = False | |
2127 for j in J: | |
2128 for x in j.lr_after: | |
2129 if getattr(x, 'lr0_added', 0) == self._add_count: | |
2130 continue | |
2131 # Add B --> .G to J | |
2132 J.append(x.lr_next) | |
2133 x.lr0_added = self._add_count | |
2134 didadd = True | |
2135 | |
2136 return J | |
2137 | |
2138 # Compute the LR(0) goto function goto(I,X) where I is a set | |
2139 # of LR(0) items and X is a grammar symbol. This function is written | |
2140 # in a way that guarantees uniqueness of the generated goto sets | |
2141 # (i.e. the same goto set will never be returned as two different Python | |
2142 # objects). With uniqueness, we can later do fast set comparisons using | |
2143 # id(obj) instead of element-wise comparison. | |
2144 | |
2145 def lr0_goto(self, I, x): | |
2146 # First we look for a previously cached entry | |
2147 g = self.lr_goto_cache.get((id(I), x)) | |
2148 if g: | |
2149 return g | |
2150 | |
2151 # Now we generate the goto set in a way that guarantees uniqueness | |
2152 # of the result | |
2153 | |
2154 s = self.lr_goto_cache.get(x) | |
2155 if not s: | |
2156 s = {} | |
2157 self.lr_goto_cache[x] = s | |
2158 | |
2159 gs = [] | |
2160 for p in I: | |
2161 n = p.lr_next | |
2162 if n and n.lr_before == x: | |
2163 s1 = s.get(id(n)) | |
2164 if not s1: | |
2165 s1 = {} | |
2166 s[id(n)] = s1 | |
2167 gs.append(n) | |
2168 s = s1 | |
2169 g = s.get('$end') | |
2170 if not g: | |
2171 if gs: | |
2172 g = self.lr0_closure(gs) | |
2173 s['$end'] = g | |
2174 else: | |
2175 s['$end'] = gs | |
2176 self.lr_goto_cache[(id(I), x)] = g | |
2177 return g | |
2178 | |
2179 # Compute the LR(0) sets of item function | |
2180 def lr0_items(self): | |
2181 C = [self.lr0_closure([self.grammar.Productions[0].lr_next])] | |
2182 i = 0 | |
2183 for I in C: | |
2184 self.lr0_cidhash[id(I)] = i | |
2185 i += 1 | |
2186 | |
2187 # Loop over the items in C and each grammar symbols | |
2188 i = 0 | |
2189 while i < len(C): | |
2190 I = C[i] | |
2191 i += 1 | |
2192 | |
2193 # Collect all of the symbols that could possibly be in the goto(I,X) sets | |
2194 asyms = {} | |
2195 for ii in I: | |
2196 for s in ii.usyms: | |
2197 asyms[s] = None | |
2198 | |
2199 for x in asyms: | |
2200 g = self.lr0_goto(I, x) | |
2201 if not g or id(g) in self.lr0_cidhash: | |
2202 continue | |
2203 self.lr0_cidhash[id(g)] = len(C) | |
2204 C.append(g) | |
2205 | |
2206 return C | |
2207 | |
2208 # ----------------------------------------------------------------------------- | |
2209 # ==== LALR(1) Parsing ==== | |
2210 # | |
2211 # LALR(1) parsing is almost exactly the same as SLR except that instead of | |
2212 # relying upon Follow() sets when performing reductions, a more selective | |
2213 # lookahead set that incorporates the state of the LR(0) machine is utilized. | |
2214 # Thus, we mainly just have to focus on calculating the lookahead sets. | |
2215 # | |
2216 # The method used here is due to DeRemer and Pennelo (1982). | |
2217 # | |
2218 # DeRemer, F. L., and T. J. Pennelo: "Efficient Computation of LALR(1) | |
2219 # Lookahead Sets", ACM Transactions on Programming Languages and Systems, | |
2220 # Vol. 4, No. 4, Oct. 1982, pp. 615-649 | |
2221 # | |
2222 # Further details can also be found in: | |
2223 # | |
2224 # J. Tremblay and P. Sorenson, "The Theory and Practice of Compiler Writing", | |
2225 # McGraw-Hill Book Company, (1985). | |
2226 # | |
2227 # ----------------------------------------------------------------------------- | |
2228 | |
2229 # ----------------------------------------------------------------------------- | |
2230 # compute_nullable_nonterminals() | |
2231 # | |
2232 # Creates a dictionary containing all of the non-terminals that might produce | |
2233 # an empty production. | |
2234 # ----------------------------------------------------------------------------- | |
2235 | |
2236 def compute_nullable_nonterminals(self): | |
2237 nullable = set() | |
2238 num_nullable = 0 | |
2239 while True: | |
2240 for p in self.grammar.Productions[1:]: | |
2241 if p.len == 0: | |
2242 nullable.add(p.name) | |
2243 continue | |
2244 for t in p.prod: | |
2245 if t not in nullable: | |
2246 break | |
2247 else: | |
2248 nullable.add(p.name) | |
2249 if len(nullable) == num_nullable: | |
2250 break | |
2251 num_nullable = len(nullable) | |
2252 return nullable | |
2253 | |
2254 # ----------------------------------------------------------------------------- | |
2255 # find_nonterminal_trans(C) | |
2256 # | |
2257 # Given a set of LR(0) items, this functions finds all of the non-terminal | |
2258 # transitions. These are transitions in which a dot appears immediately before | |
2259 # a non-terminal. Returns a list of tuples of the form (state,N) where state | |
2260 # is the state number and N is the nonterminal symbol. | |
2261 # | |
2262 # The input C is the set of LR(0) items. | |
2263 # ----------------------------------------------------------------------------- | |
2264 | |
2265 def find_nonterminal_transitions(self, C): | |
2266 trans = [] | |
2267 for stateno, state in enumerate(C): | |
2268 for p in state: | |
2269 if p.lr_index < p.len - 1: | |
2270 t = (stateno, p.prod[p.lr_index+1]) | |
2271 if t[1] in self.grammar.Nonterminals: | |
2272 if t not in trans: | |
2273 trans.append(t) | |
2274 return trans | |
2275 | |
2276 # ----------------------------------------------------------------------------- | |
2277 # dr_relation() | |
2278 # | |
2279 # Computes the DR(p,A) relationships for non-terminal transitions. The input | |
2280 # is a tuple (state,N) where state is a number and N is a nonterminal symbol. | |
2281 # | |
2282 # Returns a list of terminals. | |
2283 # ----------------------------------------------------------------------------- | |
2284 | |
2285 def dr_relation(self, C, trans, nullable): | |
2286 dr_set = {} | |
2287 state, N = trans | |
2288 terms = [] | |
2289 | |
2290 g = self.lr0_goto(C[state], N) | |
2291 for p in g: | |
2292 if p.lr_index < p.len - 1: | |
2293 a = p.prod[p.lr_index+1] | |
2294 if a in self.grammar.Terminals: | |
2295 if a not in terms: | |
2296 terms.append(a) | |
2297 | |
2298 # This extra bit is to handle the start state | |
2299 if state == 0 and N == self.grammar.Productions[0].prod[0]: | |
2300 terms.append('$end') | |
2301 | |
2302 return terms | |
2303 | |
2304 # ----------------------------------------------------------------------------- | |
2305 # reads_relation() | |
2306 # | |
2307 # Computes the READS() relation (p,A) READS (t,C). | |
2308 # ----------------------------------------------------------------------------- | |
2309 | |
2310 def reads_relation(self, C, trans, empty): | |
2311 # Look for empty transitions | |
2312 rel = [] | |
2313 state, N = trans | |
2314 | |
2315 g = self.lr0_goto(C[state], N) | |
2316 j = self.lr0_cidhash.get(id(g), -1) | |
2317 for p in g: | |
2318 if p.lr_index < p.len - 1: | |
2319 a = p.prod[p.lr_index + 1] | |
2320 if a in empty: | |
2321 rel.append((j, a)) | |
2322 | |
2323 return rel | |
2324 | |
2325 # ----------------------------------------------------------------------------- | |
2326 # compute_lookback_includes() | |
2327 # | |
2328 # Determines the lookback and includes relations | |
2329 # | |
2330 # LOOKBACK: | |
2331 # | |
2332 # This relation is determined by running the LR(0) state machine forward. | |
2333 # For example, starting with a production "N : . A B C", we run it forward | |
2334 # to obtain "N : A B C ." We then build a relationship between this final | |
2335 # state and the starting state. These relationships are stored in a dictionary | |
2336 # lookdict. | |
2337 # | |
2338 # INCLUDES: | |
2339 # | |
2340 # Computes the INCLUDE() relation (p,A) INCLUDES (p',B). | |
2341 # | |
2342 # This relation is used to determine non-terminal transitions that occur | |
2343 # inside of other non-terminal transition states. (p,A) INCLUDES (p', B) | |
2344 # if the following holds: | |
2345 # | |
2346 # B -> LAT, where T -> epsilon and p' -L-> p | |
2347 # | |
2348 # L is essentially a prefix (which may be empty), T is a suffix that must be | |
2349 # able to derive an empty string. State p' must lead to state p with the string L. | |
2350 # | |
2351 # ----------------------------------------------------------------------------- | |
2352 | |
2353 def compute_lookback_includes(self, C, trans, nullable): | |
2354 lookdict = {} # Dictionary of lookback relations | |
2355 includedict = {} # Dictionary of include relations | |
2356 | |
2357 # Make a dictionary of non-terminal transitions | |
2358 dtrans = {} | |
2359 for t in trans: | |
2360 dtrans[t] = 1 | |
2361 | |
2362 # Loop over all transitions and compute lookbacks and includes | |
2363 for state, N in trans: | |
2364 lookb = [] | |
2365 includes = [] | |
2366 for p in C[state]: | |
2367 if p.name != N: | |
2368 continue | |
2369 | |
2370 # Okay, we have a name match. We now follow the production all the way | |
2371 # through the state machine until we get the . on the right hand side | |
2372 | |
2373 lr_index = p.lr_index | |
2374 j = state | |
2375 while lr_index < p.len - 1: | |
2376 lr_index = lr_index + 1 | |
2377 t = p.prod[lr_index] | |
2378 | |
2379 # Check to see if this symbol and state are a non-terminal transition | |
2380 if (j, t) in dtrans: | |
2381 # Yes. Okay, there is some chance that this is an includes relation | |
2382 # the only way to know for certain is whether the rest of the | |
2383 # production derives empty | |
2384 | |
2385 li = lr_index + 1 | |
2386 while li < p.len: | |
2387 if p.prod[li] in self.grammar.Terminals: | |
2388 break # No forget it | |
2389 if p.prod[li] not in nullable: | |
2390 break | |
2391 li = li + 1 | |
2392 else: | |
2393 # Appears to be a relation between (j,t) and (state,N) | |
2394 includes.append((j, t)) | |
2395 | |
2396 g = self.lr0_goto(C[j], t) # Go to next set | |
2397 j = self.lr0_cidhash.get(id(g), -1) # Go to next state | |
2398 | |
2399 # When we get here, j is the final state, now we have to locate the production | |
2400 for r in C[j]: | |
2401 if r.name != p.name: | |
2402 continue | |
2403 if r.len != p.len: | |
2404 continue | |
2405 i = 0 | |
2406 # This look is comparing a production ". A B C" with "A B C ." | |
2407 while i < r.lr_index: | |
2408 if r.prod[i] != p.prod[i+1]: | |
2409 break | |
2410 i = i + 1 | |
2411 else: | |
2412 lookb.append((j, r)) | |
2413 for i in includes: | |
2414 if i not in includedict: | |
2415 includedict[i] = [] | |
2416 includedict[i].append((state, N)) | |
2417 lookdict[(state, N)] = lookb | |
2418 | |
2419 return lookdict, includedict | |
2420 | |
2421 # ----------------------------------------------------------------------------- | |
2422 # compute_read_sets() | |
2423 # | |
2424 # Given a set of LR(0) items, this function computes the read sets. | |
2425 # | |
2426 # Inputs: C = Set of LR(0) items | |
2427 # ntrans = Set of nonterminal transitions | |
2428 # nullable = Set of empty transitions | |
2429 # | |
2430 # Returns a set containing the read sets | |
2431 # ----------------------------------------------------------------------------- | |
2432 | |
2433 def compute_read_sets(self, C, ntrans, nullable): | |
2434 FP = lambda x: self.dr_relation(C, x, nullable) | |
2435 R = lambda x: self.reads_relation(C, x, nullable) | |
2436 F = digraph(ntrans, R, FP) | |
2437 return F | |
2438 | |
2439 # ----------------------------------------------------------------------------- | |
2440 # compute_follow_sets() | |
2441 # | |
2442 # Given a set of LR(0) items, a set of non-terminal transitions, a readset, | |
2443 # and an include set, this function computes the follow sets | |
2444 # | |
2445 # Follow(p,A) = Read(p,A) U U {Follow(p',B) | (p,A) INCLUDES (p',B)} | |
2446 # | |
2447 # Inputs: | |
2448 # ntrans = Set of nonterminal transitions | |
2449 # readsets = Readset (previously computed) | |
2450 # inclsets = Include sets (previously computed) | |
2451 # | |
2452 # Returns a set containing the follow sets | |
2453 # ----------------------------------------------------------------------------- | |
2454 | |
2455 def compute_follow_sets(self, ntrans, readsets, inclsets): | |
2456 FP = lambda x: readsets[x] | |
2457 R = lambda x: inclsets.get(x, []) | |
2458 F = digraph(ntrans, R, FP) | |
2459 return F | |
2460 | |
2461 # ----------------------------------------------------------------------------- | |
2462 # add_lookaheads() | |
2463 # | |
2464 # Attaches the lookahead symbols to grammar rules. | |
2465 # | |
2466 # Inputs: lookbacks - Set of lookback relations | |
2467 # followset - Computed follow set | |
2468 # | |
2469 # This function directly attaches the lookaheads to productions contained | |
2470 # in the lookbacks set | |
2471 # ----------------------------------------------------------------------------- | |
2472 | |
2473 def add_lookaheads(self, lookbacks, followset): | |
2474 for trans, lb in lookbacks.items(): | |
2475 # Loop over productions in lookback | |
2476 for state, p in lb: | |
2477 if state not in p.lookaheads: | |
2478 p.lookaheads[state] = [] | |
2479 f = followset.get(trans, []) | |
2480 for a in f: | |
2481 if a not in p.lookaheads[state]: | |
2482 p.lookaheads[state].append(a) | |
2483 | |
2484 # ----------------------------------------------------------------------------- | |
2485 # add_lalr_lookaheads() | |
2486 # | |
2487 # This function does all of the work of adding lookahead information for use | |
2488 # with LALR parsing | |
2489 # ----------------------------------------------------------------------------- | |
2490 | |
2491 def add_lalr_lookaheads(self, C): | |
2492 # Determine all of the nullable nonterminals | |
2493 nullable = self.compute_nullable_nonterminals() | |
2494 | |
2495 # Find all non-terminal transitions | |
2496 trans = self.find_nonterminal_transitions(C) | |
2497 | |
2498 # Compute read sets | |
2499 readsets = self.compute_read_sets(C, trans, nullable) | |
2500 | |
2501 # Compute lookback/includes relations | |
2502 lookd, included = self.compute_lookback_includes(C, trans, nullable) | |
2503 | |
2504 # Compute LALR FOLLOW sets | |
2505 followsets = self.compute_follow_sets(trans, readsets, included) | |
2506 | |
2507 # Add all of the lookaheads | |
2508 self.add_lookaheads(lookd, followsets) | |
2509 | |
2510 # ----------------------------------------------------------------------------- | |
2511 # lr_parse_table() | |
2512 # | |
2513 # This function constructs the parse tables for SLR or LALR | |
2514 # ----------------------------------------------------------------------------- | |
2515 def lr_parse_table(self): | |
2516 Productions = self.grammar.Productions | |
2517 Precedence = self.grammar.Precedence | |
2518 goto = self.lr_goto # Goto array | |
2519 action = self.lr_action # Action array | |
2520 log = self.log # Logger for output | |
2521 | |
2522 actionp = {} # Action production array (temporary) | |
2523 | |
2524 log.info('Parsing method: %s', self.lr_method) | |
2525 | |
2526 # Step 1: Construct C = { I0, I1, ... IN}, collection of LR(0) items | |
2527 # This determines the number of states | |
2528 | |
2529 C = self.lr0_items() | |
2530 | |
2531 if self.lr_method == 'LALR': | |
2532 self.add_lalr_lookaheads(C) | |
2533 | |
2534 # Build the parser table, state by state | |
2535 st = 0 | |
2536 for I in C: | |
2537 # Loop over each production in I | |
2538 actlist = [] # List of actions | |
2539 st_action = {} | |
2540 st_actionp = {} | |
2541 st_goto = {} | |
2542 log.info('') | |
2543 log.info('state %d', st) | |
2544 log.info('') | |
2545 for p in I: | |
2546 log.info(' (%d) %s', p.number, p) | |
2547 log.info('') | |
2548 | |
2549 for p in I: | |
2550 if p.len == p.lr_index + 1: | |
2551 if p.name == "S'": | |
2552 # Start symbol. Accept! | |
2553 st_action['$end'] = 0 | |
2554 st_actionp['$end'] = p | |
2555 else: | |
2556 # We are at the end of a production. Reduce! | |
2557 if self.lr_method == 'LALR': | |
2558 laheads = p.lookaheads[st] | |
2559 else: | |
2560 laheads = self.grammar.Follow[p.name] | |
2561 for a in laheads: | |
2562 actlist.append((a, p, 'reduce using rule %d (%s)' % (p.number, p))) | |
2563 r = st_action.get(a) | |
2564 if r is not None: | |
2565 # Whoa. Have a shift/reduce or reduce/reduce conflict | |
2566 if r > 0: | |
2567 # Need to decide on shift or reduce here | |
2568 # By default we favor shifting. Need to add | |
2569 # some precedence rules here. | |
2570 sprec, slevel = Productions[st_actionp[a].number].prec | |
2571 rprec, rlevel = Precedence.get(a, ('right', 0)) | |
2572 if (slevel < rlevel) or ((slevel == rlevel) and (rprec == 'left')): | |
2573 # We really need to reduce here. | |
2574 st_action[a] = -p.number | |
2575 st_actionp[a] = p | |
2576 if not slevel and not rlevel: | |
2577 log.info(' ! shift/reduce conflict for %s resolved as reduce', a) | |
2578 self.sr_conflicts.append((st, a, 'reduce')) | |
2579 Productions[p.number].reduced += 1 | |
2580 elif (slevel == rlevel) and (rprec == 'nonassoc'): | |
2581 st_action[a] = None | |
2582 else: | |
2583 # Hmmm. Guess we'll keep the shift | |
2584 if not rlevel: | |
2585 log.info(' ! shift/reduce conflict for %s resolved as shift', a) | |
2586 self.sr_conflicts.append((st, a, 'shift')) | |
2587 elif r < 0: | |
2588 # Reduce/reduce conflict. In this case, we favor the rule | |
2589 # that was defined first in the grammar file | |
2590 oldp = Productions[-r] | |
2591 pp = Productions[p.number] | |
2592 if oldp.line > pp.line: | |
2593 st_action[a] = -p.number | |
2594 st_actionp[a] = p | |
2595 chosenp, rejectp = pp, oldp | |
2596 Productions[p.number].reduced += 1 | |
2597 Productions[oldp.number].reduced -= 1 | |
2598 else: | |
2599 chosenp, rejectp = oldp, pp | |
2600 self.rr_conflicts.append((st, chosenp, rejectp)) | |
2601 log.info(' ! reduce/reduce conflict for %s resolved using rule %d (%s)', | |
2602 a, st_actionp[a].number, st_actionp[a]) | |
2603 else: | |
2604 raise LALRError('Unknown conflict in state %d' % st) | |
2605 else: | |
2606 st_action[a] = -p.number | |
2607 st_actionp[a] = p | |
2608 Productions[p.number].reduced += 1 | |
2609 else: | |
2610 i = p.lr_index | |
2611 a = p.prod[i+1] # Get symbol right after the "." | |
2612 if a in self.grammar.Terminals: | |
2613 g = self.lr0_goto(I, a) | |
2614 j = self.lr0_cidhash.get(id(g), -1) | |
2615 if j >= 0: | |
2616 # We are in a shift state | |
2617 actlist.append((a, p, 'shift and go to state %d' % j)) | |
2618 r = st_action.get(a) | |
2619 if r is not None: | |
2620 # Whoa have a shift/reduce or shift/shift conflict | |
2621 if r > 0: | |
2622 if r != j: | |
2623 raise LALRError('Shift/shift conflict in state %d' % st) | |
2624 elif r < 0: | |
2625 # Do a precedence check. | |
2626 # - if precedence of reduce rule is higher, we reduce. | |
2627 # - if precedence of reduce is same and left assoc, we reduce. | |
2628 # - otherwise we shift | |
2629 rprec, rlevel = Productions[st_actionp[a].number].prec | |
2630 sprec, slevel = Precedence.get(a, ('right', 0)) | |
2631 if (slevel > rlevel) or ((slevel == rlevel) and (rprec == 'right')): | |
2632 # We decide to shift here... highest precedence to shift | |
2633 Productions[st_actionp[a].number].reduced -= 1 | |
2634 st_action[a] = j | |
2635 st_actionp[a] = p | |
2636 if not rlevel: | |
2637 log.info(' ! shift/reduce conflict for %s resolved as shift', a) | |
2638 self.sr_conflicts.append((st, a, 'shift')) | |
2639 elif (slevel == rlevel) and (rprec == 'nonassoc'): | |
2640 st_action[a] = None | |
2641 else: | |
2642 # Hmmm. Guess we'll keep the reduce | |
2643 if not slevel and not rlevel: | |
2644 log.info(' ! shift/reduce conflict for %s resolved as reduce', a) | |
2645 self.sr_conflicts.append((st, a, 'reduce')) | |
2646 | |
2647 else: | |
2648 raise LALRError('Unknown conflict in state %d' % st) | |
2649 else: | |
2650 st_action[a] = j | |
2651 st_actionp[a] = p | |
2652 | |
2653 # Print the actions associated with each terminal | |
2654 _actprint = {} | |
2655 for a, p, m in actlist: | |
2656 if a in st_action: | |
2657 if p is st_actionp[a]: | |
2658 log.info(' %-15s %s', a, m) | |
2659 _actprint[(a, m)] = 1 | |
2660 log.info('') | |
2661 # Print the actions that were not used. (debugging) | |
2662 not_used = 0 | |
2663 for a, p, m in actlist: | |
2664 if a in st_action: | |
2665 if p is not st_actionp[a]: | |
2666 if not (a, m) in _actprint: | |
2667 log.debug(' ! %-15s [ %s ]', a, m) | |
2668 not_used = 1 | |
2669 _actprint[(a, m)] = 1 | |
2670 if not_used: | |
2671 log.debug('') | |
2672 | |
2673 # Construct the goto table for this state | |
2674 | |
2675 nkeys = {} | |
2676 for ii in I: | |
2677 for s in ii.usyms: | |
2678 if s in self.grammar.Nonterminals: | |
2679 nkeys[s] = None | |
2680 for n in nkeys: | |
2681 g = self.lr0_goto(I, n) | |
2682 j = self.lr0_cidhash.get(id(g), -1) | |
2683 if j >= 0: | |
2684 st_goto[n] = j | |
2685 log.info(' %-30s shift and go to state %d', n, j) | |
2686 | |
2687 action[st] = st_action | |
2688 actionp[st] = st_actionp | |
2689 goto[st] = st_goto | |
2690 st += 1 | |
2691 | |
2692 # ----------------------------------------------------------------------------- | |
2693 # write() | |
2694 # | |
2695 # This function writes the LR parsing tables to a file | |
2696 # ----------------------------------------------------------------------------- | |
2697 | |
2698 def write_table(self, tabmodule, outputdir='', signature=''): | |
2699 if isinstance(tabmodule, types.ModuleType): | |
2700 raise IOError("Won't overwrite existing tabmodule") | |
2701 | |
2702 basemodulename = tabmodule.split('.')[-1] | |
2703 filename = os.path.join(outputdir, basemodulename) + '.py' | |
2704 try: | |
2705 f = open(filename, 'w') | |
2706 | |
2707 f.write(''' | |
2708 # %s | |
2709 # This file is automatically generated. Do not edit. | |
2710 _tabversion = %r | |
2711 | |
2712 _lr_method = %r | |
2713 | |
2714 _lr_signature = %r | |
2715 ''' % (os.path.basename(filename), __tabversion__, self.lr_method, signature)) | |
2716 | |
2717 # Change smaller to 0 to go back to original tables | |
2718 smaller = 1 | |
2719 | |
2720 # Factor out names to try and make smaller | |
2721 if smaller: | |
2722 items = {} | |
2723 | |
2724 for s, nd in self.lr_action.items(): | |
2725 for name, v in nd.items(): | |
2726 i = items.get(name) | |
2727 if not i: | |
2728 i = ([], []) | |
2729 items[name] = i | |
2730 i[0].append(s) | |
2731 i[1].append(v) | |
2732 | |
2733 f.write('\n_lr_action_items = {') | |
2734 for k, v in items.items(): | |
2735 f.write('%r:([' % k) | |
2736 for i in v[0]: | |
2737 f.write('%r,' % i) | |
2738 f.write('],[') | |
2739 for i in v[1]: | |
2740 f.write('%r,' % i) | |
2741 | |
2742 f.write(']),') | |
2743 f.write('}\n') | |
2744 | |
2745 f.write(''' | |
2746 _lr_action = {} | |
2747 for _k, _v in _lr_action_items.items(): | |
2748 for _x,_y in zip(_v[0],_v[1]): | |
2749 if not _x in _lr_action: _lr_action[_x] = {} | |
2750 _lr_action[_x][_k] = _y | |
2751 del _lr_action_items | |
2752 ''') | |
2753 | |
2754 else: | |
2755 f.write('\n_lr_action = { ') | |
2756 for k, v in self.lr_action.items(): | |
2757 f.write('(%r,%r):%r,' % (k[0], k[1], v)) | |
2758 f.write('}\n') | |
2759 | |
2760 if smaller: | |
2761 # Factor out names to try and make smaller | |
2762 items = {} | |
2763 | |
2764 for s, nd in self.lr_goto.items(): | |
2765 for name, v in nd.items(): | |
2766 i = items.get(name) | |
2767 if not i: | |
2768 i = ([], []) | |
2769 items[name] = i | |
2770 i[0].append(s) | |
2771 i[1].append(v) | |
2772 | |
2773 f.write('\n_lr_goto_items = {') | |
2774 for k, v in items.items(): | |
2775 f.write('%r:([' % k) | |
2776 for i in v[0]: | |
2777 f.write('%r,' % i) | |
2778 f.write('],[') | |
2779 for i in v[1]: | |
2780 f.write('%r,' % i) | |
2781 | |
2782 f.write(']),') | |
2783 f.write('}\n') | |
2784 | |
2785 f.write(''' | |
2786 _lr_goto = {} | |
2787 for _k, _v in _lr_goto_items.items(): | |
2788 for _x, _y in zip(_v[0], _v[1]): | |
2789 if not _x in _lr_goto: _lr_goto[_x] = {} | |
2790 _lr_goto[_x][_k] = _y | |
2791 del _lr_goto_items | |
2792 ''') | |
2793 else: | |
2794 f.write('\n_lr_goto = { ') | |
2795 for k, v in self.lr_goto.items(): | |
2796 f.write('(%r,%r):%r,' % (k[0], k[1], v)) | |
2797 f.write('}\n') | |
2798 | |
2799 # Write production table | |
2800 f.write('_lr_productions = [\n') | |
2801 for p in self.lr_productions: | |
2802 if p.func: | |
2803 f.write(' (%r,%r,%d,%r,%r,%d),\n' % (p.str, p.name, p.len, | |
2804 p.func, os.path.basename(p.file), p.line)) | |
2805 else: | |
2806 f.write(' (%r,%r,%d,None,None,None),\n' % (str(p), p.name, p.len)) | |
2807 f.write(']\n') | |
2808 f.close() | |
2809 | |
2810 except IOError as e: | |
2811 raise | |
2812 | |
2813 | |
2814 # ----------------------------------------------------------------------------- | |
2815 # pickle_table() | |
2816 # | |
2817 # This function pickles the LR parsing tables to a supplied file object | |
2818 # ----------------------------------------------------------------------------- | |
2819 | |
2820 def pickle_table(self, filename, signature=''): | |
2821 try: | |
2822 import cPickle as pickle | |
2823 except ImportError: | |
2824 import pickle | |
2825 with open(filename, 'wb') as outf: | |
2826 pickle.dump(__tabversion__, outf, pickle_protocol) | |
2827 pickle.dump(self.lr_method, outf, pickle_protocol) | |
2828 pickle.dump(signature, outf, pickle_protocol) | |
2829 pickle.dump(self.lr_action, outf, pickle_protocol) | |
2830 pickle.dump(self.lr_goto, outf, pickle_protocol) | |
2831 | |
2832 outp = [] | |
2833 for p in self.lr_productions: | |
2834 if p.func: | |
2835 outp.append((p.str, p.name, p.len, p.func, os.path.basename(p.file), p.line)) | |
2836 else: | |
2837 outp.append((str(p), p.name, p.len, None, None, None)) | |
2838 pickle.dump(outp, outf, pickle_protocol) | |
2839 | |
2840 # ----------------------------------------------------------------------------- | |
2841 # === INTROSPECTION === | |
2842 # | |
2843 # The following functions and classes are used to implement the PLY | |
2844 # introspection features followed by the yacc() function itself. | |
2845 # ----------------------------------------------------------------------------- | |
2846 | |
2847 # ----------------------------------------------------------------------------- | |
2848 # get_caller_module_dict() | |
2849 # | |
2850 # This function returns a dictionary containing all of the symbols defined within | |
2851 # a caller further down the call stack. This is used to get the environment | |
2852 # associated with the yacc() call if none was provided. | |
2853 # ----------------------------------------------------------------------------- | |
2854 | |
2855 def get_caller_module_dict(levels): | |
2856 f = sys._getframe(levels) | |
2857 ldict = f.f_globals.copy() | |
2858 if f.f_globals != f.f_locals: | |
2859 ldict.update(f.f_locals) | |
2860 return ldict | |
2861 | |
2862 # ----------------------------------------------------------------------------- | |
2863 # parse_grammar() | |
2864 # | |
2865 # This takes a raw grammar rule string and parses it into production data | |
2866 # ----------------------------------------------------------------------------- | |
2867 def parse_grammar(doc, file, line): | |
2868 grammar = [] | |
2869 # Split the doc string into lines | |
2870 pstrings = doc.splitlines() | |
2871 lastp = None | |
2872 dline = line | |
2873 for ps in pstrings: | |
2874 dline += 1 | |
2875 p = ps.split() | |
2876 if not p: | |
2877 continue | |
2878 try: | |
2879 if p[0] == '|': | |
2880 # This is a continuation of a previous rule | |
2881 if not lastp: | |
2882 raise SyntaxError("%s:%d: Misplaced '|'" % (file, dline)) | |
2883 prodname = lastp | |
2884 syms = p[1:] | |
2885 else: | |
2886 prodname = p[0] | |
2887 lastp = prodname | |
2888 syms = p[2:] | |
2889 assign = p[1] | |
2890 if assign != ':' and assign != '::=': | |
2891 raise SyntaxError("%s:%d: Syntax error. Expected ':'" % (file, dline)) | |
2892 | |
2893 grammar.append((file, dline, prodname, syms)) | |
2894 except SyntaxError: | |
2895 raise | |
2896 except Exception: | |
2897 raise SyntaxError('%s:%d: Syntax error in rule %r' % (file, dline, ps.strip())) | |
2898 | |
2899 return grammar | |
2900 | |
2901 # ----------------------------------------------------------------------------- | |
2902 # ParserReflect() | |
2903 # | |
2904 # This class represents information extracted for building a parser including | |
2905 # start symbol, error function, tokens, precedence list, action functions, | |
2906 # etc. | |
2907 # ----------------------------------------------------------------------------- | |
2908 class ParserReflect(object): | |
2909 def __init__(self, pdict, log=None): | |
2910 self.pdict = pdict | |
2911 self.start = None | |
2912 self.error_func = None | |
2913 self.tokens = None | |
2914 self.modules = set() | |
2915 self.grammar = [] | |
2916 self.error = False | |
2917 | |
2918 if log is None: | |
2919 self.log = PlyLogger(sys.stderr) | |
2920 else: | |
2921 self.log = log | |
2922 | |
2923 # Get all of the basic information | |
2924 def get_all(self): | |
2925 self.get_start() | |
2926 self.get_error_func() | |
2927 self.get_tokens() | |
2928 self.get_precedence() | |
2929 self.get_pfunctions() | |
2930 | |
2931 # Validate all of the information | |
2932 def validate_all(self): | |
2933 self.validate_start() | |
2934 self.validate_error_func() | |
2935 self.validate_tokens() | |
2936 self.validate_precedence() | |
2937 self.validate_pfunctions() | |
2938 self.validate_modules() | |
2939 return self.error | |
2940 | |
2941 # Compute a signature over the grammar | |
2942 def signature(self): | |
2943 try: | |
2944 from hashlib import md5 | |
2945 except ImportError: | |
2946 from md5 import md5 | |
2947 try: | |
2948 sig = md5() | |
2949 if self.start: | |
2950 sig.update(self.start.encode('latin-1')) | |
2951 if self.prec: | |
2952 sig.update(''.join([''.join(p) for p in self.prec]).encode('latin-1')) | |
2953 if self.tokens: | |
2954 sig.update(' '.join(self.tokens).encode('latin-1')) | |
2955 for f in self.pfuncs: | |
2956 if f[3]: | |
2957 sig.update(f[3].encode('latin-1')) | |
2958 except (TypeError, ValueError): | |
2959 pass | |
2960 | |
2961 digest = base64.b16encode(sig.digest()) | |
2962 if sys.version_info[0] >= 3: | |
2963 digest = digest.decode('latin-1') | |
2964 return digest | |
2965 | |
2966 # ----------------------------------------------------------------------------- | |
2967 # validate_modules() | |
2968 # | |
2969 # This method checks to see if there are duplicated p_rulename() functions | |
2970 # in the parser module file. Without this function, it is really easy for | |
2971 # users to make mistakes by cutting and pasting code fragments (and it's a real | |
2972 # bugger to try and figure out why the resulting parser doesn't work). Therefore, | |
2973 # we just do a little regular expression pattern matching of def statements | |
2974 # to try and detect duplicates. | |
2975 # ----------------------------------------------------------------------------- | |
2976 | |
2977 def validate_modules(self): | |
2978 # Match def p_funcname( | |
2979 fre = re.compile(r'\s*def\s+(p_[a-zA-Z_0-9]*)\(') | |
2980 | |
2981 for module in self.modules: | |
2982 lines, linen = inspect.getsourcelines(module) | |
2983 | |
2984 counthash = {} | |
2985 for linen, line in enumerate(lines): | |
2986 linen += 1 | |
2987 m = fre.match(line) | |
2988 if m: | |
2989 name = m.group(1) | |
2990 prev = counthash.get(name) | |
2991 if not prev: | |
2992 counthash[name] = linen | |
2993 else: | |
2994 filename = inspect.getsourcefile(module) | |
2995 self.log.warning('%s:%d: Function %s redefined. Previously defined on line %d', | |
2996 filename, linen, name, prev) | |
2997 | |
2998 # Get the start symbol | |
2999 def get_start(self): | |
3000 self.start = self.pdict.get('start') | |
3001 | |
3002 # Validate the start symbol | |
3003 def validate_start(self): | |
3004 if self.start is not None: | |
3005 if not isinstance(self.start, string_types): | |
3006 self.log.error("'start' must be a string") | |
3007 | |
3008 # Look for error handler | |
3009 def get_error_func(self): | |
3010 self.error_func = self.pdict.get('p_error') | |
3011 | |
3012 # Validate the error function | |
3013 def validate_error_func(self): | |
3014 if self.error_func: | |
3015 if isinstance(self.error_func, types.FunctionType): | |
3016 ismethod = 0 | |
3017 elif isinstance(self.error_func, types.MethodType): | |
3018 ismethod = 1 | |
3019 else: | |
3020 self.log.error("'p_error' defined, but is not a function or method") | |
3021 self.error = True | |
3022 return | |
3023 | |
3024 eline = self.error_func.__code__.co_firstlineno | |
3025 efile = self.error_func.__code__.co_filename | |
3026 module = inspect.getmodule(self.error_func) | |
3027 self.modules.add(module) | |
3028 | |
3029 argcount = self.error_func.__code__.co_argcount - ismethod | |
3030 if argcount != 1: | |
3031 self.log.error('%s:%d: p_error() requires 1 argument', efile, eline) | |
3032 self.error = True | |
3033 | |
3034 # Get the tokens map | |
3035 def get_tokens(self): | |
3036 tokens = self.pdict.get('tokens') | |
3037 if not tokens: | |
3038 self.log.error('No token list is defined') | |
3039 self.error = True | |
3040 return | |
3041 | |
3042 if not isinstance(tokens, (list, tuple)): | |
3043 self.log.error('tokens must be a list or tuple') | |
3044 self.error = True | |
3045 return | |
3046 | |
3047 if not tokens: | |
3048 self.log.error('tokens is empty') | |
3049 self.error = True | |
3050 return | |
3051 | |
3052 self.tokens = tokens | |
3053 | |
3054 # Validate the tokens | |
3055 def validate_tokens(self): | |
3056 # Validate the tokens. | |
3057 if 'error' in self.tokens: | |
3058 self.log.error("Illegal token name 'error'. Is a reserved word") | |
3059 self.error = True | |
3060 return | |
3061 | |
3062 terminals = set() | |
3063 for n in self.tokens: | |
3064 if n in terminals: | |
3065 self.log.warning('Token %r multiply defined', n) | |
3066 terminals.add(n) | |
3067 | |
3068 # Get the precedence map (if any) | |
3069 def get_precedence(self): | |
3070 self.prec = self.pdict.get('precedence') | |
3071 | |
3072 # Validate and parse the precedence map | |
3073 def validate_precedence(self): | |
3074 preclist = [] | |
3075 if self.prec: | |
3076 if not isinstance(self.prec, (list, tuple)): | |
3077 self.log.error('precedence must be a list or tuple') | |
3078 self.error = True | |
3079 return | |
3080 for level, p in enumerate(self.prec): | |
3081 if not isinstance(p, (list, tuple)): | |
3082 self.log.error('Bad precedence table') | |
3083 self.error = True | |
3084 return | |
3085 | |
3086 if len(p) < 2: | |
3087 self.log.error('Malformed precedence entry %s. Must be (assoc, term, ..., term)', p) | |
3088 self.error = True | |
3089 return | |
3090 assoc = p[0] | |
3091 if not isinstance(assoc, string_types): | |
3092 self.log.error('precedence associativity must be a string') | |
3093 self.error = True | |
3094 return | |
3095 for term in p[1:]: | |
3096 if not isinstance(term, string_types): | |
3097 self.log.error('precedence items must be strings') | |
3098 self.error = True | |
3099 return | |
3100 preclist.append((term, assoc, level+1)) | |
3101 self.preclist = preclist | |
3102 | |
3103 # Get all p_functions from the grammar | |
3104 def get_pfunctions(self): | |
3105 p_functions = [] | |
3106 for name, item in self.pdict.items(): | |
3107 if not name.startswith('p_') or name == 'p_error': | |
3108 continue | |
3109 if isinstance(item, (types.FunctionType, types.MethodType)): | |
3110 line = item.__code__.co_firstlineno | |
3111 module = inspect.getmodule(item) | |
3112 p_functions.append((line, module, name, item.__doc__)) | |
3113 | |
3114 # Sort all of the actions by line number; make sure to stringify | |
3115 # modules to make them sortable, since `line` may not uniquely sort all | |
3116 # p functions | |
3117 p_functions.sort(key=lambda p_function: ( | |
3118 p_function[0], | |
3119 str(p_function[1]), | |
3120 p_function[2], | |
3121 p_function[3])) | |
3122 self.pfuncs = p_functions | |
3123 | |
3124 # Validate all of the p_functions | |
3125 def validate_pfunctions(self): | |
3126 grammar = [] | |
3127 # Check for non-empty symbols | |
3128 if len(self.pfuncs) == 0: | |
3129 self.log.error('no rules of the form p_rulename are defined') | |
3130 self.error = True | |
3131 return | |
3132 | |
3133 for line, module, name, doc in self.pfuncs: | |
3134 file = inspect.getsourcefile(module) | |
3135 func = self.pdict[name] | |
3136 if isinstance(func, types.MethodType): | |
3137 reqargs = 2 | |
3138 else: | |
3139 reqargs = 1 | |
3140 if func.__code__.co_argcount > reqargs: | |
3141 self.log.error('%s:%d: Rule %r has too many arguments', file, line, func.__name__) | |
3142 self.error = True | |
3143 elif func.__code__.co_argcount < reqargs: | |
3144 self.log.error('%s:%d: Rule %r requires an argument', file, line, func.__name__) | |
3145 self.error = True | |
3146 elif not func.__doc__: | |
3147 self.log.warning('%s:%d: No documentation string specified in function %r (ignored)', | |
3148 file, line, func.__name__) | |
3149 else: | |
3150 try: | |
3151 parsed_g = parse_grammar(doc, file, line) | |
3152 for g in parsed_g: | |
3153 grammar.append((name, g)) | |
3154 except SyntaxError as e: | |
3155 self.log.error(str(e)) | |
3156 self.error = True | |
3157 | |
3158 # Looks like a valid grammar rule | |
3159 # Mark the file in which defined. | |
3160 self.modules.add(module) | |
3161 | |
3162 # Secondary validation step that looks for p_ definitions that are not functions | |
3163 # or functions that look like they might be grammar rules. | |
3164 | |
3165 for n, v in self.pdict.items(): | |
3166 if n.startswith('p_') and isinstance(v, (types.FunctionType, types.MethodType)): | |
3167 continue | |
3168 if n.startswith('t_'): | |
3169 continue | |
3170 if n.startswith('p_') and n != 'p_error': | |
3171 self.log.warning('%r not defined as a function', n) | |
3172 if ((isinstance(v, types.FunctionType) and v.__code__.co_argcount == 1) or | |
3173 (isinstance(v, types.MethodType) and v.__func__.__code__.co_argcount == 2)): | |
3174 if v.__doc__: | |
3175 try: | |
3176 doc = v.__doc__.split(' ') | |
3177 if doc[1] == ':': | |
3178 self.log.warning('%s:%d: Possible grammar rule %r defined without p_ prefix', | |
3179 v.__code__.co_filename, v.__code__.co_firstlineno, n) | |
3180 except IndexError: | |
3181 pass | |
3182 | |
3183 self.grammar = grammar | |
3184 | |
3185 # ----------------------------------------------------------------------------- | |
3186 # yacc(module) | |
3187 # | |
3188 # Build a parser | |
3189 # ----------------------------------------------------------------------------- | |
3190 | |
3191 def yacc(method='LALR', debug=yaccdebug, module=None, tabmodule=tab_module, start=None, | |
3192 check_recursion=True, optimize=False, write_tables=True, debugfile=debug_file, | |
3193 outputdir=None, debuglog=None, errorlog=None, picklefile=None): | |
3194 | |
3195 if tabmodule is None: | |
3196 tabmodule = tab_module | |
3197 | |
3198 # Reference to the parsing method of the last built parser | |
3199 global parse | |
3200 | |
3201 # If pickling is enabled, table files are not created | |
3202 if picklefile: | |
3203 write_tables = 0 | |
3204 | |
3205 if errorlog is None: | |
3206 errorlog = PlyLogger(sys.stderr) | |
3207 | |
3208 # Get the module dictionary used for the parser | |
3209 if module: | |
3210 _items = [(k, getattr(module, k)) for k in dir(module)] | |
3211 pdict = dict(_items) | |
3212 # If no __file__ attribute is available, try to obtain it from the __module__ instead | |
3213 if '__file__' not in pdict: | |
3214 pdict['__file__'] = sys.modules[pdict['__module__']].__file__ | |
3215 else: | |
3216 pdict = get_caller_module_dict(2) | |
3217 | |
3218 if outputdir is None: | |
3219 # If no output directory is set, the location of the output files | |
3220 # is determined according to the following rules: | |
3221 # - If tabmodule specifies a package, files go into that package directory | |
3222 # - Otherwise, files go in the same directory as the specifying module | |
3223 if isinstance(tabmodule, types.ModuleType): | |
3224 srcfile = tabmodule.__file__ | |
3225 else: | |
3226 if '.' not in tabmodule: | |
3227 srcfile = pdict['__file__'] | |
3228 else: | |
3229 parts = tabmodule.split('.') | |
3230 pkgname = '.'.join(parts[:-1]) | |
3231 exec('import %s' % pkgname) | |
3232 srcfile = getattr(sys.modules[pkgname], '__file__', '') | |
3233 outputdir = os.path.dirname(srcfile) | |
3234 | |
3235 # Determine if the module is package of a package or not. | |
3236 # If so, fix the tabmodule setting so that tables load correctly | |
3237 pkg = pdict.get('__package__') | |
3238 if pkg and isinstance(tabmodule, str): | |
3239 if '.' not in tabmodule: | |
3240 tabmodule = pkg + '.' + tabmodule | |
3241 | |
3242 | |
3243 | |
3244 # Set start symbol if it's specified directly using an argument | |
3245 if start is not None: | |
3246 pdict['start'] = start | |
3247 | |
3248 # Collect parser information from the dictionary | |
3249 pinfo = ParserReflect(pdict, log=errorlog) | |
3250 pinfo.get_all() | |
3251 | |
3252 if pinfo.error: | |
3253 raise YaccError('Unable to build parser') | |
3254 | |
3255 # Check signature against table files (if any) | |
3256 signature = pinfo.signature() | |
3257 | |
3258 # Read the tables | |
3259 try: | |
3260 lr = LRTable() | |
3261 if picklefile: | |
3262 read_signature = lr.read_pickle(picklefile) | |
3263 else: | |
3264 read_signature = lr.read_table(tabmodule) | |
3265 if optimize or (read_signature == signature): | |
3266 try: | |
3267 lr.bind_callables(pinfo.pdict) | |
3268 parser = LRParser(lr, pinfo.error_func) | |
3269 parse = parser.parse | |
3270 return parser | |
3271 except Exception as e: | |
3272 errorlog.warning('There was a problem loading the table file: %r', e) | |
3273 except VersionError as e: | |
3274 errorlog.warning(str(e)) | |
3275 except ImportError: | |
3276 pass | |
3277 | |
3278 if debuglog is None: | |
3279 if debug: | |
3280 try: | |
3281 debuglog = PlyLogger(open(os.path.join(outputdir, debugfile), 'w')) | |
3282 except IOError as e: | |
3283 errorlog.warning("Couldn't open %r. %s" % (debugfile, e)) | |
3284 debuglog = NullLogger() | |
3285 else: | |
3286 debuglog = NullLogger() | |
3287 | |
3288 debuglog.info('Created by PLY version %s (http://www.dabeaz.com/ply)', __version__) | |
3289 | |
3290 errors = False | |
3291 | |
3292 # Validate the parser information | |
3293 if pinfo.validate_all(): | |
3294 raise YaccError('Unable to build parser') | |
3295 | |
3296 if not pinfo.error_func: | |
3297 errorlog.warning('no p_error() function is defined') | |
3298 | |
3299 # Create a grammar object | |
3300 grammar = Grammar(pinfo.tokens) | |
3301 | |
3302 # Set precedence level for terminals | |
3303 for term, assoc, level in pinfo.preclist: | |
3304 try: | |
3305 grammar.set_precedence(term, assoc, level) | |
3306 except GrammarError as e: | |
3307 errorlog.warning('%s', e) | |
3308 | |
3309 # Add productions to the grammar | |
3310 for funcname, gram in pinfo.grammar: | |
3311 file, line, prodname, syms = gram | |
3312 try: | |
3313 grammar.add_production(prodname, syms, funcname, file, line) | |
3314 except GrammarError as e: | |
3315 errorlog.error('%s', e) | |
3316 errors = True | |
3317 | |
3318 # Set the grammar start symbols | |
3319 try: | |
3320 if start is None: | |
3321 grammar.set_start(pinfo.start) | |
3322 else: | |
3323 grammar.set_start(start) | |
3324 except GrammarError as e: | |
3325 errorlog.error(str(e)) | |
3326 errors = True | |
3327 | |
3328 if errors: | |
3329 raise YaccError('Unable to build parser') | |
3330 | |
3331 # Verify the grammar structure | |
3332 undefined_symbols = grammar.undefined_symbols() | |
3333 for sym, prod in undefined_symbols: | |
3334 errorlog.error('%s:%d: Symbol %r used, but not defined as a token or a rule', prod.file, prod.line, sym) | |
3335 errors = True | |
3336 | |
3337 unused_terminals = grammar.unused_terminals() | |
3338 if unused_terminals: | |
3339 debuglog.info('') | |
3340 debuglog.info('Unused terminals:') | |
3341 debuglog.info('') | |
3342 for term in unused_terminals: | |
3343 errorlog.warning('Token %r defined, but not used', term) | |
3344 debuglog.info(' %s', term) | |
3345 | |
3346 # Print out all productions to the debug log | |
3347 if debug: | |
3348 debuglog.info('') | |
3349 debuglog.info('Grammar') | |
3350 debuglog.info('') | |
3351 for n, p in enumerate(grammar.Productions): | |
3352 debuglog.info('Rule %-5d %s', n, p) | |
3353 | |
3354 # Find unused non-terminals | |
3355 unused_rules = grammar.unused_rules() | |
3356 for prod in unused_rules: | |
3357 errorlog.warning('%s:%d: Rule %r defined, but not used', prod.file, prod.line, prod.name) | |
3358 | |
3359 if len(unused_terminals) == 1: | |
3360 errorlog.warning('There is 1 unused token') | |
3361 if len(unused_terminals) > 1: | |
3362 errorlog.warning('There are %d unused tokens', len(unused_terminals)) | |
3363 | |
3364 if len(unused_rules) == 1: | |
3365 errorlog.warning('There is 1 unused rule') | |
3366 if len(unused_rules) > 1: | |
3367 errorlog.warning('There are %d unused rules', len(unused_rules)) | |
3368 | |
3369 if debug: | |
3370 debuglog.info('') | |
3371 debuglog.info('Terminals, with rules where they appear') | |
3372 debuglog.info('') | |
3373 terms = list(grammar.Terminals) | |
3374 terms.sort() | |
3375 for term in terms: | |
3376 debuglog.info('%-20s : %s', term, ' '.join([str(s) for s in grammar.Terminals[term]])) | |
3377 | |
3378 debuglog.info('') | |
3379 debuglog.info('Nonterminals, with rules where they appear') | |
3380 debuglog.info('') | |
3381 nonterms = list(grammar.Nonterminals) | |
3382 nonterms.sort() | |
3383 for nonterm in nonterms: | |
3384 debuglog.info('%-20s : %s', nonterm, ' '.join([str(s) for s in grammar.Nonterminals[nonterm]])) | |
3385 debuglog.info('') | |
3386 | |
3387 if check_recursion: | |
3388 unreachable = grammar.find_unreachable() | |
3389 for u in unreachable: | |
3390 errorlog.warning('Symbol %r is unreachable', u) | |
3391 | |
3392 infinite = grammar.infinite_cycles() | |
3393 for inf in infinite: | |
3394 errorlog.error('Infinite recursion detected for symbol %r', inf) | |
3395 errors = True | |
3396 | |
3397 unused_prec = grammar.unused_precedence() | |
3398 for term, assoc in unused_prec: | |
3399 errorlog.error('Precedence rule %r defined for unknown symbol %r', assoc, term) | |
3400 errors = True | |
3401 | |
3402 if errors: | |
3403 raise YaccError('Unable to build parser') | |
3404 | |
3405 # Run the LRGeneratedTable on the grammar | |
3406 if debug: | |
3407 errorlog.debug('Generating %s tables', method) | |
3408 | |
3409 lr = LRGeneratedTable(grammar, method, debuglog) | |
3410 | |
3411 if debug: | |
3412 num_sr = len(lr.sr_conflicts) | |
3413 | |
3414 # Report shift/reduce and reduce/reduce conflicts | |
3415 if num_sr == 1: | |
3416 errorlog.warning('1 shift/reduce conflict') | |
3417 elif num_sr > 1: | |
3418 errorlog.warning('%d shift/reduce conflicts', num_sr) | |
3419 | |
3420 num_rr = len(lr.rr_conflicts) | |
3421 if num_rr == 1: | |
3422 errorlog.warning('1 reduce/reduce conflict') | |
3423 elif num_rr > 1: | |
3424 errorlog.warning('%d reduce/reduce conflicts', num_rr) | |
3425 | |
3426 # Write out conflicts to the output file | |
3427 if debug and (lr.sr_conflicts or lr.rr_conflicts): | |
3428 debuglog.warning('') | |
3429 debuglog.warning('Conflicts:') | |
3430 debuglog.warning('') | |
3431 | |
3432 for state, tok, resolution in lr.sr_conflicts: | |
3433 debuglog.warning('shift/reduce conflict for %s in state %d resolved as %s', tok, state, resolution) | |
3434 | |
3435 already_reported = set() | |
3436 for state, rule, rejected in lr.rr_conflicts: | |
3437 if (state, id(rule), id(rejected)) in already_reported: | |
3438 continue | |
3439 debuglog.warning('reduce/reduce conflict in state %d resolved using rule (%s)', state, rule) | |
3440 debuglog.warning('rejected rule (%s) in state %d', rejected, state) | |
3441 errorlog.warning('reduce/reduce conflict in state %d resolved using rule (%s)', state, rule) | |
3442 errorlog.warning('rejected rule (%s) in state %d', rejected, state) | |
3443 already_reported.add((state, id(rule), id(rejected))) | |
3444 | |
3445 warned_never = [] | |
3446 for state, rule, rejected in lr.rr_conflicts: | |
3447 if not rejected.reduced and (rejected not in warned_never): | |
3448 debuglog.warning('Rule (%s) is never reduced', rejected) | |
3449 errorlog.warning('Rule (%s) is never reduced', rejected) | |
3450 warned_never.append(rejected) | |
3451 | |
3452 # Write the table file if requested | |
3453 if write_tables: | |
3454 try: | |
3455 lr.write_table(tabmodule, outputdir, signature) | |
3456 except IOError as e: | |
3457 errorlog.warning("Couldn't create %r. %s" % (tabmodule, e)) | |
3458 | |
3459 # Write a pickled version of the tables | |
3460 if picklefile: | |
3461 try: | |
3462 lr.pickle_table(picklefile, signature) | |
3463 except IOError as e: | |
3464 errorlog.warning("Couldn't create %r. %s" % (picklefile, e)) | |
3465 | |
3466 # Build the parser | |
3467 lr.bind_callables(pinfo.pdict) | |
3468 parser = LRParser(lr, pinfo.error_func) | |
3469 | |
3470 parse = parser.parse | |
3471 return parser |