yacc.py 134 KB

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