1PLY (Python Lex-Yacc)                   Version 3.2
2
3Copyright (C) 2001-2009,
4David M. Beazley (Dabeaz LLC)
5All rights reserved.
6
7Redistribution and use in source and binary forms, with or without
8modification, are permitted provided that the following conditions are
9met:
10
11* Redistributions of source code must retain the above copyright notice,
12  this list of conditions and the following disclaimer.  
13* Redistributions in binary form must reproduce the above copyright notice, 
14  this list of conditions and the following disclaimer in the documentation
15  and/or other materials provided with the distribution.  
16* Neither the name of the David Beazley or Dabeaz LLC may be used to
17  endorse or promote products derived from this software without
18  specific prior written permission. 
19
20THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31
32Introduction
33============
34
35PLY is a 100% Python implementation of the common parsing tools lex
36and yacc. Here are a few highlights:
37
38 -  PLY is very closely modeled after traditional lex/yacc.
39    If you know how to use these tools in C, you will find PLY
40    to be similar.
41
42 -  PLY provides *very* extensive error reporting and diagnostic 
43    information to assist in parser construction.  The original
44    implementation was developed for instructional purposes.  As
45    a result, the system tries to identify the most common types
46    of errors made by novice users.  
47
48 -  PLY provides full support for empty productions, error recovery,
49    precedence specifiers, and moderately ambiguous grammars.
50
51 -  Parsing is based on LR-parsing which is fast, memory efficient, 
52    better suited to large grammars, and which has a number of nice
53    properties when dealing with syntax errors and other parsing problems.
54    Currently, PLY builds its parsing tables using the LALR(1)
55    algorithm used in yacc.
56
57 -  PLY uses Python introspection features to build lexers and parsers.  
58    This greatly simplifies the task of parser construction since it reduces 
59    the number of files and eliminates the need to run a separate lex/yacc 
60    tool before running your program.
61
62 -  PLY can be used to build parsers for "real" programming languages.
63    Although it is not ultra-fast due to its Python implementation,
64    PLY can be used to parse grammars consisting of several hundred
65    rules (as might be found for a language like C).  The lexer and LR 
66    parser are also reasonably efficient when parsing typically
67    sized programs.  People have used PLY to build parsers for
68    C, C++, ADA, and other real programming languages.
69
70How to Use
71==========
72
73PLY consists of two files : lex.py and yacc.py.  These are contained
74within the 'ply' directory which may also be used as a Python package.
75To use PLY, simply copy the 'ply' directory to your project and import
76lex and yacc from the associated 'ply' package.  For example:
77
78     import ply.lex as lex
79     import ply.yacc as yacc
80
81Alternatively, you can copy just the files lex.py and yacc.py
82individually and use them as modules.  For example:
83
84     import lex
85     import yacc
86
87The file setup.py can be used to install ply using distutils.
88
89The file doc/ply.html contains complete documentation on how to use
90the system.
91
92The example directory contains several different examples including a
93PLY specification for ANSI C as given in K&R 2nd Ed.   
94
95A simple example is found at the end of this document
96
97Requirements
98============
99PLY requires the use of Python 2.2 or greater.  However, you should
100use the latest Python release if possible.  It should work on just
101about any platform.  PLY has been tested with both CPython and Jython.
102It also seems to work with IronPython.
103
104Resources
105=========
106More information about PLY can be obtained on the PLY webpage at:
107
108     http://www.dabeaz.com/ply
109
110For a detailed overview of parsing theory, consult the excellent
111book "Compilers : Principles, Techniques, and Tools" by Aho, Sethi, and
112Ullman.  The topics found in "Lex & Yacc" by Levine, Mason, and Brown
113may also be useful.
114
115A Google group for PLY can be found at
116
117     http://groups.google.com/group/ply-hack
118
119Acknowledgments
120===============
121A special thanks is in order for all of the students in CS326 who
122suffered through about 25 different versions of these tools :-).
123
124The CHANGES file acknowledges those who have contributed patches.
125
126Elias Ioup did the first implementation of LALR(1) parsing in PLY-1.x. 
127Andrew Waters and Markus Schoepflin were instrumental in reporting bugs
128and testing a revised LALR(1) implementation for PLY-2.0.
129
130Special Note for PLY-3.0
131========================
132PLY-3.0 the first PLY release to support Python 3. However, backwards
133compatibility with Python 2.2 is still preserved. PLY provides dual
134Python 2/3 compatibility by restricting its implementation to a common
135subset of basic language features. You should not convert PLY using
1362to3--it is not necessary and may in fact break the implementation.
137
138Example
139=======
140
141Here is a simple example showing a PLY implementation of a calculator
142with variables.
143
144# -----------------------------------------------------------------------------
145# calc.py
146#
147# A simple calculator with variables.
148# -----------------------------------------------------------------------------
149
150tokens = (
151    'NAME','NUMBER',
152    'PLUS','MINUS','TIMES','DIVIDE','EQUALS',
153    'LPAREN','RPAREN',
154    )
155
156# Tokens
157
158t_PLUS    = r'\+'
159t_MINUS   = r'-'
160t_TIMES   = r'\*'
161t_DIVIDE  = r'/'
162t_EQUALS  = r'='
163t_LPAREN  = r'\('
164t_RPAREN  = r'\)'
165t_NAME    = r'[a-zA-Z_][a-zA-Z0-9_]*'
166
167def t_NUMBER(t):
168    r'\d+'
169    t.value = int(t.value)
170    return t
171
172# Ignored characters
173t_ignore = " \t"
174
175def t_newline(t):
176    r'\n+'
177    t.lexer.lineno += t.value.count("\n")
178    
179def t_error(t):
180    print "Illegal character '%s'" % t.value[0]
181    t.lexer.skip(1)
182    
183# Build the lexer
184import ply.lex as lex
185lex.lex()
186
187# Precedence rules for the arithmetic operators
188precedence = (
189    ('left','PLUS','MINUS'),
190    ('left','TIMES','DIVIDE'),
191    ('right','UMINUS'),
192    )
193
194# dictionary of names (for storing variables)
195names = { }
196
197def p_statement_assign(p):
198    'statement : NAME EQUALS expression'
199    names[p[1]] = p[3]
200
201def p_statement_expr(p):
202    'statement : expression'
203    print p[1]
204
205def p_expression_binop(p):
206    '''expression : expression PLUS expression
207                  | expression MINUS expression
208                  | expression TIMES expression
209                  | expression DIVIDE expression'''
210    if p[2] == '+'  : p[0] = p[1] + p[3]
211    elif p[2] == '-': p[0] = p[1] - p[3]
212    elif p[2] == '*': p[0] = p[1] * p[3]
213    elif p[2] == '/': p[0] = p[1] / p[3]
214
215def p_expression_uminus(p):
216    'expression : MINUS expression %prec UMINUS'
217    p[0] = -p[2]
218
219def p_expression_group(p):
220    'expression : LPAREN expression RPAREN'
221    p[0] = p[2]
222
223def p_expression_number(p):
224    'expression : NUMBER'
225    p[0] = p[1]
226
227def p_expression_name(p):
228    'expression : NAME'
229    try:
230        p[0] = names[p[1]]
231    except LookupError:
232        print "Undefined name '%s'" % p[1]
233        p[0] = 0
234
235def p_error(p):
236    print "Syntax error at '%s'" % p.value
237
238import ply.yacc as yacc
239yacc.yacc()
240
241while 1:
242    try:
243        s = raw_input('calc > ')
244    except EOFError:
245        break
246    yacc.parse(s)
247
248
249Bug Reports and Patches
250=======================
251My goal with PLY is to simply have a decent lex/yacc implementation
252for Python.  As a general rule, I don't spend huge amounts of time
253working on it unless I receive very specific bug reports and/or
254patches to fix problems. I also try to incorporate submitted feature
255requests and enhancements into each new version.  To contact me about
256bugs and/or new features, please send email to dave@dabeaz.com.
257
258In addition there is a Google group for discussing PLY related issues at
259
260    http://groups.google.com/group/ply-hack
261 
262-- Dave
263
264
265
266
267
268
269
270
271
272