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