tools/yacc.py

   1 #-----------------------------------------------------------------------------
   2 # ply: yacc.py
   3 #
   4 # Author(s): David M. Beazley (dave@dabeaz.com)
   5 #
   6 # Copyright (C) 2001-2006, David M. Beazley
   7 #
   8 # $Header: /cvs/projects/PLY/yacc.py,v 1.6 2004/05/26 20:51:34 beazley Exp $
   9 #
  10 # This library is free software; you can redistribute it and/or
  11 # modify it under the terms of the GNU Lesser General Public
  12 # License as published by the Free Software Foundation; either
  13 # version 2.1 of the License, or (at your option) any later version.
  14 #
  15 # This library is distributed in the hope that it will be useful,
  16 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  17 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18 # Lesser General Public License for more details.
  19 #
  20 # You should have received a copy of the GNU Lesser General Public
  21 # License along with this library; if not, write to the Free Software
  22 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  23 #
  24 # See the file COPYING for a complete copy of the LGPL.
  25 #
  26 #
  27 # This implements an LR parser that is constructed from grammar rules defined
  28 # as Python functions.  Roughly speaking, this module is a cross between
  29 # John Aycock's Spark system and the GNU bison utility.
  30 #
  31 # The current implementation is only somewhat object-oriented. The
  32 # LR parser itself is defined in terms of an object (which allows multiple
  33 # parsers to co-exist).  However, most of the variables used during table
  34 # construction are defined in terms of global variables.  Users shouldn't
  35 # notice unless they are trying to define multiple parsers at the same
  36 # time using threads (in which case they should have their head examined).
  37 #
  38 # This implementation supports both SLR and LALR(1) parsing.  LALR(1)
  39 # support was implemented by Elias Ioup (ezioup@alumni.uchicago.edu)
  40 # and hacked abit by Dave to run faster.
  41 #
  42 # :::::::: WARNING :::::::
  43 #
  44 # Construction of LR parsing tables is fairly complicated and expensive.
  45 # To make this module run fast, a *LOT* of work has been put into
  46 # optimization---often at the expensive of readability and what might
  47 # consider to be good Python "coding style."   Modify the code at your
  48 # own risk!
  49 # ----------------------------------------------------------------------------
  50
  51 __version__ = "1.8"
  52
  53 import types
  54
  55 #-----------------------------------------------------------------------------
  56 #                     === User configurable parameters ===
  57 #
  58 # Change these to modify the default behavior of yacc (if you wish)
  59 #-----------------------------------------------------------------------------
  60
  61 yaccdebug   = 1                # Debugging mode.  If set, yacc generates a
  62                                # a 'parser.out' file in the current directory
  63
  64 debug_file  = 'parser.out'     # Default name of the debugging file
  65 tab_module  = 'parsetab'       # Default name of the table module
  66 default_lr  = 'SLR'            # Default LR table generation method
  67
  68 error_count = 3                # Number of symbols that must be shifted to leave recovery mode
  69
  70 import re, types, sys, cStringIO, md5, os.path
  71
  72 # Exception raised for yacc-related errors
  73 class YaccError(Exception):   pass
  74
  75 #-----------------------------------------------------------------------------
  76 #                        ===  LR Parsing Engine ===
  77 #
  78 # The following classes are used for the LR parser itself.  These are not
  79 # used during table construction and are independent of the actual LR
  80 # table generation algorithm
  81 #-----------------------------------------------------------------------------
  82
  83 # This class is used to hold non-terminal grammar symbols during parsing.
  84 # It normally has the following attributes set:
  85 #        .type       = Grammar symbol type
  86 #        .value      = Symbol value
  87 #        .lineno     = Starting line number
  88 #        .endlineno  = Ending line number (optional, set automatically)
  89
  90 class YaccSymbol:
  91     def __str__(self):    return self.type
  92     def __repr__(self):   return str(self)
  93
  94 # This class is a wrapper around the objects actually passed to each
  95 # grammar rule.   Index lookup and assignment actually assign the
  96 # .value attribute of the underlying YaccSymbol object.
  97 # The lineno() method returns the line number of a given
  98 # item (or 0 if not defined).   The linespan() method returns
  99 # a tuple of (startline,endline) representing the range of lines
 100 # for a symbol.
 101
 102 class YaccProduction:
 103     def __init__(self,s):
 104         self.slice = s
 105         self.pbstack = []
 106
 107     def __getitem__(self,n):
 108         if type(n) == types.IntType:
 109              return self.slice[n].value
 110         else:
 111              return [s.value for s in self.slice[n.start:n.stop:n.step]]
 112
 113     def __setitem__(self,n,v):
 114         self.slice[n].value = v
 115
 116     def __len__(self):
 117         return len(self.slice)
 118
 119     def lineno(self,n):
 120         return getattr(self.slice[n],"lineno",0)
 121
 122     def linespan(self,n):
 123         startline = getattr(self.slice[n],"lineno",0)
 124         endline = getattr(self.slice[n],"endlineno",startline)
 125         return startline,endline
 126
 127     def pushback(self,n):
 128         if n <= 0:
 129             raise ValueError, "Expected a positive value"
 130         if n > (len(self.slice)-1):
 131             raise ValueError, "Can't push %d tokens. Only %d are available." % (n,len(self.slice)-1)
 132         for i in range(0,n):
 133             self.pbstack.append(self.slice[-i-1])
 134
 135 # The LR Parsing engine.   This is defined as a class so that multiple parsers
 136 # can exist in the same process.  A user never instantiates this directly.
 137 # Instead, the global yacc() function should be used to create a suitable Parser
 138 # object.
 139
 140 class Parser:
 141     def __init__(self,magic=None):
 142
 143         # This is a hack to keep users from trying to instantiate a Parser
 144         # object directly.
 145
 146         if magic != "xyzzy":
 147             raise YaccError, "Can't instantiate Parser. Use yacc() instead."
 148
 149         # Reset internal state
 150         self.productions = None          # List of productions
 151         self.errorfunc   = None          # Error handling function
 152         self.action      = { }           # LR Action table
 153         self.goto        = { }           # LR goto table
 154         self.require     = { }           # Attribute require table
 155         self.method      = "Unknown LR"  # Table construction method used
 156
 157     def errok(self):
 158         self.errorcount = 0
 159
 160     def restart(self):
 161         del self.statestack[:]
 162         del self.symstack[:]
 163         sym = YaccSymbol()
 164         sym.type = '$'
 165         self.symstack.append(sym)
 166         self.statestack.append(0)
 167
 168     def parse(self,input=None,lexer=None,debug=0):
 169         lookahead = None                 # Current lookahead symbol
 170         lookaheadstack = [ ]             # Stack of lookahead symbols
 171         actions = self.action            # Local reference to action table
 172         goto    = self.goto              # Local reference to goto table
 173         prod    = self.productions       # Local reference to production list
 174         pslice  = YaccProduction(None)   # Production object passed to grammar rules
 175         pslice.parser = self             # Parser object
 176         self.errorcount = 0              # Used during error recovery
 177
 178         # If no lexer was given, we will try to use the lex module
 179         if not lexer:
 180             import lex as lexer
 181
 182         pslice.lexer = lexer
 183
 184         # If input was supplied, pass to lexer
 185         if input:
 186             lexer.input(input)
 187
 188         # Tokenize function
 189         get_token = lexer.token
 190
 191         statestack = [ ]                # Stack of parsing states
 192         self.statestack = statestack
 193         symstack   = [ ]                # Stack of grammar symbols
 194         self.symstack = symstack
 195
 196         errtoken   = None               # Err token
 197
 198         # The start state is assumed to be (0,$)
 199         statestack.append(0)
 200         sym = YaccSymbol()
 201         sym.type = '$'
 202         symstack.append(sym)
 203
 204         while 1:
 205             # Get the next symbol on the input.  If a lookahead symbol
 206             # is already set, we just use that. Otherwise, we'll pull
 207             # the next token off of the lookaheadstack or from the lexer
 208             if debug > 1:
 209                 print 'state', statestack[-1]
 210             if not lookahead:
 211                 if not lookaheadstack:
 212                     lookahead = get_token()     # Get the next token
 213                 else:
 214                     lookahead = lookaheadstack.pop()
 215                 if not lookahead:
 216                     lookahead = YaccSymbol()
 217                     lookahead.type = '$'
 218             if debug:
 219                 errorlead = ("%s . %s" % (" ".join([xx.type for xx in symstack][1:]), str(lookahead))).lstrip()
 220
 221             # Check the action table
 222             s = statestack[-1]
 223             ltype = lookahead.type
 224             t = actions.get((s,ltype),None)
 225
 226             if debug > 1:
 227                 print 'action', t
 228             if t is None:
 229                 t = actions.get((s,'#'),None)
 230                 if debug > 1:
 231                     print 'default action', t
 232             if t is not None:
 233                 if t > 0:
 234                     # shift a symbol on the stack
 235                     if ltype == '$':
 236                         # Error, end of input
 237                         sys.stderr.write("yacc: Parse error. EOF\n")
 238                         return
 239                     statestack.append(t)
 240                     if debug > 1:
 241                         sys.stderr.write("%-60s shift state %s\n" % (errorlead, t))
 242                     symstack.append(lookahead)
 243                     lookahead = None
 244
 245                     # Decrease error count on successful shift
 246                     if self.errorcount > 0:
 247                         self.errorcount -= 1
 248
 249                     continue
 250
 251                 if t < 0:
 252                     # reduce a symbol on the stack, emit a production
 253                     p = prod[-t]
 254                     pname = p.name
 255                     plen  = p.len
 256
 257                     # Get production function
 258                     sym = YaccSymbol()
 259                     sym.type = pname       # Production name
 260                     sym.value = None
 261                     if debug > 1:
 262                         sys.stderr.write("%-60s reduce %d\n" % (errorlead, -t))
 263
 264                     if plen:
 265                         targ = symstack[-plen-1:]
 266                         targ[0] = sym
 267                         try:
 268                             sym.lineno = targ[1].lineno
 269                             sym.endlineno = getattr(targ[-1],"endlineno",targ[-1].lineno)
 270                         except AttributeError:
 271                             sym.lineno = 0
 272                         del symstack[-plen:]
 273                         del statestack[-plen:]
 274                     else:
 275                         sym.lineno = 0
 276                         targ = [ sym ]
 277                     pslice.slice = targ
 278                     pslice.pbstack = []
 279                     # Call the grammar rule with our special slice object
 280                     p.func(pslice)
 281
 282                     # If there was a pushback, put that on the stack
 283                     if pslice.pbstack:
 284                         lookaheadstack.append(lookahead)
 285                         for _t in pslice.pbstack:
 286                             lookaheadstack.append(_t)
 287                         lookahead = None
 288
 289                     symstack.append(sym)
 290                     statestack.append(goto[statestack[-1],pname])
 291                     continue
 292
 293                 if t == 0:
 294                     n = symstack[-1]
 295                     return getattr(n,"value",None)
 296                     sys.stderr.write(errorlead, "\n")
 297
 298             if t == None:
 299                 if debug:
 300                     sys.stderr.write(errorlead + "\n")
 301                 # We have some kind of parsing error here.  To handle
 302                 # this, we are going to push the current token onto
 303                 # the tokenstack and replace it with an 'error' token.
 304                 # If there are any synchronization rules, they may
 305                 # catch it.
 306                 #
 307                 # In addition to pushing the error token, we call call
 308                 # the user defined p_error() function if this is the
 309                 # first syntax error.  This function is only called if
 310                 # errorcount == 0.
 311                 if not self.errorcount:
 312                     self.errorcount = error_count
 313                     errtoken = lookahead
 314                     if errtoken.type == '$':
 315                         errtoken = None               # End of file!
 316                     if self.errorfunc:
 317                         global errok,token,restart
 318                         errok = self.errok        # Set some special functions available in error recovery
 319                         token = get_token
 320                         restart = self.restart
 321                         tok = self.errorfunc(errtoken)
 322                         del errok, token, restart   # Delete special functions
 323
 324                         if not self.errorcount:
 325                             # User must have done some kind of panic
 326                             # mode recovery on their own.  The
 327                             # returned token is the next lookahead
 328                             lookahead = tok
 329                             errtoken = None
 330                             continue
 331                     else:
 332                         if errtoken:
 333                             if hasattr(errtoken,"lineno"): lineno = lookahead.lineno
 334                             else: lineno = 0
 335                             if lineno:
 336                                 sys.stderr.write("yacc: Syntax error at line %d, token=%s\n" % (lineno, errtoken.type))
 337                             else:
 338                                 sys.stderr.write("yacc: Syntax error, token=%s" % errtoken.type)
 339                         else:
 340                             sys.stderr.write("yacc: Parse error in input. EOF\n")
 341                             return
 342
 343                 else:
 344                     self.errorcount = error_count
 345
 346                 # case 1:  the statestack only has 1 entry on it.  If we're in this state, the
 347                 # entire parse has been rolled back and we're completely hosed.   The token is
 348                 # discarded and we just keep going.
 349
 350                 if len(statestack) <= 1 and lookahead.type != '$':
 351                     lookahead = None
 352                     errtoken = None
 353                     # Nuke the pushback stack
 354                     del lookaheadstack[:]
 355                     continue
 356
 357                 # case 2: the statestack has a couple of entries on it, but we're
 358                 # at the end of the file. nuke the top entry and generate an error token
 359
 360                 # Start nuking entries on the stack
 361                 if lookahead.type == '$':
 362                     # Whoa. We're really hosed here. Bail out
 363                     return
 364
 365                 if lookahead.type != 'error':
 366                     sym = symstack[-1]
 367                     if sym.type == 'error':
 368                         # Hmmm. Error is on top of stack, we'll just nuke input
 369                         # symbol and continue
 370                         lookahead = None
 371                         continue
 372                     t = YaccSymbol()
 373                     t.type = 'error'
 374                     if hasattr(lookahead,"lineno"):
 375                         t.lineno = lookahead.lineno
 376                     t.value = lookahead
 377                     lookaheadstack.append(lookahead)
 378                     lookahead = t
 379                 else:
 380                     symstack.pop()
 381                     statestack.pop()
 382
 383                 continue
 384
 385             # Call an error function here
 386             raise RuntimeError, "yacc: internal parser error!!!\n"
 387
 388 # -----------------------------------------------------------------------------
 389 #                          === Parser Construction ===
 390 #
 391 # The following functions and variables are used to implement the yacc() function
 392 # itself.   This is pretty hairy stuff involving lots of error checking,
 393 # construction of LR items, kernels, and so forth.   Although a lot of
 394 # this work is done using global variables, the resulting Parser object
 395 # is completely self contained--meaning that it is safe to repeatedly
 396 # call yacc() with different grammars in the same application.
 397 # -----------------------------------------------------------------------------
 398
 399 # -----------------------------------------------------------------------------
 400 # validate_file()
 401 #
 402 # This function checks to see if there are duplicated p_rulename() functions
 403 # in the parser module file.  Without this function, it is really easy for
 404 # users to make mistakes by cutting and pasting code fragments (and it's a real
 405 # bugger to try and figure out why the resulting parser doesn't work).  Therefore,
 406 # we just do a little regular expression pattern matching of def statements
 407 # to try and detect duplicates.
 408 # -----------------------------------------------------------------------------
 409
 410 def validate_file(filename):
 411     base,ext = os.path.splitext(filename)
 412     if ext != '.py': return 1          # No idea. Assume it's okay.
 413
 414     try:
 415         f = open(filename)
 416         lines = f.readlines()
 417         f.close()
 418     except IOError:
 419         return 1                       # Oh well
 420
 421     # Match def p_funcname(
 422     fre = re.compile(r'\s*def\s+(p_[a-zA-Z_0-9]*)\(')
 423     counthash = { }
 424     linen = 1
 425     noerror = 1
 426     for l in lines:
 427         m = fre.match(l)
 428         if m:
 429             name = m.group(1)
 430             prev = counthash.get(name)
 431             if not prev:
 432                 counthash[name] = linen
 433             else:
 434                 sys.stderr.write("%s:%d: Function %s redefined. Previously defined on line %d\n" % (filename,linen,name,prev))
 435                 noerror = 0
 436         linen += 1
 437     return noerror
 438
 439 # This function looks for functions that might be grammar rules, but which don't have the proper p_suffix.
 440 def validate_dict(d):
 441     for n,v in d.items():
 442         if n[0:2] == 'p_' and type(v) in (types.FunctionType, types.MethodType): continue
 443         if n[0:2] == 't_': continue
 444
 445         if n[0:2] == 'p_':
 446             sys.stderr.write("yacc: Warning. '%s' not defined as a function\n" % n)
 447         if 1 and isinstance(v,types.FunctionType) and v.func_code.co_argcount == 1:
 448             try:
 449                 doc = v.__doc__.split(" ")
 450                 if doc[1] == ':':
 451                     sys.stderr.write("%s:%d: Warning. Possible grammar rule '%s' defined without p_ prefix.\n" % (v.func_code.co_filename, v.func_code.co_firstlineno,n))
 452             except StandardError:
 453                 pass
 454
 455 # -----------------------------------------------------------------------------
 456 #                           === GRAMMAR FUNCTIONS ===
 457 #
 458 # The following global variables and functions are used to store, manipulate,
 459 # and verify the grammar rules specified by the user.
 460 # -----------------------------------------------------------------------------
 461
 462 # Initialize all of the global variables used during grammar construction
 463 def initialize_vars():
 464     global Productions, Prodnames, Prodmap, Terminals
 465     global Nonterminals, First, Follow, Precedence, LRitems
 466     global Errorfunc, Signature, Requires
 467
 468     # LALR(1) globals
 469     global Prodempty, TReductions, NTReductions, GotoSetNum, Canonical
 470
 471     Productions  = [None]  # A list of all of the productions.  The first
 472                            # entry is always reserved for the purpose of
 473                            # building an augmented grammar
 474
 475     Prodnames    = { }     # A dictionary mapping the names of nonterminals to a list of all
 476                            # productions of that nonterminal.
 477
 478     Prodmap      = { }     # A dictionary that is only used to detect duplicate
 479                            # productions.
 480
 481     Terminals    = { }     # A dictionary mapping the names of terminal symbols to a
 482                            # list of the rules where they are used.
 483
 484     Nonterminals = { }     # A dictionary mapping names of nonterminals to a list
 485                            # of rule numbers where they are used.
 486
 487     First        = { }     # A dictionary of precomputed FIRST(x) symbols
 488
 489     Follow       = { }     # A dictionary of precomputed FOLLOW(x) symbols
 490
 491     Precedence   = { }     # Precedence rules for each terminal. Contains tuples of the
 492                            # form ('right',level) or ('nonassoc', level) or ('left',level)
 493
 494     LRitems      = [ ]     # A list of all LR items for the grammar.  These are the
 495                            # productions with the "dot" like E -> E . PLUS E
 496
 497     Errorfunc    = None    # User defined error handler
 498
 499     Signature    = md5.new()   # Digital signature of the grammar rules, precedence
 500                                # and other information.  Used to determined when a
 501                                # parsing table needs to be regenerated.
 502
 503     Requires     = { }     # Requires list
 504
 505     # LALR(1) Initialization
 506     Prodempty    = { }     # A dictionary of all productions that have an empty rule
 507                            # of the form P : <empty>
 508
 509     TReductions  = { }     # A dictionary of precomputer reductions from
 510                            # nonterminals to terminals
 511
 512     NTReductions = { }     # A dictionary of precomputed reductions from
 513                            # nonterminals to nonterminals
 514
 515     GotoSetNum   = { }     # A dictionary that remembers goto sets based on
 516                            # the state number and symbol
 517
 518     Canonical    = { }     # A list of LR item sets. A LR item set is a list of LR
 519                            # items that represent the state of the parser
 520
 521     # File objects used when creating the parser.out debugging file
 522     global _vf, _vfc
 523     _vf           = cStringIO.StringIO()
 524     _vfc          = cStringIO.StringIO()
 525
 526 # -----------------------------------------------------------------------------
 527 # class Production:
 528 #
 529 # This class stores the raw information about a single production or grammar rule.
 530 # It has a few required attributes:
 531 #
 532 #       name     - Name of the production (nonterminal)
 533 #       prod     - A list of symbols making up its production
 534 #       number   - Production number.
 535 #
 536 # In addition, a few additional attributes are used to help with debugging or
 537 # optimization of table generation.
 538 #
 539 #       file     - File where production action is defined.
 540 #       lineno   - Line number where action is defined
 541 #       func     - Action function
 542 #       prec     - Precedence level
 543 #       lr_next  - Next LR item. Example, if we are ' E -> E . PLUS E'
 544 #                  then lr_next refers to 'E -> E PLUS . E'
 545 #       lr_index - LR item index (location of the ".") in the prod list.
 546 #       lookaheads - LALR lookahead symbols for this item
 547 #       len      - Length of the production (number of symbols on right hand side)
 548 # -----------------------------------------------------------------------------
 549
 550 class Production:
 551     def __init__(self,**kw):
 552         for k,v in kw.items():
 553             setattr(self,k,v)
 554         self.lr_index = -1
 555         self.lr0_added = 0    # Flag indicating whether or not added to LR0 closure
 556         self.lr1_added = 0    # Flag indicating whether or not added to LR1
 557         self.usyms = [ ]
 558         self.lookaheads = { }
 559         self.lk_added = { }
 560         self.setnumbers = [ ]
 561
 562     def __str__(self):
 563         if self.prod:
 564             s = "%s -> %s" % (self.name," ".join(self.prod))
 565         else:
 566             s = "%s -> <empty>" % self.name
 567         return s
 568
 569     def __repr__(self):
 570         return str(self)
 571
 572     # Compute lr_items from the production
 573     def lr_item(self,n):
 574         if n > len(self.prod): return None
 575         p = Production()
 576         p.name = self.name
 577         p.prod = list(self.prod)
 578         p.number = self.number
 579         p.lr_index = n
 580         p.lookaheads = { }
 581         p.setnumbers = self.setnumbers
 582         p.prod.insert(n,".")
 583         p.prod = tuple(p.prod)
 584         p.len = len(p.prod)
 585         p.usyms = self.usyms
 586
 587         # Precompute list of productions immediately following
 588         try:
 589             p.lrafter = Prodnames[p.prod[n+1]]
 590         except (IndexError,KeyError),e:
 591             p.lrafter = []
 592         try:
 593             p.lrbefore = p.prod[n-1]
 594         except IndexError:
 595             p.lrbefore = None
 596
 597         return p
 598
 599 class MiniProduction:
 600     pass
 601
 602 # Utility function
 603 def is_identifier(s):
 604     for c in s:
 605         if not (c.isalnum() or c == '_'): return 0
 606     return 1
 607
 608 # -----------------------------------------------------------------------------
 609 # add_production()
 610 #
 611 # Given an action function, this function assembles a production rule.
 612 # The production rule is assumed to be found in the function's docstring.
 613 # This rule has the general syntax:
 614 #
 615 #              name1 ::= production1
 616 #                     |  production2
 617 #                     |  production3
 618 #                    ...
 619 #                     |  productionn
 620 #              name2 ::= production1
 621 #                     |  production2
 622 #                    ...
 623 # -----------------------------------------------------------------------------
 624
 625 def add_production(f,file,line,prodname,syms):
 626
 627     if Terminals.has_key(prodname):
 628         sys.stderr.write("%s:%d: Illegal rule name '%s'. Already defined as a token.\n" % (file,line,prodname))
 629         return -1
 630     if prodname == 'error':
 631         sys.stderr.write("%s:%d: Illegal rule name '%s'. error is a reserved word.\n" % (file,line,prodname))
 632         return -1
 633
 634     if not is_identifier(prodname):
 635         sys.stderr.write("%s:%d: Illegal rule name '%s'\n" % (file,line,prodname))
 636         return -1
 637
 638     for s in syms:
 639         if not is_identifier(s) and s != '%prec':
 640             sys.stderr.write("%s:%d: Illegal name '%s' in rule '%s'\n" % (file,line,s, prodname))
 641             return -1
 642
 643     # See if the rule is already in the rulemap
 644     map = "%s -> %s" % (prodname,syms)
 645     if Prodmap.has_key(map):
 646         m = Prodmap[map]
 647         sys.stderr.write("%s:%d: Duplicate rule %s.\n" % (file,line, m))
 648         sys.stderr.write("%s:%d: Previous definition at %s:%d\n" % (file,line, m.file, m.line))
 649         return -1
 650
 651     p = Production()
 652     p.name = prodname
 653     p.prod = syms
 654     p.file = file
 655     p.line = line
 656     p.func = f
 657     p.number = len(Productions)
 658
 659
 660     Productions.append(p)
 661     Prodmap[map] = p
 662     if not Nonterminals.has_key(prodname):
 663         Nonterminals[prodname] = [ ]
 664
 665     # Add all terminals to Terminals
 666     i = 0
 667     while i < len(p.prod):
 668         t = p.prod[i]
 669         if t == '%prec':
 670             try:
 671                 precname = p.prod[i+1]
 672             except IndexError:
 673                 sys.stderr.write("%s:%d: Syntax error. Nothing follows %%prec.\n" % (p.file,p.line))
 674                 return -1
 675
 676             prec = Precedence.get(precname,None)
 677             if not prec:
 678                 sys.stderr.write("%s:%d: Nothing known about the precedence of '%s'\n" % (p.file,p.line,precname))
 679                 return -1
 680             else:
 681                 p.prec = prec
 682             del p.prod[i]
 683             del p.prod[i]
 684             continue
 685
 686         if Terminals.has_key(t):
 687             Terminals[t].append(p.number)
 688             # Is a terminal.  We'll assign a precedence to p based on this
 689             if not hasattr(p,"prec"):
 690                 p.prec = Precedence.get(t,('right',0))
 691         else:
 692             if not Nonterminals.has_key(t):
 693                 Nonterminals[t] = [ ]
 694             Nonterminals[t].append(p.number)
 695         i += 1
 696
 697     if not hasattr(p,"prec"):
 698         p.prec = ('right',0)
 699
 700     # Set final length of productions
 701     p.len  = len(p.prod)
 702     p.prod = tuple(p.prod)
 703
 704     # Calculate unique syms in the production
 705     p.usyms = [ ]
 706     for s in p.prod:
 707         if s not in p.usyms:
 708             p.usyms.append(s)
 709
 710     # Add to the global productions list
 711     try:
 712         Prodnames[p.name].append(p)
 713     except KeyError:
 714         Prodnames[p.name] = [ p ]
 715     return 0
 716
 717 # Given a raw rule function, this function rips out its doc string
 718 # and adds rules to the grammar
 719
 720 def add_function(f):
 721     line = f.func_code.co_firstlineno
 722     file = f.func_code.co_filename
 723     error = 0
 724
 725     if isinstance(f,types.MethodType):
 726         reqdargs = 2
 727     else:
 728         reqdargs = 1
 729
 730     if f.func_code.co_argcount > reqdargs:
 731         sys.stderr.write("%s:%d: Rule '%s' has too many arguments.\n" % (file,line,f.__name__))
 732         return -1
 733
 734     if f.func_code.co_argcount < reqdargs:
 735         sys.stderr.write("%s:%d: Rule '%s' requires an argument.\n" % (file,line,f.__name__))
 736         return -1
 737
 738     if f.__doc__:
 739         # Split the doc string into lines
 740         pstrings = f.__doc__.splitlines()
 741         lastp = None
 742         dline = line
 743         for ps in pstrings:
 744             dline += 1
 745             p = ps.split()
 746             if not p: continue
 747             try:
 748                 if p[0] == '|':
 749                     # This is a continuation of a previous rule
 750                     if not lastp:
 751                         sys.stderr.write("%s:%d: Misplaced '|'.\n" % (file,dline))
 752                         return -1
 753                     prodname = lastp
 754                     if len(p) > 1:
 755                         syms = p[1:]
 756                     else:
 757                         syms = [ ]
 758                 else:
 759                     prodname = p[0]
 760                     lastp = prodname
 761                     assign = p[1]
 762                     if len(p) > 2:
 763                         syms = p[2:]
 764                     else:
 765                         syms = [ ]
 766                     if assign != ':' and assign != '::=':
 767                         sys.stderr.write("%s:%d: Syntax error. Expected ':'\n" % (file,dline))
 768                         return -1
 769                 e = add_production(f,file,dline,prodname,syms)
 770                 error += e
 771             except StandardError:
 772                 sys.stderr.write("%s:%d: Syntax error in rule '%s'\n" % (file,dline,ps))
 773                 error -= 1
 774     else:
 775         sys.stderr.write("%s:%d: No documentation string specified in function '%s'\n" % (file,line,f.__name__))
 776     return error
 777
 778
 779 # Cycle checking code (Michael Dyck)
 780
 781 def compute_reachable():
 782     '''
 783     Find each symbol that can be reached from the start symbol.
 784     Print a warning for any nonterminals that can't be reached.
 785     (Unused terminals have already had their warning.)
 786     '''
 787     Reachable = { }
 788     for s in Terminals.keys() + Nonterminals.keys():
 789         Reachable[s] = 0
 790
 791     mark_reachable_from( Productions[0].prod[0], Reachable )
 792
 793     for s in Nonterminals.keys():
 794         if not Reachable[s]:
 795             sys.stderr.write("yacc: Symbol '%s' is unreachable.\n" % s)
 796
 797 def mark_reachable_from(s, Reachable):
 798     '''
 799     Mark all symbols that are reachable from symbol s.
 800     '''
 801     if Reachable[s]:
 802         # We've already reached symbol s.
 803         return
 804     Reachable[s] = 1
 805     for p in Prodnames.get(s,[]):
 806         for r in p.prod:
 807             mark_reachable_from(r, Reachable)
 808
 809 # -----------------------------------------------------------------------------
 810 # compute_terminates()
 811 #
 812 # This function looks at the various parsing rules and tries to detect
 813 # infinite recursion cycles (grammar rules where there is no possible way
 814 # to derive a string of only terminals).
 815 # -----------------------------------------------------------------------------
 816 def compute_terminates():
 817     '''
 818     Raise an error for any symbols that don't terminate.
 819     '''
 820     Terminates = {}
 821
 822     # Terminals:
 823     for t in Terminals.keys():
 824         Terminates[t] = 1
 825
 826     Terminates['$'] = 1
 827
 828     # Nonterminals:
 829
 830     # Initialize to false:
 831     for n in Nonterminals.keys():
 832         Terminates[n] = 0
 833
 834     # Then propagate termination until no change:
 835     while 1:
 836         some_change = 0
 837         for (n,pl) in Prodnames.items():
 838             # Nonterminal n terminates iff any of its productions terminates.
 839             for p in pl:
 840                 # Production p terminates iff all of its rhs symbols terminate.
 841                 for s in p.prod:
 842                     if not Terminates[s]:
 843                         # The symbol s does not terminate,
 844                         # so production p does not terminate.
 845                         p_terminates = 0
 846                         break
 847                 else:
 848                     # didn't break from the loop,
 849                     # so every symbol s terminates
 850                     # so production p terminates.
 851                     p_terminates = 1
 852
 853                 if p_terminates:
 854                     # symbol n terminates!
 855                     if not Terminates[n]:
 856                         Terminates[n] = 1
 857                         some_change = 1
 858                     # Don't need to consider any more productions for this n.
 859                     break
 860
 861         if not some_change:
 862             break
 863
 864     some_error = 0
 865     for (s,terminates) in Terminates.items():
 866         if not terminates:
 867             if not Prodnames.has_key(s) and not Terminals.has_key(s) and s != 'error':
 868                 # s is used-but-not-defined, and we've already warned of that,
 869                 # so it would be overkill to say that it's also non-terminating.
 870                 pass
 871             else:
 872                 sys.stderr.write("yacc: Infinite recursion detected for symbol '%s'.\n" % s)
 873                 some_error = 1
 874
 875     return some_error
 876
 877 # -----------------------------------------------------------------------------
 878 # verify_productions()
 879 #
 880 # This function examines all of the supplied rules to see if they seem valid.
 881 # -----------------------------------------------------------------------------
 882 def verify_productions(cycle_check=1):
 883     error = 0
 884     for p in Productions:
 885         if not p: continue
 886
 887         for s in p.prod:
 888             if not Prodnames.has_key(s) and not Terminals.has_key(s) and s != 'error':
 889                 sys.stderr.write("%s:%d: Symbol '%s' used, but not defined as a token or a rule.\n" % (p.file,p.line,s))
 890                 error = 1
 891                 continue
 892
 893     unused_tok = 0
 894     # Now verify all of the tokens
 895     if yaccdebug:
 896         _vf.write("Unused terminals:\n\n")
 897     for s,v in Terminals.items():
 898         if s != 'error' and not v:
 899             sys.stderr.write("yacc: Warning. Token '%s' defined, but not used.\n" % s)
 900             if yaccdebug: _vf.write("   %s\n"% s)
 901             unused_tok += 1
 902
 903     # Print out all of the productions
 904     if yaccdebug:
 905         _vf.write("\nGrammar\n\n")
 906         for i in range(1,len(Productions)):
 907             _vf.write("Rule %-5d %s\n" % (i, Productions[i]))
 908
 909     unused_prod = 0
 910     # Verify the use of all productions
 911     for s,v in Nonterminals.items():
 912         if not v:
 913             p = Prodnames[s][0]
 914             sys.stderr.write("%s:%d: Warning. Rule '%s' defined, but not used.\n" % (p.file,p.line, s))
 915             unused_prod += 1
 916
 917
 918     if unused_tok == 1:
 919         sys.stderr.write("yacc: Warning. There is 1 unused token.\n")
 920     if unused_tok > 1:
 921         sys.stderr.write("yacc: Warning. There are %d unused tokens.\n" % unused_tok)
 922
 923     if unused_prod == 1:
 924         sys.stderr.write("yacc: Warning. There is 1 unused rule.\n")
 925     if unused_prod > 1:
 926         sys.stderr.write("yacc: Warning. There are %d unused rules.\n" % unused_prod)
 927
 928     if yaccdebug:
 929         _vf.write("\nTerminals, with rules where they appear\n\n")
 930         ks = Terminals.keys()
 931         ks.sort()
 932         for k in ks:
 933             _vf.write("%-20s : %s\n" % (k, " ".join([str(s) for s in Terminals[k]])))
 934         _vf.write("\nNonterminals, with rules where they appear\n\n")
 935         ks = Nonterminals.keys()
 936         ks.sort()
 937         for k in ks:
 938             _vf.write("%-20s : %s\n" % (k, " ".join([str(s) for s in Nonterminals[k]])))
 939
 940     if (cycle_check):
 941         compute_reachable()
 942         error += compute_terminates()
 943 #        error += check_cycles()
 944     return error
 945
 946 # -----------------------------------------------------------------------------
 947 # build_lritems()
 948 #
 949 # This function walks the list of productions and builds a complete set of the
 950 # LR items.  The LR items are stored in two ways:  First, they are uniquely
 951 # numbered and placed in the list _lritems.  Second, a linked list of LR items
 952 # is built for each production.  For example:
 953 #
 954 #   E -> E PLUS E
 955 #
 956 # Creates the list
 957 #
 958 #  [E -> . E PLUS E, E -> E . PLUS E, E -> E PLUS . E, E -> E PLUS E . ]
 959 # -----------------------------------------------------------------------------
 960
 961 def build_lritems():
 962     for p in Productions:
 963         lastlri = p
 964         lri = p.lr_item(0)
 965         i = 0
 966         while 1:
 967             lri = p.lr_item(i)
 968             lastlri.lr_next = lri
 969             if not lri: break
 970             lri.lr_num = len(LRitems)
 971             LRitems.append(lri)
 972             lastlri = lri
 973             i += 1
 974
 975     # In order for the rest of the parser generator to work, we need to
 976     # guarantee that no more lritems are generated.  Therefore, we nuke
 977     # the p.lr_item method.  (Only used in debugging)
 978     # Production.lr_item = None
 979
 980 # -----------------------------------------------------------------------------
 981 # add_precedence()
 982 #
 983 # Given a list of precedence rules, add to the precedence table.
 984 # -----------------------------------------------------------------------------
 985
 986 def add_precedence(plist):
 987     plevel = 0
 988     error = 0
 989     for p in plist:
 990         plevel += 1
 991         try:
 992             prec = p[0]
 993             terms = p[1:]
 994             if prec != 'left' and prec != 'right' and prec != 'nonassoc':
 995                 sys.stderr.write("yacc: Invalid precedence '%s'\n" % prec)
 996                 return -1
 997             for t in terms:
 998                 if Precedence.has_key(t):
 999                     sys.stderr.write("yacc: Precedence already specified for terminal '%s'\n" % t)
1000                     error += 1
1001                     continue
1002                 Precedence[t] = (prec,plevel)
1003         except:
1004             sys.stderr.write("yacc: Invalid precedence table.\n")
1005             error += 1
1006
1007     return error
1008
1009 # -----------------------------------------------------------------------------
1010 # augment_grammar()
1011 #
1012 # Compute the augmented grammar.  This is just a rule S' -> start where start
1013 # is the starting symbol.
1014 # -----------------------------------------------------------------------------
1015
1016 def augment_grammar(start=None):
1017     if not start:
1018         start = Productions[1].name
1019     Productions[0] = Production(name="S'",prod=[start],number=0,len=1,prec=('right',0),func=None)
1020     Productions[0].usyms = [ start ]
1021     Nonterminals[start].append(0)
1022
1023
1024 # -------------------------------------------------------------------------
1025 # first()
1026 #
1027 # Compute the value of FIRST1(beta) where beta is a tuple of symbols.
1028 #
1029 # During execution of compute_first1, the result may be incomplete.
1030 # Afterward (e.g., when called from compute_follow()), it will be complete.
1031 # -------------------------------------------------------------------------
1032 def first(beta):
1033
1034     # We are computing First(x1,x2,x3,...,xn)
1035     result = [ ]
1036     for x in beta:
1037         x_produces_empty = 0
1038
1039         # Add all the non-<empty> symbols of First[x] to the result.
1040         for f in First[x]:
1041             if f == '<empty>':
1042                 x_produces_empty = 1
1043             else:
1044                 if f not in result: result.append(f)
1045
1046         if x_produces_empty:
1047             # We have to consider the next x in beta,
1048             # i.e. stay in the loop.
1049             pass
1050         else:
1051             # We don't have to consider any further symbols in beta.
1052             break
1053     else:
1054         # There was no 'break' from the loop,
1055         # so x_produces_empty was true for all x in beta,
1056         # so beta produces empty as well.
1057         result.append('<empty>')
1058
1059     return result
1060
1061
1062 # FOLLOW(x)
1063 # Given a non-terminal.  This function computes the set of all symbols
1064 # that might follow it.  Dragon book, p. 189.
1065
1066 def compute_follow(start=None):
1067     # Add '$' to the follow list of the start symbol
1068     for k in Nonterminals.keys():
1069         Follow[k] = [ ]
1070
1071     if not start:
1072         start = Productions[1].name
1073
1074     Follow[start] = [ '$' ]
1075
1076     while 1:
1077         didadd = 0
1078         for p in Productions[1:]:
1079             # Here is the production set
1080             for i in range(len(p.prod)):
1081                 B = p.prod[i]
1082                 if Nonterminals.has_key(B):
1083                     # Okay. We got a non-terminal in a production
1084                     fst = first(p.prod[i+1:])
1085                     hasempty = 0
1086                     for f in fst:
1087                         if f != '<empty>' and f not in Follow[B]:
1088                             Follow[B].append(f)
1089                             didadd = 1
1090                         if f == '<empty>':
1091                             hasempty = 1
1092                     if hasempty or i == (len(p.prod)-1):
1093                         # Add elements of follow(a) to follow(b)
1094                         for f in Follow[p.name]:
1095                             if f not in Follow[B]:
1096                                 Follow[B].append(f)
1097                                 didadd = 1
1098         if not didadd: break
1099
1100     if 0 and yaccdebug:
1101         _vf.write('\nFollow:\n')
1102         for k in Nonterminals.keys():
1103             _vf.write("%-20s : %s\n" % (k, " ".join([str(s) for s in Follow[k]])))
1104
1105 # -------------------------------------------------------------------------
1106 # compute_first1()
1107 #
1108 # Compute the value of FIRST1(X) for all symbols
1109 # -------------------------------------------------------------------------
1110 def compute_first1():
1111
1112     # Terminals:
1113     for t in Terminals.keys():
1114         First[t] = [t]
1115
1116     First['$'] = ['$']
1117     First['#'] = ['#'] # what's this for?
1118
1119     # Nonterminals:
1120
1121     # Initialize to the empty set:
1122     for n in Nonterminals.keys():
1123         First[n] = []
1124
1125     # Then propagate symbols until no change:
1126     while 1:
1127         some_change = 0
1128         for n in Nonterminals.keys():
1129             for p in Prodnames[n]:
1130                 for f in first(p.prod):
1131                     if f not in First[n]:
1132                         First[n].append( f )
1133                         some_change = 1
1134         if not some_change:
1135             break
1136
1137     if 0 and yaccdebug:
1138         _vf.write('\nFirst:\n')
1139         for k in Nonterminals.keys():
1140             _vf.write("%-20s : %s\n" %
1141                 (k, " ".join([str(s) for s in First[k]])))
1142
1143 # -----------------------------------------------------------------------------
1144 #                           === SLR Generation ===
1145 #
1146 # The following functions are used to construct SLR (Simple LR) parsing tables
1147 # as described on p.221-229 of the dragon book.
1148 # -----------------------------------------------------------------------------
1149
1150 # Global variables for the LR parsing engine
1151 def lr_init_vars():
1152     global _lr_action, _lr_goto, _lr_method
1153     global _lr_goto_cache, _lr0_cidhash
1154
1155     _lr_action       = { }        # Action table
1156     _lr_goto         = { }        # Goto table
1157     _lr_method       = "Unknown"  # LR method used
1158     _lr_goto_cache   = { }
1159     _lr0_cidhash     = { }
1160
1161
1162 # Compute the LR(0) closure operation on I, where I is a set of LR(0) items.
1163 # prodlist is a list of productions.
1164
1165 _add_count = 0       # Counter used to detect cycles
1166
1167 def lr0_closure(I):
1168     global _add_count
1169
1170     _add_count += 1
1171     prodlist = Productions
1172
1173     # Add everything in I to J
1174     J = I[:]
1175     didadd = 1
1176     while didadd:
1177         didadd = 0
1178         for j in J:
1179             for x in j.lrafter:
1180                 if x.lr0_added == _add_count: continue
1181                 # Add B --> .G to J
1182                 J.append(x.lr_next)
1183                 x.lr0_added = _add_count
1184                 didadd = 1
1185
1186     return J
1187
1188 # Compute the LR(0) goto function goto(I,X) where I is a set
1189 # of LR(0) items and X is a grammar symbol.   This function is written
1190 # in a way that guarantees uniqueness of the generated goto sets
1191 # (i.e. the same goto set will never be returned as two different Python
1192 # objects).  With uniqueness, we can later do fast set comparisons using
1193 # id(obj) instead of element-wise comparison.
1194
1195 def lr0_goto(I,x):
1196     # First we look for a previously cached entry
1197     g = _lr_goto_cache.get((id(I),x),None)
1198     if g: return g
1199
1200     # Now we generate the goto set in a way that guarantees uniqueness
1201     # of the result
1202
1203     s = _lr_goto_cache.get(x,None)
1204     if not s:
1205         s = { }
1206         _lr_goto_cache[x] = s
1207
1208     gs = [ ]
1209     for p in I:
1210         n = p.lr_next
1211         if n and n.lrbefore == x:
1212             s1 = s.get(id(n),None)
1213             if not s1:
1214                 s1 = { }
1215                 s[id(n)] = s1
1216             gs.append(n)
1217             s = s1
1218     g = s.get('$',None)
1219     if not g:
1220         if gs:
1221             g = lr0_closure(gs)
1222             s['$'] = g
1223         else:
1224             s['$'] = gs
1225     _lr_goto_cache[(id(I),x)] = g
1226     return g
1227
1228 # Added for LALR(1)
1229
1230 # Given a setnumber of an lr0 state and a symbol return the setnumber of the goto state
1231 def lr0_goto_setnumber(I_setnumber, x):
1232     global Canonical
1233     global GotoSetNum
1234
1235     if GotoSetNum.has_key((I_setnumber, x)):
1236         setnumber = GotoSetNum[(I_setnumber, x)]
1237     else:
1238         gset = lr0_goto(Canonical[I_setnumber], x)
1239         if not gset:
1240             return -1
1241         else:
1242             gsetlen = len(gset)
1243             for i in xrange(len(gset[0].setnumbers)):
1244                 inall = 1
1245                 for item in gset:
1246                     if not item.setnumbers[i]:
1247                         inall = 0
1248                         break
1249                 if inall and len(Canonical[i]) == gsetlen:
1250                     setnumber = i
1251                     break          # Note: DB. I added this to improve performance.
1252                                    # Not sure if this breaks the algorithm (it doesn't appear to).
1253
1254             GotoSetNum[(I_setnumber, x)] = setnumber
1255
1256     return setnumber
1257
1258 # Compute the kernel of a set of LR(0) items
1259 def lr0_kernel(I):
1260     KI = [ ]
1261     for p in I:
1262         if p.name == "S'" or p.lr_index > 0 or p.len == 0:
1263             KI.append(p)
1264
1265     return KI
1266
1267 _lr0_cidhash = { }
1268
1269 # Compute the LR(0) sets of item function
1270 def lr0_items():
1271
1272     C = [ lr0_closure([Productions[0].lr_next]) ]
1273     i = 0
1274     for I in C:
1275         _lr0_cidhash[id(I)] = i
1276         i += 1
1277
1278     # Loop over the items in C and each grammar symbols
1279     i = 0
1280     while i < len(C):
1281         I = C[i]
1282         i += 1
1283
1284         # Collect all of the symbols that could possibly be in the goto(I,X) sets
1285         asyms = { }
1286         for ii in I:
1287             for s in ii.usyms:
1288                 asyms[s] = None
1289
1290         for x in asyms.keys():
1291             g = lr0_goto(I,x)
1292             if not g:  continue
1293             if _lr0_cidhash.has_key(id(g)): continue
1294             _lr0_cidhash[id(g)] = len(C)
1295             C.append(g)
1296
1297     return C
1298
1299 # -----------------------------------------------------------------------------
1300 # slr_parse_table()
1301 #
1302 # This function constructs an SLR table.
1303 # -----------------------------------------------------------------------------
1304 def slr_parse_table():
1305     global _lr_method
1306     goto = _lr_goto           # Goto array
1307     action = _lr_action       # Action array
1308     actionp = { }             # Action production array (temporary)
1309
1310     _lr_method = "SLR"
1311
1312     n_srconflict = 0
1313     n_rrconflict = 0
1314
1315     if yaccdebug:
1316         sys.stderr.write("yacc: Generating SLR parsing table...\n")
1317         _vf.write("\n\nParsing method: SLR\n\n")
1318
1319     # Step 1: Construct C = { I0, I1, ... IN}, collection of LR(0) items
1320     # This determines the number of states
1321
1322     C = lr0_items()
1323
1324     # Build the parser table, state by state
1325     st = 0
1326     for I in C:
1327         # Loop over each production in I
1328         actlist = [ ]              # List of actions
1329
1330         if yaccdebug:
1331             _vf.write("\nstate %d\n\n" % st)
1332             for p in I:
1333                 _vf.write("    (%d) %s\n" % (p.number, str(p)))
1334             _vf.write("\n")
1335
1336         for p in I:
1337             try:
1338                 if p.prod[-1] == ".":
1339                     if p.name == "S'":
1340                         # Start symbol. Accept!
1341                         action[st,"$"] = 0
1342                         actionp[st,"$"] = p
1343                     else:
1344                         # We are at the end of a production.  Reduce!
1345                         for a in Follow[p.name]:
1346                             actlist.append((a,p,"reduce using rule %d (%s)" % (p.number,p)))
1347                             r = action.get((st,a),None)
1348                             if r is not None:
1349                                 # Whoa. Have a shift/reduce or reduce/reduce conflict
1350                                 if r > 0:
1351                                     # Need to decide on shift or reduce here
1352                                     # By default we favor shifting. Need to add
1353                                     # some precedence rules here.
1354                                     sprec,slevel = Productions[actionp[st,a].number].prec
1355                                     rprec,rlevel = Precedence.get(a,('right',0))
1356                                     if (slevel < rlevel) or ((slevel == rlevel) and (rprec == 'left')):
1357                                         # We really need to reduce here.
1358                                         action[st,a] = -p.number
1359                                         actionp[st,a] = p
1360                                         if not slevel and not rlevel:
1361                                             _vfc.write("shift/reduce conflict in state %d resolved as reduce.\n" % st)
1362                                             _vf.write("  ! shift/reduce conflict for %s resolved as reduce.\n" % a)
1363                                             n_srconflict += 1
1364                                     elif (slevel == rlevel) and (rprec == 'nonassoc'):
1365                                         action[st,a] = None
1366                                     else:
1367                                         # Hmmm. Guess we'll keep the shift
1368                                         if not slevel and not rlevel:
1369                                             _vfc.write("shift/reduce conflict in state %d resolved as shift.\n" % st)
1370                                             _vf.write("  ! shift/reduce conflict for %s resolved as shift.\n" % a)
1371                                             n_srconflict +=1
1372                                 elif r < 0:
1373                                     # Reduce/reduce conflict.   In this case, we favor the rule
1374                                     # that was defined first in the grammar file
1375                                     oldp = Productions[-r]
1376                                     pp = Productions[p.number]
1377                                     if oldp.line > pp.line:
1378                                         action[st,a] = -p.number
1379                                         actionp[st,a] = p
1380                                     # sys.stderr.write("Reduce/reduce conflict in state %d\n" % st)
1381                                     n_rrconflict += 1
1382                                     _vfc.write("reduce/reduce conflict in state %d resolved using rule %d (%s).\n" % (st, actionp[st,a].number, actionp[st,a]))
1383                                     _vf.write("  ! reduce/reduce conflict for %s resolved using rule %d (%s).\n" % (a,actionp[st,a].number, actionp[st,a]))
1384                                 else:
1385                                     sys.stderr.write("Unknown conflict in state %d\n" % st)
1386                             else:
1387                                 action[st,a] = -p.number
1388                                 actionp[st,a] = p
1389                 else:
1390                     i = p.lr_index
1391                     a = p.prod[i+1]       # Get symbol right after the "."
1392                     if Terminals.has_key(a):
1393                         g = lr0_goto(I,a)
1394                         j = _lr0_cidhash.get(id(g),-1)
1395                         if j >= 0:
1396                             # We are in a shift state
1397                             actlist.append((a,p,"shift and go to state %d" % j))
1398                             r = action.get((st,a),None)
1399                             if r is not None:
1400                                 # Whoa have a shift/reduce or shift/shift conflict
1401                                 if r > 0:
1402                                     if r != j:
1403                                         sys.stderr.write("Shift/shift conflict in state %d\n" % st)
1404                                 elif r < 0:
1405                                     # Do a precedence check.
1406                                     #   -  if precedence of reduce rule is higher, we reduce.
1407                                     #   -  if precedence of reduce is same and left assoc, we reduce.
1408                                     #   -  otherwise we shift
1409                                     rprec,rlevel = Productions[actionp[st,a].number].prec
1410                                     sprec,slevel = Precedence.get(a,('right',0))
1411                                     if (slevel > rlevel) or ((slevel == rlevel) and (rprec != 'left')):
1412                                         # We decide to shift here... highest precedence to shift
1413                                         action[st,a] = j
1414                                         actionp[st,a] = p
1415                                         if not slevel and not rlevel:
1416                                             n_srconflict += 1
1417                                             _vfc.write("shift/reduce conflict in state %d resolved as shift.\n" % st)
1418                                             _vf.write("  ! shift/reduce conflict for %s resolved as shift.\n" % a)
1419                                     elif (slevel == rlevel) and (rprec == 'nonassoc'):
1420                                         action[st,a] = None
1421                                     else:
1422                                         # Hmmm. Guess we'll keep the reduce
1423                                         if not slevel and not rlevel:
1424                                             n_srconflict +=1
1425                                             _vfc.write("shift/reduce conflict in state %d resolved as reduce.\n" % st)
1426                                             _vf.write("  ! shift/reduce conflict for %s resolved as reduce.\n" % a)
1427
1428                                 else:
1429                                     sys.stderr.write("Unknown conflict in state %d\n" % st)
1430                             else:
1431                                 action[st,a] = j
1432                                 actionp[st,a] = p
1433
1434             except StandardError,e:
1435                 raise YaccError, "Hosed in slr_parse_table", e
1436
1437         # Print the actions associated with each terminal
1438         if yaccdebug:
1439           _actprint = { }
1440           for a,p,m in actlist:
1441             if action.has_key((st,a)):
1442                 if p is actionp[st,a]:
1443                     _vf.write("    %-15s %s\n" % (a,m))
1444                     _actprint[(a,m)] = 1
1445           _vf.write("\n")
1446           for a,p,m in actlist:
1447             if action.has_key((st,a)):
1448                 if p is not actionp[st,a]:
1449                     if not _actprint.has_key((a,m)):
1450                         _vf.write("  ! %-15s [ %s ]\n" % (a,m))
1451                         _actprint[(a,m)] = 1
1452
1453         # Construct the goto table for this state
1454         if yaccdebug:
1455             _vf.write("\n")
1456         nkeys = { }
1457         for ii in I:
1458             for s in ii.usyms:
1459                 if Nonterminals.has_key(s):
1460                     nkeys[s] = None
1461         for n in nkeys.keys():
1462             g = lr0_goto(I,n)
1463             j = _lr0_cidhash.get(id(g),-1)
1464             if j >= 0:
1465                 goto[st,n] = j
1466                 if yaccdebug:
1467                     _vf.write("    %-30s shift and go to state %d\n" % (n,j))
1468
1469         st += 1
1470
1471     if yaccdebug:
1472         if n_srconflict == 1:
1473             sys.stderr.write("yacc: %d shift/reduce conflict\n" % n_srconflict)
1474         if n_srconflict > 1:
1475             sys.stderr.write("yacc: %d shift/reduce conflicts\n" % n_srconflict)
1476         if n_rrconflict == 1:
1477             sys.stderr.write("yacc: %d reduce/reduce conflict\n" % n_rrconflict)
1478         if n_rrconflict > 1:
1479             sys.stderr.write("yacc: %d reduce/reduce conflicts\n" % n_rrconflict)
1480
1481
1482
1483 # -----------------------------------------------------------------------------
1484 #                       ==== LALR(1) Parsing ====
1485 # FINISHED!  5/20/2003 by Elias Ioup
1486 # -----------------------------------------------------------------------------
1487
1488
1489 # Compute the lr1_closure of a set I.  I is a list of productions and setnumber
1490 # is the state that you want the lr items that are made from the to come from.
1491
1492 _lr1_add_count = 0
1493
1494 def lr1_closure(I, setnumber = 0):
1495     global _add_count
1496     global Nonterminals
1497
1498     _add_count += 1
1499     prodlist = Productions
1500
1501     # Add everything in I to J
1502     J = I[:]
1503     Jhash = { }
1504     for j in J:
1505         Jhash[id(j)] = 1
1506
1507     didadd = 1
1508     while didadd:
1509         didadd = 0
1510         for j in J:
1511             jprod = j.prod
1512             jlr_index = j.lr_index
1513             jprodslice = jprod[jlr_index+2:]
1514
1515             if jlr_index < len(jprod) - 1 and Nonterminals.has_key(jprod[jlr_index+1]):
1516                 first_syms = []
1517
1518                 if j.lk_added.setdefault(setnumber, 0) < len(j.lookaheads[setnumber]):
1519                     for a in j.lookaheads[setnumber][j.lk_added[setnumber]:]:
1520                         # find b in FIRST(Xa) if j = [A->a.BX,a]
1521                         temp_first_syms = first(jprodslice + (a,))
1522                         for x in temp_first_syms:
1523                             if x not in first_syms:
1524                                 first_syms.append(x)
1525
1526                 j.lk_added[setnumber] = len(j.lookaheads[setnumber])
1527
1528                 for x in j.lrafter:
1529
1530                     # Add B --> .G to J
1531                     if x.lr_next.lookaheads.has_key(setnumber):
1532                         _xlook = x.lr_next.lookaheads[setnumber]
1533                         for s in first_syms:
1534                             if s not in _xlook:
1535                                 _xlook.append(s)
1536                                 didadd = 1
1537                     else:
1538                         x.lr_next.lookaheads[setnumber] = first_syms
1539                         didadd = 1
1540
1541                     nid = id(x.lr_next)
1542                     if not Jhash.has_key(nid):
1543                         J.append(x.lr_next)
1544                         Jhash[nid] = 1
1545
1546     return J
1547
1548 def add_lookaheads(K):
1549     spontaneous = []
1550     propogate = []
1551
1552     for setnumber in range(len(K)):
1553         for kitem in K[setnumber]:
1554             kitem.lookaheads[setnumber] = ['#']
1555             J = lr1_closure([kitem], setnumber)
1556
1557             # find the lookaheads that are spontaneously created from closures
1558             # and the propogations of lookaheads between lr items
1559             for item in J:
1560                 if item.lr_index < len(item.prod)-1:
1561                     for lookahead in item.lookaheads[setnumber]:
1562                         goto_setnumber = lr0_goto_setnumber(setnumber, item.prod[item.lr_index+1])
1563                         next = None
1564                         if lookahead != '#':
1565                             if item.lr_next in K[goto_setnumber]:
1566                                 next = item.lr_next
1567                             if next:
1568                                 spontaneous.append((next, (lookahead, goto_setnumber)))
1569                         else:
1570                             if goto_setnumber > -1:
1571                                 if item.lr_next in K[goto_setnumber]:
1572                                     next = item.lr_next
1573
1574                             if next:
1575                                 propogate.append(((kitem, setnumber), (next, goto_setnumber)))
1576
1577
1578
1579         for x in K[setnumber]:
1580             x.lookaheads[setnumber] = []
1581
1582     for x in spontaneous:
1583         if x[1][0] not in x[0].lookaheads[x[1][1]]:
1584             x[0].lookaheads[x[1][1]].append(x[1][0])
1585
1586     K[0][0].lookaheads[0] = ['$']
1587
1588     pitems = {}
1589     for x in propogate:
1590         if pitems.has_key(x[0]):
1591             pitems[x[0]].append(x[1])
1592         else:
1593             pitems[x[0]] = []
1594             pitems[x[0]].append(x[1])
1595
1596     # propogate the lookaheads that were spontaneously generated
1597     # based on the propogations produced above
1598     stop = 0
1599
1600     while not stop:
1601         stop = 1
1602         kindex = 0
1603         for set in K:
1604             for item in set:
1605                 pkey = (item, kindex)
1606                 if pitems.has_key(pkey):
1607                     for propogation in pitems[pkey]:
1608                         gitem = propogation[0]
1609                         gsetnumber = propogation[1]
1610                         glookaheads = gitem.lookaheads[gsetnumber]
1611                         for lookahead in item.lookaheads[kindex]:
1612                             if lookahead not in glookaheads:
1613                                 glookaheads.append(lookahead)
1614                                 stop = 0
1615             kindex += 1
1616
1617 def ReduceNonterminals():
1618     global Nonterminals
1619
1620     global TReductions
1621     global NTReductions
1622
1623     for nt in Nonterminals.keys():
1624         TReductions[nt] = []
1625         NTReductions[nt] = []
1626
1627     for nt in Nonterminals.keys():
1628         terms = ReduceToTerminals(nt)
1629         TReductions[nt].extend(terms)
1630         if not NTReductions.has_key(nt):
1631             ReduceToNonterminals(nt)
1632
1633
1634
1635 def ReduceToTerminals(nt,cyclemap=None):
1636     global Prodnames
1637     global Terminals
1638     reducedterminals = []
1639     if not cyclemap: cyclemap = {}
1640
1641     if cyclemap.has_key(nt): return []
1642     cyclemap[nt] = 1
1643
1644     for p in Prodnames[nt]:
1645         if len(p.prod) > 0:
1646             if Terminals.has_key(p.prod[0]):
1647                 if p.prod[0] not in reducedterminals:
1648                     reducedterminals.append(p.prod[0])
1649             else:
1650                 if p.prod[0] != nt:
1651                     terms = ReduceToTerminals(p.prod[0],cyclemap)
1652                     for t in terms:
1653                         if t not in reducedterminals:
1654                             reducedterminals.append(t)
1655     del cyclemap[nt]
1656     return reducedterminals
1657
1658
1659 def ReduceToNonterminals(nt):
1660     global Prodnames
1661     global Nonterminals
1662     global NTReductions
1663     reducednonterminals = []
1664
1665     for p in Prodnames[nt]:
1666         if len(p.prod) > 0:
1667             if Nonterminals.has_key(p.prod[0]):
1668                 if p.prod[0] not in reducednonterminals:
1669                     reducednonterminals.append(p.prod[0])
1670                     if p.prod[0] != nt:
1671                         if not NTReductions.has_key(p.prod[0]):
1672                             ReduceToNonterminals(p.prod[0])
1673
1674                         nterms = NTReductions[p.prod[0]]
1675                         for nt in nterms:
1676                             if nt not in reducednonterminals:
1677                                 reducednonterminals.append(nt)
1678
1679
1680     NTReductions[nt] = reducednonterminals
1681
1682 # -----------------------------------------------------------------------------
1683 # lalr_parse_table()
1684 #
1685 # This function constructs an LALR table.
1686 # -----------------------------------------------------------------------------
1687 def lalr_parse_table():
1688     global _lr_method
1689     goto = _lr_goto           # Goto array
1690     action = _lr_action       # Action array
1691     actionp = { }             # Action production array (temporary)
1692     goto_cache = _lr_goto_cache
1693     cid_hash = _lr0_cidhash
1694
1695     _lr_method = "LALR"
1696
1697     n_srconflict = 0
1698     n_rrconflict = 0
1699
1700     if yaccdebug:
1701         sys.stderr.write("yacc: Generating LALR(1) parsing table...\n")
1702         _vf.write("\n\nParsing method: LALR(1)\n\n")
1703
1704     # Step 1: Construct C = { I0, I1, ... IN}, collection of LR(0) items
1705     # This determines the number of states
1706
1707     C = lr0_items()
1708
1709     global Canonical
1710     Canonical = C
1711
1712     ###
1713     # Create the kernel states.
1714     ###
1715     K = []
1716     setC = [0]*len(C)
1717     for x in C:
1718         K.append(lr0_kernel(x))
1719         for y in x:
1720             y.setnumbers = setC[:]
1721
1722     _cindex = 0
1723     for x in C:
1724         for y in x:
1725             y.lookaheads[_cindex] = []
1726             y.setnumbers[_cindex] = 1
1727         _cindex = _cindex + 1
1728
1729     ###
1730     # Add lookaheads to the lr items
1731     ###
1732
1733     add_lookaheads(K)
1734
1735     ###
1736     # Do the reductions for parsing first and keep them in globals
1737     ###
1738
1739     ReduceNonterminals()
1740
1741     global TReductions
1742     global NTReductions
1743     global Prodempty
1744
1745     EmptyAncestors = {}
1746     for y in Prodempty.keys():
1747         EmptyAncestors[y] = []
1748     for x in NTReductions.items():
1749         for y in x[1]:
1750             if Prodempty.has_key(y):
1751                 EmptyAncestors[y].append(x[0])
1752
1753
1754     # Build the parser table, state by state
1755     st = 0
1756     for I in C:
1757         # Loop over each production in I
1758         actlist = [ ]              # List of actions
1759         acthash = { }
1760
1761         idI = id(I)
1762
1763         if yaccdebug:
1764             _vf.write("\nstate %d\n\n" % st)
1765             for p in I:
1766                 _vf.write("    (%d) %s\n" % (p.number, str(p)))
1767             _vf.write("\n")
1768
1769         global First
1770         for p in I:
1771             try:
1772                 if p.prod[-1] == ".":
1773                     if p.name == "S'":
1774                         # Start symbol. Accept!
1775                         action[st,"$"] = 0
1776                         actionp[st,"$"] = p
1777                     elif len(p.prod) == 0:
1778                         ancestors = EmptyAncestors[p.name]
1779                         for i in ancestors:
1780                             for s in K:
1781                                 if i in s:
1782                                     input_list = []
1783                                     plist = Productions[i.name]
1784                                     for x in plist:
1785                                         if len(x.prod) > 0 and x.prod[0] == p.name:
1786                                             n = p.prod[1:]
1787                                             d = x.prod[lr_index+2:]
1788                                             for l in x.lookaheads.items():
1789                                                 flist = First[tuple(n+d+[l])]
1790                                                 for f in flist:
1791                                                     if f not in input_list and f in p.lookaheads[st]:
1792                                                         input_list.append(f)
1793
1794                                     # We are at the end of a production.  Reduce!
1795                                     #print "input_list: %s" % input_list
1796                                     #print "Follow[p.name]: %s" % Follow[p.name]
1797                                     for a in input_list:
1798                                         actlist.append((a,p,"reduce using rule %d (%s) " % (p.number,p)))
1799                                         r = action.get((st,a),None)
1800                                         if r is not None:
1801                                             # Whoa. Have a shift/reduce or reduce/reduce conflict
1802                                             if r > 0:
1803                                                 # Need to decide on shift or reduce here
1804                                                 # By default we favor shifting. Need to add
1805                                                 # some precedence rules here.
1806                                                 sprec,slevel = Productions[actionp[st,a].number].prec
1807                                                 rprec,rlevel = Precedence.get(a,('right',0))
1808                                                 if (slevel < rlevel) or ((slevel == rlevel) and (rprec == 'left')):
1809                                                     # We really need to reduce here.
1810                                                     action[st,a] = -p.number
1811                                                     actionp[st,a] = p
1812                                                     if not slevel and not rlevel:
1813                                                         _vfc.write("shift/reduce conflict in state %d resolved as reduce.\n" % st)
1814                                                         _vf.write("  ! shift/reduce conflict for %s resolved as reduce.\n" % a)
1815                                                         n_srconflict += 1
1816                                                 elif (slevel == rlevel) and (rprec == 'nonassoc'):
1817                                                     action[st,a] = None
1818                                                 else:
1819                                                     # Hmmm. Guess we'll keep the shift
1820                                                     if not slevel and not rlevel:
1821                                                         _vfc.write("shift/reduce conflict in state %d resolved as shift.\n" % st)
1822                                                         _vf.write("  ! shift/reduce conflict for %s resolved as shift.\n" % a)
1823                                                         n_srconflict +=1
1824                                             elif r < 0:
1825                                                 # Reduce/reduce conflict.   In this case, we favor the rule
1826                                                 # that was defined first in the grammar file
1827                                                 oldp = Productions[-r]
1828                                                 pp = Productions[p.number]
1829                                                 if oldp.line > pp.line:
1830                                                     action[st,a] = -p.number
1831                                                     actionp[st,a] = p
1832                                                     # print "Reduce/reduce conflict in state %d" % st
1833                                                     n_rrconflict += 1
1834                                                     _vfc.write("reduce/reduce conflict in state %d resolved using rule %d.\n" % (st, actionp[st,a].number))
1835                                                     _vf.write("  ! reduce/reduce conflict for %s resolved using rule %d.\n" % (a,actionp[st,a].number))
1836                                             else:
1837                                                 sys.stderr.write("Unknown conflict in state %d\n" % st)
1838                                         else:
1839                                             action[st,a] = -p.number
1840                                             actionp[st,a] = p
1841
1842                                     break           # break out of the for s in K loop because we only want to make
1843                                                     # sure that a production is in the Kernel
1844
1845                     else:
1846                         # We are at the end of a production.  Reduce!
1847
1848                         for a in p.lookaheads[st]:
1849                             actlist.append((a,p,"reduce using rule %d (%s)" % (p.number,p)))
1850                             r = action.get((st,a),None)
1851                             if r is not None:
1852                                 # Whoa. Have a shift/reduce or reduce/reduce conflict
1853                                 if r > 0:
1854                                     # Need to decide on shift or reduce here
1855                                     # By default we favor shifting. Need to add
1856                                     # some precedence rules here.
1857                                     sprec,slevel = Productions[actionp[st,a].number].prec
1858                                     rprec,rlevel = Precedence.get(a,('right',0))
1859                                     if (slevel < rlevel) or ((slevel == rlevel) and (rprec == 'left')):
1860                                         # We really need to reduce here.
1861                                         action[st,a] = -p.number
1862                                         actionp[st,a] = p
1863                                         if not slevel and not rlevel:
1864                                             _vfc.write("shift/reduce conflict in state %d resolved as reduce.\n" % st)
1865                                             _vf.write("  ! shift/reduce conflict for %s resolved as reduce.\n" % a)
1866                                             n_srconflict += 1
1867                                     elif (slevel == rlevel) and (rprec == 'nonassoc'):
1868                                         action[st,a] = None
1869                                     else:
1870                                         # Hmmm. Guess we'll keep the shift
1871                                         if not slevel and not rlevel:
1872                                             _vfc.write("shift/reduce conflict in state %d resolved as shift.\n" % st)
1873                                             _vf.write("  ! shift/reduce conflict for %s resolved as shift.\n" % a)
1874                                             n_srconflict +=1
1875                                 elif r < 0:
1876                                     # Reduce/reduce conflict.   In this case, we favor the rule
1877                                     # that was defined first in the grammar file
1878                                     oldp = Productions[-r]
1879                                     pp = Productions[p.number]
1880                                     if oldp.line > pp.line:
1881                                         action[st,a] = -p.number
1882                                         actionp[st,a] = p
1883                                     # print "Reduce/reduce conflict in state %d" % st
1884                                     n_rrconflict += 1
1885                                     _vfc.write("reduce/reduce conflict in state %d resolved using rule %d.\n" % (st, actionp[st,a].number))
1886                                     _vf.write("  ! reduce/reduce conflict for %s resolved using rule %d.\n" % (a,actionp[st,a].number))
1887                                 else:
1888                                     print "Unknown conflict in state %d" % st
1889                             else:
1890                                 action[st,a] = -p.number
1891                                 actionp[st,a] = p
1892                 else:
1893                     i = p.lr_index
1894                     a = p.prod[i+1]       # Get symbol right after the "."
1895                     if Terminals.has_key(a):
1896                         g = goto_cache[(idI,a)]
1897                         j = cid_hash.get(id(g),-1)
1898                         if j >= 0:
1899                             # We are in a shift state
1900                             _k = (a,j)
1901                             if not acthash.has_key(_k):
1902                                 actlist.append((a,p,"shift and go to state %d" % j))
1903                                 acthash[_k] = 1
1904                             r = action.get((st,a),None)
1905                             if r is not None:
1906                                 # Whoa have a shift/reduce or shift/shift conflict
1907                                 if r > 0:
1908                                     if r != j:
1909                                         sys.stderr.write("Shift/shift conflict in state %d\n" % st)
1910                                 elif r < 0:
1911                                     # Do a precedence check.
1912                                     #   -  if precedence of reduce rule is higher, we reduce.
1913                                     #   -  if precedence of reduce is same and left assoc, we reduce.
1914                                     #   -  otherwise we shift
1915                                     rprec,rlevel = Productions[actionp[st,a].number].prec
1916                                     sprec,slevel = Precedence.get(a,('right',0))
1917                                     if (slevel > rlevel) or ((slevel == rlevel) and (rprec != 'left')):
1918                                         # We decide to shift here... highest precedence to shift
1919                                         action[st,a] = j
1920                                         actionp[st,a] = p
1921                                         if not slevel and not rlevel:
1922                                             n_srconflict += 1
1923                                             _vfc.write("shift/reduce conflict in state %d resolved as shift.\n" % st)
1924                                             _vf.write("  ! shift/reduce conflict for %s resolved as shift.\n" % a)
1925                                     elif (slevel == rlevel) and (rprec == 'nonassoc'):
1926                                         action[st,a] = None
1927                                     else:
1928                                         # Hmmm. Guess we'll keep the reduce
1929                                         if not slevel and not rlevel:
1930                                             n_srconflict +=1
1931                                             _vfc.write("shift/reduce conflict in state %d resolved as reduce.\n" % st)
1932                                             _vf.write("  ! shift/reduce conflict for %s resolved as reduce.\n" % a)
1933
1934                                 else:
1935                                     sys.stderr.write("Unknown conflict in state %d\n" % st)
1936                             else:
1937                                 action[st,a] = j
1938                                 actionp[st,a] = p
1939                     else:
1940                         nonterminal = a
1941                         term_list = TReductions[nonterminal]
1942                         # DB: This loop gets executed a lot.  Try to optimize
1943                         for a in term_list:
1944                             g = goto_cache[(idI,a)]
1945                             j = cid_hash[id(g)]
1946                             if j >= 0:
1947                                 # We are in a shift state
1948                                 # Don't put repeated shift actions on action list (performance hack)
1949                                 _k = (a,j)
1950                                 if not acthash.has_key(_k):
1951                                     actlist.append((a,p,"shift and go to state "+str(j)))
1952                                     acthash[_k] = 1
1953
1954                                 r = action.get((st,a),None)
1955                                 if r is not None:
1956                                     # Whoa have a shift/reduce or shift/shift conflict
1957                                     if r > 0:
1958                                         if r != j:
1959                                             sys.stderr.write("Shift/shift conflict in state %d\n" % st)
1960                                         continue
1961                                     elif r < 0:
1962                                         # Do a precedence check.
1963                                         #   -  if precedence of reduce rule is higher, we reduce.
1964                                         #   -  if precedence of reduce is same and left assoc, we reduce.
1965                                         #   -  otherwise we shift
1966                                         rprec,rlevel = Productions[actionp[st,a].number].prec
1967                                         sprec,slevel = Precedence.get(a,('right',0))
1968                                         if (slevel > rlevel) or ((slevel == rlevel) and (rprec != 'left')):
1969                                             # We decide to shift here... highest precedence to shift
1970                                             action[st,a] = j
1971                                             actionp[st,a] = p
1972                                             if not slevel and not rlevel:
1973                                                 n_srconflict += 1
1974                                                 _vfc.write("shift/reduce conflict in state %d resolved as shift.\n" % st)
1975                                                 _vf.write("  ! shift/reduce conflict for %s resolved as shift.\n" % a)
1976                                         elif (slevel == rlevel) and (rprec == 'nonassoc'):
1977                                             action[st,a] = None
1978                                         else:
1979                                             # Hmmm. Guess we'll keep the reduce
1980                                             if not slevel and not rlevel:
1981                                                 n_srconflict +=1
1982                                                 _vfc.write("shift/reduce conflict in state %d resolved as reduce.\n" % st)
1983                                                 _vf.write("  ! shift/reduce conflict for %s resolved as reduce.\n" % a)
1984
1985                                     else:
1986                                         sys.stderr.write("Unknown conflict in state %d\n" % st)
1987                                 else:
1988                                     action[st,a] = j
1989                                     actionp[st,a] = p
1990
1991             except StandardError,e:
1992                 raise YaccError, "Hosed in lalr_parse_table", e
1993
1994         # Print the actions associated with each terminal
1995         if yaccdebug:
1996           for a,p,m in actlist:
1997             if action.has_key((st,a)):
1998                 if p is actionp[st,a]:
1999                     _vf.write("    %-15s %s\n" % (a,m))
2000           _vf.write("\n")
2001
2002           for a,p,m in actlist:
2003             if action.has_key((st,a)):
2004                 if p is not actionp[st,a]:
2005                     _vf.write("  ! %-15s [ %s ]\n" % (a,m))
2006
2007         # Construct the goto table for this state
2008         nkeys = { }
2009         for ii in I:
2010             for s in ii.usyms:
2011                 if Nonterminals.has_key(s):
2012                     nkeys[s] = None
2013
2014         # Construct the goto table for this state
2015         for n in nkeys.keys():
2016             g = lr0_goto(I,n)
2017             j = cid_hash.get(id(g),-1)
2018             if j >= 0:
2019                 goto[st,n] = j
2020                 if yaccdebug:
2021                     _vf.write("    %-30s shift and go to state %d\n" % (n,j))
2022
2023         st += 1
2024     if yaccdebug:
2025         if n_srconflict == 1:
2026             sys.stderr.write("yacc: %d shift/reduce conflict\n" % n_srconflict)
2027         if n_srconflict > 1:
2028             sys.stderr.write("yacc: %d shift/reduce conflicts\n" % n_srconflict)
2029         if n_rrconflict == 1:
2030             sys.stderr.write("yacc: %d reduce/reduce conflict\n" % n_rrconflict)
2031         if n_rrconflict > 1:
2032             sys.stderr.write("yacc: %d reduce/reduce conflicts\n" % n_rrconflict)
2033
2034
2035 # -----------------------------------------------------------------------------
2036 #                          ==== LR Utility functions ====
2037 # -----------------------------------------------------------------------------
2038
2039 # -----------------------------------------------------------------------------
2040 # _lr_write_tables()
2041 #
2042 # This function writes the LR parsing tables to a file
2043 # -----------------------------------------------------------------------------
2044
2045 def lr_write_tables(modulename=tab_module,outputdir=''):
2046     filename = os.path.join(outputdir,modulename) + ".py"
2047     try:
2048         f = open(filename,"w")
2049
2050         f.write("""
2051 # %s
2052 # This file is automatically generated. Do not edit.
2053
2054 _lr_method = %s
2055
2056 _lr_signature = %s
2057 """ % (filename, repr(_lr_method), repr(Signature.digest())))
2058
2059         # Change smaller to 0 to go back to original tables
2060         smaller = 1
2061
2062         # Factor out names to try and make smaller
2063         if smaller:
2064             items = { }
2065
2066             for k,v in _lr_action.items():
2067                 i = items.get(k[1])
2068                 if not i:
2069                     i = ([],[])
2070                     items[k[1]] = i
2071                 i[0].append(k[0])
2072                 i[1].append(v)
2073
2074             f.write("\n_lr_action_items = {")
2075             for k,v in items.items():
2076                 f.write("%r:([" % k)
2077                 for i in v[0]:
2078                     f.write("%r," % i)
2079                 f.write("],[")
2080                 for i in v[1]:
2081                     f.write("%r," % i)
2082
2083                 f.write("]),")
2084             f.write("}\n")
2085
2086             f.write("""
2087 _lr_action = { }
2088 for _k, _v in _lr_action_items.items():
2089    for _x,_y in zip(_v[0],_v[1]):
2090        _lr_action[(_x,_k)] = _y
2091 del _lr_action_items
2092 """)
2093
2094         else:
2095             f.write("\n_lr_action = { ");
2096             for k,v in _lr_action.items():
2097                 f.write("(%r,%r):%r," % (k[0],k[1],v))
2098             f.write("}\n");
2099
2100         if smaller:
2101             # Factor out names to try and make smaller
2102             items = { }
2103
2104             for k,v in _lr_goto.items():
2105                 i = items.get(k[1])
2106                 if not i:
2107                     i = ([],[])
2108                     items[k[1]] = i
2109                 i[0].append(k[0])
2110                 i[1].append(v)
2111
2112             f.write("\n_lr_goto_items = {")
2113             for k,v in items.items():
2114                 f.write("%r:([" % k)
2115                 for i in v[0]:
2116                     f.write("%r," % i)
2117                 f.write("],[")
2118                 for i in v[1]:
2119                     f.write("%r," % i)
2120
2121                 f.write("]),")
2122             f.write("}\n")
2123
2124             f.write("""
2125 _lr_goto = { }
2126 for _k, _v in _lr_goto_items.items():
2127    for _x,_y in zip(_v[0],_v[1]):
2128        _lr_goto[(_x,_k)] = _y
2129 del _lr_goto_items
2130 """)
2131         else:
2132             f.write("\n_lr_goto = { ");
2133             for k,v in _lr_goto.items():
2134                 f.write("(%r,%r):%r," % (k[0],k[1],v))
2135             f.write("}\n");
2136
2137         # Write production table
2138         f.write("_lr_productions = [\n")
2139         for p in Productions:
2140             if p:
2141                 if (p.func):
2142                     f.write("  (%r,%d,%r,%r,%d),\n" % (p.name, p.len, p.func.__name__,p.file,p.line))
2143                 else:
2144                     f.write("  (%r,%d,None,None,None),\n" % (p.name, p.len))
2145             else:
2146                 f.write("  None,\n")
2147         f.write("]\n")
2148         f.close()
2149
2150     except IOError,e:
2151         print "Unable to create '%s'" % filename
2152         print e
2153         return
2154
2155 def lr_read_tables(module=tab_module,optimize=0):
2156     global _lr_action, _lr_goto, _lr_productions, _lr_method
2157     try:
2158         exec "import %s as parsetab" % module
2159
2160         if (optimize) or (Signature.digest() == parsetab._lr_signature):
2161             _lr_action = parsetab._lr_action
2162             _lr_goto   = parsetab._lr_goto
2163             _lr_productions = parsetab._lr_productions
2164             _lr_method = parsetab._lr_method
2165             return 1
2166         else:
2167             return 0
2168
2169     except (ImportError,AttributeError):
2170         return 0
2171
2172
2173 # Available instance types.  This is used when parsers are defined by a class.
2174 # it's a little funky because I want to preserve backwards compatibility
2175 # with Python 2.0 where types.ObjectType is undefined.
2176
2177 try:
2178    _INSTANCETYPE = (types.InstanceType, types.ObjectType)
2179 except AttributeError:
2180    _INSTANCETYPE = types.InstanceType
2181
2182 # -----------------------------------------------------------------------------
2183 # yacc(module)
2184 #
2185 # Build the parser module
2186 # -----------------------------------------------------------------------------
2187
2188 def yacc(method=default_lr, debug=yaccdebug, module=None, tabmodule=tab_module, start=None, check_recursion=1, optimize=0,write_tables=1,debugfile=debug_file,outputdir=''):
2189     global yaccdebug
2190     yaccdebug = debug
2191
2192     initialize_vars()
2193     files = { }
2194     error = 0
2195
2196     # Add starting symbol to signature
2197     if start:
2198         Signature.update(start)
2199
2200     # Add parsing method to signature
2201     Signature.update(method)
2202
2203     # If a "module" parameter was supplied, extract its dictionary.
2204     # Note: a module may in fact be an instance as well.
2205
2206     if module:
2207         # User supplied a module object.
2208         if isinstance(module, types.ModuleType):
2209             ldict = module.__dict__
2210         elif isinstance(module, _INSTANCETYPE):
2211             _items = [(k,getattr(module,k)) for k in dir(module)]
2212             ldict = { }
2213             for i in _items:
2214                 ldict[i[0]] = i[1]
2215         else:
2216             raise ValueError,"Expected a module"
2217
2218     else:
2219         # No module given.  We might be able to get information from the caller.
2220         # Throw an exception and unwind the traceback to get the globals
2221
2222         try:
2223             raise RuntimeError
2224         except RuntimeError:
2225             e,b,t = sys.exc_info()
2226             f = t.tb_frame
2227             f = f.f_back           # Walk out to our calling function
2228             ldict = f.f_globals    # Grab its globals dictionary
2229
2230     # If running in optimized mode.  We're going to
2231
2232     if (optimize and lr_read_tables(tabmodule,1)):
2233         # Read parse table
2234         del Productions[:]
2235         for p in _lr_productions:
2236             if not p:
2237                 Productions.append(None)
2238             else:
2239                 m = MiniProduction()
2240                 m.name = p[0]
2241                 m.len  = p[1]
2242                 m.file = p[3]
2243                 m.line = p[4]
2244                 if p[2]:
2245                     m.func = ldict[p[2]]
2246                 Productions.append(m)
2247
2248     else:
2249         # Get the tokens map
2250         if (module and isinstance(module,_INSTANCETYPE)):
2251             tokens = getattr(module,"tokens",None)
2252         else:
2253             tokens = ldict.get("tokens",None)
2254
2255         if not tokens:
2256             raise YaccError,"module does not define a list 'tokens'"
2257         if not (isinstance(tokens,types.ListType) or isinstance(tokens,types.TupleType)):
2258             raise YaccError,"tokens must be a list or tuple."
2259
2260         # Check to see if a requires dictionary is defined.
2261         requires = ldict.get("require",None)
2262         if requires:
2263             if not (isinstance(requires,types.DictType)):
2264                 raise YaccError,"require must be a dictionary."
2265
2266             for r,v in requires.items():
2267                 try:
2268                     if not (isinstance(v,types.ListType)):
2269                         raise TypeError
2270                     v1 = [x.split(".") for x in v]
2271                     Requires[r] = v1
2272                 except StandardError:
2273                     print "Invalid specification for rule '%s' in require. Expected a list of strings" % r
2274
2275
2276         # Build the dictionary of terminals.  We a record a 0 in the
2277         # dictionary to track whether or not a terminal is actually
2278         # used in the grammar
2279
2280         if 'error' in tokens:
2281             print "yacc: Illegal token 'error'.  Is a reserved word."
2282             raise YaccError,"Illegal token name"
2283
2284         for n in tokens:
2285             if Terminals.has_key(n):
2286                 print "yacc: Warning. Token '%s' multiply defined." % n
2287             Terminals[n] = [ ]
2288
2289         Terminals['error'] = [ ]
2290
2291         # Get the precedence map (if any)
2292         prec = ldict.get("precedence",None)
2293         if prec:
2294             if not (isinstance(prec,types.ListType) or isinstance(prec,types.TupleType)):
2295                 raise YaccError,"precedence must be a list or tuple."
2296             add_precedence(prec)
2297             Signature.update(repr(prec))
2298
2299         for n in tokens:
2300             if not Precedence.has_key(n):
2301                 Precedence[n] = ('right',0)         # Default, right associative, 0 precedence
2302
2303         # Look for error handler
2304         ef = ldict.get('p_error',None)
2305         if ef:
2306             if isinstance(ef,types.FunctionType):
2307                 ismethod = 0
2308             elif isinstance(ef, types.MethodType):
2309                 ismethod = 1
2310             else:
2311                 raise YaccError,"'p_error' defined, but is not a function or method."
2312             eline = ef.func_code.co_firstlineno
2313             efile = ef.func_code.co_filename
2314             files[efile] = None
2315
2316             if (ef.func_code.co_argcount != 1+ismethod):
2317                 raise YaccError,"%s:%d: p_error() requires 1 argument." % (efile,eline)
2318             global Errorfunc
2319             Errorfunc = ef
2320         else:
2321             print "yacc: Warning. no p_error() function is defined."
2322
2323         # Get the list of built-in functions with p_ prefix
2324         symbols = [ldict[f] for f in ldict.keys()
2325                if (type(ldict[f]) in (types.FunctionType, types.MethodType) and ldict[f].__name__[:2] == 'p_'
2326                    and ldict[f].__name__ != 'p_error')]
2327
2328         # Check for non-empty symbols
2329         if len(symbols) == 0:
2330             raise YaccError,"no rules of the form p_rulename are defined."
2331
2332         # Sort the symbols by line number
2333         symbols.sort(lambda x,y: cmp(x.func_code.co_firstlineno,y.func_code.co_firstlineno))
2334
2335         # Add all of the symbols to the grammar
2336         for f in symbols:
2337             if (add_function(f)) < 0:
2338                 error += 1
2339             else:
2340                 files[f.func_code.co_filename] = None
2341
2342         # Make a signature of the docstrings
2343         for f in symbols:
2344             if f.__doc__:
2345                 Signature.update(f.__doc__)
2346
2347         lr_init_vars()
2348
2349         if error:
2350             raise YaccError,"Unable to construct parser."
2351
2352         if not lr_read_tables(tabmodule):
2353
2354             # Validate files
2355             for filename in files.keys():
2356                 if not validate_file(filename):
2357                     error = 1
2358
2359             # Validate dictionary
2360             validate_dict(ldict)
2361
2362             if start and not Prodnames.has_key(start):
2363                 raise YaccError,"Bad starting symbol '%s'" % start
2364
2365             augment_grammar(start)
2366             error = verify_productions(cycle_check=check_recursion)
2367             otherfunc = [ldict[f] for f in ldict.keys()
2368                if (type(f) in (types.FunctionType,types.MethodType) and ldict[f].__name__[:2] != 'p_')]
2369
2370             if error:
2371                 raise YaccError,"Unable to construct parser."
2372
2373             build_lritems()
2374             compute_first1()
2375             compute_follow(start)
2376
2377             if method == 'SLR':
2378                 slr_parse_table()
2379             elif method == 'LALR':
2380                 lalr_parse_table()
2381             else:
2382                 raise YaccError, "Unknown parsing method '%s'" % method
2383
2384             if write_tables:
2385                 lr_write_tables(tabmodule,outputdir)
2386
2387             if yaccdebug:
2388                 try:
2389                     f = open(os.path.join(outputdir,debugfile),"w")
2390                     f.write(_vfc.getvalue())
2391                     f.write("\n\n")
2392                     f.write(_vf.getvalue())
2393                     f.close()
2394                 except IOError,e:
2395                     print "yacc: can't create '%s'" % debugfile,e
2396
2397     # Made it here.   Create a parser object and set up its internal state.
2398     # Set global parse() method to bound method of parser object.
2399
2400     p = Parser("xyzzy")
2401     p.productions = Productions
2402     p.errorfunc = Errorfunc
2403     p.action = _lr_action
2404     p.goto   = _lr_goto
2405     p.method = _lr_method
2406     p.require = Requires
2407
2408     global parse
2409     parse = p.parse
2410
2411     # Clean up all of the globals we created
2412     if (not optimize):
2413         yacc_cleanup()
2414     return p
2415
2416 # yacc_cleanup function.  Delete all of the global variables
2417 # used during table construction
2418
2419 def yacc_cleanup():
2420     global _lr_action, _lr_goto, _lr_method, _lr_goto_cache
2421     del _lr_action, _lr_goto, _lr_method, _lr_goto_cache
2422
2423     global Productions, Prodnames, Prodmap, Terminals
2424     global Nonterminals, First, Follow, Precedence, LRitems
2425     global Errorfunc, Signature, Requires
2426     global Prodempty, TReductions, NTReductions, GotoSetNum, Canonical
2427
2428     del Productions, Prodnames, Prodmap, Terminals
2429     del Nonterminals, First, Follow, Precedence, LRitems
2430     del Errorfunc, Signature, Requires
2431     del Prodempty, TReductions, NTReductions, GotoSetNum, Canonical
2432
2433     global _vf, _vfc
2434     del _vf, _vfc
2435
2436
2437 # Stub that raises an error if parsing is attempted without first calling yacc()
2438 def parse(*args,**kwargs):
2439     raise YaccError, "yacc: No parser built with yacc()"
2440