internal.html 28 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874
  1. <html>
  2. <head>
  3. <title>PLY Internals</title>
  4. </head>
  5. <body bgcolor="#ffffff">
  6. <h1>PLY Internals</h1>
  7. <b>
  8. David M. Beazley <br>
  9. dave@dabeaz.com<br>
  10. </b>
  11. <p>
  12. <b>PLY Version: 3.0</b>
  13. <p>
  14. <!-- INDEX -->
  15. <div class="sectiontoc">
  16. <ul>
  17. <li><a href="#internal_nn1">Introduction</a>
  18. <li><a href="#internal_nn2">Grammar Class</a>
  19. <li><a href="#internal_nn3">Productions</a>
  20. <li><a href="#internal_nn4">LRItems</a>
  21. <li><a href="#internal_nn5">LRTable</a>
  22. <li><a href="#internal_nn6">LRGeneratedTable</a>
  23. <li><a href="#internal_nn7">LRParser</a>
  24. <li><a href="#internal_nn8">ParserReflect</a>
  25. <li><a href="#internal_nn9">High-level operation</a>
  26. </ul>
  27. </div>
  28. <!-- INDEX -->
  29. <H2><a name="internal_nn1"></a>1. Introduction</H2>
  30. This document describes classes and functions that make up the internal
  31. operation of PLY. Using this programming interface, it is possible to
  32. manually build an parser using a different interface specification
  33. than what PLY normally uses. For example, you could build a gramar
  34. from information parsed in a completely different input format. Some of
  35. these objects may be useful for building more advanced parsing engines
  36. such as GLR.
  37. <p>
  38. It should be stressed that using PLY at this level is not for the
  39. faint of heart. Generally, it's assumed that you know a bit of
  40. the underlying compiler theory and how an LR parser is put together.
  41. <H2><a name="internal_nn2"></a>2. Grammar Class</H2>
  42. The file <tt>ply.yacc</tt> defines a class <tt>Grammar</tt> that
  43. is used to hold and manipulate information about a grammar
  44. specification. It encapsulates the same basic information
  45. about a grammar that is put into a YACC file including
  46. the list of tokens, precedence rules, and grammar rules.
  47. Various operations are provided to perform different validations
  48. on the grammar. In addition, there are operations to compute
  49. the first and follow sets that are needed by the various table
  50. generation algorithms.
  51. <p>
  52. <tt><b>Grammar(terminals)</b></tt>
  53. <blockquote>
  54. Creates a new grammar object. <tt>terminals</tt> is a list of strings
  55. specifying the terminals for the grammar. An instance <tt>g</tt> of
  56. <tt>Grammar</tt> has the following methods:
  57. </blockquote>
  58. <p>
  59. <b><tt>g.set_precedence(term,assoc,level)</tt></b>
  60. <blockquote>
  61. Sets the precedence level and associativity for a given terminal <tt>term</tt>.
  62. <tt>assoc</tt> is one of <tt>'right'</tt>,
  63. <tt>'left'</tt>, or <tt>'nonassoc'</tt> and <tt>level</tt> is a positive integer. The higher
  64. the value of <tt>level</tt>, the higher the precedence. Here is an example of typical
  65. precedence settings:
  66. <pre>
  67. g.set_precedence('PLUS', 'left',1)
  68. g.set_precedence('MINUS', 'left',1)
  69. g.set_precedence('TIMES', 'left',2)
  70. g.set_precedence('DIVIDE','left',2)
  71. g.set_precedence('UMINUS','left',3)
  72. </pre>
  73. This method must be called prior to adding any productions to the
  74. grammar with <tt>g.add_production()</tt>. The precedence of individual grammar
  75. rules is determined by the precedence of the right-most terminal.
  76. </blockquote>
  77. <p>
  78. <b><tt>g.add_production(name,syms,func=None,file='',line=0)</tt></b>
  79. <blockquote>
  80. Adds a new grammar rule. <tt>name</tt> is the name of the rule,
  81. <tt>syms</tt> is a list of symbols making up the right hand
  82. side of the rule, <tt>func</tt> is the function to call when
  83. reducing the rule. <tt>file</tt> and <tt>line</tt> specify
  84. the filename and line number of the rule and are used for
  85. generating error messages.
  86. <p>
  87. The list of symbols in <tt>syms</tt> may include character
  88. literals and <tt>%prec</tt> specifiers. Here are some
  89. examples:
  90. <pre>
  91. g.add_production('expr',['expr','PLUS','term'],func,file,line)
  92. g.add_production('expr',['expr','"+"','term'],func,file,line)
  93. g.add_production('expr',['MINUS','expr','%prec','UMINUS'],func,file,line)
  94. </pre>
  95. <p>
  96. If any kind of error is detected, a <tt>GrammarError</tt> exception
  97. is raised with a message indicating the reason for the failure.
  98. </blockquote>
  99. <p>
  100. <b><tt>g.set_start(start=None)</tt></b>
  101. <blockquote>
  102. Sets the starting rule for the grammar. <tt>start</tt> is a string
  103. specifying the name of the start rule. If <tt>start</tt> is omitted,
  104. the first grammar rule added with <tt>add_production()</tt> is taken to be
  105. the starting rule. This method must always be called after all
  106. productions have been added.
  107. </blockquote>
  108. <p>
  109. <b><tt>g.find_unreachable()</tt></b>
  110. <blockquote>
  111. Diagnostic function. Returns a list of all unreachable non-terminals
  112. defined in the grammar. This is used to identify inactive parts of
  113. the grammar specification.
  114. </blockquote>
  115. <p>
  116. <b><tt>g.infinite_cycle()</tt></b>
  117. <blockquote>
  118. Diagnostic function. Returns a list of all non-terminals in the
  119. grammar that result in an infinite cycle. This condition occurs if
  120. there is no way for a grammar rule to expand to a string containing
  121. only terminal symbols.
  122. </blockquote>
  123. <p>
  124. <b><tt>g.undefined_symbols()</tt></b>
  125. <blockquote>
  126. Diagnostic function. Returns a list of tuples <tt>(name, prod)</tt>
  127. corresponding to undefined symbols in the grammar. <tt>name</tt> is the
  128. name of the undefined symbol and <tt>prod</tt> is an instance of
  129. <tt>Production</tt> which has information about the production rule
  130. where the undefined symbol was used.
  131. </blockquote>
  132. <p>
  133. <b><tt>g.unused_terminals()</tt></b>
  134. <blockquote>
  135. Diagnostic function. Returns a list of terminals that were defined,
  136. but never used in the grammar.
  137. </blockquote>
  138. <p>
  139. <b><tt>g.unused_rules()</tt></b>
  140. <blockquote>
  141. Diagnostic function. Returns a list of <tt>Production</tt> instances
  142. corresponding to production rules that were defined in the grammar,
  143. but never used anywhere. This is slightly different
  144. than <tt>find_unreachable()</tt>.
  145. </blockquote>
  146. <p>
  147. <b><tt>g.unused_precedence()</tt></b>
  148. <blockquote>
  149. Diagnostic function. Returns a list of tuples <tt>(term, assoc)</tt>
  150. corresponding to precedence rules that were set, but never used the
  151. grammar. <tt>term</tt> is the terminal name and <tt>assoc</tt> is the
  152. precedence associativity (e.g., <tt>'left'</tt>, <tt>'right'</tt>,
  153. or <tt>'nonassoc'</tt>.
  154. </blockquote>
  155. <p>
  156. <b><tt>g.compute_first()</tt></b>
  157. <blockquote>
  158. Compute all of the first sets for all symbols in the grammar. Returns a dictionary
  159. mapping symbol names to a list of all first symbols.
  160. </blockquote>
  161. <p>
  162. <b><tt>g.compute_follow()</tt></b>
  163. <blockquote>
  164. Compute all of the follow sets for all non-terminals in the grammar.
  165. The follow set is the set of all possible symbols that might follow a
  166. given non-terminal. Returns a dictionary mapping non-terminal names
  167. to a list of symbols.
  168. </blockquote>
  169. <p>
  170. <b><tt>g.build_lritems()</tt></b>
  171. <blockquote>
  172. Calculates all of the LR items for all productions in the grammar. This
  173. step is required before using the grammar for any kind of table generation.
  174. See the section on LR items below.
  175. </blockquote>
  176. <p>
  177. The following attributes are set by the above methods and may be useful
  178. in code that works with the grammar. All of these attributes should be
  179. assumed to be read-only. Changing their values directly will likely
  180. break the grammar.
  181. <p>
  182. <b><tt>g.Productions</tt></b>
  183. <blockquote>
  184. A list of all productions added. The first entry is reserved for
  185. a production representing the starting rule. The objects in this list
  186. are instances of the <tt>Production</tt> class, described shortly.
  187. </blockquote>
  188. <p>
  189. <b><tt>g.Prodnames</tt></b>
  190. <blockquote>
  191. A dictionary mapping the names of nonterminals to a list of all
  192. productions of that nonterminal.
  193. </blockquote>
  194. <p>
  195. <b><tt>g.Terminals</tt></b>
  196. <blockquote>
  197. A dictionary mapping the names of terminals to a list of the
  198. production numbers where they are used.
  199. </blockquote>
  200. <p>
  201. <b><tt>g.Nonterminals</tt></b>
  202. <blockquote>
  203. A dictionary mapping the names of nonterminals to a list of the
  204. production numbers where they are used.
  205. </blockquote>
  206. <p>
  207. <b><tt>g.First</tt></b>
  208. <blockquote>
  209. A dictionary representing the first sets for all grammar symbols. This is
  210. computed and returned by the <tt>compute_first()</tt> method.
  211. </blockquote>
  212. <p>
  213. <b><tt>g.Follow</tt></b>
  214. <blockquote>
  215. A dictionary representing the follow sets for all grammar rules. This is
  216. computed and returned by the <tt>compute_follow()</tt> method.
  217. </blockquote>
  218. <p>
  219. <b><tt>g.Start</tt></b>
  220. <blockquote>
  221. Starting symbol for the grammar. Set by the <tt>set_start()</tt> method.
  222. </blockquote>
  223. For the purposes of debugging, a <tt>Grammar</tt> object supports the <tt>__len__()</tt> and
  224. <tt>__getitem__()</tt> special methods. Accessing <tt>g[n]</tt> returns the nth production
  225. from the grammar.
  226. <H2><a name="internal_nn3"></a>3. Productions</H2>
  227. <tt>Grammar</tt> objects store grammar rules as instances of a <tt>Production</tt> class. This
  228. class has no public constructor--you should only create productions by calling <tt>Grammar.add_production()</tt>.
  229. The following attributes are available on a <tt>Production</tt> instance <tt>p</tt>.
  230. <p>
  231. <b><tt>p.name</tt></b>
  232. <blockquote>
  233. The name of the production. For a grammar rule such as <tt>A : B C D</tt>, this is <tt>'A'</tt>.
  234. </blockquote>
  235. <p>
  236. <b><tt>p.prod</tt></b>
  237. <blockquote>
  238. A tuple of symbols making up the right-hand side of the production. For a grammar rule such as <tt>A : B C D</tt>, this is <tt>('B','C','D')</tt>.
  239. </blockquote>
  240. <p>
  241. <b><tt>p.number</tt></b>
  242. <blockquote>
  243. Production number. An integer containing the index of the production in the grammar's <tt>Productions</tt> list.
  244. </blockquote>
  245. <p>
  246. <b><tt>p.func</tt></b>
  247. <blockquote>
  248. The name of the reduction function associated with the production.
  249. This is the function that will execute when reducing the entire
  250. grammar rule during parsing.
  251. </blockquote>
  252. <p>
  253. <b><tt>p.callable</tt></b>
  254. <blockquote>
  255. The callable object associated with the name in <tt>p.func</tt>. This is <tt>None</tt>
  256. unless the production has been bound using <tt>bind()</tt>.
  257. </blockquote>
  258. <p>
  259. <b><tt>p.file</tt></b>
  260. <blockquote>
  261. Filename associated with the production. Typically this is the file where the production was defined. Used for error messages.
  262. </blockquote>
  263. <p>
  264. <b><tt>p.lineno</tt></b>
  265. <blockquote>
  266. Line number associated with the production. Typically this is the line number in <tt>p.file</tt> where the production was defined. Used for error messages.
  267. </blockquote>
  268. <p>
  269. <b><tt>p.prec</tt></b>
  270. <blockquote>
  271. Precedence and associativity associated with the production. This is a tuple <tt>(assoc,level)</tt> where
  272. <tt>assoc</tt> is one of <tt>'left'</tt>,<tt>'right'</tt>, or <tt>'nonassoc'</tt> and <tt>level</tt> is
  273. an integer. This value is determined by the precedence of the right-most terminal symbol in the production
  274. or by use of the <tt>%prec</tt> specifier when adding the production.
  275. </blockquote>
  276. <p>
  277. <b><tt>p.usyms</tt></b>
  278. <blockquote>
  279. A list of all unique symbols found in the production.
  280. </blockquote>
  281. <p>
  282. <b><tt>p.lr_items</tt></b>
  283. <blockquote>
  284. A list of all LR items for this production. This attribute only has a meaningful value if the
  285. <tt>Grammar.build_lritems()</tt> method has been called. The items in this list are
  286. instances of <tt>LRItem</tt> described below.
  287. </blockquote>
  288. <p>
  289. <b><tt>p.lr_next</tt></b>
  290. <blockquote>
  291. The head of a linked-list representation of the LR items in <tt>p.lr_items</tt>.
  292. This attribute only has a meaningful value if the <tt>Grammar.build_lritems()</tt>
  293. method has been called. Each <tt>LRItem</tt> instance has a <tt>lr_next</tt> attribute
  294. to move to the next item. The list is terminated by <tt>None</tt>.
  295. </blockquote>
  296. <p>
  297. <b><tt>p.bind(dict)</tt></b>
  298. <blockquote>
  299. Binds the production function name in <tt>p.func</tt> to a callable object in
  300. <tt>dict</tt>. This operation is typically carried out in the last step
  301. prior to running the parsing engine and is needed since parsing tables are typically
  302. read from files which only include the function names, not the functions themselves.
  303. </blockquote>
  304. <P>
  305. <tt>Production</tt> objects support
  306. the <tt>__len__()</tt>, <tt>__getitem__()</tt>, and <tt>__str__()</tt>
  307. special methods.
  308. <tt>len(p)</tt> returns the number of symbols in <tt>p.prod</tt>
  309. and <tt>p[n]</tt> is the same as <tt>p.prod[n]</tt>.
  310. <H2><a name="internal_nn4"></a>4. LRItems</H2>
  311. The construction of parsing tables in an LR-based parser generator is primarily
  312. done over a set of "LR Items". An LR item represents a stage of parsing one
  313. of the grammar rules. To compute the LR items, it is first necessary to
  314. call <tt>Grammar.build_lritems()</tt>. Once this step, all of the productions
  315. in the grammar will have their LR items attached to them.
  316. <p>
  317. Here is an interactive example that shows what LR items look like if you
  318. interactively experiment. In this example, <tt>g</tt> is a <tt>Grammar</tt>
  319. object.
  320. <blockquote>
  321. <pre>
  322. >>> <b>g.build_lritems()</b>
  323. >>> <b>p = g[1]</b>
  324. >>> <b>p</b>
  325. Production(statement -> ID = expr)
  326. >>>
  327. </pre>
  328. </blockquote>
  329. In the above code, <tt>p</tt> represents the first grammar rule. In
  330. this case, a rule <tt>'statement -> ID = expr'</tt>.
  331. <p>
  332. Now, let's look at the LR items for <tt>p</tt>.
  333. <blockquote>
  334. <pre>
  335. >>> <b>p.lr_items</b>
  336. [LRItem(statement -> . ID = expr),
  337. LRItem(statement -> ID . = expr),
  338. LRItem(statement -> ID = . expr),
  339. LRItem(statement -> ID = expr .)]
  340. >>>
  341. </pre>
  342. </blockquote>
  343. In each LR item, the dot (.) represents a specific stage of parsing. In each LR item, the dot
  344. is advanced by one symbol. It is only when the dot reaches the very end that a production
  345. is successfully parsed.
  346. <p>
  347. An instance <tt>lr</tt> of <tt>LRItem</tt> has the following
  348. attributes that hold information related to that specific stage of
  349. parsing.
  350. <p>
  351. <b><tt>lr.name</tt></b>
  352. <blockquote>
  353. The name of the grammar rule. For example, <tt>'statement'</tt> in the above example.
  354. </blockquote>
  355. <p>
  356. <b><tt>lr.prod</tt></b>
  357. <blockquote>
  358. A tuple of symbols representing the right-hand side of the production, including the
  359. special <tt>'.'</tt> character. For example, <tt>('ID','.','=','expr')</tt>.
  360. </blockquote>
  361. <p>
  362. <b><tt>lr.number</tt></b>
  363. <blockquote>
  364. An integer representing the production number in the grammar.
  365. </blockquote>
  366. <p>
  367. <b><tt>lr.usyms</tt></b>
  368. <blockquote>
  369. A set of unique symbols in the production. Inherited from the original <tt>Production</tt> instance.
  370. </blockquote>
  371. <p>
  372. <b><tt>lr.lr_index</tt></b>
  373. <blockquote>
  374. An integer representing the position of the dot (.). You should never use <tt>lr.prod.index()</tt>
  375. to search for it--the result will be wrong if the grammar happens to also use (.) as a character
  376. literal.
  377. </blockquote>
  378. <p>
  379. <b><tt>lr.lr_after</tt></b>
  380. <blockquote>
  381. A list of all productions that can legally appear immediately to the right of the
  382. dot (.). This list contains <tt>Production</tt> instances. This attribute
  383. represents all of the possible branches a parse can take from the current position.
  384. For example, suppose that <tt>lr</tt> represents a stage immediately before
  385. an expression like this:
  386. <pre>
  387. >>> <b>lr</b>
  388. LRItem(statement -> ID = . expr)
  389. >>>
  390. </pre>
  391. Then, the value of <tt>lr.lr_after</tt> might look like this, showing all productions that
  392. can legally appear next:
  393. <pre>
  394. >>> <b>lr.lr_after</b>
  395. [Production(expr -> expr PLUS expr),
  396. Production(expr -> expr MINUS expr),
  397. Production(expr -> expr TIMES expr),
  398. Production(expr -> expr DIVIDE expr),
  399. Production(expr -> MINUS expr),
  400. Production(expr -> LPAREN expr RPAREN),
  401. Production(expr -> NUMBER),
  402. Production(expr -> ID)]
  403. >>>
  404. </pre>
  405. </blockquote>
  406. <p>
  407. <b><tt>lr.lr_before</tt></b>
  408. <blockquote>
  409. The grammar symbol that appears immediately before the dot (.) or <tt>None</tt> if
  410. at the beginning of the parse.
  411. </blockquote>
  412. <p>
  413. <b><tt>lr.lr_next</tt></b>
  414. <blockquote>
  415. A link to the next LR item, representing the next stage of the parse. <tt>None</tt> if <tt>lr</tt>
  416. is the last LR item.
  417. </blockquote>
  418. <tt>LRItem</tt> instances also support the <tt>__len__()</tt> and <tt>__getitem__()</tt> special methods.
  419. <tt>len(lr)</tt> returns the number of items in <tt>lr.prod</tt> including the dot (.). <tt>lr[n]</tt>
  420. returns <tt>lr.prod[n]</tt>.
  421. <p>
  422. It goes without saying that all of the attributes associated with LR
  423. items should be assumed to be read-only. Modifications will very
  424. likely create a small black-hole that will consume you and your code.
  425. <H2><a name="internal_nn5"></a>5. LRTable</H2>
  426. The <tt>LRTable</tt> class is used to represent LR parsing table data. This
  427. minimally includes the production list, action table, and goto table.
  428. <p>
  429. <b><tt>LRTable()</tt></b>
  430. <blockquote>
  431. Create an empty LRTable object. This object contains only the information needed to
  432. run an LR parser.
  433. </blockquote>
  434. An instance <tt>lrtab</tt> of <tt>LRTable</tt> has the following methods:
  435. <p>
  436. <b><tt>lrtab.read_table(module)</tt></b>
  437. <blockquote>
  438. Populates the LR table with information from the module specified in <tt>module</tt>.
  439. <tt>module</tt> is either a module object already loaded with <tt>import</tt> or
  440. the name of a Python module. If it's a string containing a module name, it is
  441. loaded and parsing data is extracted. Returns the signature value that was used
  442. when initially writing the tables. Raises a <tt>VersionError</tt> exception if
  443. the module was created using an incompatible version of PLY.
  444. </blockquote>
  445. <p>
  446. <b><tt>lrtab.bind_callables(dict)</tt></b>
  447. <blockquote>
  448. This binds all of the function names used in productions to callable objects
  449. found in the dictionary <tt>dict</tt>. During table generation and when reading
  450. LR tables from files, PLY only uses the names of action functions such as <tt>'p_expr'</tt>,
  451. <tt>'p_statement'</tt>, etc. In order to actually run the parser, these names
  452. have to be bound to callable objects. This method is always called prior to
  453. running a parser.
  454. </blockquote>
  455. After <tt>lrtab</tt> has been populated, the following attributes are defined.
  456. <p>
  457. <b><tt>lrtab.lr_method</tt></b>
  458. <blockquote>
  459. The LR parsing method used (e.g., <tt>'LALR'</tt>)
  460. </blockquote>
  461. <p>
  462. <b><tt>lrtab.lr_productions</tt></b>
  463. <blockquote>
  464. The production list. If the parsing tables have been newly
  465. constructed, this will be a list of <tt>Production</tt> instances. If
  466. the parsing tables have been read from a file, it's a list
  467. of <tt>MiniProduction</tt> instances. This, together
  468. with <tt>lr_action</tt> and <tt>lr_goto</tt> contain all of the
  469. information needed by the LR parsing engine.
  470. </blockquote>
  471. <p>
  472. <b><tt>lrtab.lr_action</tt></b>
  473. <blockquote>
  474. The LR action dictionary that implements the underlying state machine.
  475. The keys of this dictionary are the LR states.
  476. </blockquote>
  477. <p>
  478. <b><tt>lrtab.lr_goto</tt></b>
  479. <blockquote>
  480. The LR goto table that contains information about grammar rule reductions.
  481. </blockquote>
  482. <H2><a name="internal_nn6"></a>6. LRGeneratedTable</H2>
  483. The <tt>LRGeneratedTable</tt> class represents constructed LR parsing tables on a
  484. grammar. It is a subclass of <tt>LRTable</tt>.
  485. <p>
  486. <b><tt>LRGeneratedTable(grammar, method='LALR',log=None)</tt></b>
  487. <blockquote>
  488. Create the LR parsing tables on a grammar. <tt>grammar</tt> is an instance of <tt>Grammar</tt>,
  489. <tt>method</tt> is a string with the parsing method (<tt>'SLR'</tt> or <tt>'LALR'</tt>), and
  490. <tt>log</tt> is a logger object used to write debugging information. The debugging information
  491. written to <tt>log</tt> is the same as what appears in the <tt>parser.out</tt> file created
  492. by yacc. By supplying a custom logger with a different message format, it is possible to get
  493. more information (e.g., the line number in <tt>yacc.py</tt> used for issuing each line of
  494. output in the log). The result is an instance of <tt>LRGeneratedTable</tt>.
  495. </blockquote>
  496. <p>
  497. An instance <tt>lr</tt> of <tt>LRGeneratedTable</tt> has the following attributes.
  498. <p>
  499. <b><tt>lr.grammar</tt></b>
  500. <blockquote>
  501. A link to the Grammar object used to construct the parsing tables.
  502. </blockquote>
  503. <p>
  504. <b><tt>lr.lr_method</tt></b>
  505. <blockquote>
  506. The LR parsing method used (e.g., <tt>'LALR'</tt>)
  507. </blockquote>
  508. <p>
  509. <b><tt>lr.lr_productions</tt></b>
  510. <blockquote>
  511. A reference to <tt>grammar.Productions</tt>. This, together with <tt>lr_action</tt> and <tt>lr_goto</tt>
  512. contain all of the information needed by the LR parsing engine.
  513. </blockquote>
  514. <p>
  515. <b><tt>lr.lr_action</tt></b>
  516. <blockquote>
  517. The LR action dictionary that implements the underlying state machine. The keys of this dictionary are
  518. the LR states.
  519. </blockquote>
  520. <p>
  521. <b><tt>lr.lr_goto</tt></b>
  522. <blockquote>
  523. The LR goto table that contains information about grammar rule reductions.
  524. </blockquote>
  525. <p>
  526. <b><tt>lr.sr_conflicts</tt></b>
  527. <blockquote>
  528. A list of tuples <tt>(state,token,resolution)</tt> identifying all shift/reduce conflicts. <tt>state</tt> is the LR state
  529. number where the conflict occurred, <tt>token</tt> is the token causing the conflict, and <tt>resolution</tt> is
  530. a string describing the resolution taken. <tt>resolution</tt> is either <tt>'shift'</tt> or <tt>'reduce'</tt>.
  531. </blockquote>
  532. <p>
  533. <b><tt>lr.rr_conflicts</tt></b>
  534. <blockquote>
  535. A list of tuples <tt>(state,rule,rejected)</tt> identifying all reduce/reduce conflicts. <tt>state</tt> is the
  536. LR state number where the conflict occurred, <tt>rule</tt> is the production rule that was selected
  537. and <tt>rejected</tt> is the production rule that was rejected. Both <tt>rule</tt> and </tt>rejected</tt> are
  538. instances of <tt>Production</tt>. They can be inspected to provide the user with more information.
  539. </blockquote>
  540. <p>
  541. There are two public methods of <tt>LRGeneratedTable</tt>.
  542. <p>
  543. <b><tt>lr.write_table(modulename,outputdir="",signature="")</tt></b>
  544. <blockquote>
  545. Writes the LR parsing table information to a Python module. <tt>modulename</tt> is a string
  546. specifying the name of a module such as <tt>"parsetab"</tt>. <tt>outputdir</tt> is the name of a
  547. directory where the module should be created. <tt>signature</tt> is a string representing a
  548. grammar signature that's written into the output file. This can be used to detect when
  549. the data stored in a module file is out-of-sync with the the grammar specification (and that
  550. the tables need to be regenerated). If <tt>modulename</tt> is a string <tt>"parsetab"</tt>,
  551. this function creates a file called <tt>parsetab.py</tt>. If the module name represents a
  552. package such as <tt>"foo.bar.parsetab"</tt>, then only the last component, <tt>"parsetab"</tt> is
  553. used.
  554. </blockquote>
  555. <H2><a name="internal_nn7"></a>7. LRParser</H2>
  556. The <tt>LRParser</tt> class implements the low-level LR parsing engine.
  557. <p>
  558. <b><tt>LRParser(lrtab, error_func)</tt></b>
  559. <blockquote>
  560. Create an LRParser. <tt>lrtab</tt> is an instance of <tt>LRTable</tt>
  561. containing the LR production and state tables. <tt>error_func</tt> is the
  562. error function to invoke in the event of a parsing error.
  563. </blockquote>
  564. An instance <tt>p</tt> of <tt>LRParser</tt> has the following methods:
  565. <p>
  566. <b><tt>p.parse(input=None,lexer=None,debug=0,tracking=0,tokenfunc=None)</tt></b>
  567. <blockquote>
  568. Run the parser. <tt>input</tt> is a string, which if supplied is fed into the
  569. lexer using its <tt>input()</tt> method. <tt>lexer</tt> is an instance of the
  570. <tt>Lexer</tt> class to use for tokenizing. If not supplied, the last lexer
  571. created with the <tt>lex</tt> module is used. <tt>debug</tt> is a boolean flag
  572. that enables debugging. <tt>tracking</tt> is a boolean flag that tells the
  573. parser to perform additional line number tracking. <tt>tokenfunc</tt> is a callable
  574. function that returns the next token. If supplied, the parser will use it to get
  575. all tokens.
  576. </blockquote>
  577. <p>
  578. <b><tt>p.restart()</tt></b>
  579. <blockquote>
  580. Resets the parser state for a parse already in progress.
  581. </blockquote>
  582. <H2><a name="internal_nn8"></a>8. ParserReflect</H2>
  583. <p>
  584. The <tt>ParserReflect</tt> class is used to collect parser specification data
  585. from a Python module or object. This class is what collects all of the
  586. <tt>p_rule()</tt> functions in a PLY file, performs basic error checking,
  587. and collects all of the needed information to build a grammar. Most of the
  588. high-level PLY interface as used by the <tt>yacc()</tt> function is actually
  589. implemented by this class.
  590. <p>
  591. <b><tt>ParserReflect(pdict, log=None)</tt></b>
  592. <blockquote>
  593. Creates a <tt>ParserReflect</tt> instance. <tt>pdict</tt> is a dictionary
  594. containing parser specification data. This dictionary typically corresponds
  595. to the module or class dictionary of code that implements a PLY parser.
  596. <tt>log</tt> is a logger instance that will be used to report error
  597. messages.
  598. </blockquote>
  599. An instance <tt>p</tt> of <tt>ParserReflect</tt> has the following methods:
  600. <p>
  601. <b><tt>p.get_all()</tt></b>
  602. <blockquote>
  603. Collect and store all required parsing information.
  604. </blockquote>
  605. <p>
  606. <b><tt>p.validate_all()</tt></b>
  607. <blockquote>
  608. Validate all of the collected parsing information. This is a seprate step
  609. from <tt>p.get_all()</tt> as a performance optimization. In order to
  610. increase parser start-up time, a parser can elect to only validate the
  611. parsing data when regenerating the parsing tables. The validation
  612. step tries to collect as much information as possible rather than
  613. raising an exception at the first sign of trouble. The attribute
  614. <tt>p.error</tt> is set if there are any validation errors. The
  615. value of this attribute is also returned.
  616. </blockquote>
  617. <p>
  618. <b><tt>p.signature()</tt></b>
  619. <blockquote>
  620. Compute a signature representing the contents of the collected parsing
  621. data. The signature value should change if anything in the parser
  622. specification has changed in a way that would justify parser table
  623. regeneration. This method can be called after <tt>p.get_all()</tt>,
  624. but before <tt>p.validate_all()</tt>.
  625. </blockquote>
  626. The following attributes are set in the process of collecting data:
  627. <p>
  628. <b><tt>p.start</tt></b>
  629. <blockquote>
  630. The grammar start symbol, if any. Taken from <tt>pdict['start']</tt>.
  631. </blockquote>
  632. <p>
  633. <b><tt>p.error_func</tt></b>
  634. <blockquote>
  635. The error handling function or <tt>None</tt>. Taken from <tt>pdict['p_error']</tt>.
  636. </blockquote>
  637. <p>
  638. <b><tt>p.tokens</tt></b>
  639. <blockquote>
  640. The token list. Taken from <tt>pdict['tokens']</tt>.
  641. </blockquote>
  642. <p>
  643. <b><tt>p.prec</tt></b>
  644. <blockquote>
  645. The precedence specifier. Taken from <tt>pdict['precedence']</tt>.
  646. </blockquote>
  647. <p>
  648. <b><tt>p.preclist</tt></b>
  649. <blockquote>
  650. A parsed version of the precedence specified. A list of tuples of the form
  651. <tt>(token,assoc,level)</tt> where <tt>token</tt> is the terminal symbol,
  652. <tt>assoc</tt> is the associativity (e.g., <tt>'left'</tt>) and <tt>level</tt>
  653. is a numeric precedence level.
  654. </blockquote>
  655. <p>
  656. <b><tt>p.grammar</tt></b>
  657. <blockquote>
  658. A list of tuples <tt>(name, rules)</tt> representing the grammar rules. <tt>name</tt> is the
  659. name of a Python function or method in <tt>pdict</tt> that starts with <tt>"p_"</tt>.
  660. <tt>rules</tt> is a list of tuples <tt>(filename,line,prodname,syms)</tt> representing
  661. the grammar rules found in the documentation string of that function. <tt>filename</tt> and <tt>line</tt> contain location
  662. information that can be used for debugging. <tt>prodname</tt> is the name of the
  663. production. <tt>syms</tt> is the right-hand side of the production. If you have a
  664. function like this
  665. <pre>
  666. def p_expr(p):
  667. '''expr : expr PLUS expr
  668. | expr MINUS expr
  669. | expr TIMES expr
  670. | expr DIVIDE expr'''
  671. </pre>
  672. then the corresponding entry in <tt>p.grammar</tt> might look like this:
  673. <pre>
  674. ('p_expr', [ ('calc.py',10,'expr', ['expr','PLUS','expr']),
  675. ('calc.py',11,'expr', ['expr','MINUS','expr']),
  676. ('calc.py',12,'expr', ['expr','TIMES','expr']),
  677. ('calc.py',13,'expr', ['expr','DIVIDE','expr'])
  678. ])
  679. </pre>
  680. </blockquote>
  681. <p>
  682. <b><tt>p.pfuncs</tt></b>
  683. <blockquote>
  684. A sorted list of tuples <tt>(line, file, name, doc)</tt> representing all of
  685. the <tt>p_</tt> functions found. <tt>line</tt> and <tt>file</tt> give location
  686. information. <tt>name</tt> is the name of the function. <tt>doc</tt> is the
  687. documentation string. This list is sorted in ascending order by line number.
  688. </blockquote>
  689. <p>
  690. <b><tt>p.files</tt></b>
  691. <blockquote>
  692. A dictionary holding all of the source filenames that were encountered
  693. while collecting parser information. Only the keys of this dictionary have
  694. any meaning.
  695. </blockquote>
  696. <p>
  697. <b><tt>p.error</tt></b>
  698. <blockquote>
  699. An attribute that indicates whether or not any critical errors
  700. occurred in validation. If this is set, it means that that some kind
  701. of problem was detected and that no further processing should be
  702. performed.
  703. </blockquote>
  704. <H2><a name="internal_nn9"></a>9. High-level operation</H2>
  705. Using all of the above classes requires some attention to detail. The <tt>yacc()</tt>
  706. function carries out a very specific sequence of operations to create a grammar.
  707. This same sequence should be emulated if you build an alternative PLY interface.
  708. <ol>
  709. <li>A <tt>ParserReflect</tt> object is created and raw grammar specification data is
  710. collected.
  711. <li>A <tt>Grammar</tt> object is created and populated with information
  712. from the specification data.
  713. <li>A <tt>LRGenerator</tt> object is created to run the LALR algorithm over
  714. the <tt>Grammar</tt> object.
  715. <li>Productions in the LRGenerator and bound to callables using the <tt>bind_callables()</tt>
  716. method.
  717. <li>A <tt>LRParser</tt> object is created from from the information in the
  718. <tt>LRGenerator</tt> object.
  719. </ol>
  720. </body>
  721. </html>