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