ply.html revision 6498
12632Sstever@eecs.umich.edu<html> 22632Sstever@eecs.umich.edu<head> 32632Sstever@eecs.umich.edu<title>PLY (Python Lex-Yacc)</title> 42632Sstever@eecs.umich.edu</head> 52632Sstever@eecs.umich.edu<body bgcolor="#ffffff"> 62632Sstever@eecs.umich.edu 72632Sstever@eecs.umich.edu<h1>PLY (Python Lex-Yacc)</h1> 84479Sbinkertn@umich.edu 92632Sstever@eecs.umich.edu<b> 102632Sstever@eecs.umich.eduDavid M. Beazley <br> 114479Sbinkertn@umich.edudave@dabeaz.com<br> 122632Sstever@eecs.umich.edu</b> 132632Sstever@eecs.umich.edu 142632Sstever@eecs.umich.edu<p> 156498Snate@binkert.org<b>PLY Version: 3.0</b> 162632Sstever@eecs.umich.edu<p> 174479Sbinkertn@umich.edu 184479Sbinkertn@umich.edu<!-- INDEX --> 194479Sbinkertn@umich.edu<div class="sectiontoc"> 204479Sbinkertn@umich.edu<ul> 216498Snate@binkert.org<li><a href="#ply_nn1">Preface and Requirements</a> 224479Sbinkertn@umich.edu<li><a href="#ply_nn1">Introduction</a> 234479Sbinkertn@umich.edu<li><a href="#ply_nn2">PLY Overview</a> 244479Sbinkertn@umich.edu<li><a href="#ply_nn3">Lex</a> 254479Sbinkertn@umich.edu<ul> 264479Sbinkertn@umich.edu<li><a href="#ply_nn4">Lex Example</a> 274479Sbinkertn@umich.edu<li><a href="#ply_nn5">The tokens list</a> 284479Sbinkertn@umich.edu<li><a href="#ply_nn6">Specification of tokens</a> 294479Sbinkertn@umich.edu<li><a href="#ply_nn7">Token values</a> 304479Sbinkertn@umich.edu<li><a href="#ply_nn8">Discarded tokens</a> 314479Sbinkertn@umich.edu<li><a href="#ply_nn9">Line numbers and positional information</a> 324479Sbinkertn@umich.edu<li><a href="#ply_nn10">Ignored characters</a> 334479Sbinkertn@umich.edu<li><a href="#ply_nn11">Literal characters</a> 344479Sbinkertn@umich.edu<li><a href="#ply_nn12">Error handling</a> 354479Sbinkertn@umich.edu<li><a href="#ply_nn13">Building and using the lexer</a> 364479Sbinkertn@umich.edu<li><a href="#ply_nn14">The @TOKEN decorator</a> 374479Sbinkertn@umich.edu<li><a href="#ply_nn15">Optimized mode</a> 384479Sbinkertn@umich.edu<li><a href="#ply_nn16">Debugging</a> 394479Sbinkertn@umich.edu<li><a href="#ply_nn17">Alternative specification of lexers</a> 404479Sbinkertn@umich.edu<li><a href="#ply_nn18">Maintaining state</a> 416498Snate@binkert.org<li><a href="#ply_nn19">Lexer cloning</a> 424479Sbinkertn@umich.edu<li><a href="#ply_nn20">Internal lexer state</a> 434479Sbinkertn@umich.edu<li><a href="#ply_nn21">Conditional lexing and start conditions</a> 444479Sbinkertn@umich.edu<li><a href="#ply_nn21">Miscellaneous Issues</a> 454479Sbinkertn@umich.edu</ul> 464479Sbinkertn@umich.edu<li><a href="#ply_nn22">Parsing basics</a> 476498Snate@binkert.org<li><a href="#ply_nn23">Yacc</a> 484479Sbinkertn@umich.edu<ul> 494479Sbinkertn@umich.edu<li><a href="#ply_nn24">An example</a> 504479Sbinkertn@umich.edu<li><a href="#ply_nn25">Combining Grammar Rule Functions</a> 514479Sbinkertn@umich.edu<li><a href="#ply_nn26">Character Literals</a> 524479Sbinkertn@umich.edu<li><a href="#ply_nn26">Empty Productions</a> 534479Sbinkertn@umich.edu<li><a href="#ply_nn28">Changing the starting symbol</a> 544479Sbinkertn@umich.edu<li><a href="#ply_nn27">Dealing With Ambiguous Grammars</a> 554479Sbinkertn@umich.edu<li><a href="#ply_nn28">The parser.out file</a> 564479Sbinkertn@umich.edu<li><a href="#ply_nn29">Syntax Error Handling</a> 574479Sbinkertn@umich.edu<ul> 584479Sbinkertn@umich.edu<li><a href="#ply_nn30">Recovery and resynchronization with error rules</a> 594479Sbinkertn@umich.edu<li><a href="#ply_nn31">Panic mode recovery</a> 606498Snate@binkert.org<li><a href="#ply_nn35">Signaling an error from a production</a> 614479Sbinkertn@umich.edu<li><a href="#ply_nn32">General comments on error handling</a> 624479Sbinkertn@umich.edu</ul> 634479Sbinkertn@umich.edu<li><a href="#ply_nn33">Line Number and Position Tracking</a> 644479Sbinkertn@umich.edu<li><a href="#ply_nn34">AST Construction</a> 654479Sbinkertn@umich.edu<li><a href="#ply_nn35">Embedded Actions</a> 666498Snate@binkert.org<li><a href="#ply_nn36">Miscellaneous Yacc Notes</a> 674479Sbinkertn@umich.edu</ul> 686498Snate@binkert.org<li><a href="#ply_nn37">Multiple Parsers and Lexers</a> 694479Sbinkertn@umich.edu<li><a href="#ply_nn38">Using Python's Optimized Mode</a> 706498Snate@binkert.org<li><a href="#ply_nn44">Advanced Debugging</a> 716498Snate@binkert.org<ul> 726498Snate@binkert.org<li><a href="#ply_nn45">Debugging the lex() and yacc() commands</a> 736498Snate@binkert.org<li><a href="#ply_nn46">Run-time Debugging</a> 746498Snate@binkert.org</ul> 754479Sbinkertn@umich.edu<li><a href="#ply_nn39">Where to go from here?</a> 764479Sbinkertn@umich.edu</ul> 774479Sbinkertn@umich.edu</div> 784479Sbinkertn@umich.edu<!-- INDEX --> 794479Sbinkertn@umich.edu 804479Sbinkertn@umich.edu 814479Sbinkertn@umich.edu 826498Snate@binkert.org<H2><a name="ply_nn1"></a>1. Preface and Requirements</H2> 836498Snate@binkert.org 846498Snate@binkert.org 856498Snate@binkert.org<p> 866498Snate@binkert.orgThis document provides an overview of lexing and parsing with PLY. 876498Snate@binkert.orgGiven the intrinsic complexity of parsing, I would strongly advise 886498Snate@binkert.orgthat you read (or at least skim) this entire document before jumping 896498Snate@binkert.orginto a big development project with PLY. 906498Snate@binkert.org</p> 916498Snate@binkert.org 926498Snate@binkert.org<p> 936498Snate@binkert.orgPLY-3.0 is compatible with both Python 2 and Python 3. Be aware that 946498Snate@binkert.orgPython 3 support is new and has not been extensively tested (although 956498Snate@binkert.orgall of the examples and unit tests pass under Python 3.0). If you are 966498Snate@binkert.orgusing Python 2, you should try to use Python 2.4 or newer. Although PLY 976498Snate@binkert.orgworks with versions as far back as Python 2.2, some of its optional features 986498Snate@binkert.orgrequire more modern library modules. 996498Snate@binkert.org</p> 1006498Snate@binkert.org 1016498Snate@binkert.org<H2><a name="ply_nn1"></a>2. Introduction</H2> 1024479Sbinkertn@umich.edu 1034479Sbinkertn@umich.edu 1044479Sbinkertn@umich.eduPLY is a pure-Python implementation of the popular compiler 1054479Sbinkertn@umich.educonstruction tools lex and yacc. The main goal of PLY is to stay 1064479Sbinkertn@umich.edufairly faithful to the way in which traditional lex/yacc tools work. 1074479Sbinkertn@umich.eduThis includes supporting LALR(1) parsing as well as providing 1084479Sbinkertn@umich.eduextensive input validation, error reporting, and diagnostics. Thus, 1094479Sbinkertn@umich.eduif you've used yacc in another programming language, it should be 1104479Sbinkertn@umich.edurelatively straightforward to use PLY. 1114479Sbinkertn@umich.edu 1124479Sbinkertn@umich.edu<p> 1134479Sbinkertn@umich.eduEarly versions of PLY were developed to support an Introduction to 1144479Sbinkertn@umich.eduCompilers Course I taught in 2001 at the University of Chicago. In this course, 1152632Sstever@eecs.umich.edustudents built a fully functional compiler for a simple Pascal-like 1162632Sstever@eecs.umich.edulanguage. Their compiler, implemented entirely in Python, had to 1172632Sstever@eecs.umich.eduinclude lexical analysis, parsing, type checking, type inference, 1182632Sstever@eecs.umich.edunested scoping, and code generation for the SPARC processor. 1192632Sstever@eecs.umich.eduApproximately 30 different compiler implementations were completed in 1204479Sbinkertn@umich.eduthis course. Most of PLY's interface and operation has been influenced by common 1216498Snate@binkert.orgusability problems encountered by students. Since 2001, PLY has 1226498Snate@binkert.orgcontinued to be improved as feedback has been received from users. 1236498Snate@binkert.orgPLY-3.0 represents a major refactoring of the original implementation 1246498Snate@binkert.orgwith an eye towards future enhancements. 1252632Sstever@eecs.umich.edu 1262632Sstever@eecs.umich.edu<p> 1274479Sbinkertn@umich.eduSince PLY was primarily developed as an instructional tool, you will 1284479Sbinkertn@umich.edufind it to be fairly picky about token and grammar rule 1294479Sbinkertn@umich.eduspecification. In part, this 1302632Sstever@eecs.umich.eduadded formality is meant to catch common programming mistakes made by 1312632Sstever@eecs.umich.edunovice users. However, advanced users will also find such features to 1322632Sstever@eecs.umich.edube useful when building complicated grammars for real programming 1334479Sbinkertn@umich.edulanguages. It should also be noted that PLY does not provide much in 1344479Sbinkertn@umich.eduthe way of bells and whistles (e.g., automatic construction of 1354479Sbinkertn@umich.eduabstract syntax trees, tree traversal, etc.). Nor would I consider it 1364479Sbinkertn@umich.eduto be a parsing framework. Instead, you will find a bare-bones, yet 1372632Sstever@eecs.umich.edufully capable lex/yacc implementation written entirely in Python. 1382632Sstever@eecs.umich.edu 1392632Sstever@eecs.umich.edu<p> 1402632Sstever@eecs.umich.eduThe rest of this document assumes that you are somewhat familar with 1414479Sbinkertn@umich.eduparsing theory, syntax directed translation, and the use of compiler 1424479Sbinkertn@umich.educonstruction tools such as lex and yacc in other programming 1434479Sbinkertn@umich.edulanguages. If you are unfamilar with these topics, you will probably 1444479Sbinkertn@umich.eduwant to consult an introductory text such as "Compilers: Principles, 1454479Sbinkertn@umich.eduTechniques, and Tools", by Aho, Sethi, and Ullman. O'Reilly's "Lex 1464479Sbinkertn@umich.eduand Yacc" by John Levine may also be handy. In fact, the O'Reilly book can be 1474479Sbinkertn@umich.eduused as a reference for PLY as the concepts are virtually identical. 1484479Sbinkertn@umich.edu 1496498Snate@binkert.org<H2><a name="ply_nn2"></a>3. PLY Overview</H2> 1504479Sbinkertn@umich.edu 1514479Sbinkertn@umich.edu 1524479Sbinkertn@umich.eduPLY consists of two separate modules; <tt>lex.py</tt> and 1534479Sbinkertn@umich.edu<tt>yacc.py</tt>, both of which are found in a Python package 1544479Sbinkertn@umich.educalled <tt>ply</tt>. The <tt>lex.py</tt> module is used to break input text into a 1552632Sstever@eecs.umich.educollection of tokens specified by a collection of regular expression 1562632Sstever@eecs.umich.edurules. <tt>yacc.py</tt> is used to recognize language syntax that has 1574479Sbinkertn@umich.edubeen specified in the form of a context free grammar. <tt>yacc.py</tt> uses LR parsing and generates its parsing tables 1584479Sbinkertn@umich.eduusing either the LALR(1) (the default) or SLR table generation algorithms. 1592632Sstever@eecs.umich.edu 1602632Sstever@eecs.umich.edu<p> 1612632Sstever@eecs.umich.eduThe two tools are meant to work together. Specifically, 1622632Sstever@eecs.umich.edu<tt>lex.py</tt> provides an external interface in the form of a 1632632Sstever@eecs.umich.edu<tt>token()</tt> function that returns the next valid token on the 1642632Sstever@eecs.umich.eduinput stream. <tt>yacc.py</tt> calls this repeatedly to retrieve 1652632Sstever@eecs.umich.edutokens and invoke grammar rules. The output of <tt>yacc.py</tt> is 1662632Sstever@eecs.umich.eduoften an Abstract Syntax Tree (AST). However, this is entirely up to 1672632Sstever@eecs.umich.eduthe user. If desired, <tt>yacc.py</tt> can also be used to implement 1684479Sbinkertn@umich.edusimple one-pass compilers. 1692632Sstever@eecs.umich.edu 1702632Sstever@eecs.umich.edu<p> 1712632Sstever@eecs.umich.eduLike its Unix counterpart, <tt>yacc.py</tt> provides most of the 1722632Sstever@eecs.umich.edufeatures you expect including extensive error checking, grammar 1732632Sstever@eecs.umich.eduvalidation, support for empty productions, error tokens, and ambiguity 1744479Sbinkertn@umich.eduresolution via precedence rules. In fact, everything that is possible in traditional yacc 1754479Sbinkertn@umich.edushould be supported in PLY. 1762632Sstever@eecs.umich.edu 1772632Sstever@eecs.umich.edu<p> 1784479Sbinkertn@umich.eduThe primary difference between 1794479Sbinkertn@umich.edu<tt>yacc.py</tt> and Unix <tt>yacc</tt> is that <tt>yacc.py</tt> 1804479Sbinkertn@umich.edudoesn't involve a separate code-generation process. 1814479Sbinkertn@umich.eduInstead, PLY relies on reflection (introspection) 1824479Sbinkertn@umich.eduto build its lexers and parsers. Unlike traditional lex/yacc which 1834479Sbinkertn@umich.edurequire a special input file that is converted into a separate source 1844479Sbinkertn@umich.edufile, the specifications given to PLY <em>are</em> valid Python 1854479Sbinkertn@umich.eduprograms. This means that there are no extra source files nor is 1864479Sbinkertn@umich.eduthere a special compiler construction step (e.g., running yacc to 1874479Sbinkertn@umich.edugenerate Python code for the compiler). Since the generation of the 1884479Sbinkertn@umich.eduparsing tables is relatively expensive, PLY caches the results and 1894479Sbinkertn@umich.edusaves them to a file. If no changes are detected in the input source, 1904479Sbinkertn@umich.eduthe tables are read from the cache. Otherwise, they are regenerated. 1914479Sbinkertn@umich.edu 1926498Snate@binkert.org<H2><a name="ply_nn3"></a>4. Lex</H2> 1934479Sbinkertn@umich.edu 1944479Sbinkertn@umich.edu 1954479Sbinkertn@umich.edu<tt>lex.py</tt> is used to tokenize an input string. For example, suppose 1964479Sbinkertn@umich.eduyou're writing a programming language and a user supplied the following input string: 1974479Sbinkertn@umich.edu 1984479Sbinkertn@umich.edu<blockquote> 1994479Sbinkertn@umich.edu<pre> 2004479Sbinkertn@umich.edux = 3 + 42 * (s - t) 2014479Sbinkertn@umich.edu</pre> 2024479Sbinkertn@umich.edu</blockquote> 2034479Sbinkertn@umich.edu 2044479Sbinkertn@umich.eduA tokenizer splits the string into individual tokens 2054479Sbinkertn@umich.edu 2064479Sbinkertn@umich.edu<blockquote> 2074479Sbinkertn@umich.edu<pre> 2084479Sbinkertn@umich.edu'x','=', '3', '+', '42', '*', '(', 's', '-', 't', ')' 2094479Sbinkertn@umich.edu</pre> 2104479Sbinkertn@umich.edu</blockquote> 2114479Sbinkertn@umich.edu 2124479Sbinkertn@umich.eduTokens are usually given names to indicate what they are. For example: 2134479Sbinkertn@umich.edu 2144479Sbinkertn@umich.edu<blockquote> 2154479Sbinkertn@umich.edu<pre> 2164479Sbinkertn@umich.edu'ID','EQUALS','NUMBER','PLUS','NUMBER','TIMES', 2174479Sbinkertn@umich.edu'LPAREN','ID','MINUS','ID','RPAREN' 2184479Sbinkertn@umich.edu</pre> 2194479Sbinkertn@umich.edu</blockquote> 2204479Sbinkertn@umich.edu 2214479Sbinkertn@umich.eduMore specifically, the input is broken into pairs of token types and values. For example: 2224479Sbinkertn@umich.edu 2234479Sbinkertn@umich.edu<blockquote> 2244479Sbinkertn@umich.edu<pre> 2254479Sbinkertn@umich.edu('ID','x'), ('EQUALS','='), ('NUMBER','3'), 2264479Sbinkertn@umich.edu('PLUS','+'), ('NUMBER','42), ('TIMES','*'), 2274479Sbinkertn@umich.edu('LPAREN','('), ('ID','s'), ('MINUS','-'), 2284479Sbinkertn@umich.edu('ID','t'), ('RPAREN',')' 2294479Sbinkertn@umich.edu</pre> 2304479Sbinkertn@umich.edu</blockquote> 2314479Sbinkertn@umich.edu 2324479Sbinkertn@umich.eduThe identification of tokens is typically done by writing a series of regular expression 2334479Sbinkertn@umich.edurules. The next section shows how this is done using <tt>lex.py</tt>. 2344479Sbinkertn@umich.edu 2356498Snate@binkert.org<H3><a name="ply_nn4"></a>4.1 Lex Example</H3> 2364479Sbinkertn@umich.edu 2374479Sbinkertn@umich.edu 2384479Sbinkertn@umich.eduThe following example shows how <tt>lex.py</tt> is used to write a simple tokenizer. 2392632Sstever@eecs.umich.edu 2402632Sstever@eecs.umich.edu<blockquote> 2412632Sstever@eecs.umich.edu<pre> 2422632Sstever@eecs.umich.edu# ------------------------------------------------------------ 2432632Sstever@eecs.umich.edu# calclex.py 2442632Sstever@eecs.umich.edu# 2452632Sstever@eecs.umich.edu# tokenizer for a simple expression evaluator for 2462632Sstever@eecs.umich.edu# numbers and +,-,*,/ 2472632Sstever@eecs.umich.edu# ------------------------------------------------------------ 2484479Sbinkertn@umich.eduimport ply.lex as lex 2492632Sstever@eecs.umich.edu 2502632Sstever@eecs.umich.edu# List of token names. This is always required 2512632Sstever@eecs.umich.edutokens = ( 2522632Sstever@eecs.umich.edu 'NUMBER', 2532632Sstever@eecs.umich.edu 'PLUS', 2542632Sstever@eecs.umich.edu 'MINUS', 2552632Sstever@eecs.umich.edu 'TIMES', 2562632Sstever@eecs.umich.edu 'DIVIDE', 2572632Sstever@eecs.umich.edu 'LPAREN', 2582632Sstever@eecs.umich.edu 'RPAREN', 2592632Sstever@eecs.umich.edu) 2602632Sstever@eecs.umich.edu 2612632Sstever@eecs.umich.edu# Regular expression rules for simple tokens 2622632Sstever@eecs.umich.edut_PLUS = r'\+' 2632632Sstever@eecs.umich.edut_MINUS = r'-' 2642632Sstever@eecs.umich.edut_TIMES = r'\*' 2652632Sstever@eecs.umich.edut_DIVIDE = r'/' 2662632Sstever@eecs.umich.edut_LPAREN = r'\(' 2672632Sstever@eecs.umich.edut_RPAREN = r'\)' 2682632Sstever@eecs.umich.edu 2692632Sstever@eecs.umich.edu# A regular expression rule with some action code 2702632Sstever@eecs.umich.edudef t_NUMBER(t): 2712632Sstever@eecs.umich.edu r'\d+' 2726498Snate@binkert.org t.value = int(t.value) 2732632Sstever@eecs.umich.edu return t 2742632Sstever@eecs.umich.edu 2752632Sstever@eecs.umich.edu# Define a rule so we can track line numbers 2762632Sstever@eecs.umich.edudef t_newline(t): 2772632Sstever@eecs.umich.edu r'\n+' 2784479Sbinkertn@umich.edu t.lexer.lineno += len(t.value) 2792632Sstever@eecs.umich.edu 2802632Sstever@eecs.umich.edu# A string containing ignored characters (spaces and tabs) 2812632Sstever@eecs.umich.edut_ignore = ' \t' 2822632Sstever@eecs.umich.edu 2832632Sstever@eecs.umich.edu# Error handling rule 2842632Sstever@eecs.umich.edudef t_error(t): 2852632Sstever@eecs.umich.edu print "Illegal character '%s'" % t.value[0] 2864479Sbinkertn@umich.edu t.lexer.skip(1) 2872632Sstever@eecs.umich.edu 2882632Sstever@eecs.umich.edu# Build the lexer 2896498Snate@binkert.orglexer = lex.lex() 2902632Sstever@eecs.umich.edu 2914479Sbinkertn@umich.edu</pre> 2924479Sbinkertn@umich.edu</blockquote> 2936498Snate@binkert.orgTo use the lexer, you first need to feed it some input text using 2946498Snate@binkert.orgits <tt>input()</tt> method. After that, repeated calls 2956498Snate@binkert.orgto <tt>token()</tt> produce tokens. The following code shows how this 2966498Snate@binkert.orgworks: 2974479Sbinkertn@umich.edu 2984479Sbinkertn@umich.edu<blockquote> 2994479Sbinkertn@umich.edu<pre> 3004479Sbinkertn@umich.edu 3012632Sstever@eecs.umich.edu# Test it out 3022632Sstever@eecs.umich.edudata = ''' 3032632Sstever@eecs.umich.edu3 + 4 * 10 3042632Sstever@eecs.umich.edu + -20 *2 3052632Sstever@eecs.umich.edu''' 3062632Sstever@eecs.umich.edu 3072632Sstever@eecs.umich.edu# Give the lexer some input 3086498Snate@binkert.orglexer.input(data) 3092632Sstever@eecs.umich.edu 3102632Sstever@eecs.umich.edu# Tokenize 3116498Snate@binkert.orgwhile True: 3126498Snate@binkert.org tok = lexer.token() 3132632Sstever@eecs.umich.edu if not tok: break # No more input 3142632Sstever@eecs.umich.edu print tok 3152632Sstever@eecs.umich.edu</pre> 3162632Sstever@eecs.umich.edu</blockquote> 3172632Sstever@eecs.umich.edu 3184479Sbinkertn@umich.eduWhen executed, the example will produce the following output: 3194479Sbinkertn@umich.edu 3204479Sbinkertn@umich.edu<blockquote> 3214479Sbinkertn@umich.edu<pre> 3224479Sbinkertn@umich.edu$ python example.py 3234479Sbinkertn@umich.eduLexToken(NUMBER,3,2,1) 3244479Sbinkertn@umich.eduLexToken(PLUS,'+',2,3) 3254479Sbinkertn@umich.eduLexToken(NUMBER,4,2,5) 3264479Sbinkertn@umich.eduLexToken(TIMES,'*',2,7) 3274479Sbinkertn@umich.eduLexToken(NUMBER,10,2,10) 3284479Sbinkertn@umich.eduLexToken(PLUS,'+',3,14) 3294479Sbinkertn@umich.eduLexToken(MINUS,'-',3,16) 3304479Sbinkertn@umich.eduLexToken(NUMBER,20,3,18) 3314479Sbinkertn@umich.eduLexToken(TIMES,'*',3,20) 3324479Sbinkertn@umich.eduLexToken(NUMBER,2,3,21) 3334479Sbinkertn@umich.edu</pre> 3344479Sbinkertn@umich.edu</blockquote> 3354479Sbinkertn@umich.edu 3366498Snate@binkert.orgLexers also support the iteration protocol. So, you can write the above loop as follows: 3376498Snate@binkert.org 3386498Snate@binkert.org<blockquote> 3396498Snate@binkert.org<pre> 3406498Snate@binkert.orgfor tok in lexer: 3416498Snate@binkert.org print tok 3426498Snate@binkert.org</pre> 3436498Snate@binkert.org</blockquote> 3446498Snate@binkert.org 3456498Snate@binkert.orgThe tokens returned by <tt>lexer.token()</tt> are instances 3464479Sbinkertn@umich.eduof <tt>LexToken</tt>. This object has 3474479Sbinkertn@umich.eduattributes <tt>tok.type</tt>, <tt>tok.value</tt>, 3484479Sbinkertn@umich.edu<tt>tok.lineno</tt>, and <tt>tok.lexpos</tt>. The following code shows an example of 3494479Sbinkertn@umich.eduaccessing these attributes: 3504479Sbinkertn@umich.edu 3514479Sbinkertn@umich.edu<blockquote> 3524479Sbinkertn@umich.edu<pre> 3534479Sbinkertn@umich.edu# Tokenize 3546498Snate@binkert.orgwhile True: 3556498Snate@binkert.org tok = lexer.token() 3564479Sbinkertn@umich.edu if not tok: break # No more input 3574479Sbinkertn@umich.edu print tok.type, tok.value, tok.line, tok.lexpos 3584479Sbinkertn@umich.edu</pre> 3594479Sbinkertn@umich.edu</blockquote> 3604479Sbinkertn@umich.edu 3614479Sbinkertn@umich.eduThe <tt>tok.type</tt> and <tt>tok.value</tt> attributes contain the 3624479Sbinkertn@umich.edutype and value of the token itself. 3634479Sbinkertn@umich.edu<tt>tok.line</tt> and <tt>tok.lexpos</tt> contain information about 3644479Sbinkertn@umich.eduthe location of the token. <tt>tok.lexpos</tt> is the index of the 3654479Sbinkertn@umich.edutoken relative to the start of the input text. 3664479Sbinkertn@umich.edu 3676498Snate@binkert.org<H3><a name="ply_nn5"></a>4.2 The tokens list</H3> 3684479Sbinkertn@umich.edu 3694479Sbinkertn@umich.edu 3704479Sbinkertn@umich.eduAll lexers must provide a list <tt>tokens</tt> that defines all of the possible token 3714479Sbinkertn@umich.edunames that can be produced by the lexer. This list is always required 3724479Sbinkertn@umich.eduand is used to perform a variety of validation checks. The tokens list is also used by the 3734479Sbinkertn@umich.edu<tt>yacc.py</tt> module to identify terminals. 3744479Sbinkertn@umich.edu 3754479Sbinkertn@umich.edu<p> 3764479Sbinkertn@umich.eduIn the example, the following code specified the token names: 3774479Sbinkertn@umich.edu 3784479Sbinkertn@umich.edu<blockquote> 3794479Sbinkertn@umich.edu<pre> 3804479Sbinkertn@umich.edutokens = ( 3814479Sbinkertn@umich.edu 'NUMBER', 3824479Sbinkertn@umich.edu 'PLUS', 3834479Sbinkertn@umich.edu 'MINUS', 3844479Sbinkertn@umich.edu 'TIMES', 3854479Sbinkertn@umich.edu 'DIVIDE', 3864479Sbinkertn@umich.edu 'LPAREN', 3874479Sbinkertn@umich.edu 'RPAREN', 3884479Sbinkertn@umich.edu) 3894479Sbinkertn@umich.edu</pre> 3904479Sbinkertn@umich.edu</blockquote> 3914479Sbinkertn@umich.edu 3926498Snate@binkert.org<H3><a name="ply_nn6"></a>4.3 Specification of tokens</H3> 3934479Sbinkertn@umich.edu 3944479Sbinkertn@umich.edu 3954479Sbinkertn@umich.eduEach token is specified by writing a regular expression rule. Each of these rules are 3964479Sbinkertn@umich.eduare defined by making declarations with a special prefix <tt>t_</tt> to indicate that it 3972632Sstever@eecs.umich.edudefines a token. For simple tokens, the regular expression can 3982632Sstever@eecs.umich.edube specified as strings such as this (note: Python raw strings are used since they are the 3992632Sstever@eecs.umich.edumost convenient way to write regular expression strings): 4002632Sstever@eecs.umich.edu 4012632Sstever@eecs.umich.edu<blockquote> 4022632Sstever@eecs.umich.edu<pre> 4032632Sstever@eecs.umich.edut_PLUS = r'\+' 4042632Sstever@eecs.umich.edu</pre> 4052632Sstever@eecs.umich.edu</blockquote> 4062632Sstever@eecs.umich.edu 4072632Sstever@eecs.umich.eduIn this case, the name following the <tt>t_</tt> must exactly match one of the 4082632Sstever@eecs.umich.edunames supplied in <tt>tokens</tt>. If some kind of action needs to be performed, 4094479Sbinkertn@umich.edua token rule can be specified as a function. For example, this rule matches numbers and 4104479Sbinkertn@umich.educonverts the string into a Python integer. 4112632Sstever@eecs.umich.edu 4122632Sstever@eecs.umich.edu<blockquote> 4132632Sstever@eecs.umich.edu<pre> 4142632Sstever@eecs.umich.edudef t_NUMBER(t): 4152632Sstever@eecs.umich.edu r'\d+' 4166498Snate@binkert.org t.value = int(t.value) 4172632Sstever@eecs.umich.edu return t 4182632Sstever@eecs.umich.edu</pre> 4192632Sstever@eecs.umich.edu</blockquote> 4202632Sstever@eecs.umich.edu 4214479Sbinkertn@umich.eduWhen a function is used, the regular expression rule is specified in the function documentation string. 4222632Sstever@eecs.umich.eduThe function always takes a single argument which is an instance of 4234479Sbinkertn@umich.edu<tt>LexToken</tt>. This object has attributes of <tt>t.type</tt> which is the token type (as a string), 4244479Sbinkertn@umich.edu<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 4254479Sbinkertn@umich.eduis the position of the token relative to the beginning of the input text. 4262632Sstever@eecs.umich.eduBy default, <tt>t.type</tt> is set to the name following the <tt>t_</tt> prefix. The action 4272632Sstever@eecs.umich.edufunction can modify the contents of the <tt>LexToken</tt> object as appropriate. However, 4282632Sstever@eecs.umich.eduwhen it is done, the resulting token should be returned. If no value is returned by the action 4292632Sstever@eecs.umich.edufunction, the token is simply discarded and the next token read. 4302632Sstever@eecs.umich.edu 4312632Sstever@eecs.umich.edu<p> 4324479Sbinkertn@umich.eduInternally, <tt>lex.py</tt> uses the <tt>re</tt> module to do its patten matching. When building the master regular expression, 4332632Sstever@eecs.umich.edurules are added in the following order: 4342632Sstever@eecs.umich.edu<p> 4352632Sstever@eecs.umich.edu<ol> 4362632Sstever@eecs.umich.edu<li>All tokens defined by functions are added in the same order as they appear in the lexer file. 4374479Sbinkertn@umich.edu<li>Tokens defined by strings are added next by sorting them in order of decreasing regular expression length (longer expressions 4382632Sstever@eecs.umich.eduare added first). 4392632Sstever@eecs.umich.edu</ol> 4402632Sstever@eecs.umich.edu<p> 4412632Sstever@eecs.umich.eduWithout this ordering, it can be difficult to correctly match certain types of tokens. For example, if you 4422632Sstever@eecs.umich.eduwanted to have separate tokens for "=" and "==", you need to make sure that "==" is checked first. By sorting regular 4432632Sstever@eecs.umich.eduexpressions in order of decreasing length, this problem is solved for rules defined as strings. For functions, 4442632Sstever@eecs.umich.eduthe order can be explicitly controlled since rules appearing first are checked first. 4452632Sstever@eecs.umich.edu 4462632Sstever@eecs.umich.edu<p> 4476498Snate@binkert.orgTo handle reserved words, you should write a single rule to match an 4486498Snate@binkert.orgidentifier and do a special name lookup in a function like this: 4492632Sstever@eecs.umich.edu 4502632Sstever@eecs.umich.edu<blockquote> 4512632Sstever@eecs.umich.edu<pre> 4522632Sstever@eecs.umich.edureserved = { 4532632Sstever@eecs.umich.edu 'if' : 'IF', 4542632Sstever@eecs.umich.edu 'then' : 'THEN', 4552632Sstever@eecs.umich.edu 'else' : 'ELSE', 4562632Sstever@eecs.umich.edu 'while' : 'WHILE', 4572632Sstever@eecs.umich.edu ... 4582632Sstever@eecs.umich.edu} 4592632Sstever@eecs.umich.edu 4606498Snate@binkert.orgtokens = ['LPAREN','RPAREN',...,'ID'] + list(reserved.values()) 4616498Snate@binkert.org 4622632Sstever@eecs.umich.edudef t_ID(t): 4632632Sstever@eecs.umich.edu r'[a-zA-Z_][a-zA-Z_0-9]*' 4642632Sstever@eecs.umich.edu t.type = reserved.get(t.value,'ID') # Check for reserved words 4652632Sstever@eecs.umich.edu return t 4662632Sstever@eecs.umich.edu</pre> 4672632Sstever@eecs.umich.edu</blockquote> 4682632Sstever@eecs.umich.edu 4694479Sbinkertn@umich.eduThis approach greatly reduces the number of regular expression rules and is likely to make things a little faster. 4704479Sbinkertn@umich.edu 4712632Sstever@eecs.umich.edu<p> 4724479Sbinkertn@umich.edu<b>Note:</b> You should avoid writing individual rules for reserved words. For example, if you write rules like this, 4734479Sbinkertn@umich.edu 4744479Sbinkertn@umich.edu<blockquote> 4754479Sbinkertn@umich.edu<pre> 4764479Sbinkertn@umich.edut_FOR = r'for' 4774479Sbinkertn@umich.edut_PRINT = r'print' 4784479Sbinkertn@umich.edu</pre> 4794479Sbinkertn@umich.edu</blockquote> 4804479Sbinkertn@umich.edu 4814479Sbinkertn@umich.eduthose rules will be triggered for identifiers that include those words as a prefix such as "forget" or "printed". This is probably not 4824479Sbinkertn@umich.eduwhat you want. 4834479Sbinkertn@umich.edu 4846498Snate@binkert.org<H3><a name="ply_nn7"></a>4.4 Token values</H3> 4854479Sbinkertn@umich.edu 4864479Sbinkertn@umich.edu 4874479Sbinkertn@umich.eduWhen tokens are returned by lex, they have a value that is stored in the <tt>value</tt> attribute. Normally, the value is the text 4884479Sbinkertn@umich.eduthat was matched. However, the value can be assigned to any Python object. For instance, when lexing identifiers, you may 4894479Sbinkertn@umich.eduwant to return both the identifier name and information from some sort of symbol table. To do this, you might write a rule like this: 4902632Sstever@eecs.umich.edu 4912632Sstever@eecs.umich.edu<blockquote> 4922632Sstever@eecs.umich.edu<pre> 4932632Sstever@eecs.umich.edudef t_ID(t): 4942632Sstever@eecs.umich.edu ... 4954479Sbinkertn@umich.edu # Look up symbol table information and return a tuple 4962632Sstever@eecs.umich.edu t.value = (t.value, symbol_lookup(t.value)) 4972632Sstever@eecs.umich.edu ... 4982632Sstever@eecs.umich.edu return t 4992632Sstever@eecs.umich.edu</pre> 5002632Sstever@eecs.umich.edu</blockquote> 5012632Sstever@eecs.umich.edu 5024479Sbinkertn@umich.eduIt 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 5036498Snate@binkert.orgcontents of the <tt>value</tt> attribute. Thus, accessing other attributes may be unnecessarily awkward. If you 5046498Snate@binkert.orgneed to store multiple values on a token, assign a tuple, dictionary, or instance to <tt>value</tt>. 5056498Snate@binkert.org 5066498Snate@binkert.org<H3><a name="ply_nn8"></a>4.5 Discarded tokens</H3> 5074479Sbinkertn@umich.edu 5084479Sbinkertn@umich.edu 5094479Sbinkertn@umich.eduTo discard a token, such as a comment, simply define a token rule that returns no value. For example: 5104479Sbinkertn@umich.edu 5112632Sstever@eecs.umich.edu<blockquote> 5122632Sstever@eecs.umich.edu<pre> 5134479Sbinkertn@umich.edudef t_COMMENT(t): 5144479Sbinkertn@umich.edu r'\#.*' 5154479Sbinkertn@umich.edu pass 5164479Sbinkertn@umich.edu # No return value. Token discarded 5172632Sstever@eecs.umich.edu</pre> 5182632Sstever@eecs.umich.edu</blockquote> 5192632Sstever@eecs.umich.edu 5204479Sbinkertn@umich.eduAlternatively, you can include the prefix "ignore_" in the token declaration to force a token to be ignored. For example: 5214479Sbinkertn@umich.edu 5224479Sbinkertn@umich.edu<blockquote> 5234479Sbinkertn@umich.edu<pre> 5244479Sbinkertn@umich.edut_ignore_COMMENT = r'\#.*' 5254479Sbinkertn@umich.edu</pre> 5264479Sbinkertn@umich.edu</blockquote> 5274479Sbinkertn@umich.edu 5284479Sbinkertn@umich.eduBe advised that if you are ignoring many different kinds of text, you may still want to use functions since these provide more precise 5294479Sbinkertn@umich.educontrol over the order in which regular expressions are matched (i.e., functions are matched in order of specification whereas strings are 5304479Sbinkertn@umich.edusorted by regular expression length). 5314479Sbinkertn@umich.edu 5326498Snate@binkert.org<H3><a name="ply_nn9"></a>4.6 Line numbers and positional information</H3> 5334479Sbinkertn@umich.edu 5344479Sbinkertn@umich.edu 5354479Sbinkertn@umich.edu<p>By default, <tt>lex.py</tt> knows nothing about line numbers. This is because <tt>lex.py</tt> doesn't know anything 5364479Sbinkertn@umich.eduabout what constitutes a "line" of input (e.g., the newline character or even if the input is textual data). 5374479Sbinkertn@umich.eduTo update this information, you need to write a special rule. In the example, the <tt>t_newline()</tt> rule shows how to do this. 5384479Sbinkertn@umich.edu 5394479Sbinkertn@umich.edu<blockquote> 5404479Sbinkertn@umich.edu<pre> 5414479Sbinkertn@umich.edu# Define a rule so we can track line numbers 5424479Sbinkertn@umich.edudef t_newline(t): 5434479Sbinkertn@umich.edu r'\n+' 5444479Sbinkertn@umich.edu t.lexer.lineno += len(t.value) 5454479Sbinkertn@umich.edu</pre> 5464479Sbinkertn@umich.edu</blockquote> 5474479Sbinkertn@umich.eduWithin the rule, the <tt>lineno</tt> attribute of the underlying lexer <tt>t.lexer</tt> is updated. 5484479Sbinkertn@umich.eduAfter the line number is updated, the token is simply discarded since nothing is returned. 5492632Sstever@eecs.umich.edu 5502632Sstever@eecs.umich.edu<p> 5514479Sbinkertn@umich.edu<tt>lex.py</tt> does not perform and kind of automatic column tracking. However, it does record positional 5524479Sbinkertn@umich.eduinformation related to each token in the <tt>lexpos</tt> attribute. Using this, it is usually possible to compute 5534479Sbinkertn@umich.educolumn information as a separate step. For instance, just count backwards until you reach a newline. 5544479Sbinkertn@umich.edu 5554479Sbinkertn@umich.edu<blockquote> 5564479Sbinkertn@umich.edu<pre> 5574479Sbinkertn@umich.edu# Compute column. 5584479Sbinkertn@umich.edu# input is the input text string 5594479Sbinkertn@umich.edu# token is a token instance 5604479Sbinkertn@umich.edudef find_column(input,token): 5616498Snate@binkert.org last_cr = input.rfind('\n',0,token.lexpos) 5626498Snate@binkert.org if last_cr < 0: 5636498Snate@binkert.org last_cr = 0 5646498Snate@binkert.org column = (token.lexpos - last_cr) + 1 5654479Sbinkertn@umich.edu return column 5664479Sbinkertn@umich.edu</pre> 5674479Sbinkertn@umich.edu</blockquote> 5684479Sbinkertn@umich.edu 5694479Sbinkertn@umich.eduSince column information is often only useful in the context of error handling, calculating the column 5704479Sbinkertn@umich.eduposition can be performed when needed as opposed to doing it for each token. 5714479Sbinkertn@umich.edu 5726498Snate@binkert.org<H3><a name="ply_nn10"></a>4.7 Ignored characters</H3> 5734479Sbinkertn@umich.edu 5742632Sstever@eecs.umich.edu 5752632Sstever@eecs.umich.edu<p> 5764479Sbinkertn@umich.eduThe special <tt>t_ignore</tt> rule is reserved by <tt>lex.py</tt> for characters 5774479Sbinkertn@umich.eduthat should be completely ignored in the input stream. 5784479Sbinkertn@umich.eduUsually this is used to skip over whitespace and other non-essential characters. 5794479Sbinkertn@umich.eduAlthough it is possible to define a regular expression rule for whitespace in a manner 5804479Sbinkertn@umich.edusimilar to <tt>t_newline()</tt>, the use of <tt>t_ignore</tt> provides substantially better 5814479Sbinkertn@umich.edulexing performance because it is handled as a special case and is checked in a much 5824479Sbinkertn@umich.edumore efficient manner than the normal regular expression rules. 5834479Sbinkertn@umich.edu 5846498Snate@binkert.org<H3><a name="ply_nn11"></a>4.8 Literal characters</H3> 5854479Sbinkertn@umich.edu 5864479Sbinkertn@umich.edu 5874479Sbinkertn@umich.edu<p> 5884479Sbinkertn@umich.eduLiteral characters can be specified by defining a variable <tt>literals</tt> in your lexing module. For example: 5894479Sbinkertn@umich.edu 5904479Sbinkertn@umich.edu<blockquote> 5914479Sbinkertn@umich.edu<pre> 5924479Sbinkertn@umich.eduliterals = [ '+','-','*','/' ] 5934479Sbinkertn@umich.edu</pre> 5944479Sbinkertn@umich.edu</blockquote> 5954479Sbinkertn@umich.edu 5964479Sbinkertn@umich.eduor alternatively 5974479Sbinkertn@umich.edu 5984479Sbinkertn@umich.edu<blockquote> 5994479Sbinkertn@umich.edu<pre> 6004479Sbinkertn@umich.eduliterals = "+-*/" 6014479Sbinkertn@umich.edu</pre> 6024479Sbinkertn@umich.edu</blockquote> 6034479Sbinkertn@umich.edu 6044479Sbinkertn@umich.eduA literal character is simply a single character that is returned "as is" when encountered by the lexer. Literals are checked 6054479Sbinkertn@umich.eduafter all of the defined regular expression rules. Thus, if a rule starts with one of the literal characters, it will always 6064479Sbinkertn@umich.edutake precedence. 6074479Sbinkertn@umich.edu<p> 6084479Sbinkertn@umich.eduWhen 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>. 6094479Sbinkertn@umich.edu 6106498Snate@binkert.org<H3><a name="ply_nn12"></a>4.9 Error handling</H3> 6114479Sbinkertn@umich.edu 6124479Sbinkertn@umich.edu 6134479Sbinkertn@umich.edu<p> 6144479Sbinkertn@umich.eduFinally, the <tt>t_error()</tt> 6154479Sbinkertn@umich.edufunction is used to handle lexing errors that occur when illegal 6164479Sbinkertn@umich.educharacters are detected. In this case, the <tt>t.value</tt> attribute contains the 6174479Sbinkertn@umich.edurest of the input string that has not been tokenized. In the example, the error function 6184479Sbinkertn@umich.eduwas defined as follows: 6194479Sbinkertn@umich.edu 6204479Sbinkertn@umich.edu<blockquote> 6214479Sbinkertn@umich.edu<pre> 6224479Sbinkertn@umich.edu# Error handling rule 6234479Sbinkertn@umich.edudef t_error(t): 6244479Sbinkertn@umich.edu print "Illegal character '%s'" % t.value[0] 6254479Sbinkertn@umich.edu t.lexer.skip(1) 6264479Sbinkertn@umich.edu</pre> 6274479Sbinkertn@umich.edu</blockquote> 6284479Sbinkertn@umich.edu 6294479Sbinkertn@umich.eduIn this case, we simply print the offending character and skip ahead one character by calling <tt>t.lexer.skip(1)</tt>. 6304479Sbinkertn@umich.edu 6316498Snate@binkert.org<H3><a name="ply_nn13"></a>4.10 Building and using the lexer</H3> 6324479Sbinkertn@umich.edu 6334479Sbinkertn@umich.edu 6344479Sbinkertn@umich.edu<p> 6354479Sbinkertn@umich.eduTo build the lexer, the function <tt>lex.lex()</tt> is used. This function 6364479Sbinkertn@umich.eduuses Python reflection (or introspection) to read the the regular expression rules 6376498Snate@binkert.orgout of the calling context and build the lexer. Once the lexer has been built, two methods can 6384479Sbinkertn@umich.edube used to control the lexer. 6394479Sbinkertn@umich.edu 6404479Sbinkertn@umich.edu<ul> 6416498Snate@binkert.org<li><tt>lexer.input(data)</tt>. Reset the lexer and store a new input string. 6426498Snate@binkert.org<li><tt>lexer.token()</tt>. Return the next token. Returns a special <tt>LexToken</tt> instance on success or 6434479Sbinkertn@umich.eduNone if the end of the input text has been reached. 6444479Sbinkertn@umich.edu</ul> 6454479Sbinkertn@umich.edu 6466498Snate@binkert.orgThe preferred way to use PLY is to invoke the above methods directly on the lexer object returned by the 6476498Snate@binkert.org<tt>lex()</tt> function. The legacy interface to PLY involves module-level functions <tt>lex.input()</tt> and <tt>lex.token()</tt>. 6486498Snate@binkert.orgFor example: 6492632Sstever@eecs.umich.edu 6502632Sstever@eecs.umich.edu<blockquote> 6512632Sstever@eecs.umich.edu<pre> 6526498Snate@binkert.orglex.lex() 6536498Snate@binkert.orglex.input(sometext) 6542632Sstever@eecs.umich.eduwhile 1: 6556498Snate@binkert.org tok = lex.token() 6562632Sstever@eecs.umich.edu if not tok: break 6572632Sstever@eecs.umich.edu print tok 6582632Sstever@eecs.umich.edu</pre> 6592632Sstever@eecs.umich.edu</blockquote> 6602632Sstever@eecs.umich.edu 6614479Sbinkertn@umich.edu<p> 6626498Snate@binkert.orgIn this example, the module-level functions <tt>lex.input()</tt> and <tt>lex.token()</tt> are bound to the <tt>input()</tt> 6636498Snate@binkert.organd <tt>token()</tt> methods of the last lexer created by the lex module. This interface may go away at some point so 6646498Snate@binkert.orgit's probably best not to use it. 6656498Snate@binkert.org 6666498Snate@binkert.org<H3><a name="ply_nn14"></a>4.11 The @TOKEN decorator</H3> 6674479Sbinkertn@umich.edu 6684479Sbinkertn@umich.edu 6694479Sbinkertn@umich.eduIn some applications, you may want to define build tokens from as a series of 6704479Sbinkertn@umich.edumore complex regular expression rules. For example: 6712632Sstever@eecs.umich.edu 6722632Sstever@eecs.umich.edu<blockquote> 6732632Sstever@eecs.umich.edu<pre> 6744479Sbinkertn@umich.edudigit = r'([0-9])' 6754479Sbinkertn@umich.edunondigit = r'([_A-Za-z])' 6764479Sbinkertn@umich.eduidentifier = r'(' + nondigit + r'(' + digit + r'|' + nondigit + r')*)' 6774479Sbinkertn@umich.edu 6784479Sbinkertn@umich.edudef t_ID(t): 6794479Sbinkertn@umich.edu # want docstring to be identifier above. ????? 6804479Sbinkertn@umich.edu ... 6812632Sstever@eecs.umich.edu</pre> 6822632Sstever@eecs.umich.edu</blockquote> 6832632Sstever@eecs.umich.edu 6844479Sbinkertn@umich.eduIn this case, we want the regular expression rule for <tt>ID</tt> to be one of the variables above. However, there is no 6854479Sbinkertn@umich.eduway to directly specify this using a normal documentation string. To solve this problem, you can use the <tt>@TOKEN</tt> 6864479Sbinkertn@umich.edudecorator. For example: 6872632Sstever@eecs.umich.edu 6882632Sstever@eecs.umich.edu<blockquote> 6892632Sstever@eecs.umich.edu<pre> 6904479Sbinkertn@umich.edufrom ply.lex import TOKEN 6914479Sbinkertn@umich.edu 6924479Sbinkertn@umich.edu@TOKEN(identifier) 6934479Sbinkertn@umich.edudef t_ID(t): 6944479Sbinkertn@umich.edu ... 6952632Sstever@eecs.umich.edu</pre> 6962632Sstever@eecs.umich.edu</blockquote> 6972632Sstever@eecs.umich.edu 6984479Sbinkertn@umich.eduThis will attach <tt>identifier</tt> to the docstring for <tt>t_ID()</tt> allowing <tt>lex.py</tt> to work normally. An alternative 6994479Sbinkertn@umich.eduapproach this problem is to set the docstring directly like this: 7004479Sbinkertn@umich.edu 7014479Sbinkertn@umich.edu<blockquote> 7024479Sbinkertn@umich.edu<pre> 7034479Sbinkertn@umich.edudef t_ID(t): 7044479Sbinkertn@umich.edu ... 7054479Sbinkertn@umich.edu 7064479Sbinkertn@umich.edut_ID.__doc__ = identifier 7074479Sbinkertn@umich.edu</pre> 7084479Sbinkertn@umich.edu</blockquote> 7094479Sbinkertn@umich.edu 7104479Sbinkertn@umich.edu<b>NOTE:</b> Use of <tt>@TOKEN</tt> requires Python-2.4 or newer. If you're concerned about backwards compatibility with older 7114479Sbinkertn@umich.eduversions of Python, use the alternative approach of setting the docstring directly. 7124479Sbinkertn@umich.edu 7136498Snate@binkert.org<H3><a name="ply_nn15"></a>4.12 Optimized mode</H3> 7144479Sbinkertn@umich.edu 7154479Sbinkertn@umich.edu 7164479Sbinkertn@umich.eduFor improved performance, it may be desirable to use Python's 7174479Sbinkertn@umich.eduoptimized mode (e.g., running Python with the <tt>-O</tt> 7184479Sbinkertn@umich.eduoption). However, doing so causes Python to ignore documentation 7194479Sbinkertn@umich.edustrings. This presents special problems for <tt>lex.py</tt>. To 7204479Sbinkertn@umich.eduhandle this case, you can create your lexer using 7214479Sbinkertn@umich.eduthe <tt>optimize</tt> option as follows: 7224479Sbinkertn@umich.edu 7234479Sbinkertn@umich.edu<blockquote> 7244479Sbinkertn@umich.edu<pre> 7254479Sbinkertn@umich.edulexer = lex.lex(optimize=1) 7264479Sbinkertn@umich.edu</pre> 7274479Sbinkertn@umich.edu</blockquote> 7284479Sbinkertn@umich.edu 7294479Sbinkertn@umich.eduNext, run Python in its normal operating mode. When you do 7304479Sbinkertn@umich.eduthis, <tt>lex.py</tt> will write a file called <tt>lextab.py</tt> to 7314479Sbinkertn@umich.eduthe current directory. This file contains all of the regular 7324479Sbinkertn@umich.eduexpression rules and tables used during lexing. On subsequent 7334479Sbinkertn@umich.eduexecutions, 7344479Sbinkertn@umich.edu<tt>lextab.py</tt> will simply be imported to build the lexer. This 7354479Sbinkertn@umich.eduapproach substantially improves the startup time of the lexer and it 7364479Sbinkertn@umich.eduworks in Python's optimized mode. 7374479Sbinkertn@umich.edu 7382632Sstever@eecs.umich.edu<p> 7394479Sbinkertn@umich.eduTo change the name of the lexer-generated file, use the <tt>lextab</tt> keyword argument. For example: 7404479Sbinkertn@umich.edu 7414479Sbinkertn@umich.edu<blockquote> 7424479Sbinkertn@umich.edu<pre> 7434479Sbinkertn@umich.edulexer = lex.lex(optimize=1,lextab="footab") 7444479Sbinkertn@umich.edu</pre> 7454479Sbinkertn@umich.edu</blockquote> 7464479Sbinkertn@umich.edu 7474479Sbinkertn@umich.eduWhen running in optimized mode, it is important to note that lex disables most error checking. Thus, this is really only recommended 7484479Sbinkertn@umich.eduif you're sure everything is working correctly and you're ready to start releasing production code. 7494479Sbinkertn@umich.edu 7506498Snate@binkert.org<H3><a name="ply_nn16"></a>4.13 Debugging</H3> 7514479Sbinkertn@umich.edu 7524479Sbinkertn@umich.edu 7534479Sbinkertn@umich.eduFor the purpose of debugging, you can run <tt>lex()</tt> in a debugging mode as follows: 7544479Sbinkertn@umich.edu 7554479Sbinkertn@umich.edu<blockquote> 7564479Sbinkertn@umich.edu<pre> 7574479Sbinkertn@umich.edulexer = lex.lex(debug=1) 7584479Sbinkertn@umich.edu</pre> 7594479Sbinkertn@umich.edu</blockquote> 7604479Sbinkertn@umich.edu 7616498Snate@binkert.org<p> 7626498Snate@binkert.orgThis will produce various sorts of debugging information including all of the added rules, 7636498Snate@binkert.orgthe master regular expressions used by the lexer, and tokens generating during lexing. 7646498Snate@binkert.org</p> 7656498Snate@binkert.org 7666498Snate@binkert.org<p> 7674479Sbinkertn@umich.eduIn addition, <tt>lex.py</tt> comes with a simple main function which 7684479Sbinkertn@umich.eduwill either tokenize input read from standard input or from a file specified 7694479Sbinkertn@umich.eduon the command line. To use it, simply put this in your lexer: 7706498Snate@binkert.org</p> 7712632Sstever@eecs.umich.edu 7722632Sstever@eecs.umich.edu<blockquote> 7732632Sstever@eecs.umich.edu<pre> 7742632Sstever@eecs.umich.eduif __name__ == '__main__': 7752632Sstever@eecs.umich.edu lex.runmain() 7762632Sstever@eecs.umich.edu</pre> 7772632Sstever@eecs.umich.edu</blockquote> 7782632Sstever@eecs.umich.edu 7796498Snate@binkert.orgPlease refer to the "Debugging" section near the end for some more advanced details 7806498Snate@binkert.orgof debugging. 7816498Snate@binkert.org 7826498Snate@binkert.org<H3><a name="ply_nn17"></a>4.14 Alternative specification of lexers</H3> 7834479Sbinkertn@umich.edu 7844479Sbinkertn@umich.edu 7854479Sbinkertn@umich.eduAs shown in the example, lexers are specified all within one Python module. If you want to 7864479Sbinkertn@umich.eduput token rules in a different module from the one in which you invoke <tt>lex()</tt>, use the 7874479Sbinkertn@umich.edu<tt>module</tt> keyword argument. 7884479Sbinkertn@umich.edu 7894479Sbinkertn@umich.edu<p> 7904479Sbinkertn@umich.eduFor example, you might have a dedicated module that just contains 7914479Sbinkertn@umich.eduthe token rules: 7924479Sbinkertn@umich.edu 7934479Sbinkertn@umich.edu<blockquote> 7944479Sbinkertn@umich.edu<pre> 7954479Sbinkertn@umich.edu# module: tokrules.py 7964479Sbinkertn@umich.edu# This module just contains the lexing rules 7974479Sbinkertn@umich.edu 7984479Sbinkertn@umich.edu# List of token names. This is always required 7994479Sbinkertn@umich.edutokens = ( 8004479Sbinkertn@umich.edu 'NUMBER', 8014479Sbinkertn@umich.edu 'PLUS', 8024479Sbinkertn@umich.edu 'MINUS', 8034479Sbinkertn@umich.edu 'TIMES', 8044479Sbinkertn@umich.edu 'DIVIDE', 8054479Sbinkertn@umich.edu 'LPAREN', 8064479Sbinkertn@umich.edu 'RPAREN', 8074479Sbinkertn@umich.edu) 8084479Sbinkertn@umich.edu 8094479Sbinkertn@umich.edu# Regular expression rules for simple tokens 8104479Sbinkertn@umich.edut_PLUS = r'\+' 8114479Sbinkertn@umich.edut_MINUS = r'-' 8124479Sbinkertn@umich.edut_TIMES = r'\*' 8134479Sbinkertn@umich.edut_DIVIDE = r'/' 8144479Sbinkertn@umich.edut_LPAREN = r'\(' 8154479Sbinkertn@umich.edut_RPAREN = r'\)' 8164479Sbinkertn@umich.edu 8174479Sbinkertn@umich.edu# A regular expression rule with some action code 8184479Sbinkertn@umich.edudef t_NUMBER(t): 8194479Sbinkertn@umich.edu r'\d+' 8206498Snate@binkert.org t.value = int(t.value) 8214479Sbinkertn@umich.edu return t 8224479Sbinkertn@umich.edu 8234479Sbinkertn@umich.edu# Define a rule so we can track line numbers 8244479Sbinkertn@umich.edudef t_newline(t): 8254479Sbinkertn@umich.edu r'\n+' 8264479Sbinkertn@umich.edu t.lexer.lineno += len(t.value) 8274479Sbinkertn@umich.edu 8284479Sbinkertn@umich.edu# A string containing ignored characters (spaces and tabs) 8294479Sbinkertn@umich.edut_ignore = ' \t' 8304479Sbinkertn@umich.edu 8314479Sbinkertn@umich.edu# Error handling rule 8324479Sbinkertn@umich.edudef t_error(t): 8334479Sbinkertn@umich.edu print "Illegal character '%s'" % t.value[0] 8344479Sbinkertn@umich.edu t.lexer.skip(1) 8354479Sbinkertn@umich.edu</pre> 8364479Sbinkertn@umich.edu</blockquote> 8374479Sbinkertn@umich.edu 8384479Sbinkertn@umich.eduNow, 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): 8394479Sbinkertn@umich.edu 8404479Sbinkertn@umich.edu<blockquote> 8414479Sbinkertn@umich.edu<pre> 8424479Sbinkertn@umich.edu>>> import tokrules 8434479Sbinkertn@umich.edu>>> <b>lexer = lex.lex(module=tokrules)</b> 8444479Sbinkertn@umich.edu>>> lexer.input("3 + 4") 8454479Sbinkertn@umich.edu>>> lexer.token() 8464479Sbinkertn@umich.eduLexToken(NUMBER,3,1,1,0) 8474479Sbinkertn@umich.edu>>> lexer.token() 8484479Sbinkertn@umich.eduLexToken(PLUS,'+',1,2) 8494479Sbinkertn@umich.edu>>> lexer.token() 8504479Sbinkertn@umich.eduLexToken(NUMBER,4,1,4) 8514479Sbinkertn@umich.edu>>> lexer.token() 8524479Sbinkertn@umich.eduNone 8534479Sbinkertn@umich.edu>>> 8544479Sbinkertn@umich.edu</pre> 8554479Sbinkertn@umich.edu</blockquote> 8564479Sbinkertn@umich.edu 8576498Snate@binkert.orgThe <tt>module</tt> option can also be used to define lexers from instances of a class. For example: 8584479Sbinkertn@umich.edu 8594479Sbinkertn@umich.edu<blockquote> 8604479Sbinkertn@umich.edu<pre> 8614479Sbinkertn@umich.eduimport ply.lex as lex 8624479Sbinkertn@umich.edu 8634479Sbinkertn@umich.educlass MyLexer: 8644479Sbinkertn@umich.edu # List of token names. This is always required 8654479Sbinkertn@umich.edu tokens = ( 8664479Sbinkertn@umich.edu 'NUMBER', 8674479Sbinkertn@umich.edu 'PLUS', 8684479Sbinkertn@umich.edu 'MINUS', 8694479Sbinkertn@umich.edu 'TIMES', 8704479Sbinkertn@umich.edu 'DIVIDE', 8714479Sbinkertn@umich.edu 'LPAREN', 8724479Sbinkertn@umich.edu 'RPAREN', 8734479Sbinkertn@umich.edu ) 8744479Sbinkertn@umich.edu 8754479Sbinkertn@umich.edu # Regular expression rules for simple tokens 8764479Sbinkertn@umich.edu t_PLUS = r'\+' 8774479Sbinkertn@umich.edu t_MINUS = r'-' 8784479Sbinkertn@umich.edu t_TIMES = r'\*' 8794479Sbinkertn@umich.edu t_DIVIDE = r'/' 8804479Sbinkertn@umich.edu t_LPAREN = r'\(' 8814479Sbinkertn@umich.edu t_RPAREN = r'\)' 8824479Sbinkertn@umich.edu 8834479Sbinkertn@umich.edu # A regular expression rule with some action code 8844479Sbinkertn@umich.edu # Note addition of self parameter since we're in a class 8854479Sbinkertn@umich.edu def t_NUMBER(self,t): 8864479Sbinkertn@umich.edu r'\d+' 8876498Snate@binkert.org t.value = int(t.value) 8884479Sbinkertn@umich.edu return t 8894479Sbinkertn@umich.edu 8904479Sbinkertn@umich.edu # Define a rule so we can track line numbers 8914479Sbinkertn@umich.edu def t_newline(self,t): 8924479Sbinkertn@umich.edu r'\n+' 8934479Sbinkertn@umich.edu t.lexer.lineno += len(t.value) 8944479Sbinkertn@umich.edu 8954479Sbinkertn@umich.edu # A string containing ignored characters (spaces and tabs) 8964479Sbinkertn@umich.edu t_ignore = ' \t' 8974479Sbinkertn@umich.edu 8984479Sbinkertn@umich.edu # Error handling rule 8994479Sbinkertn@umich.edu def t_error(self,t): 9004479Sbinkertn@umich.edu print "Illegal character '%s'" % t.value[0] 9014479Sbinkertn@umich.edu t.lexer.skip(1) 9024479Sbinkertn@umich.edu 9034479Sbinkertn@umich.edu <b># Build the lexer 9044479Sbinkertn@umich.edu def build(self,**kwargs): 9056498Snate@binkert.org self.lexer = lex.lex(module=self, **kwargs)</b> 9064479Sbinkertn@umich.edu 9074479Sbinkertn@umich.edu # Test it output 9084479Sbinkertn@umich.edu def test(self,data): 9094479Sbinkertn@umich.edu self.lexer.input(data) 9106498Snate@binkert.org while True: 9114479Sbinkertn@umich.edu tok = lexer.token() 9124479Sbinkertn@umich.edu if not tok: break 9134479Sbinkertn@umich.edu print tok 9144479Sbinkertn@umich.edu 9154479Sbinkertn@umich.edu# Build the lexer and try it out 9164479Sbinkertn@umich.edum = MyLexer() 9174479Sbinkertn@umich.edum.build() # Build the lexer 9184479Sbinkertn@umich.edum.test("3 + 4") # Test it 9194479Sbinkertn@umich.edu</pre> 9204479Sbinkertn@umich.edu</blockquote> 9214479Sbinkertn@umich.edu 9226498Snate@binkert.org 9236498Snate@binkert.orgWhen building a lexer from class, <em>you should construct the lexer from 9246498Snate@binkert.organ instance of the class</em>, not the class object itself. This is because 9256498Snate@binkert.orgPLY only works properly if the lexer actions are defined by bound-methods. 9266498Snate@binkert.org 9276498Snate@binkert.org<p> 9286498Snate@binkert.orgWhen using the <tt>module</tt> option to <tt>lex()</tt>, PLY collects symbols 9296498Snate@binkert.orgfrom the underlying object using the <tt>dir()</tt> function. There is no 9306498Snate@binkert.orgdirect access to the <tt>__dict__</tt> attribute of the object supplied as a 9316498Snate@binkert.orgmodule value. 9326498Snate@binkert.org 9336498Snate@binkert.org<P> 9346498Snate@binkert.orgFinally, if you want to keep things nicely encapsulated, but don't want to use a 9356498Snate@binkert.orgfull-fledged class definition, lexers can be defined using closures. For example: 9366498Snate@binkert.org 9376498Snate@binkert.org<blockquote> 9386498Snate@binkert.org<pre> 9396498Snate@binkert.orgimport ply.lex as lex 9406498Snate@binkert.org 9416498Snate@binkert.org# List of token names. This is always required 9426498Snate@binkert.orgtokens = ( 9436498Snate@binkert.org 'NUMBER', 9446498Snate@binkert.org 'PLUS', 9456498Snate@binkert.org 'MINUS', 9466498Snate@binkert.org 'TIMES', 9476498Snate@binkert.org 'DIVIDE', 9486498Snate@binkert.org 'LPAREN', 9496498Snate@binkert.org 'RPAREN', 9506498Snate@binkert.org) 9516498Snate@binkert.org 9526498Snate@binkert.orgdef MyLexer(): 9536498Snate@binkert.org # Regular expression rules for simple tokens 9546498Snate@binkert.org t_PLUS = r'\+' 9556498Snate@binkert.org t_MINUS = r'-' 9566498Snate@binkert.org t_TIMES = r'\*' 9576498Snate@binkert.org t_DIVIDE = r'/' 9586498Snate@binkert.org t_LPAREN = r'\(' 9596498Snate@binkert.org t_RPAREN = r'\)' 9606498Snate@binkert.org 9616498Snate@binkert.org # A regular expression rule with some action code 9626498Snate@binkert.org def t_NUMBER(t): 9636498Snate@binkert.org r'\d+' 9646498Snate@binkert.org t.value = int(t.value) 9656498Snate@binkert.org return t 9666498Snate@binkert.org 9676498Snate@binkert.org # Define a rule so we can track line numbers 9686498Snate@binkert.org def t_newline(t): 9696498Snate@binkert.org r'\n+' 9706498Snate@binkert.org t.lexer.lineno += len(t.value) 9716498Snate@binkert.org 9726498Snate@binkert.org # A string containing ignored characters (spaces and tabs) 9736498Snate@binkert.org t_ignore = ' \t' 9746498Snate@binkert.org 9756498Snate@binkert.org # Error handling rule 9766498Snate@binkert.org def t_error(t): 9776498Snate@binkert.org print "Illegal character '%s'" % t.value[0] 9786498Snate@binkert.org t.lexer.skip(1) 9796498Snate@binkert.org 9806498Snate@binkert.org # Build the lexer from my environment and return it 9816498Snate@binkert.org return lex.lex() 9826498Snate@binkert.org</pre> 9836498Snate@binkert.org</blockquote> 9846498Snate@binkert.org 9856498Snate@binkert.org 9866498Snate@binkert.org<H3><a name="ply_nn18"></a>4.15 Maintaining state</H3> 9876498Snate@binkert.org 9886498Snate@binkert.org 9896498Snate@binkert.orgIn your lexer, you may want to maintain a variety of state 9906498Snate@binkert.orginformation. This might include mode settings, symbol tables, and 9916498Snate@binkert.orgother details. As an example, suppose that you wanted to keep 9926498Snate@binkert.orgtrack of how many NUMBER tokens had been encountered. 9936498Snate@binkert.org 9946498Snate@binkert.org<p> 9956498Snate@binkert.orgOne way to do this is to keep a set of global variables in the module 9966498Snate@binkert.orgwhere you created the lexer. For example: 9974479Sbinkertn@umich.edu 9984479Sbinkertn@umich.edu<blockquote> 9994479Sbinkertn@umich.edu<pre> 10004479Sbinkertn@umich.edunum_count = 0 10014479Sbinkertn@umich.edudef t_NUMBER(t): 10024479Sbinkertn@umich.edu r'\d+' 10034479Sbinkertn@umich.edu global num_count 10044479Sbinkertn@umich.edu num_count += 1 10056498Snate@binkert.org t.value = int(t.value) 10064479Sbinkertn@umich.edu return t 10074479Sbinkertn@umich.edu</pre> 10084479Sbinkertn@umich.edu</blockquote> 10094479Sbinkertn@umich.edu 10106498Snate@binkert.orgIf you don't like the use of a global variable, another place to store 10116498Snate@binkert.orginformation is inside the Lexer object created by <tt>lex()</tt>. 10126498Snate@binkert.orgTo this, you can use the <tt>lexer</tt> attribute of tokens passed to 10136498Snate@binkert.orgthe various rules. For example: 10144479Sbinkertn@umich.edu 10154479Sbinkertn@umich.edu<blockquote> 10164479Sbinkertn@umich.edu<pre> 10174479Sbinkertn@umich.edudef t_NUMBER(t): 10184479Sbinkertn@umich.edu r'\d+' 10194479Sbinkertn@umich.edu t.lexer.num_count += 1 # Note use of lexer attribute 10206498Snate@binkert.org t.value = int(t.value) 10214479Sbinkertn@umich.edu return t 10224479Sbinkertn@umich.edu 10234479Sbinkertn@umich.edulexer = lex.lex() 10244479Sbinkertn@umich.edulexer.num_count = 0 # Set the initial count 10254479Sbinkertn@umich.edu</pre> 10264479Sbinkertn@umich.edu</blockquote> 10274479Sbinkertn@umich.edu 10286498Snate@binkert.orgThis latter approach has the advantage of being simple and working 10296498Snate@binkert.orgcorrectly in applications where multiple instantiations of a given 10306498Snate@binkert.orglexer exist in the same application. However, this might also feel 10316498Snate@binkert.orglike a gross violation of encapsulation to OO purists. 10326498Snate@binkert.orgJust to put your mind at some ease, all 10334479Sbinkertn@umich.eduinternal attributes of the lexer (with the exception of <tt>lineno</tt>) have names that are prefixed 10344479Sbinkertn@umich.eduby <tt>lex</tt> (e.g., <tt>lexdata</tt>,<tt>lexpos</tt>, etc.). Thus, 10356498Snate@binkert.orgit is perfectly safe to store attributes in the lexer that 10366498Snate@binkert.orgdon't have names starting with that prefix or a name that conlicts with one of the 10376498Snate@binkert.orgpredefined methods (e.g., <tt>input()</tt>, <tt>token()</tt>, etc.). 10384479Sbinkertn@umich.edu 10394479Sbinkertn@umich.edu<p> 10406498Snate@binkert.orgIf you don't like assigning values on the lexer object, you can define your lexer as a class as 10416498Snate@binkert.orgshown in the previous section: 10424479Sbinkertn@umich.edu 10434479Sbinkertn@umich.edu<blockquote> 10444479Sbinkertn@umich.edu<pre> 10454479Sbinkertn@umich.educlass MyLexer: 10464479Sbinkertn@umich.edu ... 10474479Sbinkertn@umich.edu def t_NUMBER(self,t): 10484479Sbinkertn@umich.edu r'\d+' 10494479Sbinkertn@umich.edu self.num_count += 1 10506498Snate@binkert.org t.value = int(t.value) 10514479Sbinkertn@umich.edu return t 10524479Sbinkertn@umich.edu 10534479Sbinkertn@umich.edu def build(self, **kwargs): 10544479Sbinkertn@umich.edu self.lexer = lex.lex(object=self,**kwargs) 10554479Sbinkertn@umich.edu 10564479Sbinkertn@umich.edu def __init__(self): 10574479Sbinkertn@umich.edu self.num_count = 0 10584479Sbinkertn@umich.edu</pre> 10594479Sbinkertn@umich.edu</blockquote> 10604479Sbinkertn@umich.edu 10616498Snate@binkert.orgThe class approach may be the easiest to manage if your application is 10626498Snate@binkert.orggoing to be creating multiple instances of the same lexer and you need 10636498Snate@binkert.orgto manage a lot of state. 10644479Sbinkertn@umich.edu 10654479Sbinkertn@umich.edu<p> 10666498Snate@binkert.orgState can also be managed through closures. For example, in Python 3: 10676498Snate@binkert.org 10686498Snate@binkert.org<blockquote> 10696498Snate@binkert.org<pre> 10706498Snate@binkert.orgdef MyLexer(): 10716498Snate@binkert.org num_count = 0 10726498Snate@binkert.org ... 10736498Snate@binkert.org def t_NUMBER(t): 10746498Snate@binkert.org r'\d+' 10756498Snate@binkert.org nonlocal num_count 10766498Snate@binkert.org num_count += 1 10776498Snate@binkert.org t.value = int(t.value) 10786498Snate@binkert.org return t 10796498Snate@binkert.org ... 10806498Snate@binkert.org</pre> 10816498Snate@binkert.org</blockquote> 10826498Snate@binkert.org 10836498Snate@binkert.org<H3><a name="ply_nn19"></a>4.16 Lexer cloning</H3> 10846498Snate@binkert.org 10856498Snate@binkert.org 10866498Snate@binkert.org<p> 10876498Snate@binkert.orgIf necessary, a lexer object can be duplicated by invoking its <tt>clone()</tt> method. For example: 10884479Sbinkertn@umich.edu 10894479Sbinkertn@umich.edu<blockquote> 10904479Sbinkertn@umich.edu<pre> 10914479Sbinkertn@umich.edulexer = lex.lex() 10924479Sbinkertn@umich.edu... 10934479Sbinkertn@umich.edunewlexer = lexer.clone() 10944479Sbinkertn@umich.edu</pre> 10954479Sbinkertn@umich.edu</blockquote> 10964479Sbinkertn@umich.edu 10976498Snate@binkert.orgWhen a lexer is cloned, the copy is exactly identical to the original lexer 10986498Snate@binkert.orgincluding any input text and internal state. However, the clone allows a 10996498Snate@binkert.orgdifferent set of input text to be supplied which may be processed separately. 11006498Snate@binkert.orgThis may be useful in situations when you are writing a parser/compiler that 11014479Sbinkertn@umich.eduinvolves recursive or reentrant processing. For instance, if you 11024479Sbinkertn@umich.eduneeded to scan ahead in the input for some reason, you could create a 11036498Snate@binkert.orgclone and use it to look ahead. Or, if you were implementing some kind of preprocessor, 11046498Snate@binkert.orgcloned lexers could be used to handle different input files. 11054479Sbinkertn@umich.edu 11064479Sbinkertn@umich.edu<p> 11076498Snate@binkert.orgCreating a clone is different than calling <tt>lex.lex()</tt> in that 11086498Snate@binkert.orgPLY doesn't regenerate any of the internal tables or regular expressions. So, 11094479Sbinkertn@umich.edu 11104479Sbinkertn@umich.edu<p> 11116498Snate@binkert.orgSpecial considerations need to be made when cloning lexers that also 11126498Snate@binkert.orgmaintain their own internal state using classes or closures. Namely, 11136498Snate@binkert.orgyou need to be aware that the newly created lexers will share all of 11146498Snate@binkert.orgthis state with the original lexer. For example, if you defined a 11156498Snate@binkert.orglexer as a class and did this: 11164479Sbinkertn@umich.edu 11174479Sbinkertn@umich.edu<blockquote> 11184479Sbinkertn@umich.edu<pre> 11194479Sbinkertn@umich.edum = MyLexer() 11204479Sbinkertn@umich.edua = lex.lex(object=m) # Create a lexer 11214479Sbinkertn@umich.edu 11224479Sbinkertn@umich.edub = a.clone() # Clone the lexer 11234479Sbinkertn@umich.edu</pre> 11244479Sbinkertn@umich.edu</blockquote> 11254479Sbinkertn@umich.edu 11264479Sbinkertn@umich.eduThen both <tt>a</tt> and <tt>b</tt> are going to be bound to the same 11276498Snate@binkert.orgobject <tt>m</tt> and any changes to <tt>m</tt> will be reflected in both lexers. It's 11286498Snate@binkert.orgimportant to emphasize that <tt>clone()</tt> is only meant to create a new lexer 11296498Snate@binkert.orgthat reuses the regular expressions and environment of another lexer. If you 11306498Snate@binkert.orgneed to make a totally new copy of a lexer, then call <tt>lex()</tt> again. 11316498Snate@binkert.org 11326498Snate@binkert.org<H3><a name="ply_nn20"></a>4.17 Internal lexer state</H3> 11334479Sbinkertn@umich.edu 11344479Sbinkertn@umich.edu 11354479Sbinkertn@umich.eduA Lexer object <tt>lexer</tt> has a number of internal attributes that may be useful in certain 11364479Sbinkertn@umich.edusituations. 11374479Sbinkertn@umich.edu 11384479Sbinkertn@umich.edu<p> 11394479Sbinkertn@umich.edu<tt>lexer.lexpos</tt> 11404479Sbinkertn@umich.edu<blockquote> 11414479Sbinkertn@umich.eduThis attribute is an integer that contains the current position within the input text. If you modify 11424479Sbinkertn@umich.eduthe value, it will change the result of the next call to <tt>token()</tt>. Within token rule functions, this points 11434479Sbinkertn@umich.eduto the first character <em>after</em> the matched text. If the value is modified within a rule, the next returned token will be 11444479Sbinkertn@umich.edumatched at the new position. 11454479Sbinkertn@umich.edu</blockquote> 11464479Sbinkertn@umich.edu 11474479Sbinkertn@umich.edu<p> 11484479Sbinkertn@umich.edu<tt>lexer.lineno</tt> 11494479Sbinkertn@umich.edu<blockquote> 11506498Snate@binkert.orgThe current value of the line number attribute stored in the lexer. PLY only specifies that the attribute 11516498Snate@binkert.orgexists---it never sets, updates, or performs any processing with it. If you want to track line numbers, 11526498Snate@binkert.orgyou will need to add code yourself (see the section on line numbers and positional information). 11534479Sbinkertn@umich.edu</blockquote> 11544479Sbinkertn@umich.edu 11554479Sbinkertn@umich.edu<p> 11564479Sbinkertn@umich.edu<tt>lexer.lexdata</tt> 11574479Sbinkertn@umich.edu<blockquote> 11584479Sbinkertn@umich.eduThe current input text stored in the lexer. This is the string passed with the <tt>input()</tt> method. It 11594479Sbinkertn@umich.eduwould probably be a bad idea to modify this unless you really know what you're doing. 11604479Sbinkertn@umich.edu</blockquote> 11614479Sbinkertn@umich.edu 11624479Sbinkertn@umich.edu<P> 11634479Sbinkertn@umich.edu<tt>lexer.lexmatch</tt> 11644479Sbinkertn@umich.edu<blockquote> 11654479Sbinkertn@umich.eduThis is the raw <tt>Match</tt> object returned by the Python <tt>re.match()</tt> function (used internally by PLY) for the 11664479Sbinkertn@umich.educurrent token. If you have written a regular expression that contains named groups, you can use this to retrieve those values. 11676498Snate@binkert.orgNote: This attribute is only updated when tokens are defined and processed by functions. 11684479Sbinkertn@umich.edu</blockquote> 11694479Sbinkertn@umich.edu 11706498Snate@binkert.org<H3><a name="ply_nn21"></a>4.18 Conditional lexing and start conditions</H3> 11714479Sbinkertn@umich.edu 11724479Sbinkertn@umich.edu 11734479Sbinkertn@umich.eduIn advanced parsing applications, it may be useful to have different 11744479Sbinkertn@umich.edulexing states. For instance, you may want the occurrence of a certain 11754479Sbinkertn@umich.edutoken or syntactic construct to trigger a different kind of lexing. 11764479Sbinkertn@umich.eduPLY supports a feature that allows the underlying lexer to be put into 11774479Sbinkertn@umich.edua series of different states. Each state can have its own tokens, 11784479Sbinkertn@umich.edulexing rules, and so forth. The implementation is based largely on 11794479Sbinkertn@umich.eduthe "start condition" feature of GNU flex. Details of this can be found 11804479Sbinkertn@umich.eduat <a 11814479Sbinkertn@umich.eduhref="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>. 11824479Sbinkertn@umich.edu 11834479Sbinkertn@umich.edu<p> 11844479Sbinkertn@umich.eduTo define a new lexing state, it must first be declared. This is done by including a "states" declaration in your 11854479Sbinkertn@umich.edulex file. For example: 11864479Sbinkertn@umich.edu 11874479Sbinkertn@umich.edu<blockquote> 11884479Sbinkertn@umich.edu<pre> 11894479Sbinkertn@umich.edustates = ( 11904479Sbinkertn@umich.edu ('foo','exclusive'), 11914479Sbinkertn@umich.edu ('bar','inclusive'), 11924479Sbinkertn@umich.edu) 11934479Sbinkertn@umich.edu</pre> 11944479Sbinkertn@umich.edu</blockquote> 11954479Sbinkertn@umich.edu 11964479Sbinkertn@umich.eduThis declaration declares two states, <tt>'foo'</tt> 11974479Sbinkertn@umich.eduand <tt>'bar'</tt>. States may be of two types; <tt>'exclusive'</tt> 11984479Sbinkertn@umich.eduand <tt>'inclusive'</tt>. An exclusive state completely overrides the 11994479Sbinkertn@umich.edudefault behavior of the lexer. That is, lex will only return tokens 12004479Sbinkertn@umich.eduand apply rules defined specifically for that state. An inclusive 12014479Sbinkertn@umich.edustate adds additional tokens and rules to the default set of rules. 12024479Sbinkertn@umich.eduThus, lex will return both the tokens defined by default in addition 12034479Sbinkertn@umich.eduto those defined for the inclusive state. 12044479Sbinkertn@umich.edu 12054479Sbinkertn@umich.edu<p> 12064479Sbinkertn@umich.eduOnce a state has been declared, tokens and rules are declared by including the 12074479Sbinkertn@umich.edustate name in token/rule declaration. For example: 12084479Sbinkertn@umich.edu 12094479Sbinkertn@umich.edu<blockquote> 12104479Sbinkertn@umich.edu<pre> 12114479Sbinkertn@umich.edut_foo_NUMBER = r'\d+' # Token 'NUMBER' in state 'foo' 12124479Sbinkertn@umich.edut_bar_ID = r'[a-zA-Z_][a-zA-Z0-9_]*' # Token 'ID' in state 'bar' 12134479Sbinkertn@umich.edu 12144479Sbinkertn@umich.edudef t_foo_newline(t): 12154479Sbinkertn@umich.edu r'\n' 12164479Sbinkertn@umich.edu t.lexer.lineno += 1 12174479Sbinkertn@umich.edu</pre> 12184479Sbinkertn@umich.edu</blockquote> 12194479Sbinkertn@umich.edu 12204479Sbinkertn@umich.eduA token can be declared in multiple states by including multiple state names in the declaration. For example: 12214479Sbinkertn@umich.edu 12224479Sbinkertn@umich.edu<blockquote> 12234479Sbinkertn@umich.edu<pre> 12244479Sbinkertn@umich.edut_foo_bar_NUMBER = r'\d+' # Defines token 'NUMBER' in both state 'foo' and 'bar' 12254479Sbinkertn@umich.edu</pre> 12264479Sbinkertn@umich.edu</blockquote> 12274479Sbinkertn@umich.edu 12284479Sbinkertn@umich.eduAlternative, a token can be declared in all states using the 'ANY' in the name. 12294479Sbinkertn@umich.edu 12304479Sbinkertn@umich.edu<blockquote> 12314479Sbinkertn@umich.edu<pre> 12324479Sbinkertn@umich.edut_ANY_NUMBER = r'\d+' # Defines a token 'NUMBER' in all states 12334479Sbinkertn@umich.edu</pre> 12344479Sbinkertn@umich.edu</blockquote> 12354479Sbinkertn@umich.edu 12364479Sbinkertn@umich.eduIf no state name is supplied, as is normally the case, the token is associated with a special state <tt>'INITIAL'</tt>. For example, 12374479Sbinkertn@umich.eduthese two declarations are identical: 12384479Sbinkertn@umich.edu 12394479Sbinkertn@umich.edu<blockquote> 12404479Sbinkertn@umich.edu<pre> 12414479Sbinkertn@umich.edut_NUMBER = r'\d+' 12424479Sbinkertn@umich.edut_INITIAL_NUMBER = r'\d+' 12434479Sbinkertn@umich.edu</pre> 12444479Sbinkertn@umich.edu</blockquote> 12454479Sbinkertn@umich.edu 12464479Sbinkertn@umich.edu<p> 12474479Sbinkertn@umich.eduStates are also associated with the special <tt>t_ignore</tt> and <tt>t_error()</tt> declarations. For example, if a state treats 12484479Sbinkertn@umich.eduthese differently, you can declare: 12494479Sbinkertn@umich.edu 12504479Sbinkertn@umich.edu<blockquote> 12514479Sbinkertn@umich.edu<pre> 12524479Sbinkertn@umich.edut_foo_ignore = " \t\n" # Ignored characters for state 'foo' 12534479Sbinkertn@umich.edu 12544479Sbinkertn@umich.edudef t_bar_error(t): # Special error handler for state 'bar' 12554479Sbinkertn@umich.edu pass 12564479Sbinkertn@umich.edu</pre> 12574479Sbinkertn@umich.edu</blockquote> 12584479Sbinkertn@umich.edu 12594479Sbinkertn@umich.eduBy default, lexing operates in the <tt>'INITIAL'</tt> state. This state includes all of the normally defined tokens. 12604479Sbinkertn@umich.eduFor users who aren't using different states, this fact is completely transparent. If, during lexing or parsing, you want to change 12614479Sbinkertn@umich.eduthe lexing state, use the <tt>begin()</tt> method. For example: 12624479Sbinkertn@umich.edu 12634479Sbinkertn@umich.edu<blockquote> 12644479Sbinkertn@umich.edu<pre> 12654479Sbinkertn@umich.edudef t_begin_foo(t): 12664479Sbinkertn@umich.edu r'start_foo' 12674479Sbinkertn@umich.edu t.lexer.begin('foo') # Starts 'foo' state 12684479Sbinkertn@umich.edu</pre> 12694479Sbinkertn@umich.edu</blockquote> 12704479Sbinkertn@umich.edu 12714479Sbinkertn@umich.eduTo get out of a state, you use <tt>begin()</tt> to switch back to the initial state. For example: 12724479Sbinkertn@umich.edu 12734479Sbinkertn@umich.edu<blockquote> 12744479Sbinkertn@umich.edu<pre> 12754479Sbinkertn@umich.edudef t_foo_end(t): 12764479Sbinkertn@umich.edu r'end_foo' 12774479Sbinkertn@umich.edu t.lexer.begin('INITIAL') # Back to the initial state 12784479Sbinkertn@umich.edu</pre> 12794479Sbinkertn@umich.edu</blockquote> 12804479Sbinkertn@umich.edu 12814479Sbinkertn@umich.eduThe management of states can also be done with a stack. For example: 12824479Sbinkertn@umich.edu 12834479Sbinkertn@umich.edu<blockquote> 12844479Sbinkertn@umich.edu<pre> 12854479Sbinkertn@umich.edudef t_begin_foo(t): 12864479Sbinkertn@umich.edu r'start_foo' 12874479Sbinkertn@umich.edu t.lexer.push_state('foo') # Starts 'foo' state 12884479Sbinkertn@umich.edu 12894479Sbinkertn@umich.edudef t_foo_end(t): 12904479Sbinkertn@umich.edu r'end_foo' 12914479Sbinkertn@umich.edu t.lexer.pop_state() # Back to the previous state 12924479Sbinkertn@umich.edu</pre> 12934479Sbinkertn@umich.edu</blockquote> 12944479Sbinkertn@umich.edu 12954479Sbinkertn@umich.edu<p> 12964479Sbinkertn@umich.eduThe 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 12974479Sbinkertn@umich.eduto the previous state afterwards. 12984479Sbinkertn@umich.edu 12994479Sbinkertn@umich.edu<P> 13004479Sbinkertn@umich.eduAn example might help clarify. Suppose you were writing a parser and you wanted to grab sections of arbitrary C code enclosed by 13014479Sbinkertn@umich.educurly braces. That is, whenever you encounter a starting brace '{', you want to read all of the enclosed code up to the ending brace '}' 13024479Sbinkertn@umich.eduand return it as a string. Doing this with a normal regular expression rule is nearly (if not actually) impossible. This is because braces can 13034479Sbinkertn@umich.edube 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 13044479Sbinkertn@umich.eduyou might use lexer states to do this: 13054479Sbinkertn@umich.edu 13064479Sbinkertn@umich.edu<blockquote> 13074479Sbinkertn@umich.edu<pre> 13084479Sbinkertn@umich.edu# Declare the state 13094479Sbinkertn@umich.edustates = ( 13104479Sbinkertn@umich.edu ('ccode','exclusive'), 13114479Sbinkertn@umich.edu) 13124479Sbinkertn@umich.edu 13134479Sbinkertn@umich.edu# Match the first {. Enter ccode state. 13144479Sbinkertn@umich.edudef t_ccode(t): 13154479Sbinkertn@umich.edu r'\{' 13164479Sbinkertn@umich.edu t.lexer.code_start = t.lexer.lexpos # Record the starting position 13174479Sbinkertn@umich.edu t.lexer.level = 1 # Initial brace level 13184479Sbinkertn@umich.edu t.lexer.begin('ccode') # Enter 'ccode' state 13194479Sbinkertn@umich.edu 13204479Sbinkertn@umich.edu# Rules for the ccode state 13214479Sbinkertn@umich.edudef t_ccode_lbrace(t): 13224479Sbinkertn@umich.edu r'\{' 13234479Sbinkertn@umich.edu t.lexer.level +=1 13244479Sbinkertn@umich.edu 13254479Sbinkertn@umich.edudef t_ccode_rbrace(t): 13264479Sbinkertn@umich.edu r'\}' 13274479Sbinkertn@umich.edu t.lexer.level -=1 13284479Sbinkertn@umich.edu 13294479Sbinkertn@umich.edu # If closing brace, return the code fragment 13304479Sbinkertn@umich.edu if t.lexer.level == 0: 13314479Sbinkertn@umich.edu t.value = t.lexer.lexdata[t.lexer.code_start:t.lexer.lexpos+1] 13324479Sbinkertn@umich.edu t.type = "CCODE" 13334479Sbinkertn@umich.edu t.lexer.lineno += t.value.count('\n') 13344479Sbinkertn@umich.edu t.lexer.begin('INITIAL') 13354479Sbinkertn@umich.edu return t 13364479Sbinkertn@umich.edu 13374479Sbinkertn@umich.edu# C or C++ comment (ignore) 13384479Sbinkertn@umich.edudef t_ccode_comment(t): 13394479Sbinkertn@umich.edu r'(/\*(.|\n)*?*/)|(//.*)' 13404479Sbinkertn@umich.edu pass 13414479Sbinkertn@umich.edu 13424479Sbinkertn@umich.edu# C string 13434479Sbinkertn@umich.edudef t_ccode_string(t): 13444479Sbinkertn@umich.edu r'\"([^\\\n]|(\\.))*?\"' 13454479Sbinkertn@umich.edu 13464479Sbinkertn@umich.edu# C character literal 13474479Sbinkertn@umich.edudef t_ccode_char(t): 13484479Sbinkertn@umich.edu r'\'([^\\\n]|(\\.))*?\'' 13494479Sbinkertn@umich.edu 13504479Sbinkertn@umich.edu# Any sequence of non-whitespace characters (not braces, strings) 13514479Sbinkertn@umich.edudef t_ccode_nonspace(t): 13524479Sbinkertn@umich.edu r'[^\s\{\}\'\"]+' 13534479Sbinkertn@umich.edu 13544479Sbinkertn@umich.edu# Ignored characters (whitespace) 13554479Sbinkertn@umich.edut_ccode_ignore = " \t\n" 13564479Sbinkertn@umich.edu 13574479Sbinkertn@umich.edu# For bad characters, we just skip over it 13584479Sbinkertn@umich.edudef t_ccode_error(t): 13594479Sbinkertn@umich.edu t.lexer.skip(1) 13604479Sbinkertn@umich.edu</pre> 13614479Sbinkertn@umich.edu</blockquote> 13624479Sbinkertn@umich.edu 13634479Sbinkertn@umich.eduIn 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 13644479Sbinkertn@umich.eduvarious parts of the input that follow (comments, strings, etc.). All of these rules merely discard the token (by not returning a value). 13654479Sbinkertn@umich.eduHowever, if the closing right brace is encountered, the rule <tt>t_ccode_rbrace</tt> collects all of the code (using the earlier recorded starting 13664479Sbinkertn@umich.eduposition), stores it, and returns a token 'CCODE' containing all of that text. When returning the token, the lexing state is restored back to its 13674479Sbinkertn@umich.eduinitial state. 13684479Sbinkertn@umich.edu 13696498Snate@binkert.org<H3><a name="ply_nn21"></a>4.19 Miscellaneous Issues</H3> 13704479Sbinkertn@umich.edu 13714479Sbinkertn@umich.edu 13724479Sbinkertn@umich.edu<P> 13734479Sbinkertn@umich.edu<li>The lexer requires input to be supplied as a single input string. Since most machines have more than enough memory, this 13744479Sbinkertn@umich.edurarely presents a performance concern. However, it means that the lexer currently can't be used with streaming data 13754479Sbinkertn@umich.edusuch as open files or sockets. This limitation is primarily a side-effect of using the <tt>re</tt> module. 13764479Sbinkertn@umich.edu 13774479Sbinkertn@umich.edu<p> 13784479Sbinkertn@umich.edu<li>The lexer should work properly with both Unicode strings given as token and pattern matching rules as 13794479Sbinkertn@umich.eduwell as for input text. 13804479Sbinkertn@umich.edu 13814479Sbinkertn@umich.edu<p> 13824479Sbinkertn@umich.edu<li>If you need to supply optional flags to the re.compile() function, use the reflags option to lex. For example: 13834479Sbinkertn@umich.edu 13844479Sbinkertn@umich.edu<blockquote> 13854479Sbinkertn@umich.edu<pre> 13864479Sbinkertn@umich.edulex.lex(reflags=re.UNICODE) 13874479Sbinkertn@umich.edu</pre> 13884479Sbinkertn@umich.edu</blockquote> 13892632Sstever@eecs.umich.edu 13902632Sstever@eecs.umich.edu<p> 13912632Sstever@eecs.umich.edu<li>Since the lexer is written entirely in Python, its performance is 13922632Sstever@eecs.umich.edulargely determined by that of the Python <tt>re</tt> module. Although 13932632Sstever@eecs.umich.eduthe lexer has been written to be as efficient as possible, it's not 13944479Sbinkertn@umich.edublazingly fast when used on very large input files. If 13952632Sstever@eecs.umich.eduperformance is concern, you might consider upgrading to the most 13962632Sstever@eecs.umich.edurecent version of Python, creating a hand-written lexer, or offloading 13974479Sbinkertn@umich.eduthe lexer into a C extension module. 13984479Sbinkertn@umich.edu 13994479Sbinkertn@umich.edu<p> 14004479Sbinkertn@umich.eduIf you are going to create a hand-written lexer and you plan to use it with <tt>yacc.py</tt>, 14014479Sbinkertn@umich.eduit only needs to conform to the following requirements: 14024479Sbinkertn@umich.edu 14034479Sbinkertn@umich.edu<ul> 14044479Sbinkertn@umich.edu<li>It must provide a <tt>token()</tt> method that returns the next token or <tt>None</tt> if no more 14054479Sbinkertn@umich.edutokens are available. 14064479Sbinkertn@umich.edu<li>The <tt>token()</tt> method must return an object <tt>tok</tt> that has <tt>type</tt> and <tt>value</tt> attributes. 14072632Sstever@eecs.umich.edu</ul> 14082632Sstever@eecs.umich.edu 14096498Snate@binkert.org<H2><a name="ply_nn22"></a>5. Parsing basics</H2> 14104479Sbinkertn@umich.edu 14112632Sstever@eecs.umich.edu 14122632Sstever@eecs.umich.edu<tt>yacc.py</tt> is used to parse language syntax. Before showing an 14132632Sstever@eecs.umich.eduexample, there are a few important bits of background that must be 14144479Sbinkertn@umich.edumentioned. First, <em>syntax</em> is usually specified in terms of a BNF grammar. 14154479Sbinkertn@umich.eduFor example, if you wanted to parse 14162632Sstever@eecs.umich.edusimple arithmetic expressions, you might first write an unambiguous 14172632Sstever@eecs.umich.edugrammar specification like this: 14182632Sstever@eecs.umich.edu 14192632Sstever@eecs.umich.edu<blockquote> 14202632Sstever@eecs.umich.edu<pre> 14212632Sstever@eecs.umich.eduexpression : expression + term 14222632Sstever@eecs.umich.edu | expression - term 14232632Sstever@eecs.umich.edu | term 14242632Sstever@eecs.umich.edu 14252632Sstever@eecs.umich.eduterm : term * factor 14262632Sstever@eecs.umich.edu | term / factor 14272632Sstever@eecs.umich.edu | factor 14282632Sstever@eecs.umich.edu 14292632Sstever@eecs.umich.edufactor : NUMBER 14302632Sstever@eecs.umich.edu | ( expression ) 14312632Sstever@eecs.umich.edu</pre> 14322632Sstever@eecs.umich.edu</blockquote> 14332632Sstever@eecs.umich.edu 14344479Sbinkertn@umich.eduIn the grammar, symbols such as <tt>NUMBER</tt>, <tt>+</tt>, <tt>-</tt>, <tt>*</tt>, and <tt>/</tt> are known 14356498Snate@binkert.orgas <em>terminals</em> and correspond to raw input tokens. Identifiers such as <tt>term</tt> and <tt>factor</tt> refer to 14366498Snate@binkert.orggrammar rules comprised of a collection of terminals and other rules. These identifiers are known as <em>non-terminals</em>. 14374479Sbinkertn@umich.edu<P> 14386498Snate@binkert.org 14394479Sbinkertn@umich.eduThe semantic behavior of a language is often specified using a 14402632Sstever@eecs.umich.edutechnique known as syntax directed translation. In syntax directed 14412632Sstever@eecs.umich.edutranslation, attributes are attached to each symbol in a given grammar 14422632Sstever@eecs.umich.edurule along with an action. Whenever a particular grammar rule is 14432632Sstever@eecs.umich.edurecognized, the action describes what to do. For example, given the 14442632Sstever@eecs.umich.eduexpression grammar above, you might write the specification for a 14452632Sstever@eecs.umich.edusimple calculator like this: 14462632Sstever@eecs.umich.edu 14472632Sstever@eecs.umich.edu<blockquote> 14482632Sstever@eecs.umich.edu<pre> 14492632Sstever@eecs.umich.eduGrammar Action 14502632Sstever@eecs.umich.edu-------------------------------- -------------------------------------------- 14512632Sstever@eecs.umich.eduexpression0 : expression1 + term expression0.val = expression1.val + term.val 14522632Sstever@eecs.umich.edu | expression1 - term expression0.val = expression1.val - term.val 14532632Sstever@eecs.umich.edu | term expression0.val = term.val 14542632Sstever@eecs.umich.edu 14552632Sstever@eecs.umich.eduterm0 : term1 * factor term0.val = term1.val * factor.val 14562632Sstever@eecs.umich.edu | term1 / factor term0.val = term1.val / factor.val 14572632Sstever@eecs.umich.edu | factor term0.val = factor.val 14582632Sstever@eecs.umich.edu 14592632Sstever@eecs.umich.edufactor : NUMBER factor.val = int(NUMBER.lexval) 14602632Sstever@eecs.umich.edu | ( expression ) factor.val = expression.val 14612632Sstever@eecs.umich.edu</pre> 14622632Sstever@eecs.umich.edu</blockquote> 14632632Sstever@eecs.umich.edu 14646498Snate@binkert.orgA good way to think about syntax directed translation is to 14656498Snate@binkert.orgview each symbol in the grammar as a kind of object. Associated 14666498Snate@binkert.orgwith each symbol is a value representing its "state" (for example, the 14676498Snate@binkert.org<tt>val</tt> attribute above). Semantic 14686498Snate@binkert.orgactions are then expressed as a collection of functions or methods 14696498Snate@binkert.orgthat operate on the symbols and associated values. 14704479Sbinkertn@umich.edu 14714479Sbinkertn@umich.edu<p> 14724479Sbinkertn@umich.eduYacc uses a parsing technique known as LR-parsing or shift-reduce parsing. LR parsing is a 14732632Sstever@eecs.umich.edubottom up technique that tries to recognize the right-hand-side of various grammar rules. 14742632Sstever@eecs.umich.eduWhenever a valid right-hand-side is found in the input, the appropriate action code is triggered and the 14752632Sstever@eecs.umich.edugrammar symbols are replaced by the grammar symbol on the left-hand-side. 14762632Sstever@eecs.umich.edu 14772632Sstever@eecs.umich.edu<p> 14786498Snate@binkert.orgLR parsing is commonly implemented by shifting grammar symbols onto a 14796498Snate@binkert.orgstack and looking at the stack and the next input token for patterns that 14806498Snate@binkert.orgmatch one of the grammar rules. 14816498Snate@binkert.orgThe details of the algorithm can be found in a compiler textbook, but the 14826498Snate@binkert.orgfollowing example illustrates the steps that are performed if you 14836498Snate@binkert.orgwanted to parse the expression 14846498Snate@binkert.org<tt>3 + 5 * (10 - 20)</tt> using the grammar defined above. In the example, 14856498Snate@binkert.orgthe special symbol <tt>$</tt> represents the end of input. 14866498Snate@binkert.org 14872632Sstever@eecs.umich.edu 14882632Sstever@eecs.umich.edu<blockquote> 14892632Sstever@eecs.umich.edu<pre> 14902632Sstever@eecs.umich.eduStep Symbol Stack Input Tokens Action 14912632Sstever@eecs.umich.edu---- --------------------- --------------------- ------------------------------- 14926498Snate@binkert.org1 3 + 5 * ( 10 - 20 )$ Shift 3 14936498Snate@binkert.org2 3 + 5 * ( 10 - 20 )$ Reduce factor : NUMBER 14946498Snate@binkert.org3 factor + 5 * ( 10 - 20 )$ Reduce term : factor 14956498Snate@binkert.org4 term + 5 * ( 10 - 20 )$ Reduce expr : term 14966498Snate@binkert.org5 expr + 5 * ( 10 - 20 )$ Shift + 14976498Snate@binkert.org6 expr + 5 * ( 10 - 20 )$ Shift 5 14986498Snate@binkert.org7 expr + 5 * ( 10 - 20 )$ Reduce factor : NUMBER 14996498Snate@binkert.org8 expr + factor * ( 10 - 20 )$ Reduce term : factor 15006498Snate@binkert.org9 expr + term * ( 10 - 20 )$ Shift * 15016498Snate@binkert.org10 expr + term * ( 10 - 20 )$ Shift ( 15026498Snate@binkert.org11 expr + term * ( 10 - 20 )$ Shift 10 15036498Snate@binkert.org12 expr + term * ( 10 - 20 )$ Reduce factor : NUMBER 15046498Snate@binkert.org13 expr + term * ( factor - 20 )$ Reduce term : factor 15056498Snate@binkert.org14 expr + term * ( term - 20 )$ Reduce expr : term 15066498Snate@binkert.org15 expr + term * ( expr - 20 )$ Shift - 15076498Snate@binkert.org16 expr + term * ( expr - 20 )$ Shift 20 15086498Snate@binkert.org17 expr + term * ( expr - 20 )$ Reduce factor : NUMBER 15096498Snate@binkert.org18 expr + term * ( expr - factor )$ Reduce term : factor 15106498Snate@binkert.org19 expr + term * ( expr - term )$ Reduce expr : expr - term 15116498Snate@binkert.org20 expr + term * ( expr )$ Shift ) 15126498Snate@binkert.org21 expr + term * ( expr ) $ Reduce factor : (expr) 15136498Snate@binkert.org22 expr + term * factor $ Reduce term : term * factor 15146498Snate@binkert.org23 expr + term $ Reduce expr : expr + term 15156498Snate@binkert.org24 expr $ Reduce expr 15166498Snate@binkert.org25 $ Success! 15172632Sstever@eecs.umich.edu</pre> 15182632Sstever@eecs.umich.edu</blockquote> 15192632Sstever@eecs.umich.edu 15206498Snate@binkert.orgWhen parsing the expression, an underlying state machine and the 15216498Snate@binkert.orgcurrent input token determine what happens next. If the next token 15226498Snate@binkert.orglooks like part of a valid grammar rule (based on other items on the 15236498Snate@binkert.orgstack), it is generally shifted onto the stack. If the top of the 15246498Snate@binkert.orgstack contains a valid right-hand-side of a grammar rule, it is 15256498Snate@binkert.orgusually "reduced" and the symbols replaced with the symbol on the 15266498Snate@binkert.orgleft-hand-side. When this reduction occurs, the appropriate action is 15276498Snate@binkert.orgtriggered (if defined). If the input token can't be shifted and the 15286498Snate@binkert.orgtop of stack doesn't match any grammar rules, a syntax error has 15296498Snate@binkert.orgoccurred and the parser must take some kind of recovery step (or bail 15306498Snate@binkert.orgout). A parse is only successful if the parser reaches a state where 15316498Snate@binkert.orgthe symbol stack is empty and there are no more input tokens. 15322632Sstever@eecs.umich.edu 15332632Sstever@eecs.umich.edu<p> 15346498Snate@binkert.orgIt is important to note that the underlying implementation is built 15356498Snate@binkert.orgaround a large finite-state machine that is encoded in a collection of 15366498Snate@binkert.orgtables. The construction of these tables is non-trivial and 15376498Snate@binkert.orgbeyond the scope of this discussion. However, subtle details of this 15386498Snate@binkert.orgprocess explain why, in the example above, the parser chooses to shift 15396498Snate@binkert.orga token onto the stack in step 9 rather than reducing the 15406498Snate@binkert.orgrule <tt>expr : expr + term</tt>. 15416498Snate@binkert.org 15426498Snate@binkert.org<H2><a name="ply_nn23"></a>6. Yacc</H2> 15436498Snate@binkert.org 15446498Snate@binkert.org 15456498Snate@binkert.orgThe <tt>ply.yacc</tt> module implements the parsing component of PLY. 15466498Snate@binkert.orgThe name "yacc" stands for "Yet Another Compiler Compiler" and is 15476498Snate@binkert.orgborrowed from the Unix tool of the same name. 15486498Snate@binkert.org 15496498Snate@binkert.org<H3><a name="ply_nn24"></a>6.1 An example</H3> 15504479Sbinkertn@umich.edu 15512632Sstever@eecs.umich.edu 15522632Sstever@eecs.umich.eduSuppose you wanted to make a grammar for simple arithmetic expressions as previously described. Here is 15532632Sstever@eecs.umich.eduhow you would do it with <tt>yacc.py</tt>: 15542632Sstever@eecs.umich.edu 15552632Sstever@eecs.umich.edu<blockquote> 15562632Sstever@eecs.umich.edu<pre> 15572632Sstever@eecs.umich.edu# Yacc example 15582632Sstever@eecs.umich.edu 15594479Sbinkertn@umich.eduimport ply.yacc as yacc 15602632Sstever@eecs.umich.edu 15612632Sstever@eecs.umich.edu# Get the token map from the lexer. This is required. 15622632Sstever@eecs.umich.edufrom calclex import tokens 15632632Sstever@eecs.umich.edu 15644479Sbinkertn@umich.edudef p_expression_plus(p): 15652632Sstever@eecs.umich.edu 'expression : expression PLUS term' 15664479Sbinkertn@umich.edu p[0] = p[1] + p[3] 15674479Sbinkertn@umich.edu 15684479Sbinkertn@umich.edudef p_expression_minus(p): 15692632Sstever@eecs.umich.edu 'expression : expression MINUS term' 15704479Sbinkertn@umich.edu p[0] = p[1] - p[3] 15714479Sbinkertn@umich.edu 15724479Sbinkertn@umich.edudef p_expression_term(p): 15732632Sstever@eecs.umich.edu 'expression : term' 15744479Sbinkertn@umich.edu p[0] = p[1] 15754479Sbinkertn@umich.edu 15764479Sbinkertn@umich.edudef p_term_times(p): 15772632Sstever@eecs.umich.edu 'term : term TIMES factor' 15784479Sbinkertn@umich.edu p[0] = p[1] * p[3] 15794479Sbinkertn@umich.edu 15804479Sbinkertn@umich.edudef p_term_div(p): 15812632Sstever@eecs.umich.edu 'term : term DIVIDE factor' 15824479Sbinkertn@umich.edu p[0] = p[1] / p[3] 15834479Sbinkertn@umich.edu 15844479Sbinkertn@umich.edudef p_term_factor(p): 15852632Sstever@eecs.umich.edu 'term : factor' 15864479Sbinkertn@umich.edu p[0] = p[1] 15874479Sbinkertn@umich.edu 15884479Sbinkertn@umich.edudef p_factor_num(p): 15892632Sstever@eecs.umich.edu 'factor : NUMBER' 15904479Sbinkertn@umich.edu p[0] = p[1] 15914479Sbinkertn@umich.edu 15924479Sbinkertn@umich.edudef p_factor_expr(p): 15932632Sstever@eecs.umich.edu 'factor : LPAREN expression RPAREN' 15944479Sbinkertn@umich.edu p[0] = p[2] 15952632Sstever@eecs.umich.edu 15962632Sstever@eecs.umich.edu# Error rule for syntax errors 15974479Sbinkertn@umich.edudef p_error(p): 15982632Sstever@eecs.umich.edu print "Syntax error in input!" 15992632Sstever@eecs.umich.edu 16002632Sstever@eecs.umich.edu# Build the parser 16016498Snate@binkert.orgparser = yacc.yacc() 16026498Snate@binkert.org 16036498Snate@binkert.orgwhile True: 16042632Sstever@eecs.umich.edu try: 16052632Sstever@eecs.umich.edu s = raw_input('calc > ') 16062632Sstever@eecs.umich.edu except EOFError: 16072632Sstever@eecs.umich.edu break 16082632Sstever@eecs.umich.edu if not s: continue 16096498Snate@binkert.org result = parser.parse(s) 16102632Sstever@eecs.umich.edu print result 16112632Sstever@eecs.umich.edu</pre> 16122632Sstever@eecs.umich.edu</blockquote> 16132632Sstever@eecs.umich.edu 16146498Snate@binkert.orgIn this example, each grammar rule is defined by a Python function 16156498Snate@binkert.orgwhere the docstring to that function contains the appropriate 16166498Snate@binkert.orgcontext-free grammar specification. The statements that make up the 16176498Snate@binkert.orgfunction body implement the semantic actions of the rule. Each function 16186498Snate@binkert.orgaccepts a single argument <tt>p</tt> that is a sequence containing the 16196498Snate@binkert.orgvalues of each grammar symbol in the corresponding rule. The values 16206498Snate@binkert.orgof <tt>p[i]</tt> are mapped to grammar symbols as shown here: 16212632Sstever@eecs.umich.edu 16222632Sstever@eecs.umich.edu<blockquote> 16232632Sstever@eecs.umich.edu<pre> 16244479Sbinkertn@umich.edudef p_expression_plus(p): 16252632Sstever@eecs.umich.edu 'expression : expression PLUS term' 16262632Sstever@eecs.umich.edu # ^ ^ ^ ^ 16274479Sbinkertn@umich.edu # p[0] p[1] p[2] p[3] 16284479Sbinkertn@umich.edu 16294479Sbinkertn@umich.edu p[0] = p[1] + p[3] 16302632Sstever@eecs.umich.edu</pre> 16312632Sstever@eecs.umich.edu</blockquote> 16322632Sstever@eecs.umich.edu 16336498Snate@binkert.org<p> 16344479Sbinkertn@umich.eduFor tokens, the "value" of the corresponding <tt>p[i]</tt> is the 16356498Snate@binkert.org<em>same</em> as the <tt>p.value</tt> attribute assigned in the lexer 16366498Snate@binkert.orgmodule. For non-terminals, the value is determined by whatever is 16376498Snate@binkert.orgplaced in <tt>p[0]</tt> when rules are reduced. This value can be 16386498Snate@binkert.organything at all. However, it probably most common for the value to be 16396498Snate@binkert.orga simple Python type, a tuple, or an instance. In this example, we 16406498Snate@binkert.orgare relying on the fact that the <tt>NUMBER</tt> token stores an 16416498Snate@binkert.orginteger value in its value field. All of the other rules simply 16426498Snate@binkert.orgperform various types of integer operations and propagate the result. 16436498Snate@binkert.org</p> 16444479Sbinkertn@umich.edu 16452632Sstever@eecs.umich.edu<p> 16466498Snate@binkert.orgNote: The use of negative indices have a special meaning in 16476498Snate@binkert.orgyacc---specially <tt>p[-1]</tt> does not have the same value 16486498Snate@binkert.orgas <tt>p[3]</tt> in this example. Please see the section on "Embedded 16496498Snate@binkert.orgActions" for further details. 16506498Snate@binkert.org</p> 16516498Snate@binkert.org 16526498Snate@binkert.org<p> 16536498Snate@binkert.orgThe first rule defined in the yacc specification determines the 16546498Snate@binkert.orgstarting grammar symbol (in this case, a rule for <tt>expression</tt> 16556498Snate@binkert.orgappears first). Whenever the starting rule is reduced by the parser 16566498Snate@binkert.organd no more input is available, parsing stops and the final value is 16576498Snate@binkert.orgreturned (this value will be whatever the top-most rule placed 16586498Snate@binkert.orgin <tt>p[0]</tt>). Note: an alternative starting symbol can be 16596498Snate@binkert.orgspecified using the <tt>start</tt> keyword argument to 16604479Sbinkertn@umich.edu<tt>yacc()</tt>. 16614479Sbinkertn@umich.edu 16626498Snate@binkert.org<p>The <tt>p_error(p)</tt> rule is defined to catch syntax errors. 16636498Snate@binkert.orgSee the error handling section below for more detail. 16642632Sstever@eecs.umich.edu 16652632Sstever@eecs.umich.edu<p> 16666498Snate@binkert.orgTo build the parser, call the <tt>yacc.yacc()</tt> function. This 16676498Snate@binkert.orgfunction looks at the module and attempts to construct all of the LR 16686498Snate@binkert.orgparsing tables for the grammar you have specified. The first 16696498Snate@binkert.orgtime <tt>yacc.yacc()</tt> is invoked, you will get a message such as 16706498Snate@binkert.orgthis: 16712632Sstever@eecs.umich.edu 16722632Sstever@eecs.umich.edu<blockquote> 16732632Sstever@eecs.umich.edu<pre> 16742632Sstever@eecs.umich.edu$ python calcparse.py 16756498Snate@binkert.orgGenerating LALR tables 16762632Sstever@eecs.umich.educalc > 16772632Sstever@eecs.umich.edu</pre> 16782632Sstever@eecs.umich.edu</blockquote> 16792632Sstever@eecs.umich.edu 16802632Sstever@eecs.umich.eduSince table construction is relatively expensive (especially for large 16812632Sstever@eecs.umich.edugrammars), the resulting parsing table is written to the current 16822632Sstever@eecs.umich.edudirectory in a file called <tt>parsetab.py</tt>. In addition, a 16832632Sstever@eecs.umich.edudebugging file called <tt>parser.out</tt> is created. On subsequent 16842632Sstever@eecs.umich.eduexecutions, <tt>yacc</tt> will reload the table from 16852632Sstever@eecs.umich.edu<tt>parsetab.py</tt> unless it has detected a change in the underlying 16862632Sstever@eecs.umich.edugrammar (in which case the tables and <tt>parsetab.py</tt> file are 16876498Snate@binkert.orgregenerated). Note: The names of parser output files can be changed 16886498Snate@binkert.orgif necessary. See the <a href="reference.html">PLY Reference</a> for details. 16892632Sstever@eecs.umich.edu 16902632Sstever@eecs.umich.edu<p> 16912632Sstever@eecs.umich.eduIf any errors are detected in your grammar specification, <tt>yacc.py</tt> will produce 16922632Sstever@eecs.umich.edudiagnostic messages and possibly raise an exception. Some of the errors that can be detected include: 16932632Sstever@eecs.umich.edu 16942632Sstever@eecs.umich.edu<ul> 16952632Sstever@eecs.umich.edu<li>Duplicated function names (if more than one rule function have the same name in the grammar file). 16962632Sstever@eecs.umich.edu<li>Shift/reduce and reduce/reduce conflicts generated by ambiguous grammars. 16972632Sstever@eecs.umich.edu<li>Badly specified grammar rules. 16982632Sstever@eecs.umich.edu<li>Infinite recursion (rules that can never terminate). 16992632Sstever@eecs.umich.edu<li>Unused rules and tokens 17002632Sstever@eecs.umich.edu<li>Undefined rules and tokens 17012632Sstever@eecs.umich.edu</ul> 17022632Sstever@eecs.umich.edu 17036498Snate@binkert.orgThe next few sections discuss grammar specification in more detail. 17046498Snate@binkert.org 17056498Snate@binkert.org<p> 17066498Snate@binkert.orgThe final part of the example shows how to actually run the parser 17076498Snate@binkert.orgcreated by 17086498Snate@binkert.org<tt>yacc()</tt>. To run the parser, you simply have to call 17096498Snate@binkert.orgthe <tt>parse()</tt> with a string of input text. This will run all 17106498Snate@binkert.orgof the grammar rules and return the result of the entire parse. This 17116498Snate@binkert.orgresult return is the value assigned to <tt>p[0]</tt> in the starting 17126498Snate@binkert.orggrammar rule. 17136498Snate@binkert.org 17146498Snate@binkert.org<H3><a name="ply_nn25"></a>6.2 Combining Grammar Rule Functions</H3> 17154479Sbinkertn@umich.edu 17162632Sstever@eecs.umich.edu 17172632Sstever@eecs.umich.eduWhen grammar rules are similar, they can be combined into a single function. 17182632Sstever@eecs.umich.eduFor example, consider the two rules in our earlier example: 17192632Sstever@eecs.umich.edu 17202632Sstever@eecs.umich.edu<blockquote> 17212632Sstever@eecs.umich.edu<pre> 17224479Sbinkertn@umich.edudef p_expression_plus(p): 17232632Sstever@eecs.umich.edu 'expression : expression PLUS term' 17244479Sbinkertn@umich.edu p[0] = p[1] + p[3] 17252632Sstever@eecs.umich.edu 17262632Sstever@eecs.umich.edudef p_expression_minus(t): 17272632Sstever@eecs.umich.edu 'expression : expression MINUS term' 17284479Sbinkertn@umich.edu p[0] = p[1] - p[3] 17292632Sstever@eecs.umich.edu</pre> 17302632Sstever@eecs.umich.edu</blockquote> 17312632Sstever@eecs.umich.edu 17322632Sstever@eecs.umich.eduInstead of writing two functions, you might write a single function like this: 17332632Sstever@eecs.umich.edu 17342632Sstever@eecs.umich.edu<blockquote> 17352632Sstever@eecs.umich.edu<pre> 17364479Sbinkertn@umich.edudef p_expression(p): 17372632Sstever@eecs.umich.edu '''expression : expression PLUS term 17382632Sstever@eecs.umich.edu | expression MINUS term''' 17394479Sbinkertn@umich.edu if p[2] == '+': 17404479Sbinkertn@umich.edu p[0] = p[1] + p[3] 17414479Sbinkertn@umich.edu elif p[2] == '-': 17424479Sbinkertn@umich.edu p[0] = p[1] - p[3] 17432632Sstever@eecs.umich.edu</pre> 17442632Sstever@eecs.umich.edu</blockquote> 17452632Sstever@eecs.umich.edu 17462632Sstever@eecs.umich.eduIn general, the doc string for any given function can contain multiple grammar rules. So, it would 17472632Sstever@eecs.umich.eduhave also been legal (although possibly confusing) to write this: 17482632Sstever@eecs.umich.edu 17492632Sstever@eecs.umich.edu<blockquote> 17502632Sstever@eecs.umich.edu<pre> 17514479Sbinkertn@umich.edudef p_binary_operators(p): 17522632Sstever@eecs.umich.edu '''expression : expression PLUS term 17532632Sstever@eecs.umich.edu | expression MINUS term 17542632Sstever@eecs.umich.edu term : term TIMES factor 17552632Sstever@eecs.umich.edu | term DIVIDE factor''' 17564479Sbinkertn@umich.edu if p[2] == '+': 17574479Sbinkertn@umich.edu p[0] = p[1] + p[3] 17584479Sbinkertn@umich.edu elif p[2] == '-': 17594479Sbinkertn@umich.edu p[0] = p[1] - p[3] 17604479Sbinkertn@umich.edu elif p[2] == '*': 17614479Sbinkertn@umich.edu p[0] = p[1] * p[3] 17624479Sbinkertn@umich.edu elif p[2] == '/': 17634479Sbinkertn@umich.edu p[0] = p[1] / p[3] 17642632Sstever@eecs.umich.edu</pre> 17652632Sstever@eecs.umich.edu</blockquote> 17662632Sstever@eecs.umich.edu 17672632Sstever@eecs.umich.eduWhen combining grammar rules into a single function, it is usually a good idea for all of the rules to have 17682632Sstever@eecs.umich.edua similar structure (e.g., the same number of terms). Otherwise, the corresponding action code may be more 17694479Sbinkertn@umich.educomplicated than necessary. However, it is possible to handle simple cases using len(). For example: 17702632Sstever@eecs.umich.edu 17712632Sstever@eecs.umich.edu<blockquote> 17722632Sstever@eecs.umich.edu<pre> 17734479Sbinkertn@umich.edudef p_expressions(p): 17744479Sbinkertn@umich.edu '''expression : expression MINUS expression 17754479Sbinkertn@umich.edu | MINUS expression''' 17764479Sbinkertn@umich.edu if (len(p) == 4): 17774479Sbinkertn@umich.edu p[0] = p[1] - p[3] 17784479Sbinkertn@umich.edu elif (len(p) == 3): 17794479Sbinkertn@umich.edu p[0] = -p[2] 17804479Sbinkertn@umich.edu</pre> 17814479Sbinkertn@umich.edu</blockquote> 17824479Sbinkertn@umich.edu 17836498Snate@binkert.orgIf parsing performance is a concern, you should resist the urge to put 17846498Snate@binkert.orgtoo much conditional processing into a single grammar rule as shown in 17856498Snate@binkert.orgthese examples. When you add checks to see which grammar rule is 17866498Snate@binkert.orgbeing handled, you are actually duplicating the work that the parser 17876498Snate@binkert.orghas already performed (i.e., the parser already knows exactly what rule it 17886498Snate@binkert.orgmatched). You can eliminate this overhead by using a 17896498Snate@binkert.orgseparate <tt>p_rule()</tt> function for each grammar rule. 17906498Snate@binkert.org 17916498Snate@binkert.org<H3><a name="ply_nn26"></a>6.3 Character Literals</H3> 17924479Sbinkertn@umich.edu 17934479Sbinkertn@umich.edu 17944479Sbinkertn@umich.eduIf desired, a grammar may contain tokens defined as single character literals. For example: 17954479Sbinkertn@umich.edu 17964479Sbinkertn@umich.edu<blockquote> 17974479Sbinkertn@umich.edu<pre> 17984479Sbinkertn@umich.edudef p_binary_operators(p): 17994479Sbinkertn@umich.edu '''expression : expression '+' term 18004479Sbinkertn@umich.edu | expression '-' term 18014479Sbinkertn@umich.edu term : term '*' factor 18024479Sbinkertn@umich.edu | term '/' factor''' 18034479Sbinkertn@umich.edu if p[2] == '+': 18044479Sbinkertn@umich.edu p[0] = p[1] + p[3] 18054479Sbinkertn@umich.edu elif p[2] == '-': 18064479Sbinkertn@umich.edu p[0] = p[1] - p[3] 18074479Sbinkertn@umich.edu elif p[2] == '*': 18084479Sbinkertn@umich.edu p[0] = p[1] * p[3] 18094479Sbinkertn@umich.edu elif p[2] == '/': 18104479Sbinkertn@umich.edu p[0] = p[1] / p[3] 18114479Sbinkertn@umich.edu</pre> 18124479Sbinkertn@umich.edu</blockquote> 18134479Sbinkertn@umich.edu 18144479Sbinkertn@umich.eduA character literal must be enclosed in quotes such as <tt>'+'</tt>. In addition, if literals are used, they must be declared in the 18154479Sbinkertn@umich.educorresponding <tt>lex</tt> file through the use of a special <tt>literals</tt> declaration. 18164479Sbinkertn@umich.edu 18174479Sbinkertn@umich.edu<blockquote> 18184479Sbinkertn@umich.edu<pre> 18194479Sbinkertn@umich.edu# Literals. Should be placed in module given to lex() 18204479Sbinkertn@umich.eduliterals = ['+','-','*','/' ] 18214479Sbinkertn@umich.edu</pre> 18224479Sbinkertn@umich.edu</blockquote> 18234479Sbinkertn@umich.edu 18244479Sbinkertn@umich.edu<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 18254479Sbinkertn@umich.eduthe normal lexing rules (e.g., define a rule such as <tt>t_EQ = r'=='</tt>). 18264479Sbinkertn@umich.edu 18276498Snate@binkert.org<H3><a name="ply_nn26"></a>6.4 Empty Productions</H3> 18284479Sbinkertn@umich.edu 18294479Sbinkertn@umich.edu 18304479Sbinkertn@umich.edu<tt>yacc.py</tt> can handle empty productions by defining a rule like this: 18314479Sbinkertn@umich.edu 18324479Sbinkertn@umich.edu<blockquote> 18334479Sbinkertn@umich.edu<pre> 18344479Sbinkertn@umich.edudef p_empty(p): 18352632Sstever@eecs.umich.edu 'empty :' 18362632Sstever@eecs.umich.edu pass 18372632Sstever@eecs.umich.edu</pre> 18382632Sstever@eecs.umich.edu</blockquote> 18392632Sstever@eecs.umich.edu 18402632Sstever@eecs.umich.eduNow to use the empty production, simply use 'empty' as a symbol. For example: 18412632Sstever@eecs.umich.edu 18422632Sstever@eecs.umich.edu<blockquote> 18432632Sstever@eecs.umich.edu<pre> 18444479Sbinkertn@umich.edudef p_optitem(p): 18452632Sstever@eecs.umich.edu 'optitem : item' 18462632Sstever@eecs.umich.edu ' | empty' 18472632Sstever@eecs.umich.edu ... 18482632Sstever@eecs.umich.edu</pre> 18492632Sstever@eecs.umich.edu</blockquote> 18502632Sstever@eecs.umich.edu 18516498Snate@binkert.orgNote: You can write empty rules anywhere by simply specifying an empty 18526498Snate@binkert.orgright hand side. However, I personally find that writing an "empty" 18536498Snate@binkert.orgrule and using "empty" to denote an empty production is easier to read 18546498Snate@binkert.organd more clearly states your intentions. 18556498Snate@binkert.org 18566498Snate@binkert.org<H3><a name="ply_nn28"></a>6.5 Changing the starting symbol</H3> 18574479Sbinkertn@umich.edu 18584479Sbinkertn@umich.edu 18594479Sbinkertn@umich.eduNormally, the first rule found in a yacc specification defines the starting grammar rule (top level rule). To change this, simply 18604479Sbinkertn@umich.edusupply a <tt>start</tt> specifier in your file. For example: 18614479Sbinkertn@umich.edu 18624479Sbinkertn@umich.edu<blockquote> 18634479Sbinkertn@umich.edu<pre> 18644479Sbinkertn@umich.edustart = 'foo' 18654479Sbinkertn@umich.edu 18664479Sbinkertn@umich.edudef p_bar(p): 18674479Sbinkertn@umich.edu 'bar : A B' 18684479Sbinkertn@umich.edu 18694479Sbinkertn@umich.edu# This is the starting rule due to the start specifier above 18704479Sbinkertn@umich.edudef p_foo(p): 18714479Sbinkertn@umich.edu 'foo : bar X' 18724479Sbinkertn@umich.edu... 18734479Sbinkertn@umich.edu</pre> 18744479Sbinkertn@umich.edu</blockquote> 18754479Sbinkertn@umich.edu 18766498Snate@binkert.orgThe use of a <tt>start</tt> specifier may be useful during debugging 18776498Snate@binkert.orgsince you can use it to have yacc build a subset of a larger grammar. 18786498Snate@binkert.orgFor this purpose, it is also possible to specify a starting symbol as 18796498Snate@binkert.organ argument to <tt>yacc()</tt>. For example: 18804479Sbinkertn@umich.edu 18814479Sbinkertn@umich.edu<blockquote> 18824479Sbinkertn@umich.edu<pre> 18834479Sbinkertn@umich.eduyacc.yacc(start='foo') 18844479Sbinkertn@umich.edu</pre> 18854479Sbinkertn@umich.edu</blockquote> 18864479Sbinkertn@umich.edu 18876498Snate@binkert.org<H3><a name="ply_nn27"></a>6.6 Dealing With Ambiguous Grammars</H3> 18886498Snate@binkert.org 18896498Snate@binkert.org 18906498Snate@binkert.orgThe expression grammar given in the earlier example has been written 18916498Snate@binkert.orgin a special format to eliminate ambiguity. However, in many 18926498Snate@binkert.orgsituations, it is extremely difficult or awkward to write grammars in 18936498Snate@binkert.orgthis format. A much more natural way to express the grammar is in a 18946498Snate@binkert.orgmore compact form like this: 18952632Sstever@eecs.umich.edu 18962632Sstever@eecs.umich.edu<blockquote> 18972632Sstever@eecs.umich.edu<pre> 18982632Sstever@eecs.umich.eduexpression : expression PLUS expression 18992632Sstever@eecs.umich.edu | expression MINUS expression 19002632Sstever@eecs.umich.edu | expression TIMES expression 19012632Sstever@eecs.umich.edu | expression DIVIDE expression 19022632Sstever@eecs.umich.edu | LPAREN expression RPAREN 19032632Sstever@eecs.umich.edu | NUMBER 19042632Sstever@eecs.umich.edu</pre> 19052632Sstever@eecs.umich.edu</blockquote> 19062632Sstever@eecs.umich.edu 19076498Snate@binkert.orgUnfortunately, this grammar specification is ambiguous. For example, 19086498Snate@binkert.orgif you are parsing the string "3 * 4 + 5", there is no way to tell how 19096498Snate@binkert.orgthe operators are supposed to be grouped. For example, does the 19106498Snate@binkert.orgexpression mean "(3 * 4) + 5" or is it "3 * (4+5)"? 19112632Sstever@eecs.umich.edu 19122632Sstever@eecs.umich.edu<p> 19136498Snate@binkert.orgWhen an ambiguous grammar is given to <tt>yacc.py</tt> it will print 19146498Snate@binkert.orgmessages about "shift/reduce conflicts" or "reduce/reduce conflicts". 19156498Snate@binkert.orgA shift/reduce conflict is caused when the parser generator can't 19166498Snate@binkert.orgdecide whether or not to reduce a rule or shift a symbol on the 19176498Snate@binkert.orgparsing stack. For example, consider the string "3 * 4 + 5" and the 19186498Snate@binkert.orginternal parsing stack: 19192632Sstever@eecs.umich.edu 19202632Sstever@eecs.umich.edu<blockquote> 19212632Sstever@eecs.umich.edu<pre> 19222632Sstever@eecs.umich.eduStep Symbol Stack Input Tokens Action 19232632Sstever@eecs.umich.edu---- --------------------- --------------------- ------------------------------- 19242632Sstever@eecs.umich.edu1 $ 3 * 4 + 5$ Shift 3 19252632Sstever@eecs.umich.edu2 $ 3 * 4 + 5$ Reduce : expression : NUMBER 19262632Sstever@eecs.umich.edu3 $ expr * 4 + 5$ Shift * 19272632Sstever@eecs.umich.edu4 $ expr * 4 + 5$ Shift 4 19282632Sstever@eecs.umich.edu5 $ expr * 4 + 5$ Reduce: expression : NUMBER 19292632Sstever@eecs.umich.edu6 $ expr * expr + 5$ SHIFT/REDUCE CONFLICT ???? 19302632Sstever@eecs.umich.edu</pre> 19312632Sstever@eecs.umich.edu</blockquote> 19322632Sstever@eecs.umich.edu 19336498Snate@binkert.orgIn this case, when the parser reaches step 6, it has two options. One 19346498Snate@binkert.orgis to reduce the rule <tt>expr : expr * expr</tt> on the stack. The 19356498Snate@binkert.orgother option is to shift the token <tt>+</tt> on the stack. Both 19366498Snate@binkert.orgoptions are perfectly legal from the rules of the 19376498Snate@binkert.orgcontext-free-grammar. 19382632Sstever@eecs.umich.edu 19392632Sstever@eecs.umich.edu<p> 19406498Snate@binkert.orgBy default, all shift/reduce conflicts are resolved in favor of 19416498Snate@binkert.orgshifting. Therefore, in the above example, the parser will always 19426498Snate@binkert.orgshift the <tt>+</tt> instead of reducing. Although this strategy 19436498Snate@binkert.orgworks in many cases (for example, the case of 19446498Snate@binkert.org"if-then" versus "if-then-else"), it is not enough for arithmetic expressions. In fact, 19456498Snate@binkert.orgin the above example, the decision to shift <tt>+</tt> is completely 19466498Snate@binkert.orgwrong---we should have reduced <tt>expr * expr</tt> since 19476498Snate@binkert.orgmultiplication has higher mathematical precedence than addition. 19486498Snate@binkert.org 19496498Snate@binkert.org<p>To resolve ambiguity, especially in expression 19506498Snate@binkert.orggrammars, <tt>yacc.py</tt> allows individual tokens to be assigned a 19516498Snate@binkert.orgprecedence level and associativity. This is done by adding a variable 19522632Sstever@eecs.umich.edu<tt>precedence</tt> to the grammar file like this: 19532632Sstever@eecs.umich.edu 19542632Sstever@eecs.umich.edu<blockquote> 19552632Sstever@eecs.umich.edu<pre> 19562632Sstever@eecs.umich.eduprecedence = ( 19572632Sstever@eecs.umich.edu ('left', 'PLUS', 'MINUS'), 19582632Sstever@eecs.umich.edu ('left', 'TIMES', 'DIVIDE'), 19592632Sstever@eecs.umich.edu) 19602632Sstever@eecs.umich.edu</pre> 19612632Sstever@eecs.umich.edu</blockquote> 19622632Sstever@eecs.umich.edu 19636498Snate@binkert.orgThis declaration specifies that <tt>PLUS</tt>/<tt>MINUS</tt> have the 19646498Snate@binkert.orgsame precedence level and are left-associative and that 19656498Snate@binkert.org<tt>TIMES</tt>/<tt>DIVIDE</tt> have the same precedence and are 19666498Snate@binkert.orgleft-associative. Within the <tt>precedence</tt> declaration, tokens 19676498Snate@binkert.orgare ordered from lowest to highest precedence. Thus, this declaration 19686498Snate@binkert.orgspecifies that <tt>TIMES</tt>/<tt>DIVIDE</tt> have higher precedence 19696498Snate@binkert.orgthan <tt>PLUS</tt>/<tt>MINUS</tt> (since they appear later in the 19702632Sstever@eecs.umich.eduprecedence specification). 19712632Sstever@eecs.umich.edu 19722632Sstever@eecs.umich.edu<p> 19736498Snate@binkert.orgThe precedence specification works by associating a numerical 19746498Snate@binkert.orgprecedence level value and associativity direction to the listed 19756498Snate@binkert.orgtokens. For example, in the above example you get: 19762632Sstever@eecs.umich.edu 19772632Sstever@eecs.umich.edu<blockquote> 19782632Sstever@eecs.umich.edu<pre> 19794479Sbinkertn@umich.eduPLUS : level = 1, assoc = 'left' 19804479Sbinkertn@umich.eduMINUS : level = 1, assoc = 'left' 19814479Sbinkertn@umich.eduTIMES : level = 2, assoc = 'left' 19824479Sbinkertn@umich.eduDIVIDE : level = 2, assoc = 'left' 19834479Sbinkertn@umich.edu</pre> 19844479Sbinkertn@umich.edu</blockquote> 19854479Sbinkertn@umich.edu 19866498Snate@binkert.orgThese values are then used to attach a numerical precedence value and 19876498Snate@binkert.orgassociativity direction to each grammar rule. <em>This is always 19886498Snate@binkert.orgdetermined by looking at the precedence of the right-most terminal 19896498Snate@binkert.orgsymbol.</em> For example: 19904479Sbinkertn@umich.edu 19914479Sbinkertn@umich.edu<blockquote> 19924479Sbinkertn@umich.edu<pre> 19934479Sbinkertn@umich.eduexpression : expression PLUS expression # level = 1, left 19944479Sbinkertn@umich.edu | expression MINUS expression # level = 1, left 19954479Sbinkertn@umich.edu | expression TIMES expression # level = 2, left 19964479Sbinkertn@umich.edu | expression DIVIDE expression # level = 2, left 19974479Sbinkertn@umich.edu | LPAREN expression RPAREN # level = None (not specified) 19984479Sbinkertn@umich.edu | NUMBER # level = None (not specified) 19992632Sstever@eecs.umich.edu</pre> 20002632Sstever@eecs.umich.edu</blockquote> 20012632Sstever@eecs.umich.edu 20022632Sstever@eecs.umich.eduWhen shift/reduce conflicts are encountered, the parser generator resolves the conflict by 20032632Sstever@eecs.umich.edulooking at the precedence rules and associativity specifiers. 20042632Sstever@eecs.umich.edu 20052632Sstever@eecs.umich.edu<p> 20062632Sstever@eecs.umich.edu<ol> 20076498Snate@binkert.org<li>If the current token has higher precedence than the rule on the stack, it is shifted. 20082632Sstever@eecs.umich.edu<li>If the grammar rule on the stack has higher precedence, the rule is reduced. 20092632Sstever@eecs.umich.edu<li>If the current token and the grammar rule have the same precedence, the 20102632Sstever@eecs.umich.edurule is reduced for left associativity, whereas the token is shifted for right associativity. 20112632Sstever@eecs.umich.edu<li>If nothing is known about the precedence, shift/reduce conflicts are resolved in 20122632Sstever@eecs.umich.edufavor of shifting (the default). 20132632Sstever@eecs.umich.edu</ol> 20142632Sstever@eecs.umich.edu 20156498Snate@binkert.orgFor example, if "expression PLUS expression" has been parsed and the 20166498Snate@binkert.orgnext token is "TIMES", the action is going to be a shift because 20176498Snate@binkert.org"TIMES" has a higher precedence level than "PLUS". On the other hand, 20186498Snate@binkert.orgif "expression TIMES expression" has been parsed and the next token is 20196498Snate@binkert.org"PLUS", the action is going to be reduce because "PLUS" has a lower 20206498Snate@binkert.orgprecedence than "TIMES." 20214479Sbinkertn@umich.edu 20222632Sstever@eecs.umich.edu<p> 20236498Snate@binkert.orgWhen shift/reduce conflicts are resolved using the first three 20246498Snate@binkert.orgtechniques (with the help of precedence rules), <tt>yacc.py</tt> will 20256498Snate@binkert.orgreport no errors or conflicts in the grammar (although it will print 20266498Snate@binkert.orgsome information in the <tt>parser.out</tt> debugging file). 20272632Sstever@eecs.umich.edu 20282632Sstever@eecs.umich.edu<p> 20296498Snate@binkert.orgOne problem with the precedence specifier technique is that it is 20306498Snate@binkert.orgsometimes necessary to change the precedence of an operator in certain 20316498Snate@binkert.orgcontexts. For example, consider a unary-minus operator in "3 + 4 * 20326498Snate@binkert.org-5". Mathematically, the unary minus is normally given a very high 20336498Snate@binkert.orgprecedence--being evaluated before the multiply. However, in our 20346498Snate@binkert.orgprecedence specifier, MINUS has a lower precedence than TIMES. To 20356498Snate@binkert.orgdeal with this, precedence rules can be given for so-called "fictitious tokens" 20366498Snate@binkert.orglike this: 20372632Sstever@eecs.umich.edu 20382632Sstever@eecs.umich.edu<blockquote> 20392632Sstever@eecs.umich.edu<pre> 20402632Sstever@eecs.umich.eduprecedence = ( 20412632Sstever@eecs.umich.edu ('left', 'PLUS', 'MINUS'), 20422632Sstever@eecs.umich.edu ('left', 'TIMES', 'DIVIDE'), 20432632Sstever@eecs.umich.edu ('right', 'UMINUS'), # Unary minus operator 20442632Sstever@eecs.umich.edu) 20452632Sstever@eecs.umich.edu</pre> 20462632Sstever@eecs.umich.edu</blockquote> 20472632Sstever@eecs.umich.edu 20482632Sstever@eecs.umich.eduNow, in the grammar file, we can write our unary minus rule like this: 20492632Sstever@eecs.umich.edu 20502632Sstever@eecs.umich.edu<blockquote> 20512632Sstever@eecs.umich.edu<pre> 20524479Sbinkertn@umich.edudef p_expr_uminus(p): 20532632Sstever@eecs.umich.edu 'expression : MINUS expression %prec UMINUS' 20544479Sbinkertn@umich.edu p[0] = -p[2] 20552632Sstever@eecs.umich.edu</pre> 20562632Sstever@eecs.umich.edu</blockquote> 20572632Sstever@eecs.umich.edu 20582632Sstever@eecs.umich.eduIn this case, <tt>%prec UMINUS</tt> overrides the default rule precedence--setting it to that 20592632Sstever@eecs.umich.eduof UMINUS in the precedence specifier. 20602632Sstever@eecs.umich.edu 20612632Sstever@eecs.umich.edu<p> 20624479Sbinkertn@umich.eduAt first, the use of UMINUS in this example may appear very confusing. 20634479Sbinkertn@umich.eduUMINUS is not an input token or a grammer rule. Instead, you should 20644479Sbinkertn@umich.eduthink of it as the name of a special marker in the precedence table. When you use the <tt>%prec</tt> qualifier, you're simply 20654479Sbinkertn@umich.edutelling yacc that you want the precedence of the expression to be the same as for this special marker instead of the usual precedence. 20664479Sbinkertn@umich.edu 20674479Sbinkertn@umich.edu<p> 20682632Sstever@eecs.umich.eduIt is also possible to specify non-associativity in the <tt>precedence</tt> table. This would 20692632Sstever@eecs.umich.edube used when you <em>don't</em> want operations to chain together. For example, suppose 20704479Sbinkertn@umich.eduyou wanted to support comparison operators like <tt><</tt> and <tt>></tt> but you didn't want to allow 20712632Sstever@eecs.umich.educombinations like <tt>a < b < c</tt>. To do this, simply specify a rule like this: 20722632Sstever@eecs.umich.edu 20732632Sstever@eecs.umich.edu<blockquote> 20742632Sstever@eecs.umich.edu<pre> 20752632Sstever@eecs.umich.eduprecedence = ( 20762632Sstever@eecs.umich.edu ('nonassoc', 'LESSTHAN', 'GREATERTHAN'), # Nonassociative operators 20772632Sstever@eecs.umich.edu ('left', 'PLUS', 'MINUS'), 20782632Sstever@eecs.umich.edu ('left', 'TIMES', 'DIVIDE'), 20792632Sstever@eecs.umich.edu ('right', 'UMINUS'), # Unary minus operator 20802632Sstever@eecs.umich.edu) 20812632Sstever@eecs.umich.edu</pre> 20822632Sstever@eecs.umich.edu</blockquote> 20832632Sstever@eecs.umich.edu 20842632Sstever@eecs.umich.edu<p> 20854479Sbinkertn@umich.eduIf you do this, the occurrence of input text such as <tt> a < b < c</tt> will result in a syntax error. However, simple 20864479Sbinkertn@umich.eduexpressions such as <tt>a < b</tt> will still be fine. 20874479Sbinkertn@umich.edu 20884479Sbinkertn@umich.edu<p> 20892632Sstever@eecs.umich.eduReduce/reduce conflicts are caused when there are multiple grammar 20902632Sstever@eecs.umich.edurules that can be applied to a given set of symbols. This kind of 20912632Sstever@eecs.umich.educonflict is almost always bad and is always resolved by picking the 20922632Sstever@eecs.umich.edurule that appears first in the grammar file. Reduce/reduce conflicts 20932632Sstever@eecs.umich.eduare almost always caused when different sets of grammar rules somehow 20942632Sstever@eecs.umich.edugenerate the same set of symbols. For example: 20952632Sstever@eecs.umich.edu 20962632Sstever@eecs.umich.edu<blockquote> 20972632Sstever@eecs.umich.edu<pre> 20982632Sstever@eecs.umich.eduassignment : ID EQUALS NUMBER 20992632Sstever@eecs.umich.edu | ID EQUALS expression 21002632Sstever@eecs.umich.edu 21012632Sstever@eecs.umich.eduexpression : expression PLUS expression 21022632Sstever@eecs.umich.edu | expression MINUS expression 21032632Sstever@eecs.umich.edu | expression TIMES expression 21042632Sstever@eecs.umich.edu | expression DIVIDE expression 21052632Sstever@eecs.umich.edu | LPAREN expression RPAREN 21062632Sstever@eecs.umich.edu | NUMBER 21072632Sstever@eecs.umich.edu</pre> 21082632Sstever@eecs.umich.edu</blockquote> 21092632Sstever@eecs.umich.edu 21102632Sstever@eecs.umich.eduIn this case, a reduce/reduce conflict exists between these two rules: 21112632Sstever@eecs.umich.edu 21122632Sstever@eecs.umich.edu<blockquote> 21132632Sstever@eecs.umich.edu<pre> 21142632Sstever@eecs.umich.eduassignment : ID EQUALS NUMBER 21152632Sstever@eecs.umich.eduexpression : NUMBER 21162632Sstever@eecs.umich.edu</pre> 21172632Sstever@eecs.umich.edu</blockquote> 21182632Sstever@eecs.umich.edu 21192632Sstever@eecs.umich.eduFor example, if you wrote "a = 5", the parser can't figure out if this 21204479Sbinkertn@umich.eduis supposed to be reduced as <tt>assignment : ID EQUALS NUMBER</tt> or 21212632Sstever@eecs.umich.eduwhether it's supposed to reduce the 5 as an expression and then reduce 21222632Sstever@eecs.umich.eduthe rule <tt>assignment : ID EQUALS expression</tt>. 21232632Sstever@eecs.umich.edu 21244479Sbinkertn@umich.edu<p> 21256498Snate@binkert.orgIt should be noted that reduce/reduce conflicts are notoriously 21266498Snate@binkert.orgdifficult to spot simply looking at the input grammer. When a 21276498Snate@binkert.orgreduce/reduce conflict occurs, <tt>yacc()</tt> will try to help by 21286498Snate@binkert.orgprinting a warning message such as this: 21296498Snate@binkert.org 21306498Snate@binkert.org<blockquote> 21316498Snate@binkert.org<pre> 21326498Snate@binkert.orgWARNING: 1 reduce/reduce conflict 21336498Snate@binkert.orgWARNING: reduce/reduce conflict in state 15 resolved using rule (assignment -> ID EQUALS NUMBER) 21346498Snate@binkert.orgWARNING: rejected rule (expression -> NUMBER) 21356498Snate@binkert.org</pre> 21366498Snate@binkert.org</blockquote> 21376498Snate@binkert.org 21386498Snate@binkert.orgThis message identifies the two rules that are in conflict. However, 21396498Snate@binkert.orgit may not tell you how the parser arrived at such a state. To try 21406498Snate@binkert.organd figure it out, you'll probably have to look at your grammar and 21416498Snate@binkert.orgthe contents of the 21426498Snate@binkert.org<tt>parser.out</tt> debugging file with an appropriately high level of 21436498Snate@binkert.orgcaffeination. 21446498Snate@binkert.org 21456498Snate@binkert.org<H3><a name="ply_nn28"></a>6.7 The parser.out file</H3> 21464479Sbinkertn@umich.edu 21472632Sstever@eecs.umich.edu 21482632Sstever@eecs.umich.eduTracking down shift/reduce and reduce/reduce conflicts is one of the finer pleasures of using an LR 21492632Sstever@eecs.umich.eduparsing algorithm. To assist in debugging, <tt>yacc.py</tt> creates a debugging file called 21502632Sstever@eecs.umich.edu'parser.out' when it generates the parsing table. The contents of this file look like the following: 21512632Sstever@eecs.umich.edu 21522632Sstever@eecs.umich.edu<blockquote> 21532632Sstever@eecs.umich.edu<pre> 21542632Sstever@eecs.umich.eduUnused terminals: 21552632Sstever@eecs.umich.edu 21562632Sstever@eecs.umich.edu 21572632Sstever@eecs.umich.eduGrammar 21582632Sstever@eecs.umich.edu 21592632Sstever@eecs.umich.eduRule 1 expression -> expression PLUS expression 21602632Sstever@eecs.umich.eduRule 2 expression -> expression MINUS expression 21612632Sstever@eecs.umich.eduRule 3 expression -> expression TIMES expression 21622632Sstever@eecs.umich.eduRule 4 expression -> expression DIVIDE expression 21632632Sstever@eecs.umich.eduRule 5 expression -> NUMBER 21642632Sstever@eecs.umich.eduRule 6 expression -> LPAREN expression RPAREN 21652632Sstever@eecs.umich.edu 21662632Sstever@eecs.umich.eduTerminals, with rules where they appear 21672632Sstever@eecs.umich.edu 21682632Sstever@eecs.umich.eduTIMES : 3 21692632Sstever@eecs.umich.eduerror : 21702632Sstever@eecs.umich.eduMINUS : 2 21712632Sstever@eecs.umich.eduRPAREN : 6 21722632Sstever@eecs.umich.eduLPAREN : 6 21732632Sstever@eecs.umich.eduDIVIDE : 4 21742632Sstever@eecs.umich.eduPLUS : 1 21752632Sstever@eecs.umich.eduNUMBER : 5 21762632Sstever@eecs.umich.edu 21772632Sstever@eecs.umich.eduNonterminals, with rules where they appear 21782632Sstever@eecs.umich.edu 21792632Sstever@eecs.umich.eduexpression : 1 1 2 2 3 3 4 4 6 0 21802632Sstever@eecs.umich.edu 21812632Sstever@eecs.umich.edu 21824479Sbinkertn@umich.eduParsing method: LALR 21832632Sstever@eecs.umich.edu 21842632Sstever@eecs.umich.edu 21852632Sstever@eecs.umich.edustate 0 21862632Sstever@eecs.umich.edu 21872632Sstever@eecs.umich.edu S' -> . expression 21882632Sstever@eecs.umich.edu expression -> . expression PLUS expression 21892632Sstever@eecs.umich.edu expression -> . expression MINUS expression 21902632Sstever@eecs.umich.edu expression -> . expression TIMES expression 21912632Sstever@eecs.umich.edu expression -> . expression DIVIDE expression 21922632Sstever@eecs.umich.edu expression -> . NUMBER 21932632Sstever@eecs.umich.edu expression -> . LPAREN expression RPAREN 21942632Sstever@eecs.umich.edu 21952632Sstever@eecs.umich.edu NUMBER shift and go to state 3 21962632Sstever@eecs.umich.edu LPAREN shift and go to state 2 21972632Sstever@eecs.umich.edu 21982632Sstever@eecs.umich.edu 21992632Sstever@eecs.umich.edustate 1 22002632Sstever@eecs.umich.edu 22012632Sstever@eecs.umich.edu S' -> expression . 22022632Sstever@eecs.umich.edu expression -> expression . PLUS expression 22032632Sstever@eecs.umich.edu expression -> expression . MINUS expression 22042632Sstever@eecs.umich.edu expression -> expression . TIMES expression 22052632Sstever@eecs.umich.edu expression -> expression . DIVIDE expression 22062632Sstever@eecs.umich.edu 22072632Sstever@eecs.umich.edu PLUS shift and go to state 6 22082632Sstever@eecs.umich.edu MINUS shift and go to state 5 22092632Sstever@eecs.umich.edu TIMES shift and go to state 4 22102632Sstever@eecs.umich.edu DIVIDE shift and go to state 7 22112632Sstever@eecs.umich.edu 22122632Sstever@eecs.umich.edu 22132632Sstever@eecs.umich.edustate 2 22142632Sstever@eecs.umich.edu 22152632Sstever@eecs.umich.edu expression -> LPAREN . expression RPAREN 22162632Sstever@eecs.umich.edu expression -> . expression PLUS expression 22172632Sstever@eecs.umich.edu expression -> . expression MINUS expression 22182632Sstever@eecs.umich.edu expression -> . expression TIMES expression 22192632Sstever@eecs.umich.edu expression -> . expression DIVIDE expression 22202632Sstever@eecs.umich.edu expression -> . NUMBER 22212632Sstever@eecs.umich.edu expression -> . LPAREN expression RPAREN 22222632Sstever@eecs.umich.edu 22232632Sstever@eecs.umich.edu NUMBER shift and go to state 3 22242632Sstever@eecs.umich.edu LPAREN shift and go to state 2 22252632Sstever@eecs.umich.edu 22262632Sstever@eecs.umich.edu 22272632Sstever@eecs.umich.edustate 3 22282632Sstever@eecs.umich.edu 22292632Sstever@eecs.umich.edu expression -> NUMBER . 22302632Sstever@eecs.umich.edu 22312632Sstever@eecs.umich.edu $ reduce using rule 5 22322632Sstever@eecs.umich.edu PLUS reduce using rule 5 22332632Sstever@eecs.umich.edu MINUS reduce using rule 5 22342632Sstever@eecs.umich.edu TIMES reduce using rule 5 22352632Sstever@eecs.umich.edu DIVIDE reduce using rule 5 22362632Sstever@eecs.umich.edu RPAREN reduce using rule 5 22372632Sstever@eecs.umich.edu 22382632Sstever@eecs.umich.edu 22392632Sstever@eecs.umich.edustate 4 22402632Sstever@eecs.umich.edu 22412632Sstever@eecs.umich.edu expression -> expression TIMES . expression 22422632Sstever@eecs.umich.edu expression -> . expression PLUS expression 22432632Sstever@eecs.umich.edu expression -> . expression MINUS expression 22442632Sstever@eecs.umich.edu expression -> . expression TIMES expression 22452632Sstever@eecs.umich.edu expression -> . expression DIVIDE expression 22462632Sstever@eecs.umich.edu expression -> . NUMBER 22472632Sstever@eecs.umich.edu expression -> . LPAREN expression RPAREN 22482632Sstever@eecs.umich.edu 22492632Sstever@eecs.umich.edu NUMBER shift and go to state 3 22502632Sstever@eecs.umich.edu LPAREN shift and go to state 2 22512632Sstever@eecs.umich.edu 22522632Sstever@eecs.umich.edu 22532632Sstever@eecs.umich.edustate 5 22542632Sstever@eecs.umich.edu 22552632Sstever@eecs.umich.edu expression -> expression MINUS . expression 22562632Sstever@eecs.umich.edu expression -> . expression PLUS expression 22572632Sstever@eecs.umich.edu expression -> . expression MINUS expression 22582632Sstever@eecs.umich.edu expression -> . expression TIMES expression 22592632Sstever@eecs.umich.edu expression -> . expression DIVIDE expression 22602632Sstever@eecs.umich.edu expression -> . NUMBER 22612632Sstever@eecs.umich.edu expression -> . LPAREN expression RPAREN 22622632Sstever@eecs.umich.edu 22632632Sstever@eecs.umich.edu NUMBER shift and go to state 3 22642632Sstever@eecs.umich.edu LPAREN shift and go to state 2 22652632Sstever@eecs.umich.edu 22662632Sstever@eecs.umich.edu 22672632Sstever@eecs.umich.edustate 6 22682632Sstever@eecs.umich.edu 22692632Sstever@eecs.umich.edu expression -> expression PLUS . expression 22702632Sstever@eecs.umich.edu expression -> . expression PLUS expression 22712632Sstever@eecs.umich.edu expression -> . expression MINUS expression 22722632Sstever@eecs.umich.edu expression -> . expression TIMES expression 22732632Sstever@eecs.umich.edu expression -> . expression DIVIDE expression 22742632Sstever@eecs.umich.edu expression -> . NUMBER 22752632Sstever@eecs.umich.edu expression -> . LPAREN expression RPAREN 22762632Sstever@eecs.umich.edu 22772632Sstever@eecs.umich.edu NUMBER shift and go to state 3 22782632Sstever@eecs.umich.edu LPAREN shift and go to state 2 22792632Sstever@eecs.umich.edu 22802632Sstever@eecs.umich.edu 22812632Sstever@eecs.umich.edustate 7 22822632Sstever@eecs.umich.edu 22832632Sstever@eecs.umich.edu expression -> expression DIVIDE . expression 22842632Sstever@eecs.umich.edu expression -> . expression PLUS expression 22852632Sstever@eecs.umich.edu expression -> . expression MINUS expression 22862632Sstever@eecs.umich.edu expression -> . expression TIMES expression 22872632Sstever@eecs.umich.edu expression -> . expression DIVIDE expression 22882632Sstever@eecs.umich.edu expression -> . NUMBER 22892632Sstever@eecs.umich.edu expression -> . LPAREN expression RPAREN 22902632Sstever@eecs.umich.edu 22912632Sstever@eecs.umich.edu NUMBER shift and go to state 3 22922632Sstever@eecs.umich.edu LPAREN shift and go to state 2 22932632Sstever@eecs.umich.edu 22942632Sstever@eecs.umich.edu 22952632Sstever@eecs.umich.edustate 8 22962632Sstever@eecs.umich.edu 22972632Sstever@eecs.umich.edu expression -> LPAREN expression . RPAREN 22982632Sstever@eecs.umich.edu expression -> expression . PLUS expression 22992632Sstever@eecs.umich.edu expression -> expression . MINUS expression 23002632Sstever@eecs.umich.edu expression -> expression . TIMES expression 23012632Sstever@eecs.umich.edu expression -> expression . DIVIDE expression 23022632Sstever@eecs.umich.edu 23032632Sstever@eecs.umich.edu RPAREN shift and go to state 13 23042632Sstever@eecs.umich.edu PLUS shift and go to state 6 23052632Sstever@eecs.umich.edu MINUS shift and go to state 5 23062632Sstever@eecs.umich.edu TIMES shift and go to state 4 23072632Sstever@eecs.umich.edu DIVIDE shift and go to state 7 23082632Sstever@eecs.umich.edu 23092632Sstever@eecs.umich.edu 23102632Sstever@eecs.umich.edustate 9 23112632Sstever@eecs.umich.edu 23122632Sstever@eecs.umich.edu expression -> expression TIMES expression . 23132632Sstever@eecs.umich.edu expression -> expression . PLUS expression 23142632Sstever@eecs.umich.edu expression -> expression . MINUS expression 23152632Sstever@eecs.umich.edu expression -> expression . TIMES expression 23162632Sstever@eecs.umich.edu expression -> expression . DIVIDE expression 23172632Sstever@eecs.umich.edu 23182632Sstever@eecs.umich.edu $ reduce using rule 3 23192632Sstever@eecs.umich.edu PLUS reduce using rule 3 23202632Sstever@eecs.umich.edu MINUS reduce using rule 3 23212632Sstever@eecs.umich.edu TIMES reduce using rule 3 23222632Sstever@eecs.umich.edu DIVIDE reduce using rule 3 23232632Sstever@eecs.umich.edu RPAREN reduce using rule 3 23242632Sstever@eecs.umich.edu 23252632Sstever@eecs.umich.edu ! PLUS [ shift and go to state 6 ] 23262632Sstever@eecs.umich.edu ! MINUS [ shift and go to state 5 ] 23272632Sstever@eecs.umich.edu ! TIMES [ shift and go to state 4 ] 23282632Sstever@eecs.umich.edu ! DIVIDE [ shift and go to state 7 ] 23292632Sstever@eecs.umich.edu 23302632Sstever@eecs.umich.edustate 10 23312632Sstever@eecs.umich.edu 23322632Sstever@eecs.umich.edu expression -> expression MINUS expression . 23332632Sstever@eecs.umich.edu expression -> expression . PLUS expression 23342632Sstever@eecs.umich.edu expression -> expression . MINUS expression 23352632Sstever@eecs.umich.edu expression -> expression . TIMES expression 23362632Sstever@eecs.umich.edu expression -> expression . DIVIDE expression 23372632Sstever@eecs.umich.edu 23382632Sstever@eecs.umich.edu $ reduce using rule 2 23392632Sstever@eecs.umich.edu PLUS reduce using rule 2 23402632Sstever@eecs.umich.edu MINUS reduce using rule 2 23412632Sstever@eecs.umich.edu RPAREN reduce using rule 2 23422632Sstever@eecs.umich.edu TIMES shift and go to state 4 23432632Sstever@eecs.umich.edu DIVIDE shift and go to state 7 23442632Sstever@eecs.umich.edu 23452632Sstever@eecs.umich.edu ! TIMES [ reduce using rule 2 ] 23462632Sstever@eecs.umich.edu ! DIVIDE [ reduce using rule 2 ] 23472632Sstever@eecs.umich.edu ! PLUS [ shift and go to state 6 ] 23482632Sstever@eecs.umich.edu ! MINUS [ shift and go to state 5 ] 23492632Sstever@eecs.umich.edu 23502632Sstever@eecs.umich.edustate 11 23512632Sstever@eecs.umich.edu 23522632Sstever@eecs.umich.edu expression -> expression PLUS expression . 23532632Sstever@eecs.umich.edu expression -> expression . PLUS expression 23542632Sstever@eecs.umich.edu expression -> expression . MINUS expression 23552632Sstever@eecs.umich.edu expression -> expression . TIMES expression 23562632Sstever@eecs.umich.edu expression -> expression . DIVIDE expression 23572632Sstever@eecs.umich.edu 23582632Sstever@eecs.umich.edu $ reduce using rule 1 23592632Sstever@eecs.umich.edu PLUS reduce using rule 1 23602632Sstever@eecs.umich.edu MINUS reduce using rule 1 23612632Sstever@eecs.umich.edu RPAREN reduce using rule 1 23622632Sstever@eecs.umich.edu TIMES shift and go to state 4 23632632Sstever@eecs.umich.edu DIVIDE shift and go to state 7 23642632Sstever@eecs.umich.edu 23652632Sstever@eecs.umich.edu ! TIMES [ reduce using rule 1 ] 23662632Sstever@eecs.umich.edu ! DIVIDE [ reduce using rule 1 ] 23672632Sstever@eecs.umich.edu ! PLUS [ shift and go to state 6 ] 23682632Sstever@eecs.umich.edu ! MINUS [ shift and go to state 5 ] 23692632Sstever@eecs.umich.edu 23702632Sstever@eecs.umich.edustate 12 23712632Sstever@eecs.umich.edu 23722632Sstever@eecs.umich.edu expression -> expression DIVIDE expression . 23732632Sstever@eecs.umich.edu expression -> expression . PLUS expression 23742632Sstever@eecs.umich.edu expression -> expression . MINUS expression 23752632Sstever@eecs.umich.edu expression -> expression . TIMES expression 23762632Sstever@eecs.umich.edu expression -> expression . DIVIDE expression 23772632Sstever@eecs.umich.edu 23782632Sstever@eecs.umich.edu $ reduce using rule 4 23792632Sstever@eecs.umich.edu PLUS reduce using rule 4 23802632Sstever@eecs.umich.edu MINUS reduce using rule 4 23812632Sstever@eecs.umich.edu TIMES reduce using rule 4 23822632Sstever@eecs.umich.edu DIVIDE reduce using rule 4 23832632Sstever@eecs.umich.edu RPAREN reduce using rule 4 23842632Sstever@eecs.umich.edu 23852632Sstever@eecs.umich.edu ! PLUS [ shift and go to state 6 ] 23862632Sstever@eecs.umich.edu ! MINUS [ shift and go to state 5 ] 23872632Sstever@eecs.umich.edu ! TIMES [ shift and go to state 4 ] 23882632Sstever@eecs.umich.edu ! DIVIDE [ shift and go to state 7 ] 23892632Sstever@eecs.umich.edu 23902632Sstever@eecs.umich.edustate 13 23912632Sstever@eecs.umich.edu 23922632Sstever@eecs.umich.edu expression -> LPAREN expression RPAREN . 23932632Sstever@eecs.umich.edu 23942632Sstever@eecs.umich.edu $ reduce using rule 6 23952632Sstever@eecs.umich.edu PLUS reduce using rule 6 23962632Sstever@eecs.umich.edu MINUS reduce using rule 6 23972632Sstever@eecs.umich.edu TIMES reduce using rule 6 23982632Sstever@eecs.umich.edu DIVIDE reduce using rule 6 23992632Sstever@eecs.umich.edu RPAREN reduce using rule 6 24002632Sstever@eecs.umich.edu</pre> 24012632Sstever@eecs.umich.edu</blockquote> 24022632Sstever@eecs.umich.edu 24036498Snate@binkert.orgThe different states that appear in this file are a representation of 24046498Snate@binkert.orgevery possible sequence of valid input tokens allowed by the grammar. 24056498Snate@binkert.orgWhen receiving input tokens, the parser is building up a stack and 24066498Snate@binkert.orglooking for matching rules. Each state keeps track of the grammar 24076498Snate@binkert.orgrules that might be in the process of being matched at that point. Within each 24086498Snate@binkert.orgrule, the "." character indicates the current location of the parse 24096498Snate@binkert.orgwithin that rule. In addition, the actions for each valid input token 24106498Snate@binkert.orgare listed. When a shift/reduce or reduce/reduce conflict arises, 24116498Snate@binkert.orgrules <em>not</em> selected are prefixed with an !. For example: 24122632Sstever@eecs.umich.edu 24132632Sstever@eecs.umich.edu<blockquote> 24142632Sstever@eecs.umich.edu<pre> 24152632Sstever@eecs.umich.edu ! TIMES [ reduce using rule 2 ] 24162632Sstever@eecs.umich.edu ! DIVIDE [ reduce using rule 2 ] 24172632Sstever@eecs.umich.edu ! PLUS [ shift and go to state 6 ] 24182632Sstever@eecs.umich.edu ! MINUS [ shift and go to state 5 ] 24192632Sstever@eecs.umich.edu</pre> 24202632Sstever@eecs.umich.edu</blockquote> 24212632Sstever@eecs.umich.edu 24222632Sstever@eecs.umich.eduBy looking at these rules (and with a little practice), you can usually track down the source 24232632Sstever@eecs.umich.eduof most parsing conflicts. It should also be stressed that not all shift-reduce conflicts are 24242632Sstever@eecs.umich.edubad. However, the only way to be sure that they are resolved correctly is to look at <tt>parser.out</tt>. 24252632Sstever@eecs.umich.edu 24266498Snate@binkert.org<H3><a name="ply_nn29"></a>6.8 Syntax Error Handling</H3> 24276498Snate@binkert.org 24286498Snate@binkert.org 24296498Snate@binkert.orgIf you are creating a parser for production use, the handling of 24306498Snate@binkert.orgsyntax errors is important. As a general rule, you don't want a 24316498Snate@binkert.orgparser to simply throw up its hands and stop at the first sign of 24326498Snate@binkert.orgtrouble. Instead, you want it to report the error, recover if possible, and 24336498Snate@binkert.orgcontinue parsing so that all of the errors in the input get reported 24346498Snate@binkert.orgto the user at once. This is the standard behavior found in compilers 24356498Snate@binkert.orgfor languages such as C, C++, and Java. 24366498Snate@binkert.org 24376498Snate@binkert.orgIn PLY, when a syntax error occurs during parsing, the error is immediately 24382632Sstever@eecs.umich.edudetected (i.e., the parser does not read any more tokens beyond the 24396498Snate@binkert.orgsource of the error). However, at this point, the parser enters a 24406498Snate@binkert.orgrecovery mode that can be used to try and continue further parsing. 24416498Snate@binkert.orgAs a general rule, error recovery in LR parsers is a delicate 24422632Sstever@eecs.umich.edutopic that involves ancient rituals and black-magic. The recovery mechanism 24432632Sstever@eecs.umich.eduprovided by <tt>yacc.py</tt> is comparable to Unix yacc so you may want 24442632Sstever@eecs.umich.educonsult a book like O'Reilly's "Lex and Yacc" for some of the finer details. 24452632Sstever@eecs.umich.edu 24462632Sstever@eecs.umich.edu<p> 24472632Sstever@eecs.umich.eduWhen a syntax error occurs, <tt>yacc.py</tt> performs the following steps: 24482632Sstever@eecs.umich.edu 24492632Sstever@eecs.umich.edu<ol> 24502632Sstever@eecs.umich.edu<li>On the first occurrence of an error, the user-defined <tt>p_error()</tt> function 24516498Snate@binkert.orgis called with the offending token as an argument. However, if the syntax error is due to 24526498Snate@binkert.orgreaching the end-of-file, <tt>p_error()</tt> is called with an argument of <tt>None</tt>. 24536498Snate@binkert.orgAfterwards, the parser enters 24542632Sstever@eecs.umich.eduan "error-recovery" mode in which it will not make future calls to <tt>p_error()</tt> until it 24552632Sstever@eecs.umich.eduhas successfully shifted at least 3 tokens onto the parsing stack. 24562632Sstever@eecs.umich.edu 24572632Sstever@eecs.umich.edu<p> 24582632Sstever@eecs.umich.edu<li>If no recovery action is taken in <tt>p_error()</tt>, the offending lookahead token is replaced 24592632Sstever@eecs.umich.eduwith a special <tt>error</tt> token. 24602632Sstever@eecs.umich.edu 24612632Sstever@eecs.umich.edu<p> 24622632Sstever@eecs.umich.edu<li>If the offending lookahead token is already set to <tt>error</tt>, the top item of the parsing stack is 24632632Sstever@eecs.umich.edudeleted. 24642632Sstever@eecs.umich.edu 24652632Sstever@eecs.umich.edu<p> 24662632Sstever@eecs.umich.edu<li>If the entire parsing stack is unwound, the parser enters a restart state and attempts to start 24672632Sstever@eecs.umich.eduparsing from its initial state. 24682632Sstever@eecs.umich.edu 24692632Sstever@eecs.umich.edu<p> 24702632Sstever@eecs.umich.edu<li>If a grammar rule accepts <tt>error</tt> as a token, it will be 24712632Sstever@eecs.umich.edushifted onto the parsing stack. 24722632Sstever@eecs.umich.edu 24732632Sstever@eecs.umich.edu<p> 24742632Sstever@eecs.umich.edu<li>If the top item of the parsing stack is <tt>error</tt>, lookahead tokens will be discarded until the 24752632Sstever@eecs.umich.eduparser can successfully shift a new symbol or reduce a rule involving <tt>error</tt>. 24762632Sstever@eecs.umich.edu</ol> 24772632Sstever@eecs.umich.edu 24786498Snate@binkert.org<H4><a name="ply_nn30"></a>6.8.1 Recovery and resynchronization with error rules</H4> 24794479Sbinkertn@umich.edu 24802632Sstever@eecs.umich.edu 24812632Sstever@eecs.umich.eduThe most well-behaved approach for handling syntax errors is to write grammar rules that include the <tt>error</tt> 24822632Sstever@eecs.umich.edutoken. For example, suppose your language had a grammar rule for a print statement like this: 24832632Sstever@eecs.umich.edu 24842632Sstever@eecs.umich.edu<blockquote> 24852632Sstever@eecs.umich.edu<pre> 24864479Sbinkertn@umich.edudef p_statement_print(p): 24872632Sstever@eecs.umich.edu 'statement : PRINT expr SEMI' 24882632Sstever@eecs.umich.edu ... 24892632Sstever@eecs.umich.edu</pre> 24902632Sstever@eecs.umich.edu</blockquote> 24912632Sstever@eecs.umich.edu 24922632Sstever@eecs.umich.eduTo account for the possibility of a bad expression, you might write an additional grammar rule like this: 24932632Sstever@eecs.umich.edu 24942632Sstever@eecs.umich.edu<blockquote> 24952632Sstever@eecs.umich.edu<pre> 24964479Sbinkertn@umich.edudef p_statement_print_error(p): 24972632Sstever@eecs.umich.edu 'statement : PRINT error SEMI' 24982632Sstever@eecs.umich.edu print "Syntax error in print statement. Bad expression" 24992632Sstever@eecs.umich.edu 25002632Sstever@eecs.umich.edu</pre> 25012632Sstever@eecs.umich.edu</blockquote> 25022632Sstever@eecs.umich.edu 25032632Sstever@eecs.umich.eduIn this case, the <tt>error</tt> token will match any sequence of 25042632Sstever@eecs.umich.edutokens that might appear up to the first semicolon that is 25052632Sstever@eecs.umich.eduencountered. Once the semicolon is reached, the rule will be 25062632Sstever@eecs.umich.eduinvoked and the <tt>error</tt> token will go away. 25072632Sstever@eecs.umich.edu 25082632Sstever@eecs.umich.edu<p> 25092632Sstever@eecs.umich.eduThis type of recovery is sometimes known as parser resynchronization. 25102632Sstever@eecs.umich.eduThe <tt>error</tt> token acts as a wildcard for any bad input text and 25112632Sstever@eecs.umich.eduthe token immediately following <tt>error</tt> acts as a 25122632Sstever@eecs.umich.edusynchronization token. 25132632Sstever@eecs.umich.edu 25142632Sstever@eecs.umich.edu<p> 25152632Sstever@eecs.umich.eduIt is important to note that the <tt>error</tt> token usually does not appear as the last token 25162632Sstever@eecs.umich.eduon the right in an error rule. For example: 25172632Sstever@eecs.umich.edu 25182632Sstever@eecs.umich.edu<blockquote> 25192632Sstever@eecs.umich.edu<pre> 25204479Sbinkertn@umich.edudef p_statement_print_error(p): 25212632Sstever@eecs.umich.edu 'statement : PRINT error' 25222632Sstever@eecs.umich.edu print "Syntax error in print statement. Bad expression" 25232632Sstever@eecs.umich.edu</pre> 25242632Sstever@eecs.umich.edu</blockquote> 25252632Sstever@eecs.umich.edu 25262632Sstever@eecs.umich.eduThis is because the first bad token encountered will cause the rule to 25272632Sstever@eecs.umich.edube reduced--which may make it difficult to recover if more bad tokens 25282632Sstever@eecs.umich.eduimmediately follow. 25292632Sstever@eecs.umich.edu 25306498Snate@binkert.org<H4><a name="ply_nn31"></a>6.8.2 Panic mode recovery</H4> 25314479Sbinkertn@umich.edu 25322632Sstever@eecs.umich.edu 25332632Sstever@eecs.umich.eduAn alternative error recovery scheme is to enter a panic mode recovery in which tokens are 25342632Sstever@eecs.umich.edudiscarded to a point where the parser might be able to recover in some sensible manner. 25352632Sstever@eecs.umich.edu 25362632Sstever@eecs.umich.edu<p> 25372632Sstever@eecs.umich.eduPanic mode recovery is implemented entirely in the <tt>p_error()</tt> function. For example, this 25382632Sstever@eecs.umich.edufunction starts discarding tokens until it reaches a closing '}'. Then, it restarts the 25392632Sstever@eecs.umich.eduparser in its initial state. 25402632Sstever@eecs.umich.edu 25412632Sstever@eecs.umich.edu<blockquote> 25422632Sstever@eecs.umich.edu<pre> 25434479Sbinkertn@umich.edudef p_error(p): 25442632Sstever@eecs.umich.edu print "Whoa. You are seriously hosed." 25452632Sstever@eecs.umich.edu # Read ahead looking for a closing '}' 25462632Sstever@eecs.umich.edu while 1: 25472632Sstever@eecs.umich.edu tok = yacc.token() # Get the next token 25482632Sstever@eecs.umich.edu if not tok or tok.type == 'RBRACE': break 25492632Sstever@eecs.umich.edu yacc.restart() 25502632Sstever@eecs.umich.edu</pre> 25512632Sstever@eecs.umich.edu</blockquote> 25522632Sstever@eecs.umich.edu 25532632Sstever@eecs.umich.edu<p> 25542632Sstever@eecs.umich.eduThis function simply discards the bad token and tells the parser that the error was ok. 25552632Sstever@eecs.umich.edu 25562632Sstever@eecs.umich.edu<blockquote> 25572632Sstever@eecs.umich.edu<pre> 25584479Sbinkertn@umich.edudef p_error(p): 25594479Sbinkertn@umich.edu print "Syntax error at token", p.type 25602632Sstever@eecs.umich.edu # Just discard the token and tell the parser it's okay. 25612632Sstever@eecs.umich.edu yacc.errok() 25622632Sstever@eecs.umich.edu</pre> 25632632Sstever@eecs.umich.edu</blockquote> 25642632Sstever@eecs.umich.edu 25652632Sstever@eecs.umich.edu<P> 25662632Sstever@eecs.umich.eduWithin the <tt>p_error()</tt> function, three functions are available to control the behavior 25672632Sstever@eecs.umich.eduof the parser: 25682632Sstever@eecs.umich.edu<p> 25692632Sstever@eecs.umich.edu<ul> 25702632Sstever@eecs.umich.edu<li><tt>yacc.errok()</tt>. This resets the parser state so it doesn't think it's in error-recovery 25712632Sstever@eecs.umich.edumode. This will prevent an <tt>error</tt> token from being generated and will reset the internal 25722632Sstever@eecs.umich.eduerror counters so that the next syntax error will call <tt>p_error()</tt> again. 25732632Sstever@eecs.umich.edu 25742632Sstever@eecs.umich.edu<p> 25752632Sstever@eecs.umich.edu<li><tt>yacc.token()</tt>. This returns the next token on the input stream. 25762632Sstever@eecs.umich.edu 25772632Sstever@eecs.umich.edu<p> 25782632Sstever@eecs.umich.edu<li><tt>yacc.restart()</tt>. This discards the entire parsing stack and resets the parser 25792632Sstever@eecs.umich.eduto its initial state. 25802632Sstever@eecs.umich.edu</ul> 25812632Sstever@eecs.umich.edu 25822632Sstever@eecs.umich.eduNote: these functions are only available when invoking <tt>p_error()</tt> and are not available 25832632Sstever@eecs.umich.eduat any other time. 25842632Sstever@eecs.umich.edu 25852632Sstever@eecs.umich.edu<p> 25862632Sstever@eecs.umich.eduTo supply the next lookahead token to the parser, <tt>p_error()</tt> can return a token. This might be 25872632Sstever@eecs.umich.eduuseful if trying to synchronize on special characters. For example: 25882632Sstever@eecs.umich.edu 25892632Sstever@eecs.umich.edu<blockquote> 25902632Sstever@eecs.umich.edu<pre> 25914479Sbinkertn@umich.edudef p_error(p): 25922632Sstever@eecs.umich.edu # Read ahead looking for a terminating ";" 25932632Sstever@eecs.umich.edu while 1: 25942632Sstever@eecs.umich.edu tok = yacc.token() # Get the next token 25952632Sstever@eecs.umich.edu if not tok or tok.type == 'SEMI': break 25962632Sstever@eecs.umich.edu yacc.errok() 25972632Sstever@eecs.umich.edu 25982632Sstever@eecs.umich.edu # Return SEMI to the parser as the next lookahead token 25992632Sstever@eecs.umich.edu return tok 26002632Sstever@eecs.umich.edu</pre> 26012632Sstever@eecs.umich.edu</blockquote> 26022632Sstever@eecs.umich.edu 26036498Snate@binkert.org<H4><a name="ply_nn35"></a>6.8.3 Signaling an error from a production</H4> 26046498Snate@binkert.org 26056498Snate@binkert.org 26066498Snate@binkert.orgIf necessary, a production rule can manually force the parser to enter error recovery. This 26076498Snate@binkert.orgis done by raising the <tt>SyntaxError</tt> exception like this: 26086498Snate@binkert.org 26096498Snate@binkert.org<blockquote> 26106498Snate@binkert.org<pre> 26116498Snate@binkert.orgdef p_production(p): 26126498Snate@binkert.org 'production : some production ...' 26136498Snate@binkert.org raise SyntaxError 26146498Snate@binkert.org</pre> 26156498Snate@binkert.org</blockquote> 26166498Snate@binkert.org 26176498Snate@binkert.orgThe effect of raising <tt>SyntaxError</tt> is the same as if the last symbol shifted onto the 26186498Snate@binkert.orgparsing stack was actually a syntax error. Thus, when you do this, the last symbol shifted is popped off 26196498Snate@binkert.orgof the parsing stack and the current lookahead token is set to an <tt>error</tt> token. The parser 26206498Snate@binkert.orgthen enters error-recovery mode where it tries to reduce rules that can accept <tt>error</tt> tokens. 26216498Snate@binkert.orgThe steps that follow from this point are exactly the same as if a syntax error were detected and 26226498Snate@binkert.org<tt>p_error()</tt> were called. 26236498Snate@binkert.org 26246498Snate@binkert.org<P> 26256498Snate@binkert.orgOne important aspect of manually setting an error is that the <tt>p_error()</tt> function will <b>NOT</b> be 26266498Snate@binkert.orgcalled in this case. If you need to issue an error message, make sure you do it in the production that 26276498Snate@binkert.orgraises <tt>SyntaxError</tt>. 26286498Snate@binkert.org 26296498Snate@binkert.org<P> 26306498Snate@binkert.orgNote: This feature of PLY is meant to mimic the behavior of the YYERROR macro in yacc. 26316498Snate@binkert.org 26326498Snate@binkert.org 26336498Snate@binkert.org<H4><a name="ply_nn32"></a>6.8.4 General comments on error handling</H4> 26344479Sbinkertn@umich.edu 26352632Sstever@eecs.umich.edu 26362632Sstever@eecs.umich.eduFor normal types of languages, error recovery with error rules and resynchronization characters is probably the most reliable 26372632Sstever@eecs.umich.edutechnique. This is because you can instrument the grammar to catch errors at selected places where it is relatively easy 26382632Sstever@eecs.umich.eduto recover and continue parsing. Panic mode recovery is really only useful in certain specialized applications where you might want 26392632Sstever@eecs.umich.eduto discard huge portions of the input text to find a valid restart point. 26402632Sstever@eecs.umich.edu 26416498Snate@binkert.org<H3><a name="ply_nn33"></a>6.9 Line Number and Position Tracking</H3> 26426498Snate@binkert.org 26436498Snate@binkert.org 26446498Snate@binkert.orgPosition tracking is often a tricky problem when writing compilers. 26456498Snate@binkert.orgBy default, PLY tracks the line number and position of all tokens. 26466498Snate@binkert.orgThis information is available using the following functions: 26472632Sstever@eecs.umich.edu 26482632Sstever@eecs.umich.edu<ul> 26494479Sbinkertn@umich.edu<li><tt>p.lineno(num)</tt>. Return the line number for symbol <em>num</em> 26504479Sbinkertn@umich.edu<li><tt>p.lexpos(num)</tt>. Return the lexing position for symbol <em>num</em> 26512632Sstever@eecs.umich.edu</ul> 26522632Sstever@eecs.umich.edu 26532632Sstever@eecs.umich.eduFor example: 26542632Sstever@eecs.umich.edu 26552632Sstever@eecs.umich.edu<blockquote> 26562632Sstever@eecs.umich.edu<pre> 26574479Sbinkertn@umich.edudef p_expression(p): 26582632Sstever@eecs.umich.edu 'expression : expression PLUS expression' 26594479Sbinkertn@umich.edu line = p.lineno(2) # line number of the PLUS token 26604479Sbinkertn@umich.edu index = p.lexpos(2) # Position of the PLUS token 26612632Sstever@eecs.umich.edu</pre> 26622632Sstever@eecs.umich.edu</blockquote> 26632632Sstever@eecs.umich.edu 26646498Snate@binkert.orgAs an optional feature, <tt>yacc.py</tt> can automatically track line 26656498Snate@binkert.orgnumbers and positions for all of the grammar symbols as well. 26666498Snate@binkert.orgHowever, this extra tracking requires extra processing and can 26676498Snate@binkert.orgsignificantly slow down parsing. Therefore, it must be enabled by 26686498Snate@binkert.orgpassing the 26694479Sbinkertn@umich.edu<tt>tracking=True</tt> option to <tt>yacc.parse()</tt>. For example: 26704479Sbinkertn@umich.edu 26714479Sbinkertn@umich.edu<blockquote> 26724479Sbinkertn@umich.edu<pre> 26734479Sbinkertn@umich.eduyacc.parse(data,tracking=True) 26744479Sbinkertn@umich.edu</pre> 26754479Sbinkertn@umich.edu</blockquote> 26764479Sbinkertn@umich.edu 26776498Snate@binkert.orgOnce enabled, the <tt>lineno()</tt> and <tt>lexpos()</tt> methods work 26786498Snate@binkert.orgfor all grammar symbols. In addition, two additional methods can be 26796498Snate@binkert.orgused: 26804479Sbinkertn@umich.edu 26814479Sbinkertn@umich.edu<ul> 26824479Sbinkertn@umich.edu<li><tt>p.linespan(num)</tt>. Return a tuple (startline,endline) with the starting and ending line number for symbol <em>num</em>. 26834479Sbinkertn@umich.edu<li><tt>p.lexspan(num)</tt>. Return a tuple (start,end) with the starting and ending positions for symbol <em>num</em>. 26844479Sbinkertn@umich.edu</ul> 26854479Sbinkertn@umich.edu 26864479Sbinkertn@umich.eduFor example: 26874479Sbinkertn@umich.edu 26884479Sbinkertn@umich.edu<blockquote> 26894479Sbinkertn@umich.edu<pre> 26904479Sbinkertn@umich.edudef p_expression(p): 26914479Sbinkertn@umich.edu 'expression : expression PLUS expression' 26924479Sbinkertn@umich.edu p.lineno(1) # Line number of the left expression 26934479Sbinkertn@umich.edu p.lineno(2) # line number of the PLUS operator 26944479Sbinkertn@umich.edu p.lineno(3) # line number of the right expression 26954479Sbinkertn@umich.edu ... 26964479Sbinkertn@umich.edu start,end = p.linespan(3) # Start,end lines of the right expression 26974479Sbinkertn@umich.edu starti,endi = p.lexspan(3) # Start,end positions of right expression 26984479Sbinkertn@umich.edu 26994479Sbinkertn@umich.edu</pre> 27004479Sbinkertn@umich.edu</blockquote> 27014479Sbinkertn@umich.edu 27024479Sbinkertn@umich.eduNote: The <tt>lexspan()</tt> function only returns the range of values up to the start of the last grammar symbol. 27034479Sbinkertn@umich.edu 27044479Sbinkertn@umich.edu<p> 27054479Sbinkertn@umich.eduAlthough it may be convenient for PLY to track position information on 27064479Sbinkertn@umich.eduall grammar symbols, this is often unnecessary. For example, if you 27074479Sbinkertn@umich.eduare merely using line number information in an error message, you can 27084479Sbinkertn@umich.eduoften just key off of a specific token in the grammar rule. For 27094479Sbinkertn@umich.eduexample: 27104479Sbinkertn@umich.edu 27114479Sbinkertn@umich.edu<blockquote> 27124479Sbinkertn@umich.edu<pre> 27134479Sbinkertn@umich.edudef p_bad_func(p): 27144479Sbinkertn@umich.edu 'funccall : fname LPAREN error RPAREN' 27154479Sbinkertn@umich.edu # Line number reported from LPAREN token 27164479Sbinkertn@umich.edu print "Bad function call at line", p.lineno(2) 27174479Sbinkertn@umich.edu</pre> 27184479Sbinkertn@umich.edu</blockquote> 27194479Sbinkertn@umich.edu 27204479Sbinkertn@umich.edu<p> 27216498Snate@binkert.orgSimilarly, you may get better parsing performance if you only 27226498Snate@binkert.orgselectively propagate line number information where it's needed using 27236498Snate@binkert.orgthe <tt>p.set_lineno()</tt> method. For example: 27244479Sbinkertn@umich.edu 27254479Sbinkertn@umich.edu<blockquote> 27264479Sbinkertn@umich.edu<pre> 27274479Sbinkertn@umich.edudef p_fname(p): 27284479Sbinkertn@umich.edu 'fname : ID' 27296498Snate@binkert.org p[0] = p[1] 27306498Snate@binkert.org p.set_lineno(0,p.lineno(1)) 27314479Sbinkertn@umich.edu</pre> 27324479Sbinkertn@umich.edu</blockquote> 27334479Sbinkertn@umich.edu 27346498Snate@binkert.orgPLY doesn't retain line number information from rules that have already been 27356498Snate@binkert.orgparsed. If you are building an abstract syntax tree and need to have line numbers, 27366498Snate@binkert.orgyou should make sure that the line numbers appear in the tree itself. 27376498Snate@binkert.org 27386498Snate@binkert.org<H3><a name="ply_nn34"></a>6.10 AST Construction</H3> 27396498Snate@binkert.org 27406498Snate@binkert.org 27416498Snate@binkert.org<tt>yacc.py</tt> provides no special functions for constructing an 27426498Snate@binkert.orgabstract syntax tree. However, such construction is easy enough to do 27436498Snate@binkert.orgon your own. 27446498Snate@binkert.org 27456498Snate@binkert.org<p>A minimal way to construct a tree is to simply create and 27466498Snate@binkert.orgpropagate a tuple or list in each grammar rule function. There 27476498Snate@binkert.orgare many possible ways to do this, but one example would be something 27486498Snate@binkert.orglike this: 27496498Snate@binkert.org 27506498Snate@binkert.org<blockquote> 27516498Snate@binkert.org<pre> 27526498Snate@binkert.orgdef p_expression_binop(p): 27536498Snate@binkert.org '''expression : expression PLUS expression 27546498Snate@binkert.org | expression MINUS expression 27556498Snate@binkert.org | expression TIMES expression 27566498Snate@binkert.org | expression DIVIDE expression''' 27576498Snate@binkert.org 27586498Snate@binkert.org p[0] = ('binary-expression',p[2],p[1],p[3]) 27596498Snate@binkert.org 27606498Snate@binkert.orgdef p_expression_group(p): 27616498Snate@binkert.org 'expression : LPAREN expression RPAREN' 27626498Snate@binkert.org p[0] = ('group-expression',p[2]) 27636498Snate@binkert.org 27646498Snate@binkert.orgdef p_expression_number(p): 27656498Snate@binkert.org 'expression : NUMBER' 27666498Snate@binkert.org p[0] = ('number-expression',p[1]) 27676498Snate@binkert.org</pre> 27686498Snate@binkert.org</blockquote> 27696498Snate@binkert.org 27706498Snate@binkert.org<p> 27716498Snate@binkert.orgAnother approach is to create a set of data structure for different 27726498Snate@binkert.orgkinds of abstract syntax tree nodes and assign nodes to <tt>p[0]</tt> 27736498Snate@binkert.orgin each rule. For example: 27742632Sstever@eecs.umich.edu 27752632Sstever@eecs.umich.edu<blockquote> 27762632Sstever@eecs.umich.edu<pre> 27772632Sstever@eecs.umich.educlass Expr: pass 27782632Sstever@eecs.umich.edu 27792632Sstever@eecs.umich.educlass BinOp(Expr): 27802632Sstever@eecs.umich.edu def __init__(self,left,op,right): 27812632Sstever@eecs.umich.edu self.type = "binop" 27822632Sstever@eecs.umich.edu self.left = left 27832632Sstever@eecs.umich.edu self.right = right 27842632Sstever@eecs.umich.edu self.op = op 27852632Sstever@eecs.umich.edu 27862632Sstever@eecs.umich.educlass Number(Expr): 27872632Sstever@eecs.umich.edu def __init__(self,value): 27882632Sstever@eecs.umich.edu self.type = "number" 27892632Sstever@eecs.umich.edu self.value = value 27902632Sstever@eecs.umich.edu 27914479Sbinkertn@umich.edudef p_expression_binop(p): 27922632Sstever@eecs.umich.edu '''expression : expression PLUS expression 27932632Sstever@eecs.umich.edu | expression MINUS expression 27942632Sstever@eecs.umich.edu | expression TIMES expression 27952632Sstever@eecs.umich.edu | expression DIVIDE expression''' 27962632Sstever@eecs.umich.edu 27974479Sbinkertn@umich.edu p[0] = BinOp(p[1],p[2],p[3]) 27984479Sbinkertn@umich.edu 27994479Sbinkertn@umich.edudef p_expression_group(p): 28002632Sstever@eecs.umich.edu 'expression : LPAREN expression RPAREN' 28014479Sbinkertn@umich.edu p[0] = p[2] 28024479Sbinkertn@umich.edu 28034479Sbinkertn@umich.edudef p_expression_number(p): 28042632Sstever@eecs.umich.edu 'expression : NUMBER' 28054479Sbinkertn@umich.edu p[0] = Number(p[1]) 28062632Sstever@eecs.umich.edu</pre> 28072632Sstever@eecs.umich.edu</blockquote> 28082632Sstever@eecs.umich.edu 28096498Snate@binkert.orgThe advantage to this approach is that it may make it easier to attach more complicated 28106498Snate@binkert.orgsemantics, type checking, code generation, and other features to the node classes. 28116498Snate@binkert.org 28126498Snate@binkert.org<p> 28136498Snate@binkert.orgTo simplify tree traversal, it may make sense to pick a very generic 28146498Snate@binkert.orgtree structure for your parse tree nodes. For example: 28152632Sstever@eecs.umich.edu 28162632Sstever@eecs.umich.edu<blockquote> 28172632Sstever@eecs.umich.edu<pre> 28182632Sstever@eecs.umich.educlass Node: 28192632Sstever@eecs.umich.edu def __init__(self,type,children=None,leaf=None): 28202632Sstever@eecs.umich.edu self.type = type 28212632Sstever@eecs.umich.edu if children: 28222632Sstever@eecs.umich.edu self.children = children 28232632Sstever@eecs.umich.edu else: 28242632Sstever@eecs.umich.edu self.children = [ ] 28252632Sstever@eecs.umich.edu self.leaf = leaf 28262632Sstever@eecs.umich.edu 28274479Sbinkertn@umich.edudef p_expression_binop(p): 28282632Sstever@eecs.umich.edu '''expression : expression PLUS expression 28292632Sstever@eecs.umich.edu | expression MINUS expression 28302632Sstever@eecs.umich.edu | expression TIMES expression 28312632Sstever@eecs.umich.edu | expression DIVIDE expression''' 28322632Sstever@eecs.umich.edu 28334479Sbinkertn@umich.edu p[0] = Node("binop", [p[1],p[3]], p[2]) 28342632Sstever@eecs.umich.edu</pre> 28352632Sstever@eecs.umich.edu</blockquote> 28362632Sstever@eecs.umich.edu 28376498Snate@binkert.org<H3><a name="ply_nn35"></a>6.11 Embedded Actions</H3> 28384479Sbinkertn@umich.edu 28394479Sbinkertn@umich.edu 28404479Sbinkertn@umich.eduThe parsing technique used by yacc only allows actions to be executed at the end of a rule. For example, 28414479Sbinkertn@umich.edusuppose you have a rule like this: 28424479Sbinkertn@umich.edu 28434479Sbinkertn@umich.edu<blockquote> 28444479Sbinkertn@umich.edu<pre> 28454479Sbinkertn@umich.edudef p_foo(p): 28464479Sbinkertn@umich.edu "foo : A B C D" 28474479Sbinkertn@umich.edu print "Parsed a foo", p[1],p[2],p[3],p[4] 28484479Sbinkertn@umich.edu</pre> 28494479Sbinkertn@umich.edu</blockquote> 28504479Sbinkertn@umich.edu 28514479Sbinkertn@umich.edu<p> 28524479Sbinkertn@umich.eduIn this case, the supplied action code only executes after all of the 28534479Sbinkertn@umich.edusymbols <tt>A</tt>, <tt>B</tt>, <tt>C</tt>, and <tt>D</tt> have been 28544479Sbinkertn@umich.eduparsed. Sometimes, however, it is useful to execute small code 28554479Sbinkertn@umich.edufragments during intermediate stages of parsing. For example, suppose 28564479Sbinkertn@umich.eduyou wanted to perform some action immediately after <tt>A</tt> has 28576498Snate@binkert.orgbeen parsed. To do this, write an empty rule like this: 28584479Sbinkertn@umich.edu 28594479Sbinkertn@umich.edu<blockquote> 28604479Sbinkertn@umich.edu<pre> 28614479Sbinkertn@umich.edudef p_foo(p): 28624479Sbinkertn@umich.edu "foo : A seen_A B C D" 28634479Sbinkertn@umich.edu print "Parsed a foo", p[1],p[3],p[4],p[5] 28644479Sbinkertn@umich.edu print "seen_A returned", p[2] 28654479Sbinkertn@umich.edu 28664479Sbinkertn@umich.edudef p_seen_A(p): 28674479Sbinkertn@umich.edu "seen_A :" 28684479Sbinkertn@umich.edu print "Saw an A = ", p[-1] # Access grammar symbol to left 28694479Sbinkertn@umich.edu p[0] = some_value # Assign value to seen_A 28704479Sbinkertn@umich.edu 28714479Sbinkertn@umich.edu</pre> 28724479Sbinkertn@umich.edu</blockquote> 28734479Sbinkertn@umich.edu 28744479Sbinkertn@umich.edu<p> 28754479Sbinkertn@umich.eduIn this example, the empty <tt>seen_A</tt> rule executes immediately 28764479Sbinkertn@umich.eduafter <tt>A</tt> is shifted onto the parsing stack. Within this 28774479Sbinkertn@umich.edurule, <tt>p[-1]</tt> refers to the symbol on the stack that appears 28784479Sbinkertn@umich.eduimmediately to the left of the <tt>seen_A</tt> symbol. In this case, 28794479Sbinkertn@umich.eduit would be the value of <tt>A</tt> in the <tt>foo</tt> rule 28804479Sbinkertn@umich.eduimmediately above. Like other rules, a value can be returned from an 28814479Sbinkertn@umich.eduembedded action by simply assigning it to <tt>p[0]</tt> 28824479Sbinkertn@umich.edu 28834479Sbinkertn@umich.edu<p> 28844479Sbinkertn@umich.eduThe use of embedded actions can sometimes introduce extra shift/reduce conflicts. For example, 28854479Sbinkertn@umich.eduthis grammar has no conflicts: 28864479Sbinkertn@umich.edu 28874479Sbinkertn@umich.edu<blockquote> 28884479Sbinkertn@umich.edu<pre> 28894479Sbinkertn@umich.edudef p_foo(p): 28904479Sbinkertn@umich.edu """foo : abcd 28914479Sbinkertn@umich.edu | abcx""" 28924479Sbinkertn@umich.edu 28934479Sbinkertn@umich.edudef p_abcd(p): 28944479Sbinkertn@umich.edu "abcd : A B C D" 28954479Sbinkertn@umich.edu 28964479Sbinkertn@umich.edudef p_abcx(p): 28974479Sbinkertn@umich.edu "abcx : A B C X" 28984479Sbinkertn@umich.edu</pre> 28994479Sbinkertn@umich.edu</blockquote> 29004479Sbinkertn@umich.edu 29014479Sbinkertn@umich.eduHowever, if you insert an embedded action into one of the rules like this, 29024479Sbinkertn@umich.edu 29034479Sbinkertn@umich.edu<blockquote> 29044479Sbinkertn@umich.edu<pre> 29054479Sbinkertn@umich.edudef p_foo(p): 29064479Sbinkertn@umich.edu """foo : abcd 29074479Sbinkertn@umich.edu | abcx""" 29084479Sbinkertn@umich.edu 29094479Sbinkertn@umich.edudef p_abcd(p): 29104479Sbinkertn@umich.edu "abcd : A B C D" 29114479Sbinkertn@umich.edu 29124479Sbinkertn@umich.edudef p_abcx(p): 29134479Sbinkertn@umich.edu "abcx : A B seen_AB C X" 29144479Sbinkertn@umich.edu 29154479Sbinkertn@umich.edudef p_seen_AB(p): 29164479Sbinkertn@umich.edu "seen_AB :" 29174479Sbinkertn@umich.edu</pre> 29184479Sbinkertn@umich.edu</blockquote> 29194479Sbinkertn@umich.edu 29206498Snate@binkert.organ extra shift-reduce conflict will be introduced. This conflict is 29216498Snate@binkert.orgcaused by the fact that the same symbol <tt>C</tt> appears next in 29226498Snate@binkert.orgboth the <tt>abcd</tt> and <tt>abcx</tt> rules. The parser can either 29236498Snate@binkert.orgshift the symbol (<tt>abcd</tt> rule) or reduce the empty 29246498Snate@binkert.orgrule <tt>seen_AB</tt> (<tt>abcx</tt> rule). 29254479Sbinkertn@umich.edu 29264479Sbinkertn@umich.edu<p> 29274479Sbinkertn@umich.eduA common use of embedded rules is to control other aspects of parsing 29284479Sbinkertn@umich.edusuch as scoping of local variables. For example, if you were parsing C code, you might 29294479Sbinkertn@umich.eduwrite code like this: 29304479Sbinkertn@umich.edu 29314479Sbinkertn@umich.edu<blockquote> 29324479Sbinkertn@umich.edu<pre> 29334479Sbinkertn@umich.edudef p_statements_block(p): 29344479Sbinkertn@umich.edu "statements: LBRACE new_scope statements RBRACE""" 29354479Sbinkertn@umich.edu # Action code 29364479Sbinkertn@umich.edu ... 29374479Sbinkertn@umich.edu pop_scope() # Return to previous scope 29384479Sbinkertn@umich.edu 29394479Sbinkertn@umich.edudef p_new_scope(p): 29404479Sbinkertn@umich.edu "new_scope :" 29414479Sbinkertn@umich.edu # Create a new scope for local variables 29424479Sbinkertn@umich.edu s = new_scope() 29434479Sbinkertn@umich.edu push_scope(s) 29444479Sbinkertn@umich.edu ... 29454479Sbinkertn@umich.edu</pre> 29464479Sbinkertn@umich.edu</blockquote> 29474479Sbinkertn@umich.edu 29486498Snate@binkert.orgIn this case, the embedded action <tt>new_scope</tt> executes 29496498Snate@binkert.orgimmediately after a <tt>LBRACE</tt> (<tt>{</tt>) symbol is parsed. 29506498Snate@binkert.orgThis might adjust internal symbol tables and other aspects of the 29516498Snate@binkert.orgparser. Upon completion of the rule <tt>statements_block</tt>, code 29526498Snate@binkert.orgmight undo the operations performed in the embedded action 29536498Snate@binkert.org(e.g., <tt>pop_scope()</tt>). 29546498Snate@binkert.org 29556498Snate@binkert.org<H3><a name="ply_nn36"></a>6.12 Miscellaneous Yacc Notes</H3> 29564479Sbinkertn@umich.edu 29572632Sstever@eecs.umich.edu 29582632Sstever@eecs.umich.edu<ul> 29594479Sbinkertn@umich.edu<li>The default parsing method is LALR. To use SLR instead, run yacc() as follows: 29604479Sbinkertn@umich.edu 29614479Sbinkertn@umich.edu<blockquote> 29624479Sbinkertn@umich.edu<pre> 29634479Sbinkertn@umich.eduyacc.yacc(method="SLR") 29644479Sbinkertn@umich.edu</pre> 29654479Sbinkertn@umich.edu</blockquote> 29664479Sbinkertn@umich.eduNote: LALR table generation takes approximately twice as long as SLR table generation. There is no 29674479Sbinkertn@umich.edudifference in actual parsing performance---the same code is used in both cases. LALR is preferred when working 29684479Sbinkertn@umich.eduwith more complicated grammars since it is more powerful. 29694479Sbinkertn@umich.edu 29704479Sbinkertn@umich.edu<p> 29714479Sbinkertn@umich.edu 29722632Sstever@eecs.umich.edu<li>By default, <tt>yacc.py</tt> relies on <tt>lex.py</tt> for tokenizing. However, an alternative tokenizer 29732632Sstever@eecs.umich.educan be supplied as follows: 29742632Sstever@eecs.umich.edu 29752632Sstever@eecs.umich.edu<blockquote> 29762632Sstever@eecs.umich.edu<pre> 29772632Sstever@eecs.umich.eduyacc.parse(lexer=x) 29782632Sstever@eecs.umich.edu</pre> 29792632Sstever@eecs.umich.edu</blockquote> 29802632Sstever@eecs.umich.eduin this case, <tt>x</tt> must be a Lexer object that minimally has a <tt>x.token()</tt> method for retrieving the next 29812632Sstever@eecs.umich.edutoken. If an input string is given to <tt>yacc.parse()</tt>, the lexer must also have an <tt>x.input()</tt> method. 29822632Sstever@eecs.umich.edu 29832632Sstever@eecs.umich.edu<p> 29842632Sstever@eecs.umich.edu<li>By default, the yacc generates tables in debugging mode (which produces the parser.out file and other output). 29852632Sstever@eecs.umich.eduTo disable this, use 29862632Sstever@eecs.umich.edu 29872632Sstever@eecs.umich.edu<blockquote> 29882632Sstever@eecs.umich.edu<pre> 29892632Sstever@eecs.umich.eduyacc.yacc(debug=0) 29902632Sstever@eecs.umich.edu</pre> 29912632Sstever@eecs.umich.edu</blockquote> 29922632Sstever@eecs.umich.edu 29932632Sstever@eecs.umich.edu<p> 29942632Sstever@eecs.umich.edu<li>To change the name of the <tt>parsetab.py</tt> file, use: 29952632Sstever@eecs.umich.edu 29962632Sstever@eecs.umich.edu<blockquote> 29972632Sstever@eecs.umich.edu<pre> 29982632Sstever@eecs.umich.eduyacc.yacc(tabmodule="foo") 29992632Sstever@eecs.umich.edu</pre> 30002632Sstever@eecs.umich.edu</blockquote> 30012632Sstever@eecs.umich.edu 30024479Sbinkertn@umich.edu<p> 30034479Sbinkertn@umich.edu<li>To change the directory in which the <tt>parsetab.py</tt> file (and other output files) are written, use: 30044479Sbinkertn@umich.edu<blockquote> 30054479Sbinkertn@umich.edu<pre> 30064479Sbinkertn@umich.eduyacc.yacc(tabmodule="foo",outputdir="somedirectory") 30074479Sbinkertn@umich.edu</pre> 30084479Sbinkertn@umich.edu</blockquote> 30094479Sbinkertn@umich.edu 30104479Sbinkertn@umich.edu<p> 30114479Sbinkertn@umich.edu<li>To prevent yacc from generating any kind of parser table file, use: 30124479Sbinkertn@umich.edu<blockquote> 30134479Sbinkertn@umich.edu<pre> 30144479Sbinkertn@umich.eduyacc.yacc(write_tables=0) 30154479Sbinkertn@umich.edu</pre> 30164479Sbinkertn@umich.edu</blockquote> 30174479Sbinkertn@umich.edu 30184479Sbinkertn@umich.eduNote: If you disable table generation, yacc() will regenerate the parsing tables 30194479Sbinkertn@umich.edueach time it runs (which may take awhile depending on how large your grammar is). 30204479Sbinkertn@umich.edu 30212632Sstever@eecs.umich.edu<P> 30222632Sstever@eecs.umich.edu<li>To print copious amounts of debugging during parsing, use: 30232632Sstever@eecs.umich.edu 30242632Sstever@eecs.umich.edu<blockquote> 30252632Sstever@eecs.umich.edu<pre> 30266498Snate@binkert.orgyacc.parse(debug=1) 30274479Sbinkertn@umich.edu</pre> 30284479Sbinkertn@umich.edu</blockquote> 30294479Sbinkertn@umich.edu 30304479Sbinkertn@umich.edu<p> 30312632Sstever@eecs.umich.edu<li>The <tt>yacc.yacc()</tt> function really returns a parser object. If you want to support multiple 30322632Sstever@eecs.umich.eduparsers in the same application, do this: 30332632Sstever@eecs.umich.edu 30342632Sstever@eecs.umich.edu<blockquote> 30352632Sstever@eecs.umich.edu<pre> 30362632Sstever@eecs.umich.edup = yacc.yacc() 30372632Sstever@eecs.umich.edu... 30382632Sstever@eecs.umich.edup.parse() 30392632Sstever@eecs.umich.edu</pre> 30402632Sstever@eecs.umich.edu</blockquote> 30412632Sstever@eecs.umich.edu 30422632Sstever@eecs.umich.eduNote: The function <tt>yacc.parse()</tt> is bound to the last parser that was generated. 30432632Sstever@eecs.umich.edu 30442632Sstever@eecs.umich.edu<p> 30454479Sbinkertn@umich.edu<li>Since the generation of the LALR tables is relatively expensive, previously generated tables are 30462632Sstever@eecs.umich.educached and reused if possible. The decision to regenerate the tables is determined by taking an MD5 30472632Sstever@eecs.umich.educhecksum of all grammar rules and precedence rules. Only in the event of a mismatch are the tables regenerated. 30482632Sstever@eecs.umich.edu 30492632Sstever@eecs.umich.edu<p> 30502632Sstever@eecs.umich.eduIt should be noted that table generation is reasonably efficient, even for grammars that involve around a 100 rules 30512632Sstever@eecs.umich.eduand several hundred states. For more complex languages such as C, table generation may take 30-60 seconds on a slow 30522632Sstever@eecs.umich.edumachine. Please be patient. 30532632Sstever@eecs.umich.edu 30542632Sstever@eecs.umich.edu<p> 30554479Sbinkertn@umich.edu<li>Since LR parsing is driven by tables, the performance of the parser is largely independent of the 30564479Sbinkertn@umich.edusize of the grammar. The biggest bottlenecks will be the lexer and the complexity of the code in your grammar rules. 30572632Sstever@eecs.umich.edu</ul> 30582632Sstever@eecs.umich.edu 30596498Snate@binkert.org<H2><a name="ply_nn37"></a>7. Multiple Parsers and Lexers</H2> 30604479Sbinkertn@umich.edu 30612632Sstever@eecs.umich.edu 30622632Sstever@eecs.umich.eduIn advanced parsing applications, you may want to have multiple 30636498Snate@binkert.orgparsers and lexers. 30642632Sstever@eecs.umich.edu 30652632Sstever@eecs.umich.edu<p> 30666498Snate@binkert.orgAs a general rules this isn't a problem. However, to make it work, 30676498Snate@binkert.orgyou need to carefully make sure everything gets hooked up correctly. 30686498Snate@binkert.orgFirst, make sure you save the objects returned by <tt>lex()</tt> and 30696498Snate@binkert.org<tt>yacc()</tt>. For example: 30702632Sstever@eecs.umich.edu 30712632Sstever@eecs.umich.edu<blockquote> 30722632Sstever@eecs.umich.edu<pre> 30732632Sstever@eecs.umich.edulexer = lex.lex() # Return lexer object 30742632Sstever@eecs.umich.eduparser = yacc.yacc() # Return parser object 30752632Sstever@eecs.umich.edu</pre> 30762632Sstever@eecs.umich.edu</blockquote> 30772632Sstever@eecs.umich.edu 30786498Snate@binkert.orgNext, when parsing, make sure you give the <tt>parse()</tt> function a reference to the lexer it 30796498Snate@binkert.orgshould be using. For example: 30804479Sbinkertn@umich.edu 30814479Sbinkertn@umich.edu<blockquote> 30824479Sbinkertn@umich.edu<pre> 30834479Sbinkertn@umich.eduparser.parse(text,lexer=lexer) 30844479Sbinkertn@umich.edu</pre> 30854479Sbinkertn@umich.edu</blockquote> 30864479Sbinkertn@umich.edu 30876498Snate@binkert.orgIf you forget to do this, the parser will use the last lexer 30886498Snate@binkert.orgcreated--which is not always what you want. 30896498Snate@binkert.org 30906498Snate@binkert.org<p> 30916498Snate@binkert.orgWithin lexer and parser rule functions, these objects are also 30926498Snate@binkert.orgavailable. In the lexer, the "lexer" attribute of a token refers to 30936498Snate@binkert.orgthe lexer object that triggered the rule. For example: 30942632Sstever@eecs.umich.edu 30952632Sstever@eecs.umich.edu<blockquote> 30962632Sstever@eecs.umich.edu<pre> 30972632Sstever@eecs.umich.edudef t_NUMBER(t): 30982632Sstever@eecs.umich.edu r'\d+' 30992632Sstever@eecs.umich.edu ... 31002632Sstever@eecs.umich.edu print t.lexer # Show lexer object 31012632Sstever@eecs.umich.edu</pre> 31022632Sstever@eecs.umich.edu</blockquote> 31032632Sstever@eecs.umich.edu 31042632Sstever@eecs.umich.eduIn the parser, the "lexer" and "parser" attributes refer to the lexer 31052632Sstever@eecs.umich.eduand parser objects respectively. 31062632Sstever@eecs.umich.edu 31072632Sstever@eecs.umich.edu<blockquote> 31082632Sstever@eecs.umich.edu<pre> 31094479Sbinkertn@umich.edudef p_expr_plus(p): 31102632Sstever@eecs.umich.edu 'expr : expr PLUS expr' 31112632Sstever@eecs.umich.edu ... 31124479Sbinkertn@umich.edu print p.parser # Show parser object 31134479Sbinkertn@umich.edu print p.lexer # Show lexer object 31142632Sstever@eecs.umich.edu</pre> 31152632Sstever@eecs.umich.edu</blockquote> 31162632Sstever@eecs.umich.edu 31172632Sstever@eecs.umich.eduIf necessary, arbitrary attributes can be attached to the lexer or parser object. 31182632Sstever@eecs.umich.eduFor example, if you wanted to have different parsing modes, you could attach a mode 31192632Sstever@eecs.umich.eduattribute to the parser object and look at it later. 31202632Sstever@eecs.umich.edu 31216498Snate@binkert.org<H2><a name="ply_nn38"></a>8. Using Python's Optimized Mode</H2> 31224479Sbinkertn@umich.edu 31232632Sstever@eecs.umich.edu 31242632Sstever@eecs.umich.eduBecause PLY uses information from doc-strings, parsing and lexing 31252632Sstever@eecs.umich.eduinformation must be gathered while running the Python interpreter in 31262632Sstever@eecs.umich.edunormal mode (i.e., not with the -O or -OO options). However, if you 31272632Sstever@eecs.umich.eduspecify optimized mode like this: 31282632Sstever@eecs.umich.edu 31292632Sstever@eecs.umich.edu<blockquote> 31302632Sstever@eecs.umich.edu<pre> 31312632Sstever@eecs.umich.edulex.lex(optimize=1) 31322632Sstever@eecs.umich.eduyacc.yacc(optimize=1) 31332632Sstever@eecs.umich.edu</pre> 31342632Sstever@eecs.umich.edu</blockquote> 31352632Sstever@eecs.umich.edu 31362632Sstever@eecs.umich.eduthen PLY can later be used when Python runs in optimized mode. To make this work, 31372632Sstever@eecs.umich.edumake sure you first run Python in normal mode. Once the lexing and parsing tables 31382632Sstever@eecs.umich.eduhave been generated the first time, run Python in optimized mode. PLY will use 31392632Sstever@eecs.umich.eduthe tables without the need for doc strings. 31402632Sstever@eecs.umich.edu 31412632Sstever@eecs.umich.edu<p> 31422632Sstever@eecs.umich.eduBeware: running PLY in optimized mode disables a lot of error 31432632Sstever@eecs.umich.educhecking. You should only do this when your project has stabilized 31446498Snate@binkert.organd you don't need to do any debugging. One of the purposes of 31456498Snate@binkert.orgoptimized mode is to substantially decrease the startup time of 31466498Snate@binkert.orgyour compiler (by assuming that everything is already properly 31476498Snate@binkert.orgspecified and works). 31486498Snate@binkert.org 31496498Snate@binkert.org<H2><a name="ply_nn44"></a>9. Advanced Debugging</H2> 31506498Snate@binkert.org 31516498Snate@binkert.org 31526498Snate@binkert.org<p> 31536498Snate@binkert.orgDebugging a compiler is typically not an easy task. PLY provides some 31546498Snate@binkert.orgadvanced diagonistic capabilities through the use of Python's 31556498Snate@binkert.org<tt>logging</tt> module. The next two sections describe this: 31566498Snate@binkert.org 31576498Snate@binkert.org<H3><a name="ply_nn45"></a>9.1 Debugging the lex() and yacc() commands</H3> 31586498Snate@binkert.org 31596498Snate@binkert.org 31606498Snate@binkert.org<p> 31616498Snate@binkert.orgBoth the <tt>lex()</tt> and <tt>yacc()</tt> commands have a debugging 31626498Snate@binkert.orgmode that can be enabled using the <tt>debug</tt> flag. For example: 31636498Snate@binkert.org 31646498Snate@binkert.org<blockquote> 31656498Snate@binkert.org<pre> 31666498Snate@binkert.orglex.lex(debug=True) 31676498Snate@binkert.orgyacc.yacc(debug=True) 31686498Snate@binkert.org</pre> 31696498Snate@binkert.org</blockquote> 31706498Snate@binkert.org 31716498Snate@binkert.orgNormally, the output produced by debugging is routed to either 31726498Snate@binkert.orgstandard error or, in the case of <tt>yacc()</tt>, to a file 31736498Snate@binkert.org<tt>parser.out</tt>. This output can be more carefully controlled 31746498Snate@binkert.orgby supplying a logging object. Here is an example that adds 31756498Snate@binkert.orginformation about where different debugging messages are coming from: 31766498Snate@binkert.org 31776498Snate@binkert.org<blockquote> 31786498Snate@binkert.org<pre> 31796498Snate@binkert.org# Set up a logging object 31806498Snate@binkert.orgimport logging 31816498Snate@binkert.orglogging.basicConfig( 31826498Snate@binkert.org level = logging.DEBUG, 31836498Snate@binkert.org filename = "parselog.txt", 31846498Snate@binkert.org filemode = "w", 31856498Snate@binkert.org format = "%(filename)10s:%(lineno)4d:%(message)s" 31866498Snate@binkert.org) 31876498Snate@binkert.orglog = logging.getLogger() 31886498Snate@binkert.org 31896498Snate@binkert.orglex.lex(debug=True,debuglog=log) 31906498Snate@binkert.orgyacc.yacc(debug=True,debuglog=log) 31916498Snate@binkert.org</pre> 31926498Snate@binkert.org</blockquote> 31936498Snate@binkert.org 31946498Snate@binkert.orgIf you supply a custom logger, the amount of debugging 31956498Snate@binkert.orginformation produced can be controlled by setting the logging level. 31966498Snate@binkert.orgTypically, debugging messages are either issued at the <tt>DEBUG</tt>, 31976498Snate@binkert.org<tt>INFO</tt>, or <tt>WARNING</tt> levels. 31986498Snate@binkert.org 31996498Snate@binkert.org<p> 32006498Snate@binkert.orgPLY's error messages and warnings are also produced using the logging 32016498Snate@binkert.orginterface. This can be controlled by passing a logging object 32026498Snate@binkert.orgusing the <tt>errorlog</tt> parameter. 32036498Snate@binkert.org 32046498Snate@binkert.org<blockquote> 32056498Snate@binkert.org<pre> 32066498Snate@binkert.orglex.lex(errorlog=log) 32076498Snate@binkert.orgyacc.yacc(errorlog=log) 32086498Snate@binkert.org</pre> 32096498Snate@binkert.org</blockquote> 32106498Snate@binkert.org 32116498Snate@binkert.orgIf you want to completely silence warnings, you can either pass in a 32126498Snate@binkert.orglogging object with an appropriate filter level or use the <tt>NullLogger</tt> 32136498Snate@binkert.orgobject defined in either <tt>lex</tt> or <tt>yacc</tt>. For example: 32146498Snate@binkert.org 32156498Snate@binkert.org<blockquote> 32166498Snate@binkert.org<pre> 32176498Snate@binkert.orgyacc.yacc(errorlog=yacc.NullLogger()) 32186498Snate@binkert.org</pre> 32196498Snate@binkert.org</blockquote> 32206498Snate@binkert.org 32216498Snate@binkert.org<H3><a name="ply_nn46"></a>9.2 Run-time Debugging</H3> 32226498Snate@binkert.org 32236498Snate@binkert.org 32246498Snate@binkert.org<p> 32256498Snate@binkert.orgTo enable run-time debugging of a parser, use the <tt>debug</tt> option to parse. This 32266498Snate@binkert.orgoption can either be an integer (which simply turns debugging on or off) or an instance 32276498Snate@binkert.orgof a logger object. For example: 32286498Snate@binkert.org 32296498Snate@binkert.org<blockquote> 32306498Snate@binkert.org<pre> 32316498Snate@binkert.orglog = logging.getLogger() 32326498Snate@binkert.orgparser.parse(input,debug=log) 32336498Snate@binkert.org</pre> 32346498Snate@binkert.org</blockquote> 32356498Snate@binkert.org 32366498Snate@binkert.orgIf a logging object is passed, you can use its filtering level to control how much 32376498Snate@binkert.orgoutput gets generated. The <tt>INFO</tt> level is used to produce information 32386498Snate@binkert.orgabout rule reductions. The <tt>DEBUG</tt> level will show information about the 32396498Snate@binkert.orgparsing stack, token shifts, and other details. The <tt>ERROR</tt> level shows information 32406498Snate@binkert.orgrelated to parsing errors. 32416498Snate@binkert.org 32426498Snate@binkert.org<p> 32436498Snate@binkert.orgFor very complicated problems, you should pass in a logging object that 32446498Snate@binkert.orgredirects to a file where you can more easily inspect the output after 32456498Snate@binkert.orgexecution. 32466498Snate@binkert.org 32476498Snate@binkert.org<H2><a name="ply_nn39"></a>10. Where to go from here?</H2> 32484479Sbinkertn@umich.edu 32492632Sstever@eecs.umich.edu 32502632Sstever@eecs.umich.eduThe <tt>examples</tt> directory of the PLY distribution contains several simple examples. Please consult a 32512632Sstever@eecs.umich.educompilers textbook for the theory and underlying implementation details or LR parsing. 32522632Sstever@eecs.umich.edu 32532632Sstever@eecs.umich.edu</body> 32542632Sstever@eecs.umich.edu</html> 32552632Sstever@eecs.umich.edu 32562632Sstever@eecs.umich.edu 32572632Sstever@eecs.umich.edu 32582632Sstever@eecs.umich.edu 32592632Sstever@eecs.umich.edu 32602632Sstever@eecs.umich.edu 32612632Sstever@eecs.umich.edu 3262