113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle#----------------------------------------------------------------------------- 213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ply: yacc.py 313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Author(s): David M. Beazley (dave@dabeaz.com) 513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Copyright (C) 2001-2006, David M. Beazley 713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This library is free software; you can redistribute it and/or 913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# modify it under the terms of the GNU Lesser General Public 1013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# License as published by the Free Software Foundation; either 1113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# version 2.1 of the License, or (at your option) any later version. 1213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 1313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This library is distributed in the hope that it will be useful, 1413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# but WITHOUT ANY WARRANTY; without even the implied warranty of 1513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Lesser General Public License for more details. 1713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 1813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# You should have received a copy of the GNU Lesser General Public 1913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# License along with this library; if not, write to the Free Software 2013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 2113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 2213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# See the file COPYING for a complete copy of the LGPL. 2313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 2413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 2513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This implements an LR parser that is constructed from grammar rules defined 2613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# as Python functions. The grammer is specified by supplying the BNF inside 2713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Python documentation strings. The inspiration for this technique was borrowed 2813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# from John Aycock's Spark parsing system. PLY might be viewed as cross between 2913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Spark and the GNU bison utility. 3013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 3113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# The current implementation is only somewhat object-oriented. The 3213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# LR parser itself is defined in terms of an object (which allows multiple 3313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# parsers to co-exist). However, most of the variables used during table 3413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# construction are defined in terms of global variables. Users shouldn't 3513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# notice unless they are trying to define multiple parsers at the same 3613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# time using threads (in which case they should have their head examined). 3713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 3813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This implementation supports both SLR and LALR(1) parsing. LALR(1) 3913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# support was originally implemented by Elias Ioup (ezioup@alumni.uchicago.edu), 4013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# using the algorithm found in Aho, Sethi, and Ullman "Compilers: Principles, 4113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Techniques, and Tools" (The Dragon Book). LALR(1) has since been replaced 4213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# by the more efficient DeRemer and Pennello algorithm. 4313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 4413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# :::::::: WARNING ::::::: 4513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 4613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Construction of LR parsing tables is fairly complicated and expensive. 4713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# To make this module run fast, a *LOT* of work has been put into 4813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# optimization---often at the expensive of readability and what might 4913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# consider to be good Python "coding style." Modify the code at your 5013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# own risk! 5113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ---------------------------------------------------------------------------- 5213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 5313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle__version__ = "2.2" 5413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 5513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle#----------------------------------------------------------------------------- 5613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# === User configurable parameters === 5713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 5813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Change these to modify the default behavior of yacc (if you wish) 5913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle#----------------------------------------------------------------------------- 6013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 6113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindleyaccdebug = 1 # Debugging mode. If set, yacc generates a 6213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # a 'parser.out' file in the current directory 6313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 6413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledebug_file = 'parser.out' # Default name of the debugging file 6513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindletab_module = 'parsetab' # Default name of the table module 6613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledefault_lr = 'LALR' # Default LR table generation method 6713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 6813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindleerror_count = 3 # Number of symbols that must be shifted to leave recovery mode 6913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 70fb50c7b4ef11a3001051ae2b37b3dd7f869edbc9Joshua Brindleimport re, types, sys, cStringIO, hashlib, os.path 7113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 7213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Exception raised for yacc-related errors 7313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindleclass YaccError(Exception): pass 7413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 7513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle#----------------------------------------------------------------------------- 7613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# === LR Parsing Engine === 7713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 7813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# The following classes are used for the LR parser itself. These are not 7913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# used during table construction and are independent of the actual LR 8013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# table generation algorithm 8113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle#----------------------------------------------------------------------------- 8213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 8313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This class is used to hold non-terminal grammar symbols during parsing. 8413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# It normally has the following attributes set: 8513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# .type = Grammar symbol type 8613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# .value = Symbol value 8713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# .lineno = Starting line number 8813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# .endlineno = Ending line number (optional, set automatically) 8913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# .lexpos = Starting lex position 9013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# .endlexpos = Ending lex position (optional, set automatically) 9113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 9213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindleclass YaccSymbol: 9313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def __str__(self): return self.type 9413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def __repr__(self): return str(self) 9513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 9613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This class is a wrapper around the objects actually passed to each 9713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# grammar rule. Index lookup and assignment actually assign the 9813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# .value attribute of the underlying YaccSymbol object. 9913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# The lineno() method returns the line number of a given 10013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# item (or 0 if not defined). The linespan() method returns 10113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# a tuple of (startline,endline) representing the range of lines 10213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# for a symbol. The lexspan() method returns a tuple (lexpos,endlexpos) 10313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# representing the range of positional information for a symbol. 10413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 10513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindleclass YaccProduction: 10613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def __init__(self,s,stack=None): 10713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.slice = s 10813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.pbstack = [] 10913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.stack = stack 11013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 11113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def __getitem__(self,n): 11213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if type(n) == types.IntType: 11313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if n >= 0: return self.slice[n].value 11413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: return self.stack[n].value 11513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 11613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return [s.value for s in self.slice[n.start:n.stop:n.step]] 11713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 11813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def __setitem__(self,n,v): 11913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.slice[n].value = v 12013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 12113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def __len__(self): 12213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return len(self.slice) 12313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 12413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def lineno(self,n): 12513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return getattr(self.slice[n],"lineno",0) 12613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 12713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def linespan(self,n): 12813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle startline = getattr(self.slice[n],"lineno",0) 12913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle endline = getattr(self.slice[n],"endlineno",startline) 13013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return startline,endline 13113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 13213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def lexpos(self,n): 13313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return getattr(self.slice[n],"lexpos",0) 13413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 13513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def lexspan(self,n): 13613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle startpos = getattr(self.slice[n],"lexpos",0) 13713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle endpos = getattr(self.slice[n],"endlexpos",startpos) 13813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return startpos,endpos 13913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 14013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def pushback(self,n): 14113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if n <= 0: 14213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise ValueError, "Expected a positive value" 14313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if n > (len(self.slice)-1): 14413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise ValueError, "Can't push %d tokens. Only %d are available." % (n,len(self.slice)-1) 14513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for i in range(0,n): 14613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.pbstack.append(self.slice[-i-1]) 14713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 14813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# The LR Parsing engine. This is defined as a class so that multiple parsers 14913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# can exist in the same process. A user never instantiates this directly. 15013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Instead, the global yacc() function should be used to create a suitable Parser 15113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# object. 15213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 15313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindleclass Parser: 15413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def __init__(self,magic=None): 15513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 15613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # This is a hack to keep users from trying to instantiate a Parser 15713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # object directly. 15813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 15913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if magic != "xyzzy": 16013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError, "Can't instantiate Parser. Use yacc() instead." 16113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 16213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Reset internal state 16313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.productions = None # List of productions 16413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.errorfunc = None # Error handling function 16513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.action = { } # LR Action table 16613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.goto = { } # LR goto table 16713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.require = { } # Attribute require table 16813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.method = "Unknown LR" # Table construction method used 16913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 17013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def errok(self): 17113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.errorcount = 0 17213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 17313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def restart(self): 17413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle del self.statestack[:] 17513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle del self.symstack[:] 17613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sym = YaccSymbol() 17713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sym.type = '$end' 17813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.symstack.append(sym) 17913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.statestack.append(0) 18013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 18113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def parse(self,input=None,lexer=None,debug=0): 18213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookahead = None # Current lookahead symbol 18313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookaheadstack = [ ] # Stack of lookahead symbols 18413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle actions = self.action # Local reference to action table 18513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle goto = self.goto # Local reference to goto table 18613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle prod = self.productions # Local reference to production list 18713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle pslice = YaccProduction(None) # Production object passed to grammar rules 18813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle pslice.parser = self # Parser object 18913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.errorcount = 0 # Used during error recovery 19013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 19113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # If no lexer was given, we will try to use the lex module 19213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not lexer: 19313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle import lex 19413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lexer = lex.lexer 19513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 19613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle pslice.lexer = lexer 19713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 19813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # If input was supplied, pass to lexer 19913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if input: 20013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lexer.input(input) 20113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 20213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Tokenize function 20313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle get_token = lexer.token 20413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 20513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle statestack = [ ] # Stack of parsing states 20613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.statestack = statestack 20713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle symstack = [ ] # Stack of grammar symbols 20813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.symstack = symstack 20913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 21013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle pslice.stack = symstack # Put in the production 21113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle errtoken = None # Err token 21213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 21313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # The start state is assumed to be (0,$end) 21413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle statestack.append(0) 21513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sym = YaccSymbol() 21613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sym.type = '$end' 21713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle symstack.append(sym) 21813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 21913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle while 1: 22013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Get the next symbol on the input. If a lookahead symbol 22113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # is already set, we just use that. Otherwise, we'll pull 22213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # the next token off of the lookaheadstack or from the lexer 22313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if debug > 1: 22413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle print 'state', statestack[-1] 22513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not lookahead: 22613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not lookaheadstack: 22713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookahead = get_token() # Get the next token 22813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 22913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookahead = lookaheadstack.pop() 23013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not lookahead: 23113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookahead = YaccSymbol() 23213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookahead.type = '$end' 23313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if debug: 23413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle errorlead = ("%s . %s" % (" ".join([xx.type for xx in symstack][1:]), str(lookahead))).lstrip() 23513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 23613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Check the action table 23713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle s = statestack[-1] 23813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ltype = lookahead.type 23913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle t = actions.get((s,ltype),None) 24013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 24113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if debug > 1: 24213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle print 'action', t 24313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if t is not None: 24413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if t > 0: 24513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # shift a symbol on the stack 24613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if ltype == '$end': 24713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Error, end of input 24813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Parse error. EOF\n") 24913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return 25013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle statestack.append(t) 25113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if debug > 1: 25213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%-60s shift state %s\n" % (errorlead, t)) 25313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle symstack.append(lookahead) 25413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookahead = None 25513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 25613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Decrease error count on successful shift 25713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if self.errorcount > 0: 25813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.errorcount -= 1 25913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 26013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle continue 26113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 26213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if t < 0: 26313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # reduce a symbol on the stack, emit a production 26413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p = prod[-t] 26513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle pname = p.name 26613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle plen = p.len 26713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 26813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Get production function 26913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sym = YaccSymbol() 27013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sym.type = pname # Production name 27113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sym.value = None 27213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if debug > 1: 27313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%-60s reduce %d\n" % (errorlead, -t)) 27413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 27513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if plen: 27613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle targ = symstack[-plen-1:] 27713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle targ[0] = sym 27813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 27913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sym.lineno = targ[1].lineno 28013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sym.endlineno = getattr(targ[-1],"endlineno",targ[-1].lineno) 28113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sym.lexpos = targ[1].lexpos 28213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sym.endlexpos = getattr(targ[-1],"endlexpos",targ[-1].lexpos) 28313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except AttributeError: 28413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sym.lineno = 0 28513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle del symstack[-plen:] 28613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle del statestack[-plen:] 28713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 28813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sym.lineno = 0 28913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle targ = [ sym ] 29013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle pslice.slice = targ 29113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle pslice.pbstack = [] 29213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Call the grammar rule with our special slice object 29313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.func(pslice) 29413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 29513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # If there was a pushback, put that on the stack 29613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if pslice.pbstack: 29713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookaheadstack.append(lookahead) 29813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for _t in pslice.pbstack: 29913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookaheadstack.append(_t) 30013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookahead = None 30113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 30213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle symstack.append(sym) 30313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle statestack.append(goto[statestack[-1],pname]) 30413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle continue 30513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 30613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if t == 0: 30713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle n = symstack[-1] 30813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return getattr(n,"value",None) 30913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write(errorlead, "\n") 31013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 31113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if t == None: 31213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if debug: 31313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write(errorlead + "\n") 31413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # We have some kind of parsing error here. To handle 31513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # this, we are going to push the current token onto 31613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # the tokenstack and replace it with an 'error' token. 31713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # If there are any synchronization rules, they may 31813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # catch it. 31913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # 32013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # In addition to pushing the error token, we call call 32113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # the user defined p_error() function if this is the 32213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # first syntax error. This function is only called if 32313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # errorcount == 0. 32413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not self.errorcount: 32513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.errorcount = error_count 32613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle errtoken = lookahead 32713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if errtoken.type == '$end': 32813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle errtoken = None # End of file! 32913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if self.errorfunc: 33013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global errok,token,restart 33113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle errok = self.errok # Set some special functions available in error recovery 33213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle token = get_token 33313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle restart = self.restart 33413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle tok = self.errorfunc(errtoken) 33513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle del errok, token, restart # Delete special functions 33613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 33713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not self.errorcount: 33813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # User must have done some kind of panic 33913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # mode recovery on their own. The 34013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # returned token is the next lookahead 34113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookahead = tok 34213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle errtoken = None 34313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle continue 34413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 34513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if errtoken: 34613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if hasattr(errtoken,"lineno"): lineno = lookahead.lineno 34713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: lineno = 0 34813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if lineno: 34913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Syntax error at line %d, token=%s\n" % (lineno, errtoken.type)) 35013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 35113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Syntax error, token=%s" % errtoken.type) 35213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 35313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Parse error in input. EOF\n") 35413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return 35513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 35613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 35713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.errorcount = error_count 35813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 35913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # case 1: the statestack only has 1 entry on it. If we're in this state, the 36013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # entire parse has been rolled back and we're completely hosed. The token is 36113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # discarded and we just keep going. 36213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 36313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if len(statestack) <= 1 and lookahead.type != '$end': 36413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookahead = None 36513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle errtoken = None 36613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Nuke the pushback stack 36713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle del lookaheadstack[:] 36813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle continue 36913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 37013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # case 2: the statestack has a couple of entries on it, but we're 37113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # at the end of the file. nuke the top entry and generate an error token 37213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 37313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Start nuking entries on the stack 37413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if lookahead.type == '$end': 37513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Whoa. We're really hosed here. Bail out 37613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return 37713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 37813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if lookahead.type != 'error': 37913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sym = symstack[-1] 38013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if sym.type == 'error': 38113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Hmmm. Error is on top of stack, we'll just nuke input 38213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # symbol and continue 38313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookahead = None 38413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle continue 38513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle t = YaccSymbol() 38613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle t.type = 'error' 38713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if hasattr(lookahead,"lineno"): 38813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle t.lineno = lookahead.lineno 38913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle t.value = lookahead 39013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookaheadstack.append(lookahead) 39113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookahead = t 39213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 39313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle symstack.pop() 39413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle statestack.pop() 39513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 39613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle continue 39713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 39813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Call an error function here 39913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise RuntimeError, "yacc: internal parser error!!!\n" 40013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 40113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 40213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# === Parser Construction === 40313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 40413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# The following functions and variables are used to implement the yacc() function 40513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# itself. This is pretty hairy stuff involving lots of error checking, 40613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# construction of LR items, kernels, and so forth. Although a lot of 40713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# this work is done using global variables, the resulting Parser object 40813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# is completely self contained--meaning that it is safe to repeatedly 40913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# call yacc() with different grammars in the same application. 41013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 41113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 41213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 41313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# validate_file() 41413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 41513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This function checks to see if there are duplicated p_rulename() functions 41613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# in the parser module file. Without this function, it is really easy for 41713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# users to make mistakes by cutting and pasting code fragments (and it's a real 41813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# bugger to try and figure out why the resulting parser doesn't work). Therefore, 41913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# we just do a little regular expression pattern matching of def statements 42013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# to try and detect duplicates. 42113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 42213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 42313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef validate_file(filename): 42413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle base,ext = os.path.splitext(filename) 42513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if ext != '.py': return 1 # No idea. Assume it's okay. 42613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 42713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 42813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f = open(filename) 42913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lines = f.readlines() 43013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.close() 43113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except IOError: 43213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return 1 # Oh well 43313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 43413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Match def p_funcname( 43513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle fre = re.compile(r'\s*def\s+(p_[a-zA-Z_0-9]*)\(') 43613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle counthash = { } 43713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle linen = 1 43813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle noerror = 1 43913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for l in lines: 44013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle m = fre.match(l) 44113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if m: 44213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle name = m.group(1) 44313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle prev = counthash.get(name) 44413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not prev: 44513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle counthash[name] = linen 44613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 44713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Function %s redefined. Previously defined on line %d\n" % (filename,linen,name,prev)) 44813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle noerror = 0 44913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle linen += 1 45013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return noerror 45113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 45213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This function looks for functions that might be grammar rules, but which don't have the proper p_suffix. 45313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef validate_dict(d): 45413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for n,v in d.items(): 45513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if n[0:2] == 'p_' and type(v) in (types.FunctionType, types.MethodType): continue 45613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if n[0:2] == 't_': continue 45713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 45813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if n[0:2] == 'p_': 45913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Warning. '%s' not defined as a function\n" % n) 46013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if 1 and isinstance(v,types.FunctionType) and v.func_code.co_argcount == 1: 46113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 46213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle doc = v.__doc__.split(" ") 46313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if doc[1] == ':': 46413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 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)) 46513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except StandardError: 46613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle pass 46713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 46813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 46913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# === GRAMMAR FUNCTIONS === 47013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 47113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# The following global variables and functions are used to store, manipulate, 47213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# and verify the grammar rules specified by the user. 47313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 47413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 47513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Initialize all of the global variables used during grammar construction 47613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef initialize_vars(): 47713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global Productions, Prodnames, Prodmap, Terminals 47813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global Nonterminals, First, Follow, Precedence, LRitems 47913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global Errorfunc, Signature, Requires 48013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 48113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Productions = [None] # A list of all of the productions. The first 48213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # entry is always reserved for the purpose of 48313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # building an augmented grammar 48413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 48513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Prodnames = { } # A dictionary mapping the names of nonterminals to a list of all 48613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # productions of that nonterminal. 48713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 48813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Prodmap = { } # A dictionary that is only used to detect duplicate 48913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # productions. 49013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 49113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Terminals = { } # A dictionary mapping the names of terminal symbols to a 49213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # list of the rules where they are used. 49313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 49413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Nonterminals = { } # A dictionary mapping names of nonterminals to a list 49513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # of rule numbers where they are used. 49613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 49713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle First = { } # A dictionary of precomputed FIRST(x) symbols 49813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 49913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Follow = { } # A dictionary of precomputed FOLLOW(x) symbols 50013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 50113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Precedence = { } # Precedence rules for each terminal. Contains tuples of the 50213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # form ('right',level) or ('nonassoc', level) or ('left',level) 50313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 50413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle LRitems = [ ] # A list of all LR items for the grammar. These are the 50513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # productions with the "dot" like E -> E . PLUS E 50613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 50713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Errorfunc = None # User defined error handler 50813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 5098f3207eda0b7c13c5aa1969c1fd8d11abb1677eeDan Walsh Signature = hashlib.sha256() # Digital signature of the grammar rules, precedence 51013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # and other information. Used to determined when a 51113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # parsing table needs to be regenerated. 51213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 51313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Requires = { } # Requires list 51413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 51513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # File objects used when creating the parser.out debugging file 51613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global _vf, _vfc 51713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf = cStringIO.StringIO() 51813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vfc = cStringIO.StringIO() 51913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 52013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 52113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# class Production: 52213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 52313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This class stores the raw information about a single production or grammar rule. 52413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# It has a few required attributes: 52513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 52613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# name - Name of the production (nonterminal) 52713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# prod - A list of symbols making up its production 52813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# number - Production number. 52913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 53013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# In addition, a few additional attributes are used to help with debugging or 53113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# optimization of table generation. 53213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 53313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# file - File where production action is defined. 53413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# lineno - Line number where action is defined 53513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# func - Action function 53613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# prec - Precedence level 53713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# lr_next - Next LR item. Example, if we are ' E -> E . PLUS E' 53813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# then lr_next refers to 'E -> E PLUS . E' 53913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# lr_index - LR item index (location of the ".") in the prod list. 54013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# lookaheads - LALR lookahead symbols for this item 54113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# len - Length of the production (number of symbols on right hand side) 54213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 54313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 54413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindleclass Production: 54513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def __init__(self,**kw): 54613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for k,v in kw.items(): 54713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle setattr(self,k,v) 54813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.lr_index = -1 54913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.lr0_added = 0 # Flag indicating whether or not added to LR0 closure 55013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.lr1_added = 0 # Flag indicating whether or not added to LR1 55113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.usyms = [ ] 55213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.lookaheads = { } 55313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.lk_added = { } 55413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle self.setnumbers = [ ] 55513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 55613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def __str__(self): 55713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if self.prod: 55813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle s = "%s -> %s" % (self.name," ".join(self.prod)) 55913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 56013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle s = "%s -> <empty>" % self.name 56113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return s 56213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 56313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def __repr__(self): 56413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return str(self) 56513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 56613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Compute lr_items from the production 56713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle def lr_item(self,n): 56813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if n > len(self.prod): return None 56913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p = Production() 57013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.name = self.name 57113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.prod = list(self.prod) 57213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.number = self.number 57313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.lr_index = n 57413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.lookaheads = { } 57513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.setnumbers = self.setnumbers 57613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.prod.insert(n,".") 57713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.prod = tuple(p.prod) 57813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.len = len(p.prod) 57913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.usyms = self.usyms 58013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 58113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Precompute list of productions immediately following 58213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 58313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.lrafter = Prodnames[p.prod[n+1]] 58413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except (IndexError,KeyError),e: 58513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.lrafter = [] 58613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 58713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.lrbefore = p.prod[n-1] 58813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except IndexError: 58913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.lrbefore = None 59013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 59113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return p 59213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 59313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindleclass MiniProduction: 59413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle pass 59513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 59613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# regex matching identifiers 597a0af38a531788d2ffc4fd1c03c38fb66c3a61c17Dan Walsh_is_identifier = re.compile(r'^[a-zA-Z0-9_-~]+$') 59813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 59913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 60013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# add_production() 60113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 60213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Given an action function, this function assembles a production rule. 60313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# The production rule is assumed to be found in the function's docstring. 60413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This rule has the general syntax: 60513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 60613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# name1 ::= production1 60713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# | production2 60813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# | production3 60913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ... 61013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# | productionn 61113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# name2 ::= production1 61213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# | production2 61313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ... 61413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 61513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 61613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef add_production(f,file,line,prodname,syms): 61713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 61813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if Terminals.has_key(prodname): 61913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Illegal rule name '%s'. Already defined as a token.\n" % (file,line,prodname)) 62013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return -1 62113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if prodname == 'error': 62213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Illegal rule name '%s'. error is a reserved word.\n" % (file,line,prodname)) 62313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return -1 62413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 62513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not _is_identifier.match(prodname): 62613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Illegal rule name '%s'\n" % (file,line,prodname)) 62713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return -1 62813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 62913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for x in range(len(syms)): 63013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle s = syms[x] 63113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if s[0] in "'\"": 63213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 63313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle c = eval(s) 63413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if (len(c) > 1): 63513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Literal token %s in rule '%s' may only be a single character\n" % (file,line,s, prodname)) 63613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return -1 63713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not Terminals.has_key(c): 63813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Terminals[c] = [] 63913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle syms[x] = c 64013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle continue 64113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except SyntaxError: 64213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle pass 64313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not _is_identifier.match(s) and s != '%prec': 64413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Illegal name '%s' in rule '%s'\n" % (file,line,s, prodname)) 64513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return -1 64613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 64713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # See if the rule is already in the rulemap 64813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle map = "%s -> %s" % (prodname,syms) 64913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if Prodmap.has_key(map): 65013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle m = Prodmap[map] 65113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Duplicate rule %s.\n" % (file,line, m)) 65213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Previous definition at %s:%d\n" % (file,line, m.file, m.line)) 65313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return -1 65413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 65513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p = Production() 65613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.name = prodname 65713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.prod = syms 65813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.file = file 65913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.line = line 66013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.func = f 66113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.number = len(Productions) 66213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 66313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 66413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Productions.append(p) 66513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Prodmap[map] = p 66613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not Nonterminals.has_key(prodname): 66713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Nonterminals[prodname] = [ ] 66813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 66913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Add all terminals to Terminals 67013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i = 0 67113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle while i < len(p.prod): 67213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle t = p.prod[i] 67313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if t == '%prec': 67413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 67513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle precname = p.prod[i+1] 67613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except IndexError: 67713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Syntax error. Nothing follows %%prec.\n" % (p.file,p.line)) 67813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return -1 67913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 68013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle prec = Precedence.get(precname,None) 68113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not prec: 68213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Nothing known about the precedence of '%s'\n" % (p.file,p.line,precname)) 68313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return -1 68413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 68513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.prec = prec 68613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle del p.prod[i] 68713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle del p.prod[i] 68813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle continue 68913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 69013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if Terminals.has_key(t): 69113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Terminals[t].append(p.number) 69213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Is a terminal. We'll assign a precedence to p based on this 69313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not hasattr(p,"prec"): 69413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.prec = Precedence.get(t,('right',0)) 69513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 69613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not Nonterminals.has_key(t): 69713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Nonterminals[t] = [ ] 69813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Nonterminals[t].append(p.number) 69913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i += 1 70013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 70113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not hasattr(p,"prec"): 70213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.prec = ('right',0) 70313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 70413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Set final length of productions 70513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.len = len(p.prod) 70613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.prod = tuple(p.prod) 70713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 70813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Calculate unique syms in the production 70913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.usyms = [ ] 71013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for s in p.prod: 71113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if s not in p.usyms: 71213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.usyms.append(s) 71313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 71413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Add to the global productions list 71513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 71613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Prodnames[p.name].append(p) 71713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except KeyError: 71813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Prodnames[p.name] = [ p ] 71913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return 0 72013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 72113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Given a raw rule function, this function rips out its doc string 72213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# and adds rules to the grammar 72313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 72413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef add_function(f): 72513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle line = f.func_code.co_firstlineno 72613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle file = f.func_code.co_filename 72713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle error = 0 72813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 72913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if isinstance(f,types.MethodType): 73013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle reqdargs = 2 73113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 73213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle reqdargs = 1 73313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 73413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if f.func_code.co_argcount > reqdargs: 73513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Rule '%s' has too many arguments.\n" % (file,line,f.__name__)) 73613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return -1 73713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 73813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if f.func_code.co_argcount < reqdargs: 73913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Rule '%s' requires an argument.\n" % (file,line,f.__name__)) 74013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return -1 74113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 74213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if f.__doc__: 74313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Split the doc string into lines 74413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle pstrings = f.__doc__.splitlines() 74513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lastp = None 74613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle dline = line 74713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for ps in pstrings: 74813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle dline += 1 74913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p = ps.split() 75013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not p: continue 75113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 75213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if p[0] == '|': 75313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # This is a continuation of a previous rule 75413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not lastp: 75513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Misplaced '|'.\n" % (file,dline)) 75613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return -1 75713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle prodname = lastp 75813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if len(p) > 1: 75913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle syms = p[1:] 76013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 76113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle syms = [ ] 76213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 76313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle prodname = p[0] 76413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lastp = prodname 76513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle assign = p[1] 76613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if len(p) > 2: 76713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle syms = p[2:] 76813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 76913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle syms = [ ] 77013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if assign != ':' and assign != '::=': 77113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Syntax error. Expected ':'\n" % (file,dline)) 77213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return -1 77313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 77413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 77513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle e = add_production(f,file,dline,prodname,syms) 77613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle error += e 77713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 77813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 77913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except StandardError: 78013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Syntax error in rule '%s'\n" % (file,dline,ps)) 78113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle error -= 1 78213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 78313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: No documentation string specified in function '%s'\n" % (file,line,f.__name__)) 78413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return error 78513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 78613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 78713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Cycle checking code (Michael Dyck) 78813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 78913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef compute_reachable(): 79013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ''' 79113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Find each symbol that can be reached from the start symbol. 79213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Print a warning for any nonterminals that can't be reached. 79313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle (Unused terminals have already had their warning.) 79413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ''' 79513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Reachable = { } 79613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for s in Terminals.keys() + Nonterminals.keys(): 79713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Reachable[s] = 0 79813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 79913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle mark_reachable_from( Productions[0].prod[0], Reachable ) 80013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 80113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for s in Nonterminals.keys(): 80213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not Reachable[s]: 80313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Symbol '%s' is unreachable.\n" % s) 80413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 80513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef mark_reachable_from(s, Reachable): 80613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ''' 80713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Mark all symbols that are reachable from symbol s. 80813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ''' 80913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if Reachable[s]: 81013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # We've already reached symbol s. 81113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return 81213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Reachable[s] = 1 81313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in Prodnames.get(s,[]): 81413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for r in p.prod: 81513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle mark_reachable_from(r, Reachable) 81613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 81713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 81813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# compute_terminates() 81913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 82013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This function looks at the various parsing rules and tries to detect 82113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# infinite recursion cycles (grammar rules where there is no possible way 82213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# to derive a string of only terminals). 82313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 82413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef compute_terminates(): 82513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ''' 82613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Raise an error for any symbols that don't terminate. 82713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ''' 82813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Terminates = {} 82913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 83013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Terminals: 83113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for t in Terminals.keys(): 83213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Terminates[t] = 1 83313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 83413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Terminates['$end'] = 1 83513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 83613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Nonterminals: 83713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 83813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Initialize to false: 83913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for n in Nonterminals.keys(): 84013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Terminates[n] = 0 84113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 84213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Then propagate termination until no change: 84313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle while 1: 84413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle some_change = 0 84513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for (n,pl) in Prodnames.items(): 84613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Nonterminal n terminates iff any of its productions terminates. 84713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in pl: 84813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Production p terminates iff all of its rhs symbols terminate. 84913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for s in p.prod: 85013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not Terminates[s]: 85113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # The symbol s does not terminate, 85213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # so production p does not terminate. 85313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p_terminates = 0 85413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle break 85513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 85613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # didn't break from the loop, 85713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # so every symbol s terminates 85813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # so production p terminates. 85913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p_terminates = 1 86013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 86113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if p_terminates: 86213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # symbol n terminates! 86313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not Terminates[n]: 86413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Terminates[n] = 1 86513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle some_change = 1 86613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Don't need to consider any more productions for this n. 86713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle break 86813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 86913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not some_change: 87013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle break 87113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 87213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle some_error = 0 87313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for (s,terminates) in Terminates.items(): 87413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not terminates: 87513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not Prodnames.has_key(s) and not Terminals.has_key(s) and s != 'error': 87613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # s is used-but-not-defined, and we've already warned of that, 87713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # so it would be overkill to say that it's also non-terminating. 87813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle pass 87913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 88013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Infinite recursion detected for symbol '%s'.\n" % s) 88113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle some_error = 1 88213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 88313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return some_error 88413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 88513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 88613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# verify_productions() 88713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 88813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This function examines all of the supplied rules to see if they seem valid. 88913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 89013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef verify_productions(cycle_check=1): 89113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle error = 0 89213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in Productions: 89313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not p: continue 89413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 89513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for s in p.prod: 89613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not Prodnames.has_key(s) and not Terminals.has_key(s) and s != 'error': 89713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Symbol '%s' used, but not defined as a token or a rule.\n" % (p.file,p.line,s)) 89813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle error = 1 89913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle continue 90013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 90113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle unused_tok = 0 90213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Now verify all of the tokens 90313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if yaccdebug: 90413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write("Unused terminals:\n\n") 90513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for s,v in Terminals.items(): 90613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if s != 'error' and not v: 90713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Warning. Token '%s' defined, but not used.\n" % s) 90813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if yaccdebug: _vf.write(" %s\n"% s) 90913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle unused_tok += 1 91013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 91113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Print out all of the productions 91213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if yaccdebug: 91313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write("\nGrammar\n\n") 91413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for i in range(1,len(Productions)): 91513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write("Rule %-5d %s\n" % (i, Productions[i])) 91613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 91713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle unused_prod = 0 91813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Verify the use of all productions 91913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for s,v in Nonterminals.items(): 92013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not v: 92113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p = Prodnames[s][0] 92213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("%s:%d: Warning. Rule '%s' defined, but not used.\n" % (p.file,p.line, s)) 92313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle unused_prod += 1 92413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 92513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 92613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if unused_tok == 1: 92713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Warning. There is 1 unused token.\n") 92813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if unused_tok > 1: 92913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Warning. There are %d unused tokens.\n" % unused_tok) 93013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 93113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if unused_prod == 1: 93213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Warning. There is 1 unused rule.\n") 93313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if unused_prod > 1: 93413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Warning. There are %d unused rules.\n" % unused_prod) 93513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 93613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if yaccdebug: 93713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write("\nTerminals, with rules where they appear\n\n") 93813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ks = Terminals.keys() 93913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ks.sort() 94013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for k in ks: 94113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write("%-20s : %s\n" % (k, " ".join([str(s) for s in Terminals[k]]))) 94213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write("\nNonterminals, with rules where they appear\n\n") 94313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ks = Nonterminals.keys() 94413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ks.sort() 94513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for k in ks: 94613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write("%-20s : %s\n" % (k, " ".join([str(s) for s in Nonterminals[k]]))) 94713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 94813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if (cycle_check): 94913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle compute_reachable() 95013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle error += compute_terminates() 95113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# error += check_cycles() 95213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return error 95313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 95413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 95513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# build_lritems() 95613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 95713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This function walks the list of productions and builds a complete set of the 95813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# LR items. The LR items are stored in two ways: First, they are uniquely 95913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# numbered and placed in the list _lritems. Second, a linked list of LR items 96013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# is built for each production. For example: 96113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 96213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# E -> E PLUS E 96313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 96413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Creates the list 96513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 96613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# [E -> . E PLUS E, E -> E . PLUS E, E -> E PLUS . E, E -> E PLUS E . ] 96713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 96813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 96913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef build_lritems(): 97013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in Productions: 97113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lastlri = p 97213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lri = p.lr_item(0) 97313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i = 0 97413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle while 1: 97513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lri = p.lr_item(i) 97613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lastlri.lr_next = lri 97713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not lri: break 97813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lri.lr_num = len(LRitems) 97913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle LRitems.append(lri) 98013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lastlri = lri 98113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i += 1 98213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 98313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # In order for the rest of the parser generator to work, we need to 98413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # guarantee that no more lritems are generated. Therefore, we nuke 98513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # the p.lr_item method. (Only used in debugging) 98613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Production.lr_item = None 98713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 98813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 98913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# add_precedence() 99013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 99113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Given a list of precedence rules, add to the precedence table. 99213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 99313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 99413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef add_precedence(plist): 99513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle plevel = 0 99613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle error = 0 99713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in plist: 99813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle plevel += 1 99913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 100013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle prec = p[0] 100113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle terms = p[1:] 100213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if prec != 'left' and prec != 'right' and prec != 'nonassoc': 100313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Invalid precedence '%s'\n" % prec) 100413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return -1 100513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for t in terms: 100613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if Precedence.has_key(t): 100713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Precedence already specified for terminal '%s'\n" % t) 100813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle error += 1 100913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle continue 101013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Precedence[t] = (prec,plevel) 101113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except: 101213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Invalid precedence table.\n") 101313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle error += 1 101413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 101513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return error 101613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 101713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 101813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# augment_grammar() 101913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 102013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Compute the augmented grammar. This is just a rule S' -> start where start 102113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# is the starting symbol. 102213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 102313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 102413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef augment_grammar(start=None): 102513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not start: 102613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle start = Productions[1].name 102713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Productions[0] = Production(name="S'",prod=[start],number=0,len=1,prec=('right',0),func=None) 102813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Productions[0].usyms = [ start ] 102913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Nonterminals[start].append(0) 103013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 103113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 103213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ------------------------------------------------------------------------- 103313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# first() 103413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 103513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Compute the value of FIRST1(beta) where beta is a tuple of symbols. 103613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 103713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# During execution of compute_first1, the result may be incomplete. 103813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Afterward (e.g., when called from compute_follow()), it will be complete. 103913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ------------------------------------------------------------------------- 104013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef first(beta): 104113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 104213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # We are computing First(x1,x2,x3,...,xn) 104313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle result = [ ] 104413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for x in beta: 104513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle x_produces_empty = 0 104613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 104713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Add all the non-<empty> symbols of First[x] to the result. 104813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for f in First[x]: 104913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if f == '<empty>': 105013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle x_produces_empty = 1 105113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 105213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if f not in result: result.append(f) 105313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 105413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if x_produces_empty: 105513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # We have to consider the next x in beta, 105613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # i.e. stay in the loop. 105713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle pass 105813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 105913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # We don't have to consider any further symbols in beta. 106013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle break 106113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 106213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # There was no 'break' from the loop, 106313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # so x_produces_empty was true for all x in beta, 106413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # so beta produces empty as well. 106513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle result.append('<empty>') 106613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 106713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return result 106813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 106913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 107013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# FOLLOW(x) 107113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Given a non-terminal. This function computes the set of all symbols 107213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# that might follow it. Dragon book, p. 189. 107313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 107413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef compute_follow(start=None): 107513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Add '$end' to the follow list of the start symbol 107613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for k in Nonterminals.keys(): 107713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Follow[k] = [ ] 107813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 107913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not start: 108013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle start = Productions[1].name 108113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 108213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Follow[start] = [ '$end' ] 108313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 108413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle while 1: 108513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle didadd = 0 108613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in Productions[1:]: 108713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Here is the production set 108813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for i in range(len(p.prod)): 108913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle B = p.prod[i] 109013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if Nonterminals.has_key(B): 109113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Okay. We got a non-terminal in a production 109213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle fst = first(p.prod[i+1:]) 109313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle hasempty = 0 109413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for f in fst: 109513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if f != '<empty>' and f not in Follow[B]: 109613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Follow[B].append(f) 109713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle didadd = 1 109813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if f == '<empty>': 109913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle hasempty = 1 110013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if hasempty or i == (len(p.prod)-1): 110113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Add elements of follow(a) to follow(b) 110213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for f in Follow[p.name]: 110313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if f not in Follow[B]: 110413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Follow[B].append(f) 110513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle didadd = 1 110613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not didadd: break 110713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 110813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if 0 and yaccdebug: 110913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write('\nFollow:\n') 111013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for k in Nonterminals.keys(): 111113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write("%-20s : %s\n" % (k, " ".join([str(s) for s in Follow[k]]))) 111213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 111313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ------------------------------------------------------------------------- 111413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# compute_first1() 111513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 111613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Compute the value of FIRST1(X) for all symbols 111713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ------------------------------------------------------------------------- 111813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef compute_first1(): 111913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 112013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Terminals: 112113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for t in Terminals.keys(): 112213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle First[t] = [t] 112313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 112413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle First['$end'] = ['$end'] 112513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle First['#'] = ['#'] # what's this for? 112613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 112713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Nonterminals: 112813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 112913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Initialize to the empty set: 113013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for n in Nonterminals.keys(): 113113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle First[n] = [] 113213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 113313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Then propagate symbols until no change: 113413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle while 1: 113513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle some_change = 0 113613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for n in Nonterminals.keys(): 113713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in Prodnames[n]: 113813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for f in first(p.prod): 113913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if f not in First[n]: 114013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle First[n].append( f ) 114113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle some_change = 1 114213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not some_change: 114313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle break 114413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 114513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if 0 and yaccdebug: 114613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write('\nFirst:\n') 114713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for k in Nonterminals.keys(): 114813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write("%-20s : %s\n" % 114913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle (k, " ".join([str(s) for s in First[k]]))) 115013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 115113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 115213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# === SLR Generation === 115313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 115413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# The following functions are used to construct SLR (Simple LR) parsing tables 115513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# as described on p.221-229 of the dragon book. 115613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 115713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 115813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Global variables for the LR parsing engine 115913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef lr_init_vars(): 116013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global _lr_action, _lr_goto, _lr_method 116113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global _lr_goto_cache, _lr0_cidhash 116213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 116313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr_action = { } # Action table 116413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr_goto = { } # Goto table 116513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr_method = "Unknown" # LR method used 116613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr_goto_cache = { } 116713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr0_cidhash = { } 116813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 116913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 117013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Compute the LR(0) closure operation on I, where I is a set of LR(0) items. 117113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# prodlist is a list of productions. 117213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 117313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle_add_count = 0 # Counter used to detect cycles 117413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 117513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef lr0_closure(I): 117613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global _add_count 117713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 117813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _add_count += 1 117913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle prodlist = Productions 118013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 118113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Add everything in I to J 118213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle J = I[:] 118313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle didadd = 1 118413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle while didadd: 118513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle didadd = 0 118613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for j in J: 118713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for x in j.lrafter: 118813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if x.lr0_added == _add_count: continue 118913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Add B --> .G to J 119013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle J.append(x.lr_next) 119113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle x.lr0_added = _add_count 119213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle didadd = 1 119313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 119413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return J 119513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 119613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Compute the LR(0) goto function goto(I,X) where I is a set 119713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# of LR(0) items and X is a grammar symbol. This function is written 119813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# in a way that guarantees uniqueness of the generated goto sets 119913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# (i.e. the same goto set will never be returned as two different Python 120013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# objects). With uniqueness, we can later do fast set comparisons using 120113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# id(obj) instead of element-wise comparison. 120213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 120313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef lr0_goto(I,x): 120413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # First we look for a previously cached entry 120513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle g = _lr_goto_cache.get((id(I),x),None) 120613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if g: return g 120713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 120813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Now we generate the goto set in a way that guarantees uniqueness 120913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # of the result 121013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 121113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle s = _lr_goto_cache.get(x,None) 121213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not s: 121313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle s = { } 121413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr_goto_cache[x] = s 121513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 121613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle gs = [ ] 121713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in I: 121813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle n = p.lr_next 121913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if n and n.lrbefore == x: 122013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle s1 = s.get(id(n),None) 122113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not s1: 122213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle s1 = { } 122313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle s[id(n)] = s1 122413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle gs.append(n) 122513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle s = s1 122613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle g = s.get('$end',None) 122713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not g: 122813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if gs: 122913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle g = lr0_closure(gs) 123013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle s['$end'] = g 123113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 123213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle s['$end'] = gs 123313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr_goto_cache[(id(I),x)] = g 123413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return g 123513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 123613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle_lr0_cidhash = { } 123713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 123813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Compute the LR(0) sets of item function 123913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef lr0_items(): 124013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 124113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle C = [ lr0_closure([Productions[0].lr_next]) ] 124213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i = 0 124313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for I in C: 124413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr0_cidhash[id(I)] = i 124513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i += 1 124613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 124713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Loop over the items in C and each grammar symbols 124813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i = 0 124913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle while i < len(C): 125013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle I = C[i] 125113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i += 1 125213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 125313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Collect all of the symbols that could possibly be in the goto(I,X) sets 125413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle asyms = { } 125513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for ii in I: 125613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for s in ii.usyms: 125713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle asyms[s] = None 125813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 125913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for x in asyms.keys(): 126013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle g = lr0_goto(I,x) 126113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not g: continue 126213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if _lr0_cidhash.has_key(id(g)): continue 126313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr0_cidhash[id(g)] = len(C) 126413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle C.append(g) 126513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 126613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return C 126713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 126813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 126913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ==== LALR(1) Parsing ==== 127013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 127113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# LALR(1) parsing is almost exactly the same as SLR except that instead of 127213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# relying upon Follow() sets when performing reductions, a more selective 127313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# lookahead set that incorporates the state of the LR(0) machine is utilized. 127413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Thus, we mainly just have to focus on calculating the lookahead sets. 127513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 127613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# The method used here is due to DeRemer and Pennelo (1982). 127713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 127813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# DeRemer, F. L., and T. J. Pennelo: "Efficient Computation of LALR(1) 127913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Lookahead Sets", ACM Transactions on Programming Languages and Systems, 128013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Vol. 4, No. 4, Oct. 1982, pp. 615-649 128113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 128213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Further details can also be found in: 128313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 128413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# J. Tremblay and P. Sorenson, "The Theory and Practice of Compiler Writing", 128513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# McGraw-Hill Book Company, (1985). 128613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 128713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Note: This implementation is a complete replacement of the LALR(1) 128813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# implementation in PLY-1.x releases. That version was based on 128913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# a less efficient algorithm and it had bugs in its implementation. 129013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 129113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 129213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 129313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# compute_nullable_nonterminals() 129413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 129513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Creates a dictionary containing all of the non-terminals that might produce 129613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# an empty production. 129713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 129813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 129913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef compute_nullable_nonterminals(): 130013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle nullable = {} 130113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle num_nullable = 0 130213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle while 1: 130313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in Productions[1:]: 130413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if p.len == 0: 130513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle nullable[p.name] = 1 130613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle continue 130713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for t in p.prod: 130813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not nullable.has_key(t): break 130913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 131013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle nullable[p.name] = 1 131113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if len(nullable) == num_nullable: break 131213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle num_nullable = len(nullable) 131313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return nullable 131413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 131513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 131613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# find_nonterminal_trans(C) 131713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 131813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Given a set of LR(0) items, this functions finds all of the non-terminal 131913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# transitions. These are transitions in which a dot appears immediately before 132013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# a non-terminal. Returns a list of tuples of the form (state,N) where state 132113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# is the state number and N is the nonterminal symbol. 132213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 132313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# The input C is the set of LR(0) items. 132413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 132513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 132613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef find_nonterminal_transitions(C): 132713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle trans = [] 132813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for state in range(len(C)): 132913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in C[state]: 133013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if p.lr_index < p.len - 1: 133113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle t = (state,p.prod[p.lr_index+1]) 133213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if Nonterminals.has_key(t[1]): 133313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if t not in trans: trans.append(t) 133413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle state = state + 1 133513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return trans 133613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 133713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 133813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# dr_relation() 133913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 134013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Computes the DR(p,A) relationships for non-terminal transitions. The input 134113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# is a tuple (state,N) where state is a number and N is a nonterminal symbol. 134213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 134313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Returns a list of terminals. 134413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 134513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 134613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef dr_relation(C,trans,nullable): 134713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle dr_set = { } 134813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle state,N = trans 134913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle terms = [] 135013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 135113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle g = lr0_goto(C[state],N) 135213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in g: 135313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if p.lr_index < p.len - 1: 135413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle a = p.prod[p.lr_index+1] 135513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if Terminals.has_key(a): 135613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if a not in terms: terms.append(a) 135713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 135813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # This extra bit is to handle the start state 135913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if state == 0 and N == Productions[0].prod[0]: 136013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle terms.append('$end') 136113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 136213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return terms 136313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 136413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 136513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# reads_relation() 136613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 136713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Computes the READS() relation (p,A) READS (t,C). 136813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 136913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 137013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef reads_relation(C, trans, empty): 137113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Look for empty transitions 137213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle rel = [] 137313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle state, N = trans 137413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 137513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle g = lr0_goto(C[state],N) 137613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle j = _lr0_cidhash.get(id(g),-1) 137713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in g: 137813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if p.lr_index < p.len - 1: 137913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle a = p.prod[p.lr_index + 1] 138013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if empty.has_key(a): 138113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle rel.append((j,a)) 138213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 138313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return rel 138413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 138513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 138613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# compute_lookback_includes() 138713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 138813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Determines the lookback and includes relations 138913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 139013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# LOOKBACK: 139113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 139213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This relation is determined by running the LR(0) state machine forward. 139313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# For example, starting with a production "N : . A B C", we run it forward 139413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# to obtain "N : A B C ." We then build a relationship between this final 139513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# state and the starting state. These relationships are stored in a dictionary 139613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# lookdict. 139713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 139813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# INCLUDES: 139913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 140013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Computes the INCLUDE() relation (p,A) INCLUDES (p',B). 140113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 140213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This relation is used to determine non-terminal transitions that occur 140313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# inside of other non-terminal transition states. (p,A) INCLUDES (p', B) 140413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# if the following holds: 140513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 140613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# B -> LAT, where T -> epsilon and p' -L-> p 140713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 140813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# L is essentially a prefix (which may be empty), T is a suffix that must be 140913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# able to derive an empty string. State p' must lead to state p with the string L. 141013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 141113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 141213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 141313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef compute_lookback_includes(C,trans,nullable): 141413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 141513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookdict = {} # Dictionary of lookback relations 141613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle includedict = {} # Dictionary of include relations 141713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 141813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Make a dictionary of non-terminal transitions 141913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle dtrans = {} 142013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for t in trans: 142113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle dtrans[t] = 1 142213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 142313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Loop over all transitions and compute lookbacks and includes 142413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for state,N in trans: 142513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookb = [] 142613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle includes = [] 142713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in C[state]: 142813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if p.name != N: continue 142913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 143013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Okay, we have a name match. We now follow the production all the way 143113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # through the state machine until we get the . on the right hand side 143213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 143313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lr_index = p.lr_index 143413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle j = state 143513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle while lr_index < p.len - 1: 143613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lr_index = lr_index + 1 143713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle t = p.prod[lr_index] 143813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 143913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Check to see if this symbol and state are a non-terminal transition 144013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if dtrans.has_key((j,t)): 144113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Yes. Okay, there is some chance that this is an includes relation 144213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # the only way to know for certain is whether the rest of the 144313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # production derives empty 144413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 144513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle li = lr_index + 1 144613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle while li < p.len: 144713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if Terminals.has_key(p.prod[li]): break # No forget it 144813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not nullable.has_key(p.prod[li]): break 144913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle li = li + 1 145013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 145113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Appears to be a relation between (j,t) and (state,N) 145213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle includes.append((j,t)) 145313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 145413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle g = lr0_goto(C[j],t) # Go to next set 145513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle j = _lr0_cidhash.get(id(g),-1) # Go to next state 145613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 145713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # When we get here, j is the final state, now we have to locate the production 145813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for r in C[j]: 145913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if r.name != p.name: continue 146013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if r.len != p.len: continue 146113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i = 0 146213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # This look is comparing a production ". A B C" with "A B C ." 146313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle while i < r.lr_index: 146413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if r.prod[i] != p.prod[i+1]: break 146513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i = i + 1 146613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 146713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookb.append((j,r)) 146813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for i in includes: 146913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not includedict.has_key(i): includedict[i] = [] 147013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle includedict[i].append((state,N)) 147113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookdict[(state,N)] = lookb 147213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 147313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return lookdict,includedict 147413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 147513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 147613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# digraph() 147713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# traverse() 147813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 147913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# The following two functions are used to compute set valued functions 148013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# of the form: 148113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 148213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# F(x) = F'(x) U U{F(y) | x R y} 148313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 148413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This is used to compute the values of Read() sets as well as FOLLOW sets 148513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# in LALR(1) generation. 148613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 148713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Inputs: X - An input set 148813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# R - A relation 148913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# FP - Set-valued function 149013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ------------------------------------------------------------------------------ 149113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 149213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef digraph(X,R,FP): 149313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle N = { } 149413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for x in X: 149513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle N[x] = 0 149613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle stack = [] 149713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle F = { } 149813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for x in X: 149913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if N[x] == 0: traverse(x,N,stack,F,X,R,FP) 150013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return F 150113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 150213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef traverse(x,N,stack,F,X,R,FP): 150313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle stack.append(x) 150413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle d = len(stack) 150513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle N[x] = d 150613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle F[x] = FP(x) # F(X) <- F'(x) 150713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 150813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle rel = R(x) # Get y's related to x 150913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for y in rel: 151013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if N[y] == 0: 151113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle traverse(y,N,stack,F,X,R,FP) 151213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle N[x] = min(N[x],N[y]) 151313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for a in F.get(y,[]): 151413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if a not in F[x]: F[x].append(a) 151513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if N[x] == d: 151613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle N[stack[-1]] = sys.maxint 151713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle F[stack[-1]] = F[x] 151813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle element = stack.pop() 151913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle while element != x: 152013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle N[stack[-1]] = sys.maxint 152113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle F[stack[-1]] = F[x] 152213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle element = stack.pop() 152313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 152413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 152513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# compute_read_sets() 152613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 152713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Given a set of LR(0) items, this function computes the read sets. 152813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 152913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Inputs: C = Set of LR(0) items 153013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ntrans = Set of nonterminal transitions 153113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# nullable = Set of empty transitions 153213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 153313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Returns a set containing the read sets 153413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 153513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 153613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef compute_read_sets(C, ntrans, nullable): 153713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle FP = lambda x: dr_relation(C,x,nullable) 153813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle R = lambda x: reads_relation(C,x,nullable) 153913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle F = digraph(ntrans,R,FP) 154013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return F 154113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 154213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 154313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# compute_follow_sets() 154413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 154513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Given a set of LR(0) items, a set of non-terminal transitions, a readset, 154613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# and an include set, this function computes the follow sets 154713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 154813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Follow(p,A) = Read(p,A) U U {Follow(p',B) | (p,A) INCLUDES (p',B)} 154913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 155013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Inputs: 155113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ntrans = Set of nonterminal transitions 155213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# readsets = Readset (previously computed) 155313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# inclsets = Include sets (previously computed) 155413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 155513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Returns a set containing the follow sets 155613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 155713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 155813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef compute_follow_sets(ntrans,readsets,inclsets): 155913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle FP = lambda x: readsets[x] 156013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle R = lambda x: inclsets.get(x,[]) 156113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle F = digraph(ntrans,R,FP) 156213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return F 156313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 156413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 156513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# add_lookaheads() 156613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 156713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Attaches the lookahead symbols to grammar rules. 156813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 156913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Inputs: lookbacks - Set of lookback relations 157013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# followset - Computed follow set 157113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 157213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This function directly attaches the lookaheads to productions contained 157313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# in the lookbacks set 157413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 157513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 157613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef add_lookaheads(lookbacks,followset): 157713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for trans,lb in lookbacks.items(): 157813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Loop over productions in lookback 157913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for state,p in lb: 158013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not p.lookaheads.has_key(state): 158113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.lookaheads[state] = [] 158213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f = followset.get(trans,[]) 158313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for a in f: 158413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if a not in p.lookaheads[state]: p.lookaheads[state].append(a) 158513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 158613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 158713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# add_lalr_lookaheads() 158813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 158913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This function does all of the work of adding lookahead information for use 159013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# with LALR parsing 159113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 159213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 159313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef add_lalr_lookaheads(C): 159413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Determine all of the nullable nonterminals 159513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle nullable = compute_nullable_nonterminals() 159613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 159713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Find all non-terminal transitions 159813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle trans = find_nonterminal_transitions(C) 159913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 160013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Compute read sets 160113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle readsets = compute_read_sets(C,trans,nullable) 160213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 160313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Compute lookback/includes relations 160413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lookd, included = compute_lookback_includes(C,trans,nullable) 160513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 160613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Compute LALR FOLLOW sets 160713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle followsets = compute_follow_sets(trans,readsets,included) 160813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 160913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Add all of the lookaheads 161013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle add_lookaheads(lookd,followsets) 161113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 161213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 161313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# lr_parse_table() 161413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 161513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This function constructs the parse tables for SLR or LALR 161613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 161713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef lr_parse_table(method): 161813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global _lr_method 161913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle goto = _lr_goto # Goto array 162013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle action = _lr_action # Action array 162113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle actionp = { } # Action production array (temporary) 162213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 162313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr_method = method 162413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 162513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle n_srconflict = 0 162613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle n_rrconflict = 0 162713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 162813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if yaccdebug: 162913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: Generating %s parsing table...\n" % method) 163013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write("\n\nParsing method: %s\n\n" % method) 163113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 163213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Step 1: Construct C = { I0, I1, ... IN}, collection of LR(0) items 163313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # This determines the number of states 163413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 163513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle C = lr0_items() 163613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 163713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if method == 'LALR': 163813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle add_lalr_lookaheads(C) 163913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 164013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Build the parser table, state by state 164113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle st = 0 164213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for I in C: 164313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Loop over each production in I 164413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle actlist = [ ] # List of actions 164513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 164613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if yaccdebug: 164713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write("\nstate %d\n\n" % st) 164813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in I: 164913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write(" (%d) %s\n" % (p.number, str(p))) 165013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write("\n") 165113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 165213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in I: 165313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 165413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if p.prod[-1] == ".": 165513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if p.name == "S'": 165613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Start symbol. Accept! 165713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle action[st,"$end"] = 0 165813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle actionp[st,"$end"] = p 165913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 166013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # We are at the end of a production. Reduce! 166113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if method == 'LALR': 166213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle laheads = p.lookaheads[st] 166313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 166413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle laheads = Follow[p.name] 166513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for a in laheads: 166613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle actlist.append((a,p,"reduce using rule %d (%s)" % (p.number,p))) 166713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle r = action.get((st,a),None) 166813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if r is not None: 166913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Whoa. Have a shift/reduce or reduce/reduce conflict 167013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if r > 0: 167113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Need to decide on shift or reduce here 167213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # By default we favor shifting. Need to add 167313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # some precedence rules here. 167413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sprec,slevel = Productions[actionp[st,a].number].prec 167513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle rprec,rlevel = Precedence.get(a,('right',0)) 167613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if (slevel < rlevel) or ((slevel == rlevel) and (rprec == 'left')): 167713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # We really need to reduce here. 167813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle action[st,a] = -p.number 167913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle actionp[st,a] = p 168013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not slevel and not rlevel: 168113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vfc.write("shift/reduce conflict in state %d resolved as reduce.\n" % st) 168213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write(" ! shift/reduce conflict for %s resolved as reduce.\n" % a) 168313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle n_srconflict += 1 168413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle elif (slevel == rlevel) and (rprec == 'nonassoc'): 168513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle action[st,a] = None 168613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 168713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Hmmm. Guess we'll keep the shift 168813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not rlevel: 168913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vfc.write("shift/reduce conflict in state %d resolved as shift.\n" % st) 169013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write(" ! shift/reduce conflict for %s resolved as shift.\n" % a) 169113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle n_srconflict +=1 169213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle elif r < 0: 169313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Reduce/reduce conflict. In this case, we favor the rule 169413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # that was defined first in the grammar file 169513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle oldp = Productions[-r] 169613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle pp = Productions[p.number] 169713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if oldp.line > pp.line: 169813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle action[st,a] = -p.number 169913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle actionp[st,a] = p 170013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # sys.stderr.write("Reduce/reduce conflict in state %d\n" % st) 170113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle n_rrconflict += 1 170213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vfc.write("reduce/reduce conflict in state %d resolved using rule %d (%s).\n" % (st, actionp[st,a].number, actionp[st,a])) 170313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write(" ! reduce/reduce conflict for %s resolved using rule %d (%s).\n" % (a,actionp[st,a].number, actionp[st,a])) 170413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 170513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("Unknown conflict in state %d\n" % st) 170613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 170713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle action[st,a] = -p.number 170813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle actionp[st,a] = p 170913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 171013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i = p.lr_index 171113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle a = p.prod[i+1] # Get symbol right after the "." 171213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if Terminals.has_key(a): 171313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle g = lr0_goto(I,a) 171413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle j = _lr0_cidhash.get(id(g),-1) 171513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if j >= 0: 171613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # We are in a shift state 171713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle actlist.append((a,p,"shift and go to state %d" % j)) 171813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle r = action.get((st,a),None) 171913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if r is not None: 172013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Whoa have a shift/reduce or shift/shift conflict 172113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if r > 0: 172213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if r != j: 172313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("Shift/shift conflict in state %d\n" % st) 172413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle elif r < 0: 172513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Do a precedence check. 172613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # - if precedence of reduce rule is higher, we reduce. 172713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # - if precedence of reduce is same and left assoc, we reduce. 172813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # - otherwise we shift 172913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle rprec,rlevel = Productions[actionp[st,a].number].prec 173013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sprec,slevel = Precedence.get(a,('right',0)) 173113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if (slevel > rlevel) or ((slevel == rlevel) and (rprec != 'left')): 173213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # We decide to shift here... highest precedence to shift 173313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle action[st,a] = j 173413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle actionp[st,a] = p 173513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not rlevel: 173613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle n_srconflict += 1 173713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vfc.write("shift/reduce conflict in state %d resolved as shift.\n" % st) 173813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write(" ! shift/reduce conflict for %s resolved as shift.\n" % a) 173913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle elif (slevel == rlevel) and (rprec == 'nonassoc'): 174013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle action[st,a] = None 174113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 174213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Hmmm. Guess we'll keep the reduce 174313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not slevel and not rlevel: 174413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle n_srconflict +=1 174513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vfc.write("shift/reduce conflict in state %d resolved as reduce.\n" % st) 174613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write(" ! shift/reduce conflict for %s resolved as reduce.\n" % a) 174713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 174813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 174913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("Unknown conflict in state %d\n" % st) 175013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 175113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle action[st,a] = j 175213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle actionp[st,a] = p 175313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 175413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except StandardError,e: 175513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError, "Hosed in lr_parse_table", e 175613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 175713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Print the actions associated with each terminal 175813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if yaccdebug: 175913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _actprint = { } 176013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for a,p,m in actlist: 176113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if action.has_key((st,a)): 176213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if p is actionp[st,a]: 176313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write(" %-15s %s\n" % (a,m)) 176413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _actprint[(a,m)] = 1 176513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write("\n") 176613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for a,p,m in actlist: 176713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if action.has_key((st,a)): 176813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if p is not actionp[st,a]: 176913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not _actprint.has_key((a,m)): 177013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write(" ! %-15s [ %s ]\n" % (a,m)) 177113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _actprint[(a,m)] = 1 177213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 177313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Construct the goto table for this state 177413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if yaccdebug: 177513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write("\n") 177613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle nkeys = { } 177713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for ii in I: 177813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for s in ii.usyms: 177913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if Nonterminals.has_key(s): 178013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle nkeys[s] = None 178113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for n in nkeys.keys(): 178213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle g = lr0_goto(I,n) 178313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle j = _lr0_cidhash.get(id(g),-1) 178413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if j >= 0: 178513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle goto[st,n] = j 178613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if yaccdebug: 178713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _vf.write(" %-30s shift and go to state %d\n" % (n,j)) 178813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 178913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle st += 1 179013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 179113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if yaccdebug: 179213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if n_srconflict == 1: 179313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: %d shift/reduce conflict\n" % n_srconflict) 179413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if n_srconflict > 1: 179513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: %d shift/reduce conflicts\n" % n_srconflict) 179613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if n_rrconflict == 1: 179713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: %d reduce/reduce conflict\n" % n_rrconflict) 179813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if n_rrconflict > 1: 179913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle sys.stderr.write("yacc: %d reduce/reduce conflicts\n" % n_rrconflict) 180013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 180113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 180213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ==== LR Utility functions ==== 180313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 180413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 180513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 180613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# _lr_write_tables() 180713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 180813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This function writes the LR parsing tables to a file 180913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 181013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 181113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef lr_write_tables(modulename=tab_module,outputdir=''): 181213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle filename = os.path.join(outputdir,modulename) + ".py" 181313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 181413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f = open(filename,"w") 181513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 181613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write(""" 181713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# %s 181813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# This file is automatically generated. Do not edit. 181913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 182013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle_lr_method = %s 182113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 182213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle_lr_signature = %s 182313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle""" % (filename, repr(_lr_method), repr(Signature.digest()))) 182413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 182513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Change smaller to 0 to go back to original tables 182613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle smaller = 1 182713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 182813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Factor out names to try and make smaller 182913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if smaller: 183013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle items = { } 183113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 183213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for k,v in _lr_action.items(): 183313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i = items.get(k[1]) 183413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not i: 183513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i = ([],[]) 183613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle items[k[1]] = i 183713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i[0].append(k[0]) 183813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i[1].append(v) 183913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 184013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("\n_lr_action_items = {") 184113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for k,v in items.items(): 184213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("%r:([" % k) 184313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for i in v[0]: 184413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("%r," % i) 184513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("],[") 184613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for i in v[1]: 184713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("%r," % i) 184813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 184913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("]),") 185013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("}\n") 185113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 185213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write(""" 185313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle_lr_action = { } 185413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindlefor _k, _v in _lr_action_items.items(): 185513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for _x,_y in zip(_v[0],_v[1]): 185613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr_action[(_x,_k)] = _y 185713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledel _lr_action_items 185813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle""") 185913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 186013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 186113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("\n_lr_action = { "); 186213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for k,v in _lr_action.items(): 186313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("(%r,%r):%r," % (k[0],k[1],v)) 186413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("}\n"); 186513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 186613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if smaller: 186713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Factor out names to try and make smaller 186813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle items = { } 186913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 187013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for k,v in _lr_goto.items(): 187113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i = items.get(k[1]) 187213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not i: 187313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i = ([],[]) 187413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle items[k[1]] = i 187513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i[0].append(k[0]) 187613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle i[1].append(v) 187713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 187813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("\n_lr_goto_items = {") 187913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for k,v in items.items(): 188013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("%r:([" % k) 188113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for i in v[0]: 188213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("%r," % i) 188313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("],[") 188413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for i in v[1]: 188513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("%r," % i) 188613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 188713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("]),") 188813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("}\n") 188913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 189013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write(""" 189113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle_lr_goto = { } 189213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindlefor _k, _v in _lr_goto_items.items(): 189313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for _x,_y in zip(_v[0],_v[1]): 189413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr_goto[(_x,_k)] = _y 189513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledel _lr_goto_items 189613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle""") 189713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 189813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("\n_lr_goto = { "); 189913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for k,v in _lr_goto.items(): 190013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("(%r,%r):%r," % (k[0],k[1],v)) 190113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("}\n"); 190213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 190313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Write production table 190413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("_lr_productions = [\n") 190513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in Productions: 190613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if p: 190713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if (p.func): 190813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write(" (%r,%d,%r,%r,%d),\n" % (p.name, p.len, p.func.__name__,p.file,p.line)) 190913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 191013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write(" (%r,%d,None,None,None),\n" % (p.name, p.len)) 191113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 191213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write(" None,\n") 191313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("]\n") 191413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 191513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.close() 191613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 191713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except IOError,e: 191813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle print "Unable to create '%s'" % filename 191913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle print e 192013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return 192113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 192213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef lr_read_tables(module=tab_module,optimize=0): 192313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global _lr_action, _lr_goto, _lr_productions, _lr_method 192413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 192513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle exec "import %s as parsetab" % module 192613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 192713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if (optimize) or (Signature.digest() == parsetab._lr_signature): 192813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr_action = parsetab._lr_action 192913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr_goto = parsetab._lr_goto 193013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr_productions = parsetab._lr_productions 193113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _lr_method = parsetab._lr_method 193213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return 1 193313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 193413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return 0 193513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 193613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except (ImportError,AttributeError): 193713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return 0 193813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 193913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 194013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Available instance types. This is used when parsers are defined by a class. 194113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# it's a little funky because I want to preserve backwards compatibility 194213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# with Python 2.0 where types.ObjectType is undefined. 194313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 194413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindletry: 194513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _INSTANCETYPE = (types.InstanceType, types.ObjectType) 194613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindleexcept AttributeError: 194713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _INSTANCETYPE = types.InstanceType 194813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 194913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 195013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# yacc(module) 195113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# 195213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Build the parser module 195313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# ----------------------------------------------------------------------------- 195413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 195513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef 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=''): 195613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global yaccdebug 195713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle yaccdebug = debug 195813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 195913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle initialize_vars() 196013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle files = { } 196113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle error = 0 196213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 196313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 196413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Add parsing method to signature 196513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Signature.update(method) 196613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 196713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # If a "module" parameter was supplied, extract its dictionary. 196813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Note: a module may in fact be an instance as well. 196913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 197013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if module: 197113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # User supplied a module object. 197213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if isinstance(module, types.ModuleType): 197313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ldict = module.__dict__ 197413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle elif isinstance(module, _INSTANCETYPE): 197513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle _items = [(k,getattr(module,k)) for k in dir(module)] 197613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ldict = { } 197713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for i in _items: 197813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ldict[i[0]] = i[1] 197913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 198013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise ValueError,"Expected a module" 198113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 198213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 198313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # No module given. We might be able to get information from the caller. 198413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Throw an exception and unwind the traceback to get the globals 198513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 198613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 198713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise RuntimeError 198813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except RuntimeError: 198913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle e,b,t = sys.exc_info() 199013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f = t.tb_frame 199113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f = f.f_back # Walk out to our calling function 199213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ldict = f.f_globals # Grab its globals dictionary 199313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 199413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Add starting symbol to signature 199513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not start: 199613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle start = ldict.get("start",None) 199713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if start: 199813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Signature.update(start) 199913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 200013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # If running in optimized mode. We're going to 200113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 200213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if (optimize and lr_read_tables(tabmodule,1)): 200313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Read parse table 200413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle del Productions[:] 200513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for p in _lr_productions: 200613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not p: 200713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Productions.append(None) 200813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 200913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle m = MiniProduction() 201013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle m.name = p[0] 201113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle m.len = p[1] 201213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle m.file = p[3] 201313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle m.line = p[4] 201413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if p[2]: 201513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle m.func = ldict[p[2]] 201613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Productions.append(m) 201713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 201813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 201913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Get the tokens map 202013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if (module and isinstance(module,_INSTANCETYPE)): 202113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle tokens = getattr(module,"tokens",None) 202213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 202313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle tokens = ldict.get("tokens",None) 202413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 202513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not tokens: 202613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError,"module does not define a list 'tokens'" 202713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not (isinstance(tokens,types.ListType) or isinstance(tokens,types.TupleType)): 202813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError,"tokens must be a list or tuple." 202913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 203013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Check to see if a requires dictionary is defined. 203113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle requires = ldict.get("require",None) 203213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if requires: 203313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not (isinstance(requires,types.DictType)): 203413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError,"require must be a dictionary." 203513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 203613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for r,v in requires.items(): 203713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 203813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not (isinstance(v,types.ListType)): 203913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise TypeError 204013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle v1 = [x.split(".") for x in v] 204113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Requires[r] = v1 204213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except StandardError: 204313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle print "Invalid specification for rule '%s' in require. Expected a list of strings" % r 204413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 204513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 204613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Build the dictionary of terminals. We a record a 0 in the 204713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # dictionary to track whether or not a terminal is actually 204813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # used in the grammar 204913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 205013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if 'error' in tokens: 205113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle print "yacc: Illegal token 'error'. Is a reserved word." 205213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError,"Illegal token name" 205313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 205413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for n in tokens: 205513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if Terminals.has_key(n): 205613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle print "yacc: Warning. Token '%s' multiply defined." % n 205713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Terminals[n] = [ ] 205813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 205913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Terminals['error'] = [ ] 206013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 206113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Get the precedence map (if any) 206213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle prec = ldict.get("precedence",None) 206313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if prec: 206413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not (isinstance(prec,types.ListType) or isinstance(prec,types.TupleType)): 206513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError,"precedence must be a list or tuple." 206613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle add_precedence(prec) 206713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Signature.update(repr(prec)) 206813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 206913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for n in tokens: 207013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not Precedence.has_key(n): 207113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Precedence[n] = ('right',0) # Default, right associative, 0 precedence 207213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 207313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Look for error handler 207413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ef = ldict.get('p_error',None) 207513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if ef: 207613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if isinstance(ef,types.FunctionType): 207713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ismethod = 0 207813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle elif isinstance(ef, types.MethodType): 207913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle ismethod = 1 208013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 208113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError,"'p_error' defined, but is not a function or method." 208213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle eline = ef.func_code.co_firstlineno 208313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle efile = ef.func_code.co_filename 208413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle files[efile] = None 208513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 208613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if (ef.func_code.co_argcount != 1+ismethod): 208713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError,"%s:%d: p_error() requires 1 argument." % (efile,eline) 208813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global Errorfunc 208913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Errorfunc = ef 209013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 209113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle print "yacc: Warning. no p_error() function is defined." 209213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 209313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Get the list of built-in functions with p_ prefix 209413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle symbols = [ldict[f] for f in ldict.keys() 209513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if (type(ldict[f]) in (types.FunctionType, types.MethodType) and ldict[f].__name__[:2] == 'p_' 209613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle and ldict[f].__name__ != 'p_error')] 209713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 209813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Check for non-empty symbols 209913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if len(symbols) == 0: 210013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError,"no rules of the form p_rulename are defined." 210113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 210213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Sort the symbols by line number 210313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle symbols.sort(lambda x,y: cmp(x.func_code.co_firstlineno,y.func_code.co_firstlineno)) 210413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 210513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Add all of the symbols to the grammar 210613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for f in symbols: 210713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if (add_function(f)) < 0: 210813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle error += 1 210913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 211013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle files[f.func_code.co_filename] = None 211113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 211213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Make a signature of the docstrings 211313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for f in symbols: 211413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if f.__doc__: 211513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle Signature.update(f.__doc__) 211613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 211713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lr_init_vars() 211813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 211913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if error: 212013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError,"Unable to construct parser." 212113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 212213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not lr_read_tables(tabmodule): 212313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 212413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Validate files 212513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle for filename in files.keys(): 212613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if not validate_file(filename): 212713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle error = 1 212813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 212913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Validate dictionary 213013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle validate_dict(ldict) 213113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 213213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if start and not Prodnames.has_key(start): 213313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError,"Bad starting symbol '%s'" % start 213413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 213513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle augment_grammar(start) 213613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle error = verify_productions(cycle_check=check_recursion) 213713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle otherfunc = [ldict[f] for f in ldict.keys() 213813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if (type(f) in (types.FunctionType,types.MethodType) and ldict[f].__name__[:2] != 'p_')] 213913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 214013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if error: 214113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError,"Unable to construct parser." 214213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 214313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle build_lritems() 214413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle compute_first1() 214513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle compute_follow(start) 214613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 214713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if method in ['SLR','LALR']: 214813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lr_parse_table(method) 214913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle else: 215013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError, "Unknown parsing method '%s'" % method 215113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 215213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if write_tables: 215313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle lr_write_tables(tabmodule,outputdir) 215413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 215513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if yaccdebug: 215613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle try: 215713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f = open(os.path.join(outputdir,debugfile),"w") 215813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write(_vfc.getvalue()) 215913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write("\n\n") 216013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.write(_vf.getvalue()) 216113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle f.close() 216213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle except IOError,e: 216313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle print "yacc: can't create '%s'" % debugfile,e 216413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 216513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Made it here. Create a parser object and set up its internal state. 216613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Set global parse() method to bound method of parser object. 216713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 216813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p = Parser("xyzzy") 216913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.productions = Productions 217013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.errorfunc = Errorfunc 217113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.action = _lr_action 217213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.goto = _lr_goto 217313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.method = _lr_method 217413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle p.require = Requires 217513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 217613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global parse 217713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle parse = p.parse 217813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 217913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global parser 218013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle parser = p 218113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 218213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle # Clean up all of the globals we created 218313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle if (not optimize): 218413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle yacc_cleanup() 218513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle return p 218613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 218713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# yacc_cleanup function. Delete all of the global variables 218813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# used during table construction 218913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 219013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef yacc_cleanup(): 219113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global _lr_action, _lr_goto, _lr_method, _lr_goto_cache 219213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle del _lr_action, _lr_goto, _lr_method, _lr_goto_cache 219313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 219413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global Productions, Prodnames, Prodmap, Terminals 219513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global Nonterminals, First, Follow, Precedence, LRitems 219613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global Errorfunc, Signature, Requires 219713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 219813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle del Productions, Prodnames, Prodmap, Terminals 219913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle del Nonterminals, First, Follow, Precedence, LRitems 220013cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle del Errorfunc, Signature, Requires 220113cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 220213cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle global _vf, _vfc 220313cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle del _vf, _vfc 220413cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 220513cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 220613cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle# Stub that raises an error if parsing is attempted without first calling yacc() 220713cd4c8960688af11ad23b4c946149015c80d54Joshua Brindledef parse(*args,**kwargs): 220813cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle raise YaccError, "yacc: No parser built with yacc()" 220913cd4c8960688af11ad23b4c946149015c80d54Joshua Brindle 2210