ply.html revision 6498
1<html> 2<head> 3<title>PLY (Python Lex-Yacc)</title> 4</head> 5<body bgcolor="#ffffff"> 6 7<h1>PLY (Python Lex-Yacc)</h1> 8 9<b> 10David M. Beazley <br> 11dave@dabeaz.com<br> 12</b> 13 14<p> 15<b>PLY Version: 3.0</b> 16<p> 17 18<!-- INDEX --> 19<div class="sectiontoc"> 20<ul> 21<li><a href="#ply_nn1">Preface and Requirements</a> 22<li><a href="#ply_nn1">Introduction</a> 23<li><a href="#ply_nn2">PLY Overview</a> 24<li><a href="#ply_nn3">Lex</a> 25<ul> 26<li><a href="#ply_nn4">Lex Example</a> 27<li><a href="#ply_nn5">The tokens list</a> 28<li><a href="#ply_nn6">Specification of tokens</a> 29<li><a href="#ply_nn7">Token values</a> 30<li><a href="#ply_nn8">Discarded tokens</a> 31<li><a href="#ply_nn9">Line numbers and positional information</a> 32<li><a href="#ply_nn10">Ignored characters</a> 33<li><a href="#ply_nn11">Literal characters</a> 34<li><a href="#ply_nn12">Error handling</a> 35<li><a href="#ply_nn13">Building and using the lexer</a> 36<li><a href="#ply_nn14">The @TOKEN decorator</a> 37<li><a href="#ply_nn15">Optimized mode</a> 38<li><a href="#ply_nn16">Debugging</a> 39<li><a href="#ply_nn17">Alternative specification of lexers</a> 40<li><a href="#ply_nn18">Maintaining state</a> 41<li><a href="#ply_nn19">Lexer cloning</a> 42<li><a href="#ply_nn20">Internal lexer state</a> 43<li><a href="#ply_nn21">Conditional lexing and start conditions</a> 44<li><a href="#ply_nn21">Miscellaneous Issues</a> 45</ul> 46<li><a href="#ply_nn22">Parsing basics</a> 47<li><a href="#ply_nn23">Yacc</a> 48<ul> 49<li><a href="#ply_nn24">An example</a> 50<li><a href="#ply_nn25">Combining Grammar Rule Functions</a> 51<li><a href="#ply_nn26">Character Literals</a> 52<li><a href="#ply_nn26">Empty Productions</a> 53<li><a href="#ply_nn28">Changing the starting symbol</a> 54<li><a href="#ply_nn27">Dealing With Ambiguous Grammars</a> 55<li><a href="#ply_nn28">The parser.out file</a> 56<li><a href="#ply_nn29">Syntax Error Handling</a> 57<ul> 58<li><a href="#ply_nn30">Recovery and resynchronization with error rules</a> 59<li><a href="#ply_nn31">Panic mode recovery</a> 60<li><a href="#ply_nn35">Signaling an error from a production</a> 61<li><a href="#ply_nn32">General comments on error handling</a> 62</ul> 63<li><a href="#ply_nn33">Line Number and Position Tracking</a> 64<li><a href="#ply_nn34">AST Construction</a> 65<li><a href="#ply_nn35">Embedded Actions</a> 66<li><a href="#ply_nn36">Miscellaneous Yacc Notes</a> 67</ul> 68<li><a href="#ply_nn37">Multiple Parsers and Lexers</a> 69<li><a href="#ply_nn38">Using Python's Optimized Mode</a> 70<li><a href="#ply_nn44">Advanced Debugging</a> 71<ul> 72<li><a href="#ply_nn45">Debugging the lex() and yacc() commands</a> 73<li><a href="#ply_nn46">Run-time Debugging</a> 74</ul> 75<li><a href="#ply_nn39">Where to go from here?</a> 76</ul> 77</div> 78<!-- INDEX --> 79 80 81 82<H2><a name="ply_nn1"></a>1. Preface and Requirements</H2> 83 84 85<p> 86This document provides an overview of lexing and parsing with PLY. 87Given the intrinsic complexity of parsing, I would strongly advise 88that you read (or at least skim) this entire document before jumping 89into a big development project with PLY. 90</p> 91 92<p> 93PLY-3.0 is compatible with both Python 2 and Python 3. Be aware that 94Python 3 support is new and has not been extensively tested (although 95all of the examples and unit tests pass under Python 3.0). If you are 96using Python 2, you should try to use Python 2.4 or newer. Although PLY 97works with versions as far back as Python 2.2, some of its optional features 98require more modern library modules. 99</p> 100 101<H2><a name="ply_nn1"></a>2. Introduction</H2> 102 103 104PLY is a pure-Python implementation of the popular compiler 105construction tools lex and yacc. The main goal of PLY is to stay 106fairly faithful to the way in which traditional lex/yacc tools work. 107This includes supporting LALR(1) parsing as well as providing 108extensive input validation, error reporting, and diagnostics. Thus, 109if you've used yacc in another programming language, it should be 110relatively straightforward to use PLY. 111 112<p> 113Early versions of PLY were developed to support an Introduction to 114Compilers Course I taught in 2001 at the University of Chicago. In this course, 115students built a fully functional compiler for a simple Pascal-like 116language. Their compiler, implemented entirely in Python, had to 117include lexical analysis, parsing, type checking, type inference, 118nested scoping, and code generation for the SPARC processor. 119Approximately 30 different compiler implementations were completed in 120this course. Most of PLY's interface and operation has been influenced by common 121usability problems encountered by students. Since 2001, PLY has 122continued to be improved as feedback has been received from users. 123PLY-3.0 represents a major refactoring of the original implementation 124with an eye towards future enhancements. 125 126<p> 127Since PLY was primarily developed as an instructional tool, you will 128find it to be fairly picky about token and grammar rule 129specification. In part, this 130added formality is meant to catch common programming mistakes made by 131novice users. However, advanced users will also find such features to 132be useful when building complicated grammars for real programming 133languages. It should also be noted that PLY does not provide much in 134the way of bells and whistles (e.g., automatic construction of 135abstract syntax trees, tree traversal, etc.). Nor would I consider it 136to be a parsing framework. Instead, you will find a bare-bones, yet 137fully capable lex/yacc implementation written entirely in Python. 138 139<p> 140The rest of this document assumes that you are somewhat familar with 141parsing theory, syntax directed translation, and the use of compiler 142construction tools such as lex and yacc in other programming 143languages. If you are unfamilar with these topics, you will probably 144want to consult an introductory text such as "Compilers: Principles, 145Techniques, and Tools", by Aho, Sethi, and Ullman. O'Reilly's "Lex 146and Yacc" by John Levine may also be handy. In fact, the O'Reilly book can be 147used as a reference for PLY as the concepts are virtually identical. 148 149<H2><a name="ply_nn2"></a>3. PLY Overview</H2> 150 151 152PLY consists of two separate modules; <tt>lex.py</tt> and 153<tt>yacc.py</tt>, both of which are found in a Python package 154called <tt>ply</tt>. The <tt>lex.py</tt> module is used to break input text into a 155collection of tokens specified by a collection of regular expression 156rules. <tt>yacc.py</tt> is used to recognize language syntax that has 157been specified in the form of a context free grammar. <tt>yacc.py</tt> uses LR parsing and generates its parsing tables 158using either the LALR(1) (the default) or SLR table generation algorithms. 159 160<p> 161The two tools are meant to work together. Specifically, 162<tt>lex.py</tt> provides an external interface in the form of a 163<tt>token()</tt> function that returns the next valid token on the 164input stream. <tt>yacc.py</tt> calls this repeatedly to retrieve 165tokens and invoke grammar rules. The output of <tt>yacc.py</tt> is 166often an Abstract Syntax Tree (AST). However, this is entirely up to 167the user. If desired, <tt>yacc.py</tt> can also be used to implement 168simple one-pass compilers. 169 170<p> 171Like its Unix counterpart, <tt>yacc.py</tt> provides most of the 172features you expect including extensive error checking, grammar 173validation, support for empty productions, error tokens, and ambiguity 174resolution via precedence rules. In fact, everything that is possible in traditional yacc 175should be supported in PLY. 176 177<p> 178The primary difference between 179<tt>yacc.py</tt> and Unix <tt>yacc</tt> is that <tt>yacc.py</tt> 180doesn't involve a separate code-generation process. 181Instead, PLY relies on reflection (introspection) 182to build its lexers and parsers. Unlike traditional lex/yacc which 183require a special input file that is converted into a separate source 184file, the specifications given to PLY <em>are</em> valid Python 185programs. This means that there are no extra source files nor is 186there a special compiler construction step (e.g., running yacc to 187generate Python code for the compiler). Since the generation of the 188parsing tables is relatively expensive, PLY caches the results and 189saves them to a file. If no changes are detected in the input source, 190the tables are read from the cache. Otherwise, they are regenerated. 191 192<H2><a name="ply_nn3"></a>4. Lex</H2> 193 194 195<tt>lex.py</tt> is used to tokenize an input string. For example, suppose 196you're writing a programming language and a user supplied the following input string: 197 198<blockquote> 199<pre> 200x = 3 + 42 * (s - t) 201</pre> 202</blockquote> 203 204A tokenizer splits the string into individual tokens 205 206<blockquote> 207<pre> 208'x','=', '3', '+', '42', '*', '(', 's', '-', 't', ')' 209</pre> 210</blockquote> 211 212Tokens are usually given names to indicate what they are. For example: 213 214<blockquote> 215<pre> 216'ID','EQUALS','NUMBER','PLUS','NUMBER','TIMES', 217'LPAREN','ID','MINUS','ID','RPAREN' 218</pre> 219</blockquote> 220 221More specifically, the input is broken into pairs of token types and values. For example: 222 223<blockquote> 224<pre> 225('ID','x'), ('EQUALS','='), ('NUMBER','3'), 226('PLUS','+'), ('NUMBER','42), ('TIMES','*'), 227('LPAREN','('), ('ID','s'), ('MINUS','-'), 228('ID','t'), ('RPAREN',')' 229</pre> 230</blockquote> 231 232The identification of tokens is typically done by writing a series of regular expression 233rules. The next section shows how this is done using <tt>lex.py</tt>. 234 235<H3><a name="ply_nn4"></a>4.1 Lex Example</H3> 236 237 238The following example shows how <tt>lex.py</tt> is used to write a simple tokenizer. 239 240<blockquote> 241<pre> 242# ------------------------------------------------------------ 243# calclex.py 244# 245# tokenizer for a simple expression evaluator for 246# numbers and +,-,*,/ 247# ------------------------------------------------------------ 248import ply.lex as lex 249 250# List of token names. This is always required 251tokens = ( 252 'NUMBER', 253 'PLUS', 254 'MINUS', 255 'TIMES', 256 'DIVIDE', 257 'LPAREN', 258 'RPAREN', 259) 260 261# Regular expression rules for simple tokens 262t_PLUS = r'\+' 263t_MINUS = r'-' 264t_TIMES = r'\*' 265t_DIVIDE = r'/' 266t_LPAREN = r'\(' 267t_RPAREN = r'\)' 268 269# A regular expression rule with some action code 270def t_NUMBER(t): 271 r'\d+' 272 t.value = int(t.value) 273 return t 274 275# Define a rule so we can track line numbers 276def t_newline(t): 277 r'\n+' 278 t.lexer.lineno += len(t.value) 279 280# A string containing ignored characters (spaces and tabs) 281t_ignore = ' \t' 282 283# Error handling rule 284def t_error(t): 285 print "Illegal character '%s'" % t.value[0] 286 t.lexer.skip(1) 287 288# Build the lexer 289lexer = lex.lex() 290 291</pre> 292</blockquote> 293To use the lexer, you first need to feed it some input text using 294its <tt>input()</tt> method. After that, repeated calls 295to <tt>token()</tt> produce tokens. The following code shows how this 296works: 297 298<blockquote> 299<pre> 300 301# Test it out 302data = ''' 3033 + 4 * 10 304 + -20 *2 305''' 306 307# Give the lexer some input 308lexer.input(data) 309 310# Tokenize 311while True: 312 tok = lexer.token() 313 if not tok: break # No more input 314 print tok 315</pre> 316</blockquote> 317 318When executed, the example will produce the following output: 319 320<blockquote> 321<pre> 322$ python example.py 323LexToken(NUMBER,3,2,1) 324LexToken(PLUS,'+',2,3) 325LexToken(NUMBER,4,2,5) 326LexToken(TIMES,'*',2,7) 327LexToken(NUMBER,10,2,10) 328LexToken(PLUS,'+',3,14) 329LexToken(MINUS,'-',3,16) 330LexToken(NUMBER,20,3,18) 331LexToken(TIMES,'*',3,20) 332LexToken(NUMBER,2,3,21) 333</pre> 334</blockquote> 335 336Lexers also support the iteration protocol. So, you can write the above loop as follows: 337 338<blockquote> 339<pre> 340for tok in lexer: 341 print tok 342</pre> 343</blockquote> 344 345The tokens returned by <tt>lexer.token()</tt> are instances 346of <tt>LexToken</tt>. This object has 347attributes <tt>tok.type</tt>, <tt>tok.value</tt>, 348<tt>tok.lineno</tt>, and <tt>tok.lexpos</tt>. The following code shows an example of 349accessing these attributes: 350 351<blockquote> 352<pre> 353# Tokenize 354while True: 355 tok = lexer.token() 356 if not tok: break # No more input 357 print tok.type, tok.value, tok.line, tok.lexpos 358</pre> 359</blockquote> 360 361The <tt>tok.type</tt> and <tt>tok.value</tt> attributes contain the 362type and value of the token itself. 363<tt>tok.line</tt> and <tt>tok.lexpos</tt> contain information about 364the location of the token. <tt>tok.lexpos</tt> is the index of the 365token relative to the start of the input text. 366 367<H3><a name="ply_nn5"></a>4.2 The tokens list</H3> 368 369 370All lexers must provide a list <tt>tokens</tt> that defines all of the possible token 371names that can be produced by the lexer. This list is always required 372and is used to perform a variety of validation checks. The tokens list is also used by the 373<tt>yacc.py</tt> module to identify terminals. 374 375<p> 376In the example, the following code specified the token names: 377 378<blockquote> 379<pre> 380tokens = ( 381 'NUMBER', 382 'PLUS', 383 'MINUS', 384 'TIMES', 385 'DIVIDE', 386 'LPAREN', 387 'RPAREN', 388) 389</pre> 390</blockquote> 391 392<H3><a name="ply_nn6"></a>4.3 Specification of tokens</H3> 393 394 395Each token is specified by writing a regular expression rule. Each of these rules are 396are defined by making declarations with a special prefix <tt>t_</tt> to indicate that it 397defines a token. For simple tokens, the regular expression can 398be specified as strings such as this (note: Python raw strings are used since they are the 399most convenient way to write regular expression strings): 400 401<blockquote> 402<pre> 403t_PLUS = r'\+' 404</pre> 405</blockquote> 406 407In this case, the name following the <tt>t_</tt> must exactly match one of the 408names supplied in <tt>tokens</tt>. If some kind of action needs to be performed, 409a token rule can be specified as a function. For example, this rule matches numbers and 410converts the string into a Python integer. 411 412<blockquote> 413<pre> 414def t_NUMBER(t): 415 r'\d+' 416 t.value = int(t.value) 417 return t 418</pre> 419</blockquote> 420 421When a function is used, the regular expression rule is specified in the function documentation string. 422The function always takes a single argument which is an instance of 423<tt>LexToken</tt>. This object has attributes of <tt>t.type</tt> which is the token type (as a string), 424<tt>t.value</tt> which is the lexeme (the actual text matched), <tt>t.lineno</tt> which is the current line number, and <tt>t.lexpos</tt> which 425is the position of the token relative to the beginning of the input text. 426By default, <tt>t.type</tt> is set to the name following the <tt>t_</tt> prefix. The action 427function can modify the contents of the <tt>LexToken</tt> object as appropriate. However, 428when it is done, the resulting token should be returned. If no value is returned by the action 429function, the token is simply discarded and the next token read. 430 431<p> 432Internally, <tt>lex.py</tt> uses the <tt>re</tt> module to do its patten matching. When building the master regular expression, 433rules are added in the following order: 434<p> 435<ol> 436<li>All tokens defined by functions are added in the same order as they appear in the lexer file. 437<li>Tokens defined by strings are added next by sorting them in order of decreasing regular expression length (longer expressions 438are added first). 439</ol> 440<p> 441Without this ordering, it can be difficult to correctly match certain types of tokens. For example, if you 442wanted to have separate tokens for "=" and "==", you need to make sure that "==" is checked first. By sorting regular 443expressions in order of decreasing length, this problem is solved for rules defined as strings. For functions, 444the order can be explicitly controlled since rules appearing first are checked first. 445 446<p> 447To handle reserved words, you should write a single rule to match an 448identifier and do a special name lookup in a function like this: 449 450<blockquote> 451<pre> 452reserved = { 453 'if' : 'IF', 454 'then' : 'THEN', 455 'else' : 'ELSE', 456 'while' : 'WHILE', 457 ... 458} 459 460tokens = ['LPAREN','RPAREN',...,'ID'] + list(reserved.values()) 461 462def t_ID(t): 463 r'[a-zA-Z_][a-zA-Z_0-9]*' 464 t.type = reserved.get(t.value,'ID') # Check for reserved words 465 return t 466</pre> 467</blockquote> 468 469This approach greatly reduces the number of regular expression rules and is likely to make things a little faster. 470 471<p> 472<b>Note:</b> You should avoid writing individual rules for reserved words. For example, if you write rules like this, 473 474<blockquote> 475<pre> 476t_FOR = r'for' 477t_PRINT = r'print' 478</pre> 479</blockquote> 480 481those rules will be triggered for identifiers that include those words as a prefix such as "forget" or "printed". This is probably not 482what you want. 483 484<H3><a name="ply_nn7"></a>4.4 Token values</H3> 485 486 487When tokens are returned by lex, they have a value that is stored in the <tt>value</tt> attribute. Normally, the value is the text 488that was matched. However, the value can be assigned to any Python object. For instance, when lexing identifiers, you may 489want to return both the identifier name and information from some sort of symbol table. To do this, you might write a rule like this: 490 491<blockquote> 492<pre> 493def t_ID(t): 494 ... 495 # Look up symbol table information and return a tuple 496 t.value = (t.value, symbol_lookup(t.value)) 497 ... 498 return t 499</pre> 500</blockquote> 501 502It is important to note that storing data in other attribute names is <em>not</em> recommended. The <tt>yacc.py</tt> module only exposes the 503contents of the <tt>value</tt> attribute. Thus, accessing other attributes may be unnecessarily awkward. If you 504need to store multiple values on a token, assign a tuple, dictionary, or instance to <tt>value</tt>. 505 506<H3><a name="ply_nn8"></a>4.5 Discarded tokens</H3> 507 508 509To discard a token, such as a comment, simply define a token rule that returns no value. For example: 510 511<blockquote> 512<pre> 513def t_COMMENT(t): 514 r'\#.*' 515 pass 516 # No return value. Token discarded 517</pre> 518</blockquote> 519 520Alternatively, you can include the prefix "ignore_" in the token declaration to force a token to be ignored. For example: 521 522<blockquote> 523<pre> 524t_ignore_COMMENT = r'\#.*' 525</pre> 526</blockquote> 527 528Be advised that if you are ignoring many different kinds of text, you may still want to use functions since these provide more precise 529control over the order in which regular expressions are matched (i.e., functions are matched in order of specification whereas strings are 530sorted by regular expression length). 531 532<H3><a name="ply_nn9"></a>4.6 Line numbers and positional information</H3> 533 534 535<p>By default, <tt>lex.py</tt> knows nothing about line numbers. This is because <tt>lex.py</tt> doesn't know anything 536about what constitutes a "line" of input (e.g., the newline character or even if the input is textual data). 537To update this information, you need to write a special rule. In the example, the <tt>t_newline()</tt> rule shows how to do this. 538 539<blockquote> 540<pre> 541# Define a rule so we can track line numbers 542def t_newline(t): 543 r'\n+' 544 t.lexer.lineno += len(t.value) 545</pre> 546</blockquote> 547Within the rule, the <tt>lineno</tt> attribute of the underlying lexer <tt>t.lexer</tt> is updated. 548After the line number is updated, the token is simply discarded since nothing is returned. 549 550<p> 551<tt>lex.py</tt> does not perform and kind of automatic column tracking. However, it does record positional 552information related to each token in the <tt>lexpos</tt> attribute. Using this, it is usually possible to compute 553column information as a separate step. For instance, just count backwards until you reach a newline. 554 555<blockquote> 556<pre> 557# Compute column. 558# input is the input text string 559# token is a token instance 560def find_column(input,token): 561 last_cr = input.rfind('\n',0,token.lexpos) 562 if last_cr < 0: 563 last_cr = 0 564 column = (token.lexpos - last_cr) + 1 565 return column 566</pre> 567</blockquote> 568 569Since column information is often only useful in the context of error handling, calculating the column 570position can be performed when needed as opposed to doing it for each token. 571 572<H3><a name="ply_nn10"></a>4.7 Ignored characters</H3> 573 574 575<p> 576The special <tt>t_ignore</tt> rule is reserved by <tt>lex.py</tt> for characters 577that should be completely ignored in the input stream. 578Usually this is used to skip over whitespace and other non-essential characters. 579Although it is possible to define a regular expression rule for whitespace in a manner 580similar to <tt>t_newline()</tt>, the use of <tt>t_ignore</tt> provides substantially better 581lexing performance because it is handled as a special case and is checked in a much 582more efficient manner than the normal regular expression rules. 583 584<H3><a name="ply_nn11"></a>4.8 Literal characters</H3> 585 586 587<p> 588Literal characters can be specified by defining a variable <tt>literals</tt> in your lexing module. For example: 589 590<blockquote> 591<pre> 592literals = [ '+','-','*','/' ] 593</pre> 594</blockquote> 595 596or alternatively 597 598<blockquote> 599<pre> 600literals = "+-*/" 601</pre> 602</blockquote> 603 604A literal character is simply a single character that is returned "as is" when encountered by the lexer. Literals are checked 605after all of the defined regular expression rules. Thus, if a rule starts with one of the literal characters, it will always 606take precedence. 607<p> 608When a literal token is returned, both its <tt>type</tt> and <tt>value</tt> attributes are set to the character itself. For example, <tt>'+'</tt>. 609 610<H3><a name="ply_nn12"></a>4.9 Error handling</H3> 611 612 613<p> 614Finally, the <tt>t_error()</tt> 615function is used to handle lexing errors that occur when illegal 616characters are detected. In this case, the <tt>t.value</tt> attribute contains the 617rest of the input string that has not been tokenized. In the example, the error function 618was defined as follows: 619 620<blockquote> 621<pre> 622# Error handling rule 623def t_error(t): 624 print "Illegal character '%s'" % t.value[0] 625 t.lexer.skip(1) 626</pre> 627</blockquote> 628 629In this case, we simply print the offending character and skip ahead one character by calling <tt>t.lexer.skip(1)</tt>. 630 631<H3><a name="ply_nn13"></a>4.10 Building and using the lexer</H3> 632 633 634<p> 635To build the lexer, the function <tt>lex.lex()</tt> is used. This function 636uses Python reflection (or introspection) to read the the regular expression rules 637out of the calling context and build the lexer. Once the lexer has been built, two methods can 638be used to control the lexer. 639 640<ul> 641<li><tt>lexer.input(data)</tt>. Reset the lexer and store a new input string. 642<li><tt>lexer.token()</tt>. Return the next token. Returns a special <tt>LexToken</tt> instance on success or 643None if the end of the input text has been reached. 644</ul> 645 646The preferred way to use PLY is to invoke the above methods directly on the lexer object returned by the 647<tt>lex()</tt> function. The legacy interface to PLY involves module-level functions <tt>lex.input()</tt> and <tt>lex.token()</tt>. 648For example: 649 650<blockquote> 651<pre> 652lex.lex() 653lex.input(sometext) 654while 1: 655 tok = lex.token() 656 if not tok: break 657 print tok 658</pre> 659</blockquote> 660 661<p> 662In this example, the module-level functions <tt>lex.input()</tt> and <tt>lex.token()</tt> are bound to the <tt>input()</tt> 663and <tt>token()</tt> methods of the last lexer created by the lex module. This interface may go away at some point so 664it's probably best not to use it. 665 666<H3><a name="ply_nn14"></a>4.11 The @TOKEN decorator</H3> 667 668 669In some applications, you may want to define build tokens from as a series of 670more complex regular expression rules. For example: 671 672<blockquote> 673<pre> 674digit = r'([0-9])' 675nondigit = r'([_A-Za-z])' 676identifier = r'(' + nondigit + r'(' + digit + r'|' + nondigit + r')*)' 677 678def t_ID(t): 679 # want docstring to be identifier above. ????? 680 ... 681</pre> 682</blockquote> 683 684In this case, we want the regular expression rule for <tt>ID</tt> to be one of the variables above. However, there is no 685way to directly specify this using a normal documentation string. To solve this problem, you can use the <tt>@TOKEN</tt> 686decorator. For example: 687 688<blockquote> 689<pre> 690from ply.lex import TOKEN 691 692@TOKEN(identifier) 693def t_ID(t): 694 ... 695</pre> 696</blockquote> 697 698This will attach <tt>identifier</tt> to the docstring for <tt>t_ID()</tt> allowing <tt>lex.py</tt> to work normally. An alternative 699approach this problem is to set the docstring directly like this: 700 701<blockquote> 702<pre> 703def t_ID(t): 704 ... 705 706t_ID.__doc__ = identifier 707</pre> 708</blockquote> 709 710<b>NOTE:</b> Use of <tt>@TOKEN</tt> requires Python-2.4 or newer. If you're concerned about backwards compatibility with older 711versions of Python, use the alternative approach of setting the docstring directly. 712 713<H3><a name="ply_nn15"></a>4.12 Optimized mode</H3> 714 715 716For improved performance, it may be desirable to use Python's 717optimized mode (e.g., running Python with the <tt>-O</tt> 718option). However, doing so causes Python to ignore documentation 719strings. This presents special problems for <tt>lex.py</tt>. To 720handle this case, you can create your lexer using 721the <tt>optimize</tt> option as follows: 722 723<blockquote> 724<pre> 725lexer = lex.lex(optimize=1) 726</pre> 727</blockquote> 728 729Next, run Python in its normal operating mode. When you do 730this, <tt>lex.py</tt> will write a file called <tt>lextab.py</tt> to 731the current directory. This file contains all of the regular 732expression rules and tables used during lexing. On subsequent 733executions, 734<tt>lextab.py</tt> will simply be imported to build the lexer. This 735approach substantially improves the startup time of the lexer and it 736works in Python's optimized mode. 737 738<p> 739To change the name of the lexer-generated file, use the <tt>lextab</tt> keyword argument. For example: 740 741<blockquote> 742<pre> 743lexer = lex.lex(optimize=1,lextab="footab") 744</pre> 745</blockquote> 746 747When running in optimized mode, it is important to note that lex disables most error checking. Thus, this is really only recommended 748if you're sure everything is working correctly and you're ready to start releasing production code. 749 750<H3><a name="ply_nn16"></a>4.13 Debugging</H3> 751 752 753For the purpose of debugging, you can run <tt>lex()</tt> in a debugging mode as follows: 754 755<blockquote> 756<pre> 757lexer = lex.lex(debug=1) 758</pre> 759</blockquote> 760 761<p> 762This will produce various sorts of debugging information including all of the added rules, 763the master regular expressions used by the lexer, and tokens generating during lexing. 764</p> 765 766<p> 767In addition, <tt>lex.py</tt> comes with a simple main function which 768will either tokenize input read from standard input or from a file specified 769on the command line. To use it, simply put this in your lexer: 770</p> 771 772<blockquote> 773<pre> 774if __name__ == '__main__': 775 lex.runmain() 776</pre> 777</blockquote> 778 779Please refer to the "Debugging" section near the end for some more advanced details 780of debugging. 781 782<H3><a name="ply_nn17"></a>4.14 Alternative specification of lexers</H3> 783 784 785As shown in the example, lexers are specified all within one Python module. If you want to 786put token rules in a different module from the one in which you invoke <tt>lex()</tt>, use the 787<tt>module</tt> keyword argument. 788 789<p> 790For example, you might have a dedicated module that just contains 791the token rules: 792 793<blockquote> 794<pre> 795# module: tokrules.py 796# This module just contains the lexing rules 797 798# List of token names. This is always required 799tokens = ( 800 'NUMBER', 801 'PLUS', 802 'MINUS', 803 'TIMES', 804 'DIVIDE', 805 'LPAREN', 806 'RPAREN', 807) 808 809# Regular expression rules for simple tokens 810t_PLUS = r'\+' 811t_MINUS = r'-' 812t_TIMES = r'\*' 813t_DIVIDE = r'/' 814t_LPAREN = r'\(' 815t_RPAREN = r'\)' 816 817# A regular expression rule with some action code 818def t_NUMBER(t): 819 r'\d+' 820 t.value = int(t.value) 821 return t 822 823# Define a rule so we can track line numbers 824def t_newline(t): 825 r'\n+' 826 t.lexer.lineno += len(t.value) 827 828# A string containing ignored characters (spaces and tabs) 829t_ignore = ' \t' 830 831# Error handling rule 832def t_error(t): 833 print "Illegal character '%s'" % t.value[0] 834 t.lexer.skip(1) 835</pre> 836</blockquote> 837 838Now, if you wanted to build a tokenizer from these rules from within a different module, you would do the following (shown for Python interactive mode): 839 840<blockquote> 841<pre> 842>>> import tokrules 843>>> <b>lexer = lex.lex(module=tokrules)</b> 844>>> lexer.input("3 + 4") 845>>> lexer.token() 846LexToken(NUMBER,3,1,1,0) 847>>> lexer.token() 848LexToken(PLUS,'+',1,2) 849>>> lexer.token() 850LexToken(NUMBER,4,1,4) 851>>> lexer.token() 852None 853>>> 854</pre> 855</blockquote> 856 857The <tt>module</tt> option can also be used to define lexers from instances of a class. For example: 858 859<blockquote> 860<pre> 861import ply.lex as lex 862 863class MyLexer: 864 # List of token names. This is always required 865 tokens = ( 866 'NUMBER', 867 'PLUS', 868 'MINUS', 869 'TIMES', 870 'DIVIDE', 871 'LPAREN', 872 'RPAREN', 873 ) 874 875 # Regular expression rules for simple tokens 876 t_PLUS = r'\+' 877 t_MINUS = r'-' 878 t_TIMES = r'\*' 879 t_DIVIDE = r'/' 880 t_LPAREN = r'\(' 881 t_RPAREN = r'\)' 882 883 # A regular expression rule with some action code 884 # Note addition of self parameter since we're in a class 885 def t_NUMBER(self,t): 886 r'\d+' 887 t.value = int(t.value) 888 return t 889 890 # Define a rule so we can track line numbers 891 def t_newline(self,t): 892 r'\n+' 893 t.lexer.lineno += len(t.value) 894 895 # A string containing ignored characters (spaces and tabs) 896 t_ignore = ' \t' 897 898 # Error handling rule 899 def t_error(self,t): 900 print "Illegal character '%s'" % t.value[0] 901 t.lexer.skip(1) 902 903 <b># Build the lexer 904 def build(self,**kwargs): 905 self.lexer = lex.lex(module=self, **kwargs)</b> 906 907 # Test it output 908 def test(self,data): 909 self.lexer.input(data) 910 while True: 911 tok = lexer.token() 912 if not tok: break 913 print tok 914 915# Build the lexer and try it out 916m = MyLexer() 917m.build() # Build the lexer 918m.test("3 + 4") # Test it 919</pre> 920</blockquote> 921 922 923When building a lexer from class, <em>you should construct the lexer from 924an instance of the class</em>, not the class object itself. This is because 925PLY only works properly if the lexer actions are defined by bound-methods. 926 927<p> 928When using the <tt>module</tt> option to <tt>lex()</tt>, PLY collects symbols 929from the underlying object using the <tt>dir()</tt> function. There is no 930direct access to the <tt>__dict__</tt> attribute of the object supplied as a 931module value. 932 933<P> 934Finally, if you want to keep things nicely encapsulated, but don't want to use a 935full-fledged class definition, lexers can be defined using closures. For example: 936 937<blockquote> 938<pre> 939import ply.lex as lex 940 941# List of token names. This is always required 942tokens = ( 943 'NUMBER', 944 'PLUS', 945 'MINUS', 946 'TIMES', 947 'DIVIDE', 948 'LPAREN', 949 'RPAREN', 950) 951 952def MyLexer(): 953 # Regular expression rules for simple tokens 954 t_PLUS = r'\+' 955 t_MINUS = r'-' 956 t_TIMES = r'\*' 957 t_DIVIDE = r'/' 958 t_LPAREN = r'\(' 959 t_RPAREN = r'\)' 960 961 # A regular expression rule with some action code 962 def t_NUMBER(t): 963 r'\d+' 964 t.value = int(t.value) 965 return t 966 967 # Define a rule so we can track line numbers 968 def t_newline(t): 969 r'\n+' 970 t.lexer.lineno += len(t.value) 971 972 # A string containing ignored characters (spaces and tabs) 973 t_ignore = ' \t' 974 975 # Error handling rule 976 def t_error(t): 977 print "Illegal character '%s'" % t.value[0] 978 t.lexer.skip(1) 979 980 # Build the lexer from my environment and return it 981 return lex.lex() 982</pre> 983</blockquote> 984 985 986<H3><a name="ply_nn18"></a>4.15 Maintaining state</H3> 987 988 989In your lexer, you may want to maintain a variety of state 990information. This might include mode settings, symbol tables, and 991other details. As an example, suppose that you wanted to keep 992track of how many NUMBER tokens had been encountered. 993 994<p> 995One way to do this is to keep a set of global variables in the module 996where you created the lexer. For example: 997 998<blockquote> 999<pre> 1000num_count = 0 1001def t_NUMBER(t): 1002 r'\d+' 1003 global num_count 1004 num_count += 1 1005 t.value = int(t.value) 1006 return t 1007</pre> 1008</blockquote> 1009 1010If you don't like the use of a global variable, another place to store 1011information is inside the Lexer object created by <tt>lex()</tt>. 1012To this, you can use the <tt>lexer</tt> attribute of tokens passed to 1013the various rules. For example: 1014 1015<blockquote> 1016<pre> 1017def t_NUMBER(t): 1018 r'\d+' 1019 t.lexer.num_count += 1 # Note use of lexer attribute 1020 t.value = int(t.value) 1021 return t 1022 1023lexer = lex.lex() 1024lexer.num_count = 0 # Set the initial count 1025</pre> 1026</blockquote> 1027 1028This latter approach has the advantage of being simple and working 1029correctly in applications where multiple instantiations of a given 1030lexer exist in the same application. However, this might also feel 1031like a gross violation of encapsulation to OO purists. 1032Just to put your mind at some ease, all 1033internal attributes of the lexer (with the exception of <tt>lineno</tt>) have names that are prefixed 1034by <tt>lex</tt> (e.g., <tt>lexdata</tt>,<tt>lexpos</tt>, etc.). Thus, 1035it is perfectly safe to store attributes in the lexer that 1036don't have names starting with that prefix or a name that conlicts with one of the 1037predefined methods (e.g., <tt>input()</tt>, <tt>token()</tt>, etc.). 1038 1039<p> 1040If you don't like assigning values on the lexer object, you can define your lexer as a class as 1041shown in the previous section: 1042 1043<blockquote> 1044<pre> 1045class MyLexer: 1046 ... 1047 def t_NUMBER(self,t): 1048 r'\d+' 1049 self.num_count += 1 1050 t.value = int(t.value) 1051 return t 1052 1053 def build(self, **kwargs): 1054 self.lexer = lex.lex(object=self,**kwargs) 1055 1056 def __init__(self): 1057 self.num_count = 0 1058</pre> 1059</blockquote> 1060 1061The class approach may be the easiest to manage if your application is 1062going to be creating multiple instances of the same lexer and you need 1063to manage a lot of state. 1064 1065<p> 1066State can also be managed through closures. For example, in Python 3: 1067 1068<blockquote> 1069<pre> 1070def MyLexer(): 1071 num_count = 0 1072 ... 1073 def t_NUMBER(t): 1074 r'\d+' 1075 nonlocal num_count 1076 num_count += 1 1077 t.value = int(t.value) 1078 return t 1079 ... 1080</pre> 1081</blockquote> 1082 1083<H3><a name="ply_nn19"></a>4.16 Lexer cloning</H3> 1084 1085 1086<p> 1087If necessary, a lexer object can be duplicated by invoking its <tt>clone()</tt> method. For example: 1088 1089<blockquote> 1090<pre> 1091lexer = lex.lex() 1092... 1093newlexer = lexer.clone() 1094</pre> 1095</blockquote> 1096 1097When a lexer is cloned, the copy is exactly identical to the original lexer 1098including any input text and internal state. However, the clone allows a 1099different set of input text to be supplied which may be processed separately. 1100This may be useful in situations when you are writing a parser/compiler that 1101involves recursive or reentrant processing. For instance, if you 1102needed to scan ahead in the input for some reason, you could create a 1103clone and use it to look ahead. Or, if you were implementing some kind of preprocessor, 1104cloned lexers could be used to handle different input files. 1105 1106<p> 1107Creating a clone is different than calling <tt>lex.lex()</tt> in that 1108PLY doesn't regenerate any of the internal tables or regular expressions. So, 1109 1110<p> 1111Special considerations need to be made when cloning lexers that also 1112maintain their own internal state using classes or closures. Namely, 1113you need to be aware that the newly created lexers will share all of 1114this state with the original lexer. For example, if you defined a 1115lexer as a class and did this: 1116 1117<blockquote> 1118<pre> 1119m = MyLexer() 1120a = lex.lex(object=m) # Create a lexer 1121 1122b = a.clone() # Clone the lexer 1123</pre> 1124</blockquote> 1125 1126Then both <tt>a</tt> and <tt>b</tt> are going to be bound to the same 1127object <tt>m</tt> and any changes to <tt>m</tt> will be reflected in both lexers. It's 1128important to emphasize that <tt>clone()</tt> is only meant to create a new lexer 1129that reuses the regular expressions and environment of another lexer. If you 1130need to make a totally new copy of a lexer, then call <tt>lex()</tt> again. 1131 1132<H3><a name="ply_nn20"></a>4.17 Internal lexer state</H3> 1133 1134 1135A Lexer object <tt>lexer</tt> has a number of internal attributes that may be useful in certain 1136situations. 1137 1138<p> 1139<tt>lexer.lexpos</tt> 1140<blockquote> 1141This attribute is an integer that contains the current position within the input text. If you modify 1142the value, it will change the result of the next call to <tt>token()</tt>. Within token rule functions, this points 1143to the first character <em>after</em> the matched text. If the value is modified within a rule, the next returned token will be 1144matched at the new position. 1145</blockquote> 1146 1147<p> 1148<tt>lexer.lineno</tt> 1149<blockquote> 1150The current value of the line number attribute stored in the lexer. PLY only specifies that the attribute 1151exists---it never sets, updates, or performs any processing with it. If you want to track line numbers, 1152you will need to add code yourself (see the section on line numbers and positional information). 1153</blockquote> 1154 1155<p> 1156<tt>lexer.lexdata</tt> 1157<blockquote> 1158The current input text stored in the lexer. This is the string passed with the <tt>input()</tt> method. It 1159would probably be a bad idea to modify this unless you really know what you're doing. 1160</blockquote> 1161 1162<P> 1163<tt>lexer.lexmatch</tt> 1164<blockquote> 1165This is the raw <tt>Match</tt> object returned by the Python <tt>re.match()</tt> function (used internally by PLY) for the 1166current token. If you have written a regular expression that contains named groups, you can use this to retrieve those values. 1167Note: This attribute is only updated when tokens are defined and processed by functions. 1168</blockquote> 1169 1170<H3><a name="ply_nn21"></a>4.18 Conditional lexing and start conditions</H3> 1171 1172 1173In advanced parsing applications, it may be useful to have different 1174lexing states. For instance, you may want the occurrence of a certain 1175token or syntactic construct to trigger a different kind of lexing. 1176PLY supports a feature that allows the underlying lexer to be put into 1177a series of different states. Each state can have its own tokens, 1178lexing rules, and so forth. The implementation is based largely on 1179the "start condition" feature of GNU flex. Details of this can be found 1180at <a 1181href="http://www.gnu.org/software/flex/manual/html_chapter/flex_11.html">http://www.gnu.org/software/flex/manual/html_chapter/flex_11.html.</a>. 1182 1183<p> 1184To define a new lexing state, it must first be declared. This is done by including a "states" declaration in your 1185lex file. For example: 1186 1187<blockquote> 1188<pre> 1189states = ( 1190 ('foo','exclusive'), 1191 ('bar','inclusive'), 1192) 1193</pre> 1194</blockquote> 1195 1196This declaration declares two states, <tt>'foo'</tt> 1197and <tt>'bar'</tt>. States may be of two types; <tt>'exclusive'</tt> 1198and <tt>'inclusive'</tt>. An exclusive state completely overrides the 1199default behavior of the lexer. That is, lex will only return tokens 1200and apply rules defined specifically for that state. An inclusive 1201state adds additional tokens and rules to the default set of rules. 1202Thus, lex will return both the tokens defined by default in addition 1203to those defined for the inclusive state. 1204 1205<p> 1206Once a state has been declared, tokens and rules are declared by including the 1207state name in token/rule declaration. For example: 1208 1209<blockquote> 1210<pre> 1211t_foo_NUMBER = r'\d+' # Token 'NUMBER' in state 'foo' 1212t_bar_ID = r'[a-zA-Z_][a-zA-Z0-9_]*' # Token 'ID' in state 'bar' 1213 1214def t_foo_newline(t): 1215 r'\n' 1216 t.lexer.lineno += 1 1217</pre> 1218</blockquote> 1219 1220A token can be declared in multiple states by including multiple state names in the declaration. For example: 1221 1222<blockquote> 1223<pre> 1224t_foo_bar_NUMBER = r'\d+' # Defines token 'NUMBER' in both state 'foo' and 'bar' 1225</pre> 1226</blockquote> 1227 1228Alternative, a token can be declared in all states using the 'ANY' in the name. 1229 1230<blockquote> 1231<pre> 1232t_ANY_NUMBER = r'\d+' # Defines a token 'NUMBER' in all states 1233</pre> 1234</blockquote> 1235 1236If no state name is supplied, as is normally the case, the token is associated with a special state <tt>'INITIAL'</tt>. For example, 1237these two declarations are identical: 1238 1239<blockquote> 1240<pre> 1241t_NUMBER = r'\d+' 1242t_INITIAL_NUMBER = r'\d+' 1243</pre> 1244</blockquote> 1245 1246<p> 1247States are also associated with the special <tt>t_ignore</tt> and <tt>t_error()</tt> declarations. For example, if a state treats 1248these differently, you can declare: 1249 1250<blockquote> 1251<pre> 1252t_foo_ignore = " \t\n" # Ignored characters for state 'foo' 1253 1254def t_bar_error(t): # Special error handler for state 'bar' 1255 pass 1256</pre> 1257</blockquote> 1258 1259By default, lexing operates in the <tt>'INITIAL'</tt> state. This state includes all of the normally defined tokens. 1260For users who aren't using different states, this fact is completely transparent. If, during lexing or parsing, you want to change 1261the lexing state, use the <tt>begin()</tt> method. For example: 1262 1263<blockquote> 1264<pre> 1265def t_begin_foo(t): 1266 r'start_foo' 1267 t.lexer.begin('foo') # Starts 'foo' state 1268</pre> 1269</blockquote> 1270 1271To get out of a state, you use <tt>begin()</tt> to switch back to the initial state. For example: 1272 1273<blockquote> 1274<pre> 1275def t_foo_end(t): 1276 r'end_foo' 1277 t.lexer.begin('INITIAL') # Back to the initial state 1278</pre> 1279</blockquote> 1280 1281The management of states can also be done with a stack. For example: 1282 1283<blockquote> 1284<pre> 1285def t_begin_foo(t): 1286 r'start_foo' 1287 t.lexer.push_state('foo') # Starts 'foo' state 1288 1289def t_foo_end(t): 1290 r'end_foo' 1291 t.lexer.pop_state() # Back to the previous state 1292</pre> 1293</blockquote> 1294 1295<p> 1296The use of a stack would be useful in situations where there are many ways of entering a new lexing state and you merely want to go back 1297to the previous state afterwards. 1298 1299<P> 1300An example might help clarify. Suppose you were writing a parser and you wanted to grab sections of arbitrary C code enclosed by 1301curly braces. That is, whenever you encounter a starting brace '{', you want to read all of the enclosed code up to the ending brace '}' 1302and return it as a string. Doing this with a normal regular expression rule is nearly (if not actually) impossible. This is because braces can 1303be nested and can be included in comments and strings. Thus, simply matching up to the first matching '}' character isn't good enough. Here is how 1304you might use lexer states to do this: 1305 1306<blockquote> 1307<pre> 1308# Declare the state 1309states = ( 1310 ('ccode','exclusive'), 1311) 1312 1313# Match the first {. Enter ccode state. 1314def t_ccode(t): 1315 r'\{' 1316 t.lexer.code_start = t.lexer.lexpos # Record the starting position 1317 t.lexer.level = 1 # Initial brace level 1318 t.lexer.begin('ccode') # Enter 'ccode' state 1319 1320# Rules for the ccode state 1321def t_ccode_lbrace(t): 1322 r'\{' 1323 t.lexer.level +=1 1324 1325def t_ccode_rbrace(t): 1326 r'\}' 1327 t.lexer.level -=1 1328 1329 # If closing brace, return the code fragment 1330 if t.lexer.level == 0: 1331 t.value = t.lexer.lexdata[t.lexer.code_start:t.lexer.lexpos+1] 1332 t.type = "CCODE" 1333 t.lexer.lineno += t.value.count('\n') 1334 t.lexer.begin('INITIAL') 1335 return t 1336 1337# C or C++ comment (ignore) 1338def t_ccode_comment(t): 1339 r'(/\*(.|\n)*?*/)|(//.*)' 1340 pass 1341 1342# C string 1343def t_ccode_string(t): 1344 r'\"([^\\\n]|(\\.))*?\"' 1345 1346# C character literal 1347def t_ccode_char(t): 1348 r'\'([^\\\n]|(\\.))*?\'' 1349 1350# Any sequence of non-whitespace characters (not braces, strings) 1351def t_ccode_nonspace(t): 1352 r'[^\s\{\}\'\"]+' 1353 1354# Ignored characters (whitespace) 1355t_ccode_ignore = " \t\n" 1356 1357# For bad characters, we just skip over it 1358def t_ccode_error(t): 1359 t.lexer.skip(1) 1360</pre> 1361</blockquote> 1362 1363In this example, the occurrence of the first '{' causes the lexer to record the starting position and enter a new state <tt>'ccode'</tt>. A collection of rules then match 1364various parts of the input that follow (comments, strings, etc.). All of these rules merely discard the token (by not returning a value). 1365However, if the closing right brace is encountered, the rule <tt>t_ccode_rbrace</tt> collects all of the code (using the earlier recorded starting 1366position), stores it, and returns a token 'CCODE' containing all of that text. When returning the token, the lexing state is restored back to its 1367initial state. 1368 1369<H3><a name="ply_nn21"></a>4.19 Miscellaneous Issues</H3> 1370 1371 1372<P> 1373<li>The lexer requires input to be supplied as a single input string. Since most machines have more than enough memory, this 1374rarely presents a performance concern. However, it means that the lexer currently can't be used with streaming data 1375such as open files or sockets. This limitation is primarily a side-effect of using the <tt>re</tt> module. 1376 1377<p> 1378<li>The lexer should work properly with both Unicode strings given as token and pattern matching rules as 1379well as for input text. 1380 1381<p> 1382<li>If you need to supply optional flags to the re.compile() function, use the reflags option to lex. For example: 1383 1384<blockquote> 1385<pre> 1386lex.lex(reflags=re.UNICODE) 1387</pre> 1388</blockquote> 1389 1390<p> 1391<li>Since the lexer is written entirely in Python, its performance is 1392largely determined by that of the Python <tt>re</tt> module. Although 1393the lexer has been written to be as efficient as possible, it's not 1394blazingly fast when used on very large input files. If 1395performance is concern, you might consider upgrading to the most 1396recent version of Python, creating a hand-written lexer, or offloading 1397the lexer into a C extension module. 1398 1399<p> 1400If you are going to create a hand-written lexer and you plan to use it with <tt>yacc.py</tt>, 1401it only needs to conform to the following requirements: 1402 1403<ul> 1404<li>It must provide a <tt>token()</tt> method that returns the next token or <tt>None</tt> if no more 1405tokens are available. 1406<li>The <tt>token()</tt> method must return an object <tt>tok</tt> that has <tt>type</tt> and <tt>value</tt> attributes. 1407</ul> 1408 1409<H2><a name="ply_nn22"></a>5. Parsing basics</H2> 1410 1411 1412<tt>yacc.py</tt> is used to parse language syntax. Before showing an 1413example, there are a few important bits of background that must be 1414mentioned. First, <em>syntax</em> is usually specified in terms of a BNF grammar. 1415For example, if you wanted to parse 1416simple arithmetic expressions, you might first write an unambiguous 1417grammar specification like this: 1418 1419<blockquote> 1420<pre> 1421expression : expression + term 1422 | expression - term 1423 | term 1424 1425term : term * factor 1426 | term / factor 1427 | factor 1428 1429factor : NUMBER 1430 | ( expression ) 1431</pre> 1432</blockquote> 1433 1434In the grammar, symbols such as <tt>NUMBER</tt>, <tt>+</tt>, <tt>-</tt>, <tt>*</tt>, and <tt>/</tt> are known 1435as <em>terminals</em> and correspond to raw input tokens. Identifiers such as <tt>term</tt> and <tt>factor</tt> refer to 1436grammar rules comprised of a collection of terminals and other rules. These identifiers are known as <em>non-terminals</em>. 1437<P> 1438 1439The semantic behavior of a language is often specified using a 1440technique known as syntax directed translation. In syntax directed 1441translation, attributes are attached to each symbol in a given grammar 1442rule along with an action. Whenever a particular grammar rule is 1443recognized, the action describes what to do. For example, given the 1444expression grammar above, you might write the specification for a 1445simple calculator like this: 1446 1447<blockquote> 1448<pre> 1449Grammar Action 1450-------------------------------- -------------------------------------------- 1451expression0 : expression1 + term expression0.val = expression1.val + term.val 1452 | expression1 - term expression0.val = expression1.val - term.val 1453 | term expression0.val = term.val 1454 1455term0 : term1 * factor term0.val = term1.val * factor.val 1456 | term1 / factor term0.val = term1.val / factor.val 1457 | factor term0.val = factor.val 1458 1459factor : NUMBER factor.val = int(NUMBER.lexval) 1460 | ( expression ) factor.val = expression.val 1461</pre> 1462</blockquote> 1463 1464A good way to think about syntax directed translation is to 1465view each symbol in the grammar as a kind of object. Associated 1466with each symbol is a value representing its "state" (for example, the 1467<tt>val</tt> attribute above). Semantic 1468actions are then expressed as a collection of functions or methods 1469that operate on the symbols and associated values. 1470 1471<p> 1472Yacc uses a parsing technique known as LR-parsing or shift-reduce parsing. LR parsing is a 1473bottom up technique that tries to recognize the right-hand-side of various grammar rules. 1474Whenever a valid right-hand-side is found in the input, the appropriate action code is triggered and the 1475grammar symbols are replaced by the grammar symbol on the left-hand-side. 1476 1477<p> 1478LR parsing is commonly implemented by shifting grammar symbols onto a 1479stack and looking at the stack and the next input token for patterns that 1480match one of the grammar rules. 1481The details of the algorithm can be found in a compiler textbook, but the 1482following example illustrates the steps that are performed if you 1483wanted to parse the expression 1484<tt>3 + 5 * (10 - 20)</tt> using the grammar defined above. In the example, 1485the special symbol <tt>$</tt> represents the end of input. 1486 1487 1488<blockquote> 1489<pre> 1490Step Symbol Stack Input Tokens Action 1491---- --------------------- --------------------- ------------------------------- 14921 3 + 5 * ( 10 - 20 )$ Shift 3 14932 3 + 5 * ( 10 - 20 )$ Reduce factor : NUMBER 14943 factor + 5 * ( 10 - 20 )$ Reduce term : factor 14954 term + 5 * ( 10 - 20 )$ Reduce expr : term 14965 expr + 5 * ( 10 - 20 )$ Shift + 14976 expr + 5 * ( 10 - 20 )$ Shift 5 14987 expr + 5 * ( 10 - 20 )$ Reduce factor : NUMBER 14998 expr + factor * ( 10 - 20 )$ Reduce term : factor 15009 expr + term * ( 10 - 20 )$ Shift * 150110 expr + term * ( 10 - 20 )$ Shift ( 150211 expr + term * ( 10 - 20 )$ Shift 10 150312 expr + term * ( 10 - 20 )$ Reduce factor : NUMBER 150413 expr + term * ( factor - 20 )$ Reduce term : factor 150514 expr + term * ( term - 20 )$ Reduce expr : term 150615 expr + term * ( expr - 20 )$ Shift - 150716 expr + term * ( expr - 20 )$ Shift 20 150817 expr + term * ( expr - 20 )$ Reduce factor : NUMBER 150918 expr + term * ( expr - factor )$ Reduce term : factor 151019 expr + term * ( expr - term )$ Reduce expr : expr - term 151120 expr + term * ( expr )$ Shift ) 151221 expr + term * ( expr ) $ Reduce factor : (expr) 151322 expr + term * factor $ Reduce term : term * factor 151423 expr + term $ Reduce expr : expr + term 151524 expr $ Reduce expr 151625 $ Success! 1517</pre> 1518</blockquote> 1519 1520When parsing the expression, an underlying state machine and the 1521current input token determine what happens next. If the next token 1522looks like part of a valid grammar rule (based on other items on the 1523stack), it is generally shifted onto the stack. If the top of the 1524stack contains a valid right-hand-side of a grammar rule, it is 1525usually "reduced" and the symbols replaced with the symbol on the 1526left-hand-side. When this reduction occurs, the appropriate action is 1527triggered (if defined). If the input token can't be shifted and the 1528top of stack doesn't match any grammar rules, a syntax error has 1529occurred and the parser must take some kind of recovery step (or bail 1530out). A parse is only successful if the parser reaches a state where 1531the symbol stack is empty and there are no more input tokens. 1532 1533<p> 1534It is important to note that the underlying implementation is built 1535around a large finite-state machine that is encoded in a collection of 1536tables. The construction of these tables is non-trivial and 1537beyond the scope of this discussion. However, subtle details of this 1538process explain why, in the example above, the parser chooses to shift 1539a token onto the stack in step 9 rather than reducing the 1540rule <tt>expr : expr + term</tt>. 1541 1542<H2><a name="ply_nn23"></a>6. Yacc</H2> 1543 1544 1545The <tt>ply.yacc</tt> module implements the parsing component of PLY. 1546The name "yacc" stands for "Yet Another Compiler Compiler" and is 1547borrowed from the Unix tool of the same name. 1548 1549<H3><a name="ply_nn24"></a>6.1 An example</H3> 1550 1551 1552Suppose you wanted to make a grammar for simple arithmetic expressions as previously described. Here is 1553how you would do it with <tt>yacc.py</tt>: 1554 1555<blockquote> 1556<pre> 1557# Yacc example 1558 1559import ply.yacc as yacc 1560 1561# Get the token map from the lexer. This is required. 1562from calclex import tokens 1563 1564def p_expression_plus(p): 1565 'expression : expression PLUS term' 1566 p[0] = p[1] + p[3] 1567 1568def p_expression_minus(p): 1569 'expression : expression MINUS term' 1570 p[0] = p[1] - p[3] 1571 1572def p_expression_term(p): 1573 'expression : term' 1574 p[0] = p[1] 1575 1576def p_term_times(p): 1577 'term : term TIMES factor' 1578 p[0] = p[1] * p[3] 1579 1580def p_term_div(p): 1581 'term : term DIVIDE factor' 1582 p[0] = p[1] / p[3] 1583 1584def p_term_factor(p): 1585 'term : factor' 1586 p[0] = p[1] 1587 1588def p_factor_num(p): 1589 'factor : NUMBER' 1590 p[0] = p[1] 1591 1592def p_factor_expr(p): 1593 'factor : LPAREN expression RPAREN' 1594 p[0] = p[2] 1595 1596# Error rule for syntax errors 1597def p_error(p): 1598 print "Syntax error in input!" 1599 1600# Build the parser 1601parser = yacc.yacc() 1602 1603while True: 1604 try: 1605 s = raw_input('calc > ') 1606 except EOFError: 1607 break 1608 if not s: continue 1609 result = parser.parse(s) 1610 print result 1611</pre> 1612</blockquote> 1613 1614In this example, each grammar rule is defined by a Python function 1615where the docstring to that function contains the appropriate 1616context-free grammar specification. The statements that make up the 1617function body implement the semantic actions of the rule. Each function 1618accepts a single argument <tt>p</tt> that is a sequence containing the 1619values of each grammar symbol in the corresponding rule. The values 1620of <tt>p[i]</tt> are mapped to grammar symbols as shown here: 1621 1622<blockquote> 1623<pre> 1624def p_expression_plus(p): 1625 'expression : expression PLUS term' 1626 # ^ ^ ^ ^ 1627 # p[0] p[1] p[2] p[3] 1628 1629 p[0] = p[1] + p[3] 1630</pre> 1631</blockquote> 1632 1633<p> 1634For tokens, the "value" of the corresponding <tt>p[i]</tt> is the 1635<em>same</em> as the <tt>p.value</tt> attribute assigned in the lexer 1636module. For non-terminals, the value is determined by whatever is 1637placed in <tt>p[0]</tt> when rules are reduced. This value can be 1638anything at all. However, it probably most common for the value to be 1639a simple Python type, a tuple, or an instance. In this example, we 1640are relying on the fact that the <tt>NUMBER</tt> token stores an 1641integer value in its value field. All of the other rules simply 1642perform various types of integer operations and propagate the result. 1643</p> 1644 1645<p> 1646Note: The use of negative indices have a special meaning in 1647yacc---specially <tt>p[-1]</tt> does not have the same value 1648as <tt>p[3]</tt> in this example. Please see the section on "Embedded 1649Actions" for further details. 1650</p> 1651 1652<p> 1653The first rule defined in the yacc specification determines the 1654starting grammar symbol (in this case, a rule for <tt>expression</tt> 1655appears first). Whenever the starting rule is reduced by the parser 1656and no more input is available, parsing stops and the final value is 1657returned (this value will be whatever the top-most rule placed 1658in <tt>p[0]</tt>). Note: an alternative starting symbol can be 1659specified using the <tt>start</tt> keyword argument to 1660<tt>yacc()</tt>. 1661 1662<p>The <tt>p_error(p)</tt> rule is defined to catch syntax errors. 1663See the error handling section below for more detail. 1664 1665<p> 1666To build the parser, call the <tt>yacc.yacc()</tt> function. This 1667function looks at the module and attempts to construct all of the LR 1668parsing tables for the grammar you have specified. The first 1669time <tt>yacc.yacc()</tt> is invoked, you will get a message such as 1670this: 1671 1672<blockquote> 1673<pre> 1674$ python calcparse.py 1675Generating LALR tables 1676calc > 1677</pre> 1678</blockquote> 1679 1680Since table construction is relatively expensive (especially for large 1681grammars), the resulting parsing table is written to the current 1682directory in a file called <tt>parsetab.py</tt>. In addition, a 1683debugging file called <tt>parser.out</tt> is created. On subsequent 1684executions, <tt>yacc</tt> will reload the table from 1685<tt>parsetab.py</tt> unless it has detected a change in the underlying 1686grammar (in which case the tables and <tt>parsetab.py</tt> file are 1687regenerated). Note: The names of parser output files can be changed 1688if necessary. See the <a href="reference.html">PLY Reference</a> for details. 1689 1690<p> 1691If any errors are detected in your grammar specification, <tt>yacc.py</tt> will produce 1692diagnostic messages and possibly raise an exception. Some of the errors that can be detected include: 1693 1694<ul> 1695<li>Duplicated function names (if more than one rule function have the same name in the grammar file). 1696<li>Shift/reduce and reduce/reduce conflicts generated by ambiguous grammars. 1697<li>Badly specified grammar rules. 1698<li>Infinite recursion (rules that can never terminate). 1699<li>Unused rules and tokens 1700<li>Undefined rules and tokens 1701</ul> 1702 1703The next few sections discuss grammar specification in more detail. 1704 1705<p> 1706The final part of the example shows how to actually run the parser 1707created by 1708<tt>yacc()</tt>. To run the parser, you simply have to call 1709the <tt>parse()</tt> with a string of input text. This will run all 1710of the grammar rules and return the result of the entire parse. This 1711result return is the value assigned to <tt>p[0]</tt> in the starting 1712grammar rule. 1713 1714<H3><a name="ply_nn25"></a>6.2 Combining Grammar Rule Functions</H3> 1715 1716 1717When grammar rules are similar, they can be combined into a single function. 1718For example, consider the two rules in our earlier example: 1719 1720<blockquote> 1721<pre> 1722def p_expression_plus(p): 1723 'expression : expression PLUS term' 1724 p[0] = p[1] + p[3] 1725 1726def p_expression_minus(t): 1727 'expression : expression MINUS term' 1728 p[0] = p[1] - p[3] 1729</pre> 1730</blockquote> 1731 1732Instead of writing two functions, you might write a single function like this: 1733 1734<blockquote> 1735<pre> 1736def p_expression(p): 1737 '''expression : expression PLUS term 1738 | expression MINUS term''' 1739 if p[2] == '+': 1740 p[0] = p[1] + p[3] 1741 elif p[2] == '-': 1742 p[0] = p[1] - p[3] 1743</pre> 1744</blockquote> 1745 1746In general, the doc string for any given function can contain multiple grammar rules. So, it would 1747have also been legal (although possibly confusing) to write this: 1748 1749<blockquote> 1750<pre> 1751def p_binary_operators(p): 1752 '''expression : expression PLUS term 1753 | expression MINUS term 1754 term : term TIMES factor 1755 | term DIVIDE factor''' 1756 if p[2] == '+': 1757 p[0] = p[1] + p[3] 1758 elif p[2] == '-': 1759 p[0] = p[1] - p[3] 1760 elif p[2] == '*': 1761 p[0] = p[1] * p[3] 1762 elif p[2] == '/': 1763 p[0] = p[1] / p[3] 1764</pre> 1765</blockquote> 1766 1767When combining grammar rules into a single function, it is usually a good idea for all of the rules to have 1768a similar structure (e.g., the same number of terms). Otherwise, the corresponding action code may be more 1769complicated than necessary. However, it is possible to handle simple cases using len(). For example: 1770 1771<blockquote> 1772<pre> 1773def p_expressions(p): 1774 '''expression : expression MINUS expression 1775 | MINUS expression''' 1776 if (len(p) == 4): 1777 p[0] = p[1] - p[3] 1778 elif (len(p) == 3): 1779 p[0] = -p[2] 1780</pre> 1781</blockquote> 1782 1783If parsing performance is a concern, you should resist the urge to put 1784too much conditional processing into a single grammar rule as shown in 1785these examples. When you add checks to see which grammar rule is 1786being handled, you are actually duplicating the work that the parser 1787has already performed (i.e., the parser already knows exactly what rule it 1788matched). You can eliminate this overhead by using a 1789separate <tt>p_rule()</tt> function for each grammar rule. 1790 1791<H3><a name="ply_nn26"></a>6.3 Character Literals</H3> 1792 1793 1794If desired, a grammar may contain tokens defined as single character literals. For example: 1795 1796<blockquote> 1797<pre> 1798def p_binary_operators(p): 1799 '''expression : expression '+' term 1800 | expression '-' term 1801 term : term '*' factor 1802 | term '/' factor''' 1803 if p[2] == '+': 1804 p[0] = p[1] + p[3] 1805 elif p[2] == '-': 1806 p[0] = p[1] - p[3] 1807 elif p[2] == '*': 1808 p[0] = p[1] * p[3] 1809 elif p[2] == '/': 1810 p[0] = p[1] / p[3] 1811</pre> 1812</blockquote> 1813 1814A character literal must be enclosed in quotes such as <tt>'+'</tt>. In addition, if literals are used, they must be declared in the 1815corresponding <tt>lex</tt> file through the use of a special <tt>literals</tt> declaration. 1816 1817<blockquote> 1818<pre> 1819# Literals. Should be placed in module given to lex() 1820literals = ['+','-','*','/' ] 1821</pre> 1822</blockquote> 1823 1824<b>Character literals are limited to a single character</b>. Thus, it is not legal to specify literals such as <tt>'<='</tt> or <tt>'=='</tt>. For this, use 1825the normal lexing rules (e.g., define a rule such as <tt>t_EQ = r'=='</tt>). 1826 1827<H3><a name="ply_nn26"></a>6.4 Empty Productions</H3> 1828 1829 1830<tt>yacc.py</tt> can handle empty productions by defining a rule like this: 1831 1832<blockquote> 1833<pre> 1834def p_empty(p): 1835 'empty :' 1836 pass 1837</pre> 1838</blockquote> 1839 1840Now to use the empty production, simply use 'empty' as a symbol. For example: 1841 1842<blockquote> 1843<pre> 1844def p_optitem(p): 1845 'optitem : item' 1846 ' | empty' 1847 ... 1848</pre> 1849</blockquote> 1850 1851Note: You can write empty rules anywhere by simply specifying an empty 1852right hand side. However, I personally find that writing an "empty" 1853rule and using "empty" to denote an empty production is easier to read 1854and more clearly states your intentions. 1855 1856<H3><a name="ply_nn28"></a>6.5 Changing the starting symbol</H3> 1857 1858 1859Normally, the first rule found in a yacc specification defines the starting grammar rule (top level rule). To change this, simply 1860supply a <tt>start</tt> specifier in your file. For example: 1861 1862<blockquote> 1863<pre> 1864start = 'foo' 1865 1866def p_bar(p): 1867 'bar : A B' 1868 1869# This is the starting rule due to the start specifier above 1870def p_foo(p): 1871 'foo : bar X' 1872... 1873</pre> 1874</blockquote> 1875 1876The use of a <tt>start</tt> specifier may be useful during debugging 1877since you can use it to have yacc build a subset of a larger grammar. 1878For this purpose, it is also possible to specify a starting symbol as 1879an argument to <tt>yacc()</tt>. For example: 1880 1881<blockquote> 1882<pre> 1883yacc.yacc(start='foo') 1884</pre> 1885</blockquote> 1886 1887<H3><a name="ply_nn27"></a>6.6 Dealing With Ambiguous Grammars</H3> 1888 1889 1890The expression grammar given in the earlier example has been written 1891in a special format to eliminate ambiguity. However, in many 1892situations, it is extremely difficult or awkward to write grammars in 1893this format. A much more natural way to express the grammar is in a 1894more compact form like this: 1895 1896<blockquote> 1897<pre> 1898expression : expression PLUS expression 1899 | expression MINUS expression 1900 | expression TIMES expression 1901 | expression DIVIDE expression 1902 | LPAREN expression RPAREN 1903 | NUMBER 1904</pre> 1905</blockquote> 1906 1907Unfortunately, this grammar specification is ambiguous. For example, 1908if you are parsing the string "3 * 4 + 5", there is no way to tell how 1909the operators are supposed to be grouped. For example, does the 1910expression mean "(3 * 4) + 5" or is it "3 * (4+5)"? 1911 1912<p> 1913When an ambiguous grammar is given to <tt>yacc.py</tt> it will print 1914messages about "shift/reduce conflicts" or "reduce/reduce conflicts". 1915A shift/reduce conflict is caused when the parser generator can't 1916decide whether or not to reduce a rule or shift a symbol on the 1917parsing stack. For example, consider the string "3 * 4 + 5" and the 1918internal parsing stack: 1919 1920<blockquote> 1921<pre> 1922Step Symbol Stack Input Tokens Action 1923---- --------------------- --------------------- ------------------------------- 19241 $ 3 * 4 + 5$ Shift 3 19252 $ 3 * 4 + 5$ Reduce : expression : NUMBER 19263 $ expr * 4 + 5$ Shift * 19274 $ expr * 4 + 5$ Shift 4 19285 $ expr * 4 + 5$ Reduce: expression : NUMBER 19296 $ expr * expr + 5$ SHIFT/REDUCE CONFLICT ???? 1930</pre> 1931</blockquote> 1932 1933In this case, when the parser reaches step 6, it has two options. One 1934is to reduce the rule <tt>expr : expr * expr</tt> on the stack. The 1935other option is to shift the token <tt>+</tt> on the stack. Both 1936options are perfectly legal from the rules of the 1937context-free-grammar. 1938 1939<p> 1940By default, all shift/reduce conflicts are resolved in favor of 1941shifting. Therefore, in the above example, the parser will always 1942shift the <tt>+</tt> instead of reducing. Although this strategy 1943works in many cases (for example, the case of 1944"if-then" versus "if-then-else"), it is not enough for arithmetic expressions. In fact, 1945in the above example, the decision to shift <tt>+</tt> is completely 1946wrong---we should have reduced <tt>expr * expr</tt> since 1947multiplication has higher mathematical precedence than addition. 1948 1949<p>To resolve ambiguity, especially in expression 1950grammars, <tt>yacc.py</tt> allows individual tokens to be assigned a 1951precedence level and associativity. This is done by adding a variable 1952<tt>precedence</tt> to the grammar file like this: 1953 1954<blockquote> 1955<pre> 1956precedence = ( 1957 ('left', 'PLUS', 'MINUS'), 1958 ('left', 'TIMES', 'DIVIDE'), 1959) 1960</pre> 1961</blockquote> 1962 1963This declaration specifies that <tt>PLUS</tt>/<tt>MINUS</tt> have the 1964same precedence level and are left-associative and that 1965<tt>TIMES</tt>/<tt>DIVIDE</tt> have the same precedence and are 1966left-associative. Within the <tt>precedence</tt> declaration, tokens 1967are ordered from lowest to highest precedence. Thus, this declaration 1968specifies that <tt>TIMES</tt>/<tt>DIVIDE</tt> have higher precedence 1969than <tt>PLUS</tt>/<tt>MINUS</tt> (since they appear later in the 1970precedence specification). 1971 1972<p> 1973The precedence specification works by associating a numerical 1974precedence level value and associativity direction to the listed 1975tokens. For example, in the above example you get: 1976 1977<blockquote> 1978<pre> 1979PLUS : level = 1, assoc = 'left' 1980MINUS : level = 1, assoc = 'left' 1981TIMES : level = 2, assoc = 'left' 1982DIVIDE : level = 2, assoc = 'left' 1983</pre> 1984</blockquote> 1985 1986These values are then used to attach a numerical precedence value and 1987associativity direction to each grammar rule. <em>This is always 1988determined by looking at the precedence of the right-most terminal 1989symbol.</em> For example: 1990 1991<blockquote> 1992<pre> 1993expression : expression PLUS expression # level = 1, left 1994 | expression MINUS expression # level = 1, left 1995 | expression TIMES expression # level = 2, left 1996 | expression DIVIDE expression # level = 2, left 1997 | LPAREN expression RPAREN # level = None (not specified) 1998 | NUMBER # level = None (not specified) 1999</pre> 2000</blockquote> 2001 2002When shift/reduce conflicts are encountered, the parser generator resolves the conflict by 2003looking at the precedence rules and associativity specifiers. 2004 2005<p> 2006<ol> 2007<li>If the current token has higher precedence than the rule on the stack, it is shifted. 2008<li>If the grammar rule on the stack has higher precedence, the rule is reduced. 2009<li>If the current token and the grammar rule have the same precedence, the 2010rule is reduced for left associativity, whereas the token is shifted for right associativity. 2011<li>If nothing is known about the precedence, shift/reduce conflicts are resolved in 2012favor of shifting (the default). 2013</ol> 2014 2015For example, if "expression PLUS expression" has been parsed and the 2016next token is "TIMES", the action is going to be a shift because 2017"TIMES" has a higher precedence level than "PLUS". On the other hand, 2018if "expression TIMES expression" has been parsed and the next token is 2019"PLUS", the action is going to be reduce because "PLUS" has a lower 2020precedence than "TIMES." 2021 2022<p> 2023When shift/reduce conflicts are resolved using the first three 2024techniques (with the help of precedence rules), <tt>yacc.py</tt> will 2025report no errors or conflicts in the grammar (although it will print 2026some information in the <tt>parser.out</tt> debugging file). 2027 2028<p> 2029One problem with the precedence specifier technique is that it is 2030sometimes necessary to change the precedence of an operator in certain 2031contexts. For example, consider a unary-minus operator in "3 + 4 * 2032-5". Mathematically, the unary minus is normally given a very high 2033precedence--being evaluated before the multiply. However, in our 2034precedence specifier, MINUS has a lower precedence than TIMES. To 2035deal with this, precedence rules can be given for so-called "fictitious tokens" 2036like this: 2037 2038<blockquote> 2039<pre> 2040precedence = ( 2041 ('left', 'PLUS', 'MINUS'), 2042 ('left', 'TIMES', 'DIVIDE'), 2043 ('right', 'UMINUS'), # Unary minus operator 2044) 2045</pre> 2046</blockquote> 2047 2048Now, in the grammar file, we can write our unary minus rule like this: 2049 2050<blockquote> 2051<pre> 2052def p_expr_uminus(p): 2053 'expression : MINUS expression %prec UMINUS' 2054 p[0] = -p[2] 2055</pre> 2056</blockquote> 2057 2058In this case, <tt>%prec UMINUS</tt> overrides the default rule precedence--setting it to that 2059of UMINUS in the precedence specifier. 2060 2061<p> 2062At first, the use of UMINUS in this example may appear very confusing. 2063UMINUS is not an input token or a grammer rule. Instead, you should 2064think of it as the name of a special marker in the precedence table. When you use the <tt>%prec</tt> qualifier, you're simply 2065telling yacc that you want the precedence of the expression to be the same as for this special marker instead of the usual precedence. 2066 2067<p> 2068It is also possible to specify non-associativity in the <tt>precedence</tt> table. This would 2069be used when you <em>don't</em> want operations to chain together. For example, suppose 2070you wanted to support comparison operators like <tt><</tt> and <tt>></tt> but you didn't want to allow 2071combinations like <tt>a < b < c</tt>. To do this, simply specify a rule like this: 2072 2073<blockquote> 2074<pre> 2075precedence = ( 2076 ('nonassoc', 'LESSTHAN', 'GREATERTHAN'), # Nonassociative operators 2077 ('left', 'PLUS', 'MINUS'), 2078 ('left', 'TIMES', 'DIVIDE'), 2079 ('right', 'UMINUS'), # Unary minus operator 2080) 2081</pre> 2082</blockquote> 2083 2084<p> 2085If you do this, the occurrence of input text such as <tt> a < b < c</tt> will result in a syntax error. However, simple 2086expressions such as <tt>a < b</tt> will still be fine. 2087 2088<p> 2089Reduce/reduce conflicts are caused when there are multiple grammar 2090rules that can be applied to a given set of symbols. This kind of 2091conflict is almost always bad and is always resolved by picking the 2092rule that appears first in the grammar file. Reduce/reduce conflicts 2093are almost always caused when different sets of grammar rules somehow 2094generate the same set of symbols. For example: 2095 2096<blockquote> 2097<pre> 2098assignment : ID EQUALS NUMBER 2099 | ID EQUALS expression 2100 2101expression : expression PLUS expression 2102 | expression MINUS expression 2103 | expression TIMES expression 2104 | expression DIVIDE expression 2105 | LPAREN expression RPAREN 2106 | NUMBER 2107</pre> 2108</blockquote> 2109 2110In this case, a reduce/reduce conflict exists between these two rules: 2111 2112<blockquote> 2113<pre> 2114assignment : ID EQUALS NUMBER 2115expression : NUMBER 2116</pre> 2117</blockquote> 2118 2119For example, if you wrote "a = 5", the parser can't figure out if this 2120is supposed to be reduced as <tt>assignment : ID EQUALS NUMBER</tt> or 2121whether it's supposed to reduce the 5 as an expression and then reduce 2122the rule <tt>assignment : ID EQUALS expression</tt>. 2123 2124<p> 2125It should be noted that reduce/reduce conflicts are notoriously 2126difficult to spot simply looking at the input grammer. When a 2127reduce/reduce conflict occurs, <tt>yacc()</tt> will try to help by 2128printing a warning message such as this: 2129 2130<blockquote> 2131<pre> 2132WARNING: 1 reduce/reduce conflict 2133WARNING: reduce/reduce conflict in state 15 resolved using rule (assignment -> ID EQUALS NUMBER) 2134WARNING: rejected rule (expression -> NUMBER) 2135</pre> 2136</blockquote> 2137 2138This message identifies the two rules that are in conflict. However, 2139it may not tell you how the parser arrived at such a state. To try 2140and figure it out, you'll probably have to look at your grammar and 2141the contents of the 2142<tt>parser.out</tt> debugging file with an appropriately high level of 2143caffeination. 2144 2145<H3><a name="ply_nn28"></a>6.7 The parser.out file</H3> 2146 2147 2148Tracking down shift/reduce and reduce/reduce conflicts is one of the finer pleasures of using an LR 2149parsing algorithm. To assist in debugging, <tt>yacc.py</tt> creates a debugging file called 2150'parser.out' when it generates the parsing table. The contents of this file look like the following: 2151 2152<blockquote> 2153<pre> 2154Unused terminals: 2155 2156 2157Grammar 2158 2159Rule 1 expression -> expression PLUS expression 2160Rule 2 expression -> expression MINUS expression 2161Rule 3 expression -> expression TIMES expression 2162Rule 4 expression -> expression DIVIDE expression 2163Rule 5 expression -> NUMBER 2164Rule 6 expression -> LPAREN expression RPAREN 2165 2166Terminals, with rules where they appear 2167 2168TIMES : 3 2169error : 2170MINUS : 2 2171RPAREN : 6 2172LPAREN : 6 2173DIVIDE : 4 2174PLUS : 1 2175NUMBER : 5 2176 2177Nonterminals, with rules where they appear 2178 2179expression : 1 1 2 2 3 3 4 4 6 0 2180 2181 2182Parsing method: LALR 2183 2184 2185state 0 2186 2187 S' -> . expression 2188 expression -> . expression PLUS expression 2189 expression -> . expression MINUS expression 2190 expression -> . expression TIMES expression 2191 expression -> . expression DIVIDE expression 2192 expression -> . NUMBER 2193 expression -> . LPAREN expression RPAREN 2194 2195 NUMBER shift and go to state 3 2196 LPAREN shift and go to state 2 2197 2198 2199state 1 2200 2201 S' -> expression . 2202 expression -> expression . PLUS expression 2203 expression -> expression . MINUS expression 2204 expression -> expression . TIMES expression 2205 expression -> expression . DIVIDE expression 2206 2207 PLUS shift and go to state 6 2208 MINUS shift and go to state 5 2209 TIMES shift and go to state 4 2210 DIVIDE shift and go to state 7 2211 2212 2213state 2 2214 2215 expression -> LPAREN . expression RPAREN 2216 expression -> . expression PLUS expression 2217 expression -> . expression MINUS expression 2218 expression -> . expression TIMES expression 2219 expression -> . expression DIVIDE expression 2220 expression -> . NUMBER 2221 expression -> . LPAREN expression RPAREN 2222 2223 NUMBER shift and go to state 3 2224 LPAREN shift and go to state 2 2225 2226 2227state 3 2228 2229 expression -> NUMBER . 2230 2231 $ reduce using rule 5 2232 PLUS reduce using rule 5 2233 MINUS reduce using rule 5 2234 TIMES reduce using rule 5 2235 DIVIDE reduce using rule 5 2236 RPAREN reduce using rule 5 2237 2238 2239state 4 2240 2241 expression -> expression TIMES . expression 2242 expression -> . expression PLUS expression 2243 expression -> . expression MINUS expression 2244 expression -> . expression TIMES expression 2245 expression -> . expression DIVIDE expression 2246 expression -> . NUMBER 2247 expression -> . LPAREN expression RPAREN 2248 2249 NUMBER shift and go to state 3 2250 LPAREN shift and go to state 2 2251 2252 2253state 5 2254 2255 expression -> expression MINUS . expression 2256 expression -> . expression PLUS expression 2257 expression -> . expression MINUS expression 2258 expression -> . expression TIMES expression 2259 expression -> . expression DIVIDE expression 2260 expression -> . NUMBER 2261 expression -> . LPAREN expression RPAREN 2262 2263 NUMBER shift and go to state 3 2264 LPAREN shift and go to state 2 2265 2266 2267state 6 2268 2269 expression -> expression PLUS . expression 2270 expression -> . expression PLUS expression 2271 expression -> . expression MINUS expression 2272 expression -> . expression TIMES expression 2273 expression -> . expression DIVIDE expression 2274 expression -> . NUMBER 2275 expression -> . LPAREN expression RPAREN 2276 2277 NUMBER shift and go to state 3 2278 LPAREN shift and go to state 2 2279 2280 2281state 7 2282 2283 expression -> expression DIVIDE . expression 2284 expression -> . expression PLUS expression 2285 expression -> . expression MINUS expression 2286 expression -> . expression TIMES expression 2287 expression -> . expression DIVIDE expression 2288 expression -> . NUMBER 2289 expression -> . LPAREN expression RPAREN 2290 2291 NUMBER shift and go to state 3 2292 LPAREN shift and go to state 2 2293 2294 2295state 8 2296 2297 expression -> LPAREN expression . RPAREN 2298 expression -> expression . PLUS expression 2299 expression -> expression . MINUS expression 2300 expression -> expression . TIMES expression 2301 expression -> expression . DIVIDE expression 2302 2303 RPAREN shift and go to state 13 2304 PLUS shift and go to state 6 2305 MINUS shift and go to state 5 2306 TIMES shift and go to state 4 2307 DIVIDE shift and go to state 7 2308 2309 2310state 9 2311 2312 expression -> expression TIMES expression . 2313 expression -> expression . PLUS expression 2314 expression -> expression . MINUS expression 2315 expression -> expression . TIMES expression 2316 expression -> expression . DIVIDE expression 2317 2318 $ reduce using rule 3 2319 PLUS reduce using rule 3 2320 MINUS reduce using rule 3 2321 TIMES reduce using rule 3 2322 DIVIDE reduce using rule 3 2323 RPAREN reduce using rule 3 2324 2325 ! PLUS [ shift and go to state 6 ] 2326 ! MINUS [ shift and go to state 5 ] 2327 ! TIMES [ shift and go to state 4 ] 2328 ! DIVIDE [ shift and go to state 7 ] 2329 2330state 10 2331 2332 expression -> expression MINUS expression . 2333 expression -> expression . PLUS expression 2334 expression -> expression . MINUS expression 2335 expression -> expression . TIMES expression 2336 expression -> expression . DIVIDE expression 2337 2338 $ reduce using rule 2 2339 PLUS reduce using rule 2 2340 MINUS reduce using rule 2 2341 RPAREN reduce using rule 2 2342 TIMES shift and go to state 4 2343 DIVIDE shift and go to state 7 2344 2345 ! TIMES [ reduce using rule 2 ] 2346 ! DIVIDE [ reduce using rule 2 ] 2347 ! PLUS [ shift and go to state 6 ] 2348 ! MINUS [ shift and go to state 5 ] 2349 2350state 11 2351 2352 expression -> expression PLUS expression . 2353 expression -> expression . PLUS expression 2354 expression -> expression . MINUS expression 2355 expression -> expression . TIMES expression 2356 expression -> expression . DIVIDE expression 2357 2358 $ reduce using rule 1 2359 PLUS reduce using rule 1 2360 MINUS reduce using rule 1 2361 RPAREN reduce using rule 1 2362 TIMES shift and go to state 4 2363 DIVIDE shift and go to state 7 2364 2365 ! TIMES [ reduce using rule 1 ] 2366 ! DIVIDE [ reduce using rule 1 ] 2367 ! PLUS [ shift and go to state 6 ] 2368 ! MINUS [ shift and go to state 5 ] 2369 2370state 12 2371 2372 expression -> expression DIVIDE expression . 2373 expression -> expression . PLUS expression 2374 expression -> expression . MINUS expression 2375 expression -> expression . TIMES expression 2376 expression -> expression . DIVIDE expression 2377 2378 $ reduce using rule 4 2379 PLUS reduce using rule 4 2380 MINUS reduce using rule 4 2381 TIMES reduce using rule 4 2382 DIVIDE reduce using rule 4 2383 RPAREN reduce using rule 4 2384 2385 ! PLUS [ shift and go to state 6 ] 2386 ! MINUS [ shift and go to state 5 ] 2387 ! TIMES [ shift and go to state 4 ] 2388 ! DIVIDE [ shift and go to state 7 ] 2389 2390state 13 2391 2392 expression -> LPAREN expression RPAREN . 2393 2394 $ reduce using rule 6 2395 PLUS reduce using rule 6 2396 MINUS reduce using rule 6 2397 TIMES reduce using rule 6 2398 DIVIDE reduce using rule 6 2399 RPAREN reduce using rule 6 2400</pre> 2401</blockquote> 2402 2403The different states that appear in this file are a representation of 2404every possible sequence of valid input tokens allowed by the grammar. 2405When receiving input tokens, the parser is building up a stack and 2406looking for matching rules. Each state keeps track of the grammar 2407rules that might be in the process of being matched at that point. Within each 2408rule, the "." character indicates the current location of the parse 2409within that rule. In addition, the actions for each valid input token 2410are listed. When a shift/reduce or reduce/reduce conflict arises, 2411rules <em>not</em> selected are prefixed with an !. For example: 2412 2413<blockquote> 2414<pre> 2415 ! TIMES [ reduce using rule 2 ] 2416 ! DIVIDE [ reduce using rule 2 ] 2417 ! PLUS [ shift and go to state 6 ] 2418 ! MINUS [ shift and go to state 5 ] 2419</pre> 2420</blockquote> 2421 2422By looking at these rules (and with a little practice), you can usually track down the source 2423of most parsing conflicts. It should also be stressed that not all shift-reduce conflicts are 2424bad. However, the only way to be sure that they are resolved correctly is to look at <tt>parser.out</tt>. 2425 2426<H3><a name="ply_nn29"></a>6.8 Syntax Error Handling</H3> 2427 2428 2429If you are creating a parser for production use, the handling of 2430syntax errors is important. As a general rule, you don't want a 2431parser to simply throw up its hands and stop at the first sign of 2432trouble. Instead, you want it to report the error, recover if possible, and 2433continue parsing so that all of the errors in the input get reported 2434to the user at once. This is the standard behavior found in compilers 2435for languages such as C, C++, and Java. 2436 2437In PLY, when a syntax error occurs during parsing, the error is immediately 2438detected (i.e., the parser does not read any more tokens beyond the 2439source of the error). However, at this point, the parser enters a 2440recovery mode that can be used to try and continue further parsing. 2441As a general rule, error recovery in LR parsers is a delicate 2442topic that involves ancient rituals and black-magic. The recovery mechanism 2443provided by <tt>yacc.py</tt> is comparable to Unix yacc so you may want 2444consult a book like O'Reilly's "Lex and Yacc" for some of the finer details. 2445 2446<p> 2447When a syntax error occurs, <tt>yacc.py</tt> performs the following steps: 2448 2449<ol> 2450<li>On the first occurrence of an error, the user-defined <tt>p_error()</tt> function 2451is called with the offending token as an argument. However, if the syntax error is due to 2452reaching the end-of-file, <tt>p_error()</tt> is called with an argument of <tt>None</tt>. 2453Afterwards, the parser enters 2454an "error-recovery" mode in which it will not make future calls to <tt>p_error()</tt> until it 2455has successfully shifted at least 3 tokens onto the parsing stack. 2456 2457<p> 2458<li>If no recovery action is taken in <tt>p_error()</tt>, the offending lookahead token is replaced 2459with a special <tt>error</tt> token. 2460 2461<p> 2462<li>If the offending lookahead token is already set to <tt>error</tt>, the top item of the parsing stack is 2463deleted. 2464 2465<p> 2466<li>If the entire parsing stack is unwound, the parser enters a restart state and attempts to start 2467parsing from its initial state. 2468 2469<p> 2470<li>If a grammar rule accepts <tt>error</tt> as a token, it will be 2471shifted onto the parsing stack. 2472 2473<p> 2474<li>If the top item of the parsing stack is <tt>error</tt>, lookahead tokens will be discarded until the 2475parser can successfully shift a new symbol or reduce a rule involving <tt>error</tt>. 2476</ol> 2477 2478<H4><a name="ply_nn30"></a>6.8.1 Recovery and resynchronization with error rules</H4> 2479 2480 2481The most well-behaved approach for handling syntax errors is to write grammar rules that include the <tt>error</tt> 2482token. For example, suppose your language had a grammar rule for a print statement like this: 2483 2484<blockquote> 2485<pre> 2486def p_statement_print(p): 2487 'statement : PRINT expr SEMI' 2488 ... 2489</pre> 2490</blockquote> 2491 2492To account for the possibility of a bad expression, you might write an additional grammar rule like this: 2493 2494<blockquote> 2495<pre> 2496def p_statement_print_error(p): 2497 'statement : PRINT error SEMI' 2498 print "Syntax error in print statement. Bad expression" 2499 2500</pre> 2501</blockquote> 2502 2503In this case, the <tt>error</tt> token will match any sequence of 2504tokens that might appear up to the first semicolon that is 2505encountered. Once the semicolon is reached, the rule will be 2506invoked and the <tt>error</tt> token will go away. 2507 2508<p> 2509This type of recovery is sometimes known as parser resynchronization. 2510The <tt>error</tt> token acts as a wildcard for any bad input text and 2511the token immediately following <tt>error</tt> acts as a 2512synchronization token. 2513 2514<p> 2515It is important to note that the <tt>error</tt> token usually does not appear as the last token 2516on the right in an error rule. For example: 2517 2518<blockquote> 2519<pre> 2520def p_statement_print_error(p): 2521 'statement : PRINT error' 2522 print "Syntax error in print statement. Bad expression" 2523</pre> 2524</blockquote> 2525 2526This is because the first bad token encountered will cause the rule to 2527be reduced--which may make it difficult to recover if more bad tokens 2528immediately follow. 2529 2530<H4><a name="ply_nn31"></a>6.8.2 Panic mode recovery</H4> 2531 2532 2533An alternative error recovery scheme is to enter a panic mode recovery in which tokens are 2534discarded to a point where the parser might be able to recover in some sensible manner. 2535 2536<p> 2537Panic mode recovery is implemented entirely in the <tt>p_error()</tt> function. For example, this 2538function starts discarding tokens until it reaches a closing '}'. Then, it restarts the 2539parser in its initial state. 2540 2541<blockquote> 2542<pre> 2543def p_error(p): 2544 print "Whoa. You are seriously hosed." 2545 # Read ahead looking for a closing '}' 2546 while 1: 2547 tok = yacc.token() # Get the next token 2548 if not tok or tok.type == 'RBRACE': break 2549 yacc.restart() 2550</pre> 2551</blockquote> 2552 2553<p> 2554This function simply discards the bad token and tells the parser that the error was ok. 2555 2556<blockquote> 2557<pre> 2558def p_error(p): 2559 print "Syntax error at token", p.type 2560 # Just discard the token and tell the parser it's okay. 2561 yacc.errok() 2562</pre> 2563</blockquote> 2564 2565<P> 2566Within the <tt>p_error()</tt> function, three functions are available to control the behavior 2567of the parser: 2568<p> 2569<ul> 2570<li><tt>yacc.errok()</tt>. This resets the parser state so it doesn't think it's in error-recovery 2571mode. This will prevent an <tt>error</tt> token from being generated and will reset the internal 2572error counters so that the next syntax error will call <tt>p_error()</tt> again. 2573 2574<p> 2575<li><tt>yacc.token()</tt>. This returns the next token on the input stream. 2576 2577<p> 2578<li><tt>yacc.restart()</tt>. This discards the entire parsing stack and resets the parser 2579to its initial state. 2580</ul> 2581 2582Note: these functions are only available when invoking <tt>p_error()</tt> and are not available 2583at any other time. 2584 2585<p> 2586To supply the next lookahead token to the parser, <tt>p_error()</tt> can return a token. This might be 2587useful if trying to synchronize on special characters. For example: 2588 2589<blockquote> 2590<pre> 2591def p_error(p): 2592 # Read ahead looking for a terminating ";" 2593 while 1: 2594 tok = yacc.token() # Get the next token 2595 if not tok or tok.type == 'SEMI': break 2596 yacc.errok() 2597 2598 # Return SEMI to the parser as the next lookahead token 2599 return tok 2600</pre> 2601</blockquote> 2602 2603<H4><a name="ply_nn35"></a>6.8.3 Signaling an error from a production</H4> 2604 2605 2606If necessary, a production rule can manually force the parser to enter error recovery. This 2607is done by raising the <tt>SyntaxError</tt> exception like this: 2608 2609<blockquote> 2610<pre> 2611def p_production(p): 2612 'production : some production ...' 2613 raise SyntaxError 2614</pre> 2615</blockquote> 2616 2617The effect of raising <tt>SyntaxError</tt> is the same as if the last symbol shifted onto the 2618parsing stack was actually a syntax error. Thus, when you do this, the last symbol shifted is popped off 2619of the parsing stack and the current lookahead token is set to an <tt>error</tt> token. The parser 2620then enters error-recovery mode where it tries to reduce rules that can accept <tt>error</tt> tokens. 2621The steps that follow from this point are exactly the same as if a syntax error were detected and 2622<tt>p_error()</tt> were called. 2623 2624<P> 2625One important aspect of manually setting an error is that the <tt>p_error()</tt> function will <b>NOT</b> be 2626called in this case. If you need to issue an error message, make sure you do it in the production that 2627raises <tt>SyntaxError</tt>. 2628 2629<P> 2630Note: This feature of PLY is meant to mimic the behavior of the YYERROR macro in yacc. 2631 2632 2633<H4><a name="ply_nn32"></a>6.8.4 General comments on error handling</H4> 2634 2635 2636For normal types of languages, error recovery with error rules and resynchronization characters is probably the most reliable 2637technique. This is because you can instrument the grammar to catch errors at selected places where it is relatively easy 2638to recover and continue parsing. Panic mode recovery is really only useful in certain specialized applications where you might want 2639to discard huge portions of the input text to find a valid restart point. 2640 2641<H3><a name="ply_nn33"></a>6.9 Line Number and Position Tracking</H3> 2642 2643 2644Position tracking is often a tricky problem when writing compilers. 2645By default, PLY tracks the line number and position of all tokens. 2646This information is available using the following functions: 2647 2648<ul> 2649<li><tt>p.lineno(num)</tt>. Return the line number for symbol <em>num</em> 2650<li><tt>p.lexpos(num)</tt>. Return the lexing position for symbol <em>num</em> 2651</ul> 2652 2653For example: 2654 2655<blockquote> 2656<pre> 2657def p_expression(p): 2658 'expression : expression PLUS expression' 2659 line = p.lineno(2) # line number of the PLUS token 2660 index = p.lexpos(2) # Position of the PLUS token 2661</pre> 2662</blockquote> 2663 2664As an optional feature, <tt>yacc.py</tt> can automatically track line 2665numbers and positions for all of the grammar symbols as well. 2666However, this extra tracking requires extra processing and can 2667significantly slow down parsing. Therefore, it must be enabled by 2668passing the 2669<tt>tracking=True</tt> option to <tt>yacc.parse()</tt>. For example: 2670 2671<blockquote> 2672<pre> 2673yacc.parse(data,tracking=True) 2674</pre> 2675</blockquote> 2676 2677Once enabled, the <tt>lineno()</tt> and <tt>lexpos()</tt> methods work 2678for all grammar symbols. In addition, two additional methods can be 2679used: 2680 2681<ul> 2682<li><tt>p.linespan(num)</tt>. Return a tuple (startline,endline) with the starting and ending line number for symbol <em>num</em>. 2683<li><tt>p.lexspan(num)</tt>. Return a tuple (start,end) with the starting and ending positions for symbol <em>num</em>. 2684</ul> 2685 2686For example: 2687 2688<blockquote> 2689<pre> 2690def p_expression(p): 2691 'expression : expression PLUS expression' 2692 p.lineno(1) # Line number of the left expression 2693 p.lineno(2) # line number of the PLUS operator 2694 p.lineno(3) # line number of the right expression 2695 ... 2696 start,end = p.linespan(3) # Start,end lines of the right expression 2697 starti,endi = p.lexspan(3) # Start,end positions of right expression 2698 2699</pre> 2700</blockquote> 2701 2702Note: The <tt>lexspan()</tt> function only returns the range of values up to the start of the last grammar symbol. 2703 2704<p> 2705Although it may be convenient for PLY to track position information on 2706all grammar symbols, this is often unnecessary. For example, if you 2707are merely using line number information in an error message, you can 2708often just key off of a specific token in the grammar rule. For 2709example: 2710 2711<blockquote> 2712<pre> 2713def p_bad_func(p): 2714 'funccall : fname LPAREN error RPAREN' 2715 # Line number reported from LPAREN token 2716 print "Bad function call at line", p.lineno(2) 2717</pre> 2718</blockquote> 2719 2720<p> 2721Similarly, you may get better parsing performance if you only 2722selectively propagate line number information where it's needed using 2723the <tt>p.set_lineno()</tt> method. For example: 2724 2725<blockquote> 2726<pre> 2727def p_fname(p): 2728 'fname : ID' 2729 p[0] = p[1] 2730 p.set_lineno(0,p.lineno(1)) 2731</pre> 2732</blockquote> 2733 2734PLY doesn't retain line number information from rules that have already been 2735parsed. If you are building an abstract syntax tree and need to have line numbers, 2736you should make sure that the line numbers appear in the tree itself. 2737 2738<H3><a name="ply_nn34"></a>6.10 AST Construction</H3> 2739 2740 2741<tt>yacc.py</tt> provides no special functions for constructing an 2742abstract syntax tree. However, such construction is easy enough to do 2743on your own. 2744 2745<p>A minimal way to construct a tree is to simply create and 2746propagate a tuple or list in each grammar rule function. There 2747are many possible ways to do this, but one example would be something 2748like this: 2749 2750<blockquote> 2751<pre> 2752def p_expression_binop(p): 2753 '''expression : expression PLUS expression 2754 | expression MINUS expression 2755 | expression TIMES expression 2756 | expression DIVIDE expression''' 2757 2758 p[0] = ('binary-expression',p[2],p[1],p[3]) 2759 2760def p_expression_group(p): 2761 'expression : LPAREN expression RPAREN' 2762 p[0] = ('group-expression',p[2]) 2763 2764def p_expression_number(p): 2765 'expression : NUMBER' 2766 p[0] = ('number-expression',p[1]) 2767</pre> 2768</blockquote> 2769 2770<p> 2771Another approach is to create a set of data structure for different 2772kinds of abstract syntax tree nodes and assign nodes to <tt>p[0]</tt> 2773in each rule. For example: 2774 2775<blockquote> 2776<pre> 2777class Expr: pass 2778 2779class BinOp(Expr): 2780 def __init__(self,left,op,right): 2781 self.type = "binop" 2782 self.left = left 2783 self.right = right 2784 self.op = op 2785 2786class Number(Expr): 2787 def __init__(self,value): 2788 self.type = "number" 2789 self.value = value 2790 2791def p_expression_binop(p): 2792 '''expression : expression PLUS expression 2793 | expression MINUS expression 2794 | expression TIMES expression 2795 | expression DIVIDE expression''' 2796 2797 p[0] = BinOp(p[1],p[2],p[3]) 2798 2799def p_expression_group(p): 2800 'expression : LPAREN expression RPAREN' 2801 p[0] = p[2] 2802 2803def p_expression_number(p): 2804 'expression : NUMBER' 2805 p[0] = Number(p[1]) 2806</pre> 2807</blockquote> 2808 2809The advantage to this approach is that it may make it easier to attach more complicated 2810semantics, type checking, code generation, and other features to the node classes. 2811 2812<p> 2813To simplify tree traversal, it may make sense to pick a very generic 2814tree structure for your parse tree nodes. For example: 2815 2816<blockquote> 2817<pre> 2818class Node: 2819 def __init__(self,type,children=None,leaf=None): 2820 self.type = type 2821 if children: 2822 self.children = children 2823 else: 2824 self.children = [ ] 2825 self.leaf = leaf 2826 2827def p_expression_binop(p): 2828 '''expression : expression PLUS expression 2829 | expression MINUS expression 2830 | expression TIMES expression 2831 | expression DIVIDE expression''' 2832 2833 p[0] = Node("binop", [p[1],p[3]], p[2]) 2834</pre> 2835</blockquote> 2836 2837<H3><a name="ply_nn35"></a>6.11 Embedded Actions</H3> 2838 2839 2840The parsing technique used by yacc only allows actions to be executed at the end of a rule. For example, 2841suppose you have a rule like this: 2842 2843<blockquote> 2844<pre> 2845def p_foo(p): 2846 "foo : A B C D" 2847 print "Parsed a foo", p[1],p[2],p[3],p[4] 2848</pre> 2849</blockquote> 2850 2851<p> 2852In this case, the supplied action code only executes after all of the 2853symbols <tt>A</tt>, <tt>B</tt>, <tt>C</tt>, and <tt>D</tt> have been 2854parsed. Sometimes, however, it is useful to execute small code 2855fragments during intermediate stages of parsing. For example, suppose 2856you wanted to perform some action immediately after <tt>A</tt> has 2857been parsed. To do this, write an empty rule like this: 2858 2859<blockquote> 2860<pre> 2861def p_foo(p): 2862 "foo : A seen_A B C D" 2863 print "Parsed a foo", p[1],p[3],p[4],p[5] 2864 print "seen_A returned", p[2] 2865 2866def p_seen_A(p): 2867 "seen_A :" 2868 print "Saw an A = ", p[-1] # Access grammar symbol to left 2869 p[0] = some_value # Assign value to seen_A 2870 2871</pre> 2872</blockquote> 2873 2874<p> 2875In this example, the empty <tt>seen_A</tt> rule executes immediately 2876after <tt>A</tt> is shifted onto the parsing stack. Within this 2877rule, <tt>p[-1]</tt> refers to the symbol on the stack that appears 2878immediately to the left of the <tt>seen_A</tt> symbol. In this case, 2879it would be the value of <tt>A</tt> in the <tt>foo</tt> rule 2880immediately above. Like other rules, a value can be returned from an 2881embedded action by simply assigning it to <tt>p[0]</tt> 2882 2883<p> 2884The use of embedded actions can sometimes introduce extra shift/reduce conflicts. For example, 2885this grammar has no conflicts: 2886 2887<blockquote> 2888<pre> 2889def p_foo(p): 2890 """foo : abcd 2891 | abcx""" 2892 2893def p_abcd(p): 2894 "abcd : A B C D" 2895 2896def p_abcx(p): 2897 "abcx : A B C X" 2898</pre> 2899</blockquote> 2900 2901However, if you insert an embedded action into one of the rules like this, 2902 2903<blockquote> 2904<pre> 2905def p_foo(p): 2906 """foo : abcd 2907 | abcx""" 2908 2909def p_abcd(p): 2910 "abcd : A B C D" 2911 2912def p_abcx(p): 2913 "abcx : A B seen_AB C X" 2914 2915def p_seen_AB(p): 2916 "seen_AB :" 2917</pre> 2918</blockquote> 2919 2920an extra shift-reduce conflict will be introduced. This conflict is 2921caused by the fact that the same symbol <tt>C</tt> appears next in 2922both the <tt>abcd</tt> and <tt>abcx</tt> rules. The parser can either 2923shift the symbol (<tt>abcd</tt> rule) or reduce the empty 2924rule <tt>seen_AB</tt> (<tt>abcx</tt> rule). 2925 2926<p> 2927A common use of embedded rules is to control other aspects of parsing 2928such as scoping of local variables. For example, if you were parsing C code, you might 2929write code like this: 2930 2931<blockquote> 2932<pre> 2933def p_statements_block(p): 2934 "statements: LBRACE new_scope statements RBRACE""" 2935 # Action code 2936 ... 2937 pop_scope() # Return to previous scope 2938 2939def p_new_scope(p): 2940 "new_scope :" 2941 # Create a new scope for local variables 2942 s = new_scope() 2943 push_scope(s) 2944 ... 2945</pre> 2946</blockquote> 2947 2948In this case, the embedded action <tt>new_scope</tt> executes 2949immediately after a <tt>LBRACE</tt> (<tt>{</tt>) symbol is parsed. 2950This might adjust internal symbol tables and other aspects of the 2951parser. Upon completion of the rule <tt>statements_block</tt>, code 2952might undo the operations performed in the embedded action 2953(e.g., <tt>pop_scope()</tt>). 2954 2955<H3><a name="ply_nn36"></a>6.12 Miscellaneous Yacc Notes</H3> 2956 2957 2958<ul> 2959<li>The default parsing method is LALR. To use SLR instead, run yacc() as follows: 2960 2961<blockquote> 2962<pre> 2963yacc.yacc(method="SLR") 2964</pre> 2965</blockquote> 2966Note: LALR table generation takes approximately twice as long as SLR table generation. There is no 2967difference in actual parsing performance---the same code is used in both cases. LALR is preferred when working 2968with more complicated grammars since it is more powerful. 2969 2970<p> 2971 2972<li>By default, <tt>yacc.py</tt> relies on <tt>lex.py</tt> for tokenizing. However, an alternative tokenizer 2973can be supplied as follows: 2974 2975<blockquote> 2976<pre> 2977yacc.parse(lexer=x) 2978</pre> 2979</blockquote> 2980in this case, <tt>x</tt> must be a Lexer object that minimally has a <tt>x.token()</tt> method for retrieving the next 2981token. If an input string is given to <tt>yacc.parse()</tt>, the lexer must also have an <tt>x.input()</tt> method. 2982 2983<p> 2984<li>By default, the yacc generates tables in debugging mode (which produces the parser.out file and other output). 2985To disable this, use 2986 2987<blockquote> 2988<pre> 2989yacc.yacc(debug=0) 2990</pre> 2991</blockquote> 2992 2993<p> 2994<li>To change the name of the <tt>parsetab.py</tt> file, use: 2995 2996<blockquote> 2997<pre> 2998yacc.yacc(tabmodule="foo") 2999</pre> 3000</blockquote> 3001 3002<p> 3003<li>To change the directory in which the <tt>parsetab.py</tt> file (and other output files) are written, use: 3004<blockquote> 3005<pre> 3006yacc.yacc(tabmodule="foo",outputdir="somedirectory") 3007</pre> 3008</blockquote> 3009 3010<p> 3011<li>To prevent yacc from generating any kind of parser table file, use: 3012<blockquote> 3013<pre> 3014yacc.yacc(write_tables=0) 3015</pre> 3016</blockquote> 3017 3018Note: If you disable table generation, yacc() will regenerate the parsing tables 3019each time it runs (which may take awhile depending on how large your grammar is). 3020 3021<P> 3022<li>To print copious amounts of debugging during parsing, use: 3023 3024<blockquote> 3025<pre> 3026yacc.parse(debug=1) 3027</pre> 3028</blockquote> 3029 3030<p> 3031<li>The <tt>yacc.yacc()</tt> function really returns a parser object. If you want to support multiple 3032parsers in the same application, do this: 3033 3034<blockquote> 3035<pre> 3036p = yacc.yacc() 3037... 3038p.parse() 3039</pre> 3040</blockquote> 3041 3042Note: The function <tt>yacc.parse()</tt> is bound to the last parser that was generated. 3043 3044<p> 3045<li>Since the generation of the LALR tables is relatively expensive, previously generated tables are 3046cached and reused if possible. The decision to regenerate the tables is determined by taking an MD5 3047checksum of all grammar rules and precedence rules. Only in the event of a mismatch are the tables regenerated. 3048 3049<p> 3050It should be noted that table generation is reasonably efficient, even for grammars that involve around a 100 rules 3051and several hundred states. For more complex languages such as C, table generation may take 30-60 seconds on a slow 3052machine. Please be patient. 3053 3054<p> 3055<li>Since LR parsing is driven by tables, the performance of the parser is largely independent of the 3056size of the grammar. The biggest bottlenecks will be the lexer and the complexity of the code in your grammar rules. 3057</ul> 3058 3059<H2><a name="ply_nn37"></a>7. Multiple Parsers and Lexers</H2> 3060 3061 3062In advanced parsing applications, you may want to have multiple 3063parsers and lexers. 3064 3065<p> 3066As a general rules this isn't a problem. However, to make it work, 3067you need to carefully make sure everything gets hooked up correctly. 3068First, make sure you save the objects returned by <tt>lex()</tt> and 3069<tt>yacc()</tt>. For example: 3070 3071<blockquote> 3072<pre> 3073lexer = lex.lex() # Return lexer object 3074parser = yacc.yacc() # Return parser object 3075</pre> 3076</blockquote> 3077 3078Next, when parsing, make sure you give the <tt>parse()</tt> function a reference to the lexer it 3079should be using. For example: 3080 3081<blockquote> 3082<pre> 3083parser.parse(text,lexer=lexer) 3084</pre> 3085</blockquote> 3086 3087If you forget to do this, the parser will use the last lexer 3088created--which is not always what you want. 3089 3090<p> 3091Within lexer and parser rule functions, these objects are also 3092available. In the lexer, the "lexer" attribute of a token refers to 3093the lexer object that triggered the rule. For example: 3094 3095<blockquote> 3096<pre> 3097def t_NUMBER(t): 3098 r'\d+' 3099 ... 3100 print t.lexer # Show lexer object 3101</pre> 3102</blockquote> 3103 3104In the parser, the "lexer" and "parser" attributes refer to the lexer 3105and parser objects respectively. 3106 3107<blockquote> 3108<pre> 3109def p_expr_plus(p): 3110 'expr : expr PLUS expr' 3111 ... 3112 print p.parser # Show parser object 3113 print p.lexer # Show lexer object 3114</pre> 3115</blockquote> 3116 3117If necessary, arbitrary attributes can be attached to the lexer or parser object. 3118For example, if you wanted to have different parsing modes, you could attach a mode 3119attribute to the parser object and look at it later. 3120 3121<H2><a name="ply_nn38"></a>8. Using Python's Optimized Mode</H2> 3122 3123 3124Because PLY uses information from doc-strings, parsing and lexing 3125information must be gathered while running the Python interpreter in 3126normal mode (i.e., not with the -O or -OO options). However, if you 3127specify optimized mode like this: 3128 3129<blockquote> 3130<pre> 3131lex.lex(optimize=1) 3132yacc.yacc(optimize=1) 3133</pre> 3134</blockquote> 3135 3136then PLY can later be used when Python runs in optimized mode. To make this work, 3137make sure you first run Python in normal mode. Once the lexing and parsing tables 3138have been generated the first time, run Python in optimized mode. PLY will use 3139the tables without the need for doc strings. 3140 3141<p> 3142Beware: running PLY in optimized mode disables a lot of error 3143checking. You should only do this when your project has stabilized 3144and you don't need to do any debugging. One of the purposes of 3145optimized mode is to substantially decrease the startup time of 3146your compiler (by assuming that everything is already properly 3147specified and works). 3148 3149<H2><a name="ply_nn44"></a>9. Advanced Debugging</H2> 3150 3151 3152<p> 3153Debugging a compiler is typically not an easy task. PLY provides some 3154advanced diagonistic capabilities through the use of Python's 3155<tt>logging</tt> module. The next two sections describe this: 3156 3157<H3><a name="ply_nn45"></a>9.1 Debugging the lex() and yacc() commands</H3> 3158 3159 3160<p> 3161Both the <tt>lex()</tt> and <tt>yacc()</tt> commands have a debugging 3162mode that can be enabled using the <tt>debug</tt> flag. For example: 3163 3164<blockquote> 3165<pre> 3166lex.lex(debug=True) 3167yacc.yacc(debug=True) 3168</pre> 3169</blockquote> 3170 3171Normally, the output produced by debugging is routed to either 3172standard error or, in the case of <tt>yacc()</tt>, to a file 3173<tt>parser.out</tt>. This output can be more carefully controlled 3174by supplying a logging object. Here is an example that adds 3175information about where different debugging messages are coming from: 3176 3177<blockquote> 3178<pre> 3179# Set up a logging object 3180import logging 3181logging.basicConfig( 3182 level = logging.DEBUG, 3183 filename = "parselog.txt", 3184 filemode = "w", 3185 format = "%(filename)10s:%(lineno)4d:%(message)s" 3186) 3187log = logging.getLogger() 3188 3189lex.lex(debug=True,debuglog=log) 3190yacc.yacc(debug=True,debuglog=log) 3191</pre> 3192</blockquote> 3193 3194If you supply a custom logger, the amount of debugging 3195information produced can be controlled by setting the logging level. 3196Typically, debugging messages are either issued at the <tt>DEBUG</tt>, 3197<tt>INFO</tt>, or <tt>WARNING</tt> levels. 3198 3199<p> 3200PLY's error messages and warnings are also produced using the logging 3201interface. This can be controlled by passing a logging object 3202using the <tt>errorlog</tt> parameter. 3203 3204<blockquote> 3205<pre> 3206lex.lex(errorlog=log) 3207yacc.yacc(errorlog=log) 3208</pre> 3209</blockquote> 3210 3211If you want to completely silence warnings, you can either pass in a 3212logging object with an appropriate filter level or use the <tt>NullLogger</tt> 3213object defined in either <tt>lex</tt> or <tt>yacc</tt>. For example: 3214 3215<blockquote> 3216<pre> 3217yacc.yacc(errorlog=yacc.NullLogger()) 3218</pre> 3219</blockquote> 3220 3221<H3><a name="ply_nn46"></a>9.2 Run-time Debugging</H3> 3222 3223 3224<p> 3225To enable run-time debugging of a parser, use the <tt>debug</tt> option to parse. This 3226option can either be an integer (which simply turns debugging on or off) or an instance 3227of a logger object. For example: 3228 3229<blockquote> 3230<pre> 3231log = logging.getLogger() 3232parser.parse(input,debug=log) 3233</pre> 3234</blockquote> 3235 3236If a logging object is passed, you can use its filtering level to control how much 3237output gets generated. The <tt>INFO</tt> level is used to produce information 3238about rule reductions. The <tt>DEBUG</tt> level will show information about the 3239parsing stack, token shifts, and other details. The <tt>ERROR</tt> level shows information 3240related to parsing errors. 3241 3242<p> 3243For very complicated problems, you should pass in a logging object that 3244redirects to a file where you can more easily inspect the output after 3245execution. 3246 3247<H2><a name="ply_nn39"></a>10. Where to go from here?</H2> 3248 3249 3250The <tt>examples</tt> directory of the PLY distribution contains several simple examples. Please consult a 3251compilers textbook for the theory and underlying implementation details or LR parsing. 3252 3253</body> 3254</html> 3255 3256 3257 3258 3259 3260 3261 3262