yacc.py 126 KB

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