|
7267
|
1 PLY (Python Lex-Yacc) Version 3.8
|
|
|
2
|
|
|
3 Copyright (C) 2001-2015,
|
|
|
4 David M. Beazley (Dabeaz LLC)
|
|
|
5 All rights reserved.
|
|
|
6
|
|
|
7 Redistribution and use in source and binary forms, with or without
|
|
|
8 modification, are permitted provided that the following conditions are
|
|
|
9 met:
|
|
|
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
|
|
|
20 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
|
|
|
21 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
|
|
|
22 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
|
|
|
23 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
|
|
|
24 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
|
|
|
25 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
|
|
|
26 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
|
|
|
27 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
|
|
|
28 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
|
|
29 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
|
|
|
30 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
|
31
|
|
|
32 Introduction
|
|
|
33 ============
|
|
|
34
|
|
|
35 PLY is a 100% Python implementation of the common parsing tools lex
|
|
|
36 and 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
|
|
|
70 How to Use
|
|
|
71 ==========
|
|
|
72
|
|
|
73 PLY consists of two files : lex.py and yacc.py. These are contained
|
|
|
74 within the 'ply' directory which may also be used as a Python package.
|
|
|
75 To use PLY, simply copy the 'ply' directory to your project and import
|
|
|
76 lex and yacc from the associated 'ply' package. For example:
|
|
|
77
|
|
|
78 import ply.lex as lex
|
|
|
79 import ply.yacc as yacc
|
|
|
80
|
|
|
81 Alternatively, you can copy just the files lex.py and yacc.py
|
|
|
82 individually and use them as modules. For example:
|
|
|
83
|
|
|
84 import lex
|
|
|
85 import yacc
|
|
|
86
|
|
|
87 The file setup.py can be used to install ply using distutils.
|
|
|
88
|
|
|
89 The file doc/ply.html contains complete documentation on how to use
|
|
|
90 the system.
|
|
|
91
|
|
|
92 The example directory contains several different examples including a
|
|
|
93 PLY specification for ANSI C as given in K&R 2nd Ed.
|
|
|
94
|
|
|
95 A simple example is found at the end of this document
|
|
|
96
|
|
|
97 Requirements
|
|
|
98 ============
|
|
|
99 PLY requires the use of Python 2.6 or greater. However, you should
|
|
|
100 use the latest Python release if possible. It should work on just
|
|
|
101 about any platform. PLY has been tested with both CPython and Jython.
|
|
|
102 It also seems to work with IronPython.
|
|
|
103
|
|
|
104 Resources
|
|
|
105 =========
|
|
|
106 More information about PLY can be obtained on the PLY webpage at:
|
|
|
107
|
|
|
108 http://www.dabeaz.com/ply
|
|
|
109
|
|
|
110 For a detailed overview of parsing theory, consult the excellent
|
|
|
111 book "Compilers : Principles, Techniques, and Tools" by Aho, Sethi, and
|
|
|
112 Ullman. The topics found in "Lex & Yacc" by Levine, Mason, and Brown
|
|
|
113 may also be useful.
|
|
|
114
|
|
|
115 The GitHub page for PLY can be found at:
|
|
|
116
|
|
|
117 https://github.com/dabeaz/ply
|
|
|
118
|
|
|
119 An old and relatively inactive discussion group for PLY is found at:
|
|
|
120
|
|
|
121 http://groups.google.com/group/ply-hack
|
|
|
122
|
|
|
123 Acknowledgments
|
|
|
124 ===============
|
|
|
125 A special thanks is in order for all of the students in CS326 who
|
|
|
126 suffered through about 25 different versions of these tools :-).
|
|
|
127
|
|
|
128 The CHANGES file acknowledges those who have contributed patches.
|
|
|
129
|
|
|
130 Elias Ioup did the first implementation of LALR(1) parsing in PLY-1.x.
|
|
|
131 Andrew Waters and Markus Schoepflin were instrumental in reporting bugs
|
|
|
132 and testing a revised LALR(1) implementation for PLY-2.0.
|
|
|
133
|
|
|
134 Special Note for PLY-3.0
|
|
|
135 ========================
|
|
|
136 PLY-3.0 the first PLY release to support Python 3. However, backwards
|
|
|
137 compatibility with Python 2.6 is still preserved. PLY provides dual
|
|
|
138 Python 2/3 compatibility by restricting its implementation to a common
|
|
|
139 subset of basic language features. You should not convert PLY using
|
|
|
140 2to3--it is not necessary and may in fact break the implementation.
|
|
|
141
|
|
|
142 Example
|
|
|
143 =======
|
|
|
144
|
|
|
145 Here is a simple example showing a PLY implementation of a calculator
|
|
|
146 with variables.
|
|
|
147
|
|
|
148 # -----------------------------------------------------------------------------
|
|
|
149 # calc.py
|
|
|
150 #
|
|
|
151 # A simple calculator with variables.
|
|
|
152 # -----------------------------------------------------------------------------
|
|
|
153
|
|
|
154 tokens = (
|
|
|
155 'NAME','NUMBER',
|
|
|
156 'PLUS','MINUS','TIMES','DIVIDE','EQUALS',
|
|
|
157 'LPAREN','RPAREN',
|
|
|
158 )
|
|
|
159
|
|
|
160 # Tokens
|
|
|
161
|
|
|
162 t_PLUS = r'\+'
|
|
|
163 t_MINUS = r'-'
|
|
|
164 t_TIMES = r'\*'
|
|
|
165 t_DIVIDE = r'/'
|
|
|
166 t_EQUALS = r'='
|
|
|
167 t_LPAREN = r'\('
|
|
|
168 t_RPAREN = r'\)'
|
|
|
169 t_NAME = r'[a-zA-Z_][a-zA-Z0-9_]*'
|
|
|
170
|
|
|
171 def t_NUMBER(t):
|
|
|
172 r'\d+'
|
|
|
173 t.value = int(t.value)
|
|
|
174 return t
|
|
|
175
|
|
|
176 # Ignored characters
|
|
|
177 t_ignore = " \t"
|
|
|
178
|
|
|
179 def t_newline(t):
|
|
|
180 r'\n+'
|
|
|
181 t.lexer.lineno += t.value.count("\n")
|
|
|
182
|
|
|
183 def t_error(t):
|
|
|
184 print("Illegal character '%s'" % t.value[0])
|
|
|
185 t.lexer.skip(1)
|
|
|
186
|
|
|
187 # Build the lexer
|
|
|
188 import ply.lex as lex
|
|
|
189 lex.lex()
|
|
|
190
|
|
|
191 # Precedence rules for the arithmetic operators
|
|
|
192 precedence = (
|
|
|
193 ('left','PLUS','MINUS'),
|
|
|
194 ('left','TIMES','DIVIDE'),
|
|
|
195 ('right','UMINUS'),
|
|
|
196 )
|
|
|
197
|
|
|
198 # dictionary of names (for storing variables)
|
|
|
199 names = { }
|
|
|
200
|
|
|
201 def p_statement_assign(p):
|
|
|
202 'statement : NAME EQUALS expression'
|
|
|
203 names[p[1]] = p[3]
|
|
|
204
|
|
|
205 def p_statement_expr(p):
|
|
|
206 'statement : expression'
|
|
|
207 print(p[1])
|
|
|
208
|
|
|
209 def p_expression_binop(p):
|
|
|
210 '''expression : expression PLUS expression
|
|
|
211 | expression MINUS expression
|
|
|
212 | expression TIMES expression
|
|
|
213 | expression DIVIDE expression'''
|
|
|
214 if p[2] == '+' : p[0] = p[1] + p[3]
|
|
|
215 elif p[2] == '-': p[0] = p[1] - p[3]
|
|
|
216 elif p[2] == '*': p[0] = p[1] * p[3]
|
|
|
217 elif p[2] == '/': p[0] = p[1] / p[3]
|
|
|
218
|
|
|
219 def p_expression_uminus(p):
|
|
|
220 'expression : MINUS expression %prec UMINUS'
|
|
|
221 p[0] = -p[2]
|
|
|
222
|
|
|
223 def p_expression_group(p):
|
|
|
224 'expression : LPAREN expression RPAREN'
|
|
|
225 p[0] = p[2]
|
|
|
226
|
|
|
227 def p_expression_number(p):
|
|
|
228 'expression : NUMBER'
|
|
|
229 p[0] = p[1]
|
|
|
230
|
|
|
231 def p_expression_name(p):
|
|
|
232 'expression : NAME'
|
|
|
233 try:
|
|
|
234 p[0] = names[p[1]]
|
|
|
235 except LookupError:
|
|
|
236 print("Undefined name '%s'" % p[1])
|
|
|
237 p[0] = 0
|
|
|
238
|
|
|
239 def p_error(p):
|
|
|
240 print("Syntax error at '%s'" % p.value)
|
|
|
241
|
|
|
242 import ply.yacc as yacc
|
|
|
243 yacc.yacc()
|
|
|
244
|
|
|
245 while True:
|
|
|
246 try:
|
|
|
247 s = raw_input('calc > ') # use input() on Python 3
|
|
|
248 except EOFError:
|
|
|
249 break
|
|
|
250 yacc.parse(s)
|
|
|
251
|
|
|
252
|
|
|
253 Bug Reports and Patches
|
|
|
254 =======================
|
|
|
255 My goal with PLY is to simply have a decent lex/yacc implementation
|
|
|
256 for Python. As a general rule, I don't spend huge amounts of time
|
|
|
257 working on it unless I receive very specific bug reports and/or
|
|
|
258 patches to fix problems. I also try to incorporate submitted feature
|
|
|
259 requests and enhancements into each new version. Please visit the PLY
|
|
|
260 github page at https://github.com/dabeaz/ply to submit issues and pull
|
|
|
261 requests. To contact me about bugs and/or new features, please send
|
|
|
262 email to dave@dabeaz.com.
|
|
|
263
|
|
|
264 -- Dave
|
|
|
265
|
|
|
266
|
|
|
267
|
|
|
268
|
|
|
269
|
|
|
270
|
|
|
271
|
|
|
272
|
|
|
273
|
