README revision 4479
1PLY (Python Lex-Yacc)                   Version 2.3  (February 18, 2007)
2
3David M. Beazley (dave@dabeaz.com)
4
5Copyright (C) 2001-2007   David M. Beazley
6
7This library is free software; you can redistribute it and/or
8modify it under the terms of the GNU Lesser General Public
9License as published by the Free Software Foundation; either
10version 2.1 of the License, or (at your option) any later version.
11
12This library is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15Lesser General Public License for more details.
16
17You should have received a copy of the GNU Lesser General Public
18License along with this library; if not, write to the Free Software
19Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20
21See the file COPYING for a complete copy of the LGPL.
22
23Introduction
24============
25
26PLY is a 100% Python implementation of the common parsing tools lex
27and yacc.   Although several other parsing tools are available for
28Python, there are several reasons why you might want to consider PLY:
29
30 -  The tools are very closely modeled after traditional lex/yacc.
31    If you know how to use these tools in C, you will find PLY
32    to be similar.
33
34 -  PLY provides *very* extensive error reporting and diagnostic 
35    information to assist in parser construction.  The original
36    implementation was developed for instructional purposes.  As
37    a result, the system tries to identify the most common types
38    of errors made by novice users.  
39
40 -  PLY provides full support for empty productions, error recovery,
41    precedence specifiers, and moderately ambiguous grammars.
42
43 -  Parsing is based on LR-parsing which is fast, memory efficient, 
44    better suited to large grammars, and which has a number of nice
45    properties when dealing with syntax errors and other parsing problems.
46    Currently, PLY builds its parsing tables using the SLR algorithm which 
47    is slightly weaker than LALR(1) used in traditional yacc. 
48
49 -  PLY uses Python introspection features to build lexers and parsers.  
50    This greatly simplifies the task of parser construction since it reduces 
51    the number of files and eliminates the need to run a separate lex/yacc 
52    tool before running your program.
53
54 -  PLY can be used to build parsers for "real" programming languages.
55    Although it is not ultra-fast due to its Python implementation,
56    PLY can be used to parse grammars consisting of several hundred
57    rules (as might be found for a language like C).  The lexer and LR 
58    parser are also reasonably efficient when parsing typically
59    sized programs.
60
61The original version of PLY was developed for an Introduction to
62Compilers course where students used it to build a compiler for a
63simple Pascal-like language.  Their compiler had to include lexical
64analysis, parsing, type checking, type inference, and generation of
65assembly code for the SPARC processor.  Because of this, the current
66implementation has been extensively tested and debugged.  In addition,
67most of the API and error checking steps have been adapted to address
68common usability problems.
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.1 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.
102However, it does not seem 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-2.x
131========================
132PLY-2.0 is the first in a series of PLY releases that will be adding a
133variety of significant new features.  The first release in this series
134(Ply-2.0) should be 100% compatible with all previous Ply-1.x releases
135except for the fact that Ply-2.0 features a correct implementation of
136LALR(1) table generation.  
137
138If you have suggestions for improving PLY in future 2.x releases, please
139contact me.   - Dave
140
141Example
142=======
143
144Here is a simple example showing a PLY implementation of a calculator
145with variables.
146
147# -----------------------------------------------------------------------------
148# calc.py
149#
150# A simple calculator with variables.
151# -----------------------------------------------------------------------------
152
153tokens = (
154    'NAME','NUMBER',
155    'PLUS','MINUS','TIMES','DIVIDE','EQUALS',
156    'LPAREN','RPAREN',
157    )
158
159# Tokens
160
161t_PLUS    = r'\+'
162t_MINUS   = r'-'
163t_TIMES   = r'\*'
164t_DIVIDE  = r'/'
165t_EQUALS  = r'='
166t_LPAREN  = r'\('
167t_RPAREN  = r'\)'
168t_NAME    = r'[a-zA-Z_][a-zA-Z0-9_]*'
169
170def t_NUMBER(t):
171    r'\d+'
172    try:
173        t.value = int(t.value)
174    except ValueError:
175        print "Integer value too large", t.value
176        t.value = 0
177    return t
178
179# Ignored characters
180t_ignore = " \t"
181
182def t_newline(t):
183    r'\n+'
184    t.lexer.lineno += t.value.count("\n")
185    
186def t_error(t):
187    print "Illegal character '%s'" % t.value[0]
188    t.lexer.skip(1)
189    
190# Build the lexer
191import ply.lex as lex
192lex.lex()
193
194# Precedence rules for the arithmetic operators
195precedence = (
196    ('left','PLUS','MINUS'),
197    ('left','TIMES','DIVIDE'),
198    ('right','UMINUS'),
199    )
200
201# dictionary of names (for storing variables)
202names = { }
203
204def p_statement_assign(p):
205    'statement : NAME EQUALS expression'
206    names[p[1]] = p[3]
207
208def p_statement_expr(p):
209    'statement : expression'
210    print p[1]
211
212def p_expression_binop(p):
213    '''expression : expression PLUS expression
214                  | expression MINUS expression
215                  | expression TIMES expression
216                  | expression DIVIDE expression'''
217    if p[2] == '+'  : p[0] = p[1] + p[3]
218    elif p[2] == '-': p[0] = p[1] - p[3]
219    elif p[2] == '*': p[0] = p[1] * p[3]
220    elif p[2] == '/': p[0] = p[1] / p[3]
221
222def p_expression_uminus(p):
223    'expression : MINUS expression %prec UMINUS'
224    p[0] = -p[2]
225
226def p_expression_group(p):
227    'expression : LPAREN expression RPAREN'
228    p[0] = p[2]
229
230def p_expression_number(p):
231    'expression : NUMBER'
232    p[0] = p[1]
233
234def p_expression_name(p):
235    'expression : NAME'
236    try:
237        p[0] = names[p[1]]
238    except LookupError:
239        print "Undefined name '%s'" % p[1]
240        p[0] = 0
241
242def p_error(p):
243    print "Syntax error at '%s'" % p.value
244
245import ply.yacc as yacc
246yacc.yacc()
247
248while 1:
249    try:
250        s = raw_input('calc > ')
251    except EOFError:
252        break
253    yacc.parse(s)
254
255
256Bug Reports and Patches
257=======================
258Because of the extremely specialized and advanced nature of PLY, I
259rarely spend much time working on it unless I receive very specific
260bug-reports and/or patches to fix problems. I also try to incorporate
261submitted feature requests and enhancements into each new version.  To
262contact me about bugs and/or new features, please send email to
263dave@dabeaz.com.
264
265In addition there is a Google group for discussing PLY related issues at
266
267    http://groups.google.com/group/ply-hack
268 
269-- Dave
270
271
272
273
274
275
276
277
278
279