OLD | NEW |
(Empty) | |
| 1 PLY (Python Lex-Yacc) Version 3.4 |
| 2 |
| 3 Copyright (C) 2001-2011, |
| 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.2 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 A Google group for PLY can be found at |
| 116 |
| 117 http://groups.google.com/group/ply-hack |
| 118 |
| 119 Acknowledgments |
| 120 =============== |
| 121 A special thanks is in order for all of the students in CS326 who |
| 122 suffered through about 25 different versions of these tools :-). |
| 123 |
| 124 The CHANGES file acknowledges those who have contributed patches. |
| 125 |
| 126 Elias Ioup did the first implementation of LALR(1) parsing in PLY-1.x. |
| 127 Andrew Waters and Markus Schoepflin were instrumental in reporting bugs |
| 128 and testing a revised LALR(1) implementation for PLY-2.0. |
| 129 |
| 130 Special Note for PLY-3.0 |
| 131 ======================== |
| 132 PLY-3.0 the first PLY release to support Python 3. However, backwards |
| 133 compatibility with Python 2.2 is still preserved. PLY provides dual |
| 134 Python 2/3 compatibility by restricting its implementation to a common |
| 135 subset of basic language features. You should not convert PLY using |
| 136 2to3--it is not necessary and may in fact break the implementation. |
| 137 |
| 138 Example |
| 139 ======= |
| 140 |
| 141 Here is a simple example showing a PLY implementation of a calculator |
| 142 with variables. |
| 143 |
| 144 # ----------------------------------------------------------------------------- |
| 145 # calc.py |
| 146 # |
| 147 # A simple calculator with variables. |
| 148 # ----------------------------------------------------------------------------- |
| 149 |
| 150 tokens = ( |
| 151 'NAME','NUMBER', |
| 152 'PLUS','MINUS','TIMES','DIVIDE','EQUALS', |
| 153 'LPAREN','RPAREN', |
| 154 ) |
| 155 |
| 156 # Tokens |
| 157 |
| 158 t_PLUS = r'\+' |
| 159 t_MINUS = r'-' |
| 160 t_TIMES = r'\*' |
| 161 t_DIVIDE = r'/' |
| 162 t_EQUALS = r'=' |
| 163 t_LPAREN = r'\(' |
| 164 t_RPAREN = r'\)' |
| 165 t_NAME = r'[a-zA-Z_][a-zA-Z0-9_]*' |
| 166 |
| 167 def t_NUMBER(t): |
| 168 r'\d+' |
| 169 t.value = int(t.value) |
| 170 return t |
| 171 |
| 172 # Ignored characters |
| 173 t_ignore = " \t" |
| 174 |
| 175 def t_newline(t): |
| 176 r'\n+' |
| 177 t.lexer.lineno += t.value.count("\n") |
| 178 |
| 179 def t_error(t): |
| 180 print("Illegal character '%s'" % t.value[0]) |
| 181 t.lexer.skip(1) |
| 182 |
| 183 # Build the lexer |
| 184 import ply.lex as lex |
| 185 lex.lex() |
| 186 |
| 187 # Precedence rules for the arithmetic operators |
| 188 precedence = ( |
| 189 ('left','PLUS','MINUS'), |
| 190 ('left','TIMES','DIVIDE'), |
| 191 ('right','UMINUS'), |
| 192 ) |
| 193 |
| 194 # dictionary of names (for storing variables) |
| 195 names = { } |
| 196 |
| 197 def p_statement_assign(p): |
| 198 'statement : NAME EQUALS expression' |
| 199 names[p[1]] = p[3] |
| 200 |
| 201 def p_statement_expr(p): |
| 202 'statement : expression' |
| 203 print(p[1]) |
| 204 |
| 205 def 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 |
| 215 def p_expression_uminus(p): |
| 216 'expression : MINUS expression %prec UMINUS' |
| 217 p[0] = -p[2] |
| 218 |
| 219 def p_expression_group(p): |
| 220 'expression : LPAREN expression RPAREN' |
| 221 p[0] = p[2] |
| 222 |
| 223 def p_expression_number(p): |
| 224 'expression : NUMBER' |
| 225 p[0] = p[1] |
| 226 |
| 227 def 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 |
| 235 def p_error(p): |
| 236 print("Syntax error at '%s'" % p.value) |
| 237 |
| 238 import ply.yacc as yacc |
| 239 yacc.yacc() |
| 240 |
| 241 while 1: |
| 242 try: |
| 243 s = raw_input('calc > ') # use input() on Python 3 |
| 244 except EOFError: |
| 245 break |
| 246 yacc.parse(s) |
| 247 |
| 248 |
| 249 Bug Reports and Patches |
| 250 ======================= |
| 251 My goal with PLY is to simply have a decent lex/yacc implementation |
| 252 for Python. As a general rule, I don't spend huge amounts of time |
| 253 working on it unless I receive very specific bug reports and/or |
| 254 patches to fix problems. I also try to incorporate submitted feature |
| 255 requests and enhancements into each new version. To contact me about |
| 256 bugs and/or new features, please send email to dave@dabeaz.com. |
| 257 |
| 258 In 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 |
OLD | NEW |