README revision 2632:1bb2f91485ea
1PLY (Python Lex-Yacc)                   Version 1.2  (November 27, 2002)
2
3David M. Beazley
4Department of Computer Science
5University of Chicago
6Chicago, IL  60637
7beazley@cs.uchicago.edu
8
9Copyright (C) 2001   David M. Beazley
10
11$Header: /home/stever/bk/newmem2/ext/ply/README 1.1 03/06/06 14:53:34-00:00 stever@ $
12
13This library is free software; you can redistribute it and/or
14modify it under the terms of the GNU Lesser General Public
15License as published by the Free Software Foundation; either
16version 2.1 of the License, or (at your option) any later version.
17
18This library is distributed in the hope that it will be useful,
19but WITHOUT ANY WARRANTY; without even the implied warranty of
20MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
21Lesser General Public License for more details.
22
23You should have received a copy of the GNU Lesser General Public
24License along with this library; if not, write to the Free Software
25Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
26
27See the file COPYING for a complete copy of the LGPL.
28
29Introduction
30============
31
32PLY is a 100% Python implementation of the common parsing tools lex
33and yacc.   Although several other parsing tools are available for
34Python, there are several reasons why you might want to consider PLY:
35
36 -  The tools are very closely modeled after traditional lex/yacc.
37    If you know how to use these tools in C, you will find PLY
38    to be similar.
39
40 -  PLY provides *very* extensive error reporting and diagnostic 
41    information to assist in parser construction.  The original
42    implementation was developed for instructional purposes.  As
43    a result, the system tries to identify the most common types
44    of errors made by novice users.  
45
46 -  PLY provides full support for empty productions, error recovery,
47    precedence specifiers, and moderately ambiguous grammars.
48
49 -  Parsing is based on LR-parsing which is fast, memory efficient, 
50    better suited to large grammars, and which has a number of nice
51    properties when dealing with syntax errors and other parsing problems.
52    Currently, PLY builds its parsing tables using the SLR algorithm which 
53    is slightly weaker than LALR(1) used in traditional yacc. 
54
55 -  Like John Aycock's excellent SPARK toolkit, PLY uses Python 
56    reflection to build lexers and parsers.  This greatly simplifies 
57    the task of parser construction since it reduces the number of files
58    and eliminates the need to run a separate lex/yacc tool before
59    running your program.
60
61 -  PLY can be used to build parsers for "real" programming languages.
62    Although it is not ultra-fast due to its Python implementation,
63    PLY can be used to parse grammars consisting of several hundred
64    rules (as might be found for a language like C).  The lexer and LR 
65    parser are also reasonably efficient when parsing typically
66    sized programs.
67
68The original version of PLY was developed for an Introduction to
69Compilers course where students used it to build a compiler for a
70simple Pascal-like language.  Their compiler had to include lexical
71analysis, parsing, type checking, type inference, and generation of
72assembly code for the SPARC processor.  Because of this, the current
73implementation has been extensively tested and debugged.  In addition,
74most of the API and error checking steps have been adapted to address
75common usability problems.
76
77How to Use
78==========
79
80PLY consists of two files : lex.py and yacc.py.  To use the system,
81simply copy these files to your project and import them like standard
82Python modules.
83
84The file doc/ply.html contains complete documentation on how to use
85the system.
86
87The example directory contains several different examples including a
88PLY specification for ANSI C as given in K&R 2nd Ed.   Note: To use
89the examples, you will need to copy the lex.py and yacc.py files to
90the example directory.
91
92A simple example is found at the end of this document
93
94Requirements
95============
96PLY requires the use of Python 2.0 or greater.  It should work on
97just about any platform.
98
99Resources
100=========
101
102More information about PLY can be obtained on the PLY webpage at:
103
104     http://systems.cs.uchicago.edu/ply
105
106For a detailed overview of parsing theory, consult the excellent
107book "Compilers : Principles, Techniques, and Tools" by Aho, Sethi, and
108Ullman.  The topics found in "Lex & Yacc" by Levine, Mason, and Brown
109may also be useful.
110
111Given that this is the first release, I welcome your comments on how
112to improve the current implementation.  See the TODO file for things that
113still need to be done.
114
115Acknowledgments
116===============
117
118A special thanks is in order for all of the students in CS326 who
119suffered through about 25 different versions of these tools :-).
120
121Example
122=======
123
124Here is a simple example showing a PLY implementation of a calculator with variables.
125
126# -----------------------------------------------------------------------------
127# calc.py
128#
129# A simple calculator with variables.
130# -----------------------------------------------------------------------------
131
132tokens = (
133    'NAME','NUMBER',
134    'PLUS','MINUS','TIMES','DIVIDE','EQUALS',
135    'LPAREN','RPAREN',
136    )
137
138# Tokens
139
140t_PLUS    = r'\+'
141t_MINUS   = r'-'
142t_TIMES   = r'\*'
143t_DIVIDE  = r'/'
144t_EQUALS  = r'='
145t_LPAREN  = r'\('
146t_RPAREN  = r'\)'
147t_NAME    = r'[a-zA-Z_][a-zA-Z0-9_]*'
148
149def t_NUMBER(t):
150    r'\d+'
151    try:
152        t.value = int(t.value)
153    except ValueError:
154        print "Integer value too large", t.value
155        t.value = 0
156    return t
157
158# Ignored characters
159t_ignore = " \t"
160
161def t_newline(t):
162    r'\n+'
163    t.lineno += t.value.count("\n")
164    
165def t_error(t):
166    print "Illegal character '%s'" % t.value[0]
167    t.skip(1)
168    
169# Build the lexer
170import lex
171lex.lex()
172
173# Precedence rules for the arithmetic operators
174precedence = (
175    ('left','PLUS','MINUS'),
176    ('left','TIMES','DIVIDE'),
177    ('right','UMINUS'),
178    )
179
180# dictionary of names (for storing variables)
181names = { }
182
183def p_statement_assign(t):
184    'statement : NAME EQUALS expression'
185    names[t[1]] = t[3]
186
187def p_statement_expr(t):
188    'statement : expression'
189    print t[1]
190
191def p_expression_binop(t):
192    '''expression : expression PLUS expression
193                  | expression MINUS expression
194                  | expression TIMES expression
195                  | expression DIVIDE expression'''
196    if t[2] == '+'  : t[0] = t[1] + t[3]
197    elif t[2] == '-': t[0] = t[1] - t[3]
198    elif t[2] == '*': t[0] = t[1] * t[3]
199    elif t[2] == '/': t[0] = t[1] / t[3]
200
201def p_expression_uminus(t):
202    'expression : MINUS expression %prec UMINUS'
203    t[0] = -t[2]
204
205def p_expression_group(t):
206    'expression : LPAREN expression RPAREN'
207    t[0] = t[2]
208
209def p_expression_number(t):
210    'expression : NUMBER'
211    t[0] = t[1]
212
213def p_expression_name(t):
214    'expression : NAME'
215    try:
216        t[0] = names[t[1]]
217    except LookupError:
218        print "Undefined name '%s'" % t[1]
219        t[0] = 0
220
221def p_error(t):
222    print "Syntax error at '%s'" % t.value
223
224import yacc
225yacc.yacc()
226
227while 1:
228    try:
229        s = raw_input('calc > ')
230    except EOFError:
231        break
232    yacc.parse(s)
233
234
235
236
237
238
239
240
241    
242
243
244
245
246
247
248
249
250