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