ext/ply/README

   1 PLY (Python Lex-Yacc)                   Version 2.3  (February 18, 2007)
   2
   3 David M. Beazley (dave@dabeaz.com)
   4
   5 Copyright (C) 2001-2007   David M. Beazley
   6
   7 This library is free software; you can redistribute it and/or
   8 modify it under the terms of the GNU Lesser General Public
   9 License as published by the Free Software Foundation; either
  10 version 2.1 of the License, or (at your option) any later version.
  11
  12 This library is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 Lesser General Public License for more details.
  16
  17 You should have received a copy of the GNU Lesser General Public
  18 License along with this library; if not, write to the Free Software
  19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20
  21 See the file COPYING for a complete copy of the LGPL.
  22
  23 Introduction
  24 ============
  25
  26 PLY is a 100% Python implementation of the common parsing tools lex
  27 and yacc.   Although several other parsing tools are available for
  28 Python, 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
  61 The original version of PLY was developed for an Introduction to
  62 Compilers course where students used it to build a compiler for a
  63 simple Pascal-like language.  Their compiler had to include lexical
  64 analysis, parsing, type checking, type inference, and generation of
  65 assembly code for the SPARC processor.  Because of this, the current
  66 implementation has been extensively tested and debugged.  In addition,
  67 most of the API and error checking steps have been adapted to address
  68 common usability problems.
  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.1 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 However, it does not seem 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-2.x
 131 ========================
 132 PLY-2.0 is the first in a series of PLY releases that will be adding a
 133 variety 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
 135 except for the fact that Ply-2.0 features a correct implementation of
 136 LALR(1) table generation.
 137
 138 If you have suggestions for improving PLY in future 2.x releases, please
 139 contact me.   - Dave
 140
 141 Example
 142 =======
 143
 144 Here is a simple example showing a PLY implementation of a calculator
 145 with variables.
 146
 147 # -----------------------------------------------------------------------------
 148 # calc.py
 149 #
 150 # A simple calculator with variables.
 151 # -----------------------------------------------------------------------------
 152
 153 tokens = (
 154     'NAME','NUMBER',
 155     'PLUS','MINUS','TIMES','DIVIDE','EQUALS',
 156     'LPAREN','RPAREN',
 157     )
 158
 159 # Tokens
 160
 161 t_PLUS    = r'\+'
 162 t_MINUS   = r'-'
 163 t_TIMES   = r'\*'
 164 t_DIVIDE  = r'/'
 165 t_EQUALS  = r'='
 166 t_LPAREN  = r'\('
 167 t_RPAREN  = r'\)'
 168 t_NAME    = r'[a-zA-Z_][a-zA-Z0-9_]*'
 169
 170 def 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
 180 t_ignore = " \t"
 181
 182 def t_newline(t):
 183     r'\n+'
 184     t.lexer.lineno += t.value.count("\n")
 185
 186 def t_error(t):
 187     print "Illegal character '%s'" % t.value[0]
 188     t.lexer.skip(1)
 189
 190 # Build the lexer
 191 import ply.lex as lex
 192 lex.lex()
 193
 194 # Precedence rules for the arithmetic operators
 195 precedence = (
 196     ('left','PLUS','MINUS'),
 197     ('left','TIMES','DIVIDE'),
 198     ('right','UMINUS'),
 199     )
 200
 201 # dictionary of names (for storing variables)
 202 names = { }
 203
 204 def p_statement_assign(p):
 205     'statement : NAME EQUALS expression'
 206     names[p[1]] = p[3]
 207
 208 def p_statement_expr(p):
 209     'statement : expression'
 210     print p[1]
 211
 212 def 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
 222 def p_expression_uminus(p):
 223     'expression : MINUS expression %prec UMINUS'
 224     p[0] = -p[2]
 225
 226 def p_expression_group(p):
 227     'expression : LPAREN expression RPAREN'
 228     p[0] = p[2]
 229
 230 def p_expression_number(p):
 231     'expression : NUMBER'
 232     p[0] = p[1]
 233
 234 def 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
 242 def p_error(p):
 243     print "Syntax error at '%s'" % p.value
 244
 245 import ply.yacc as yacc
 246 yacc.yacc()
 247
 248 while 1:
 249     try:
 250         s = raw_input('calc > ')
 251     except EOFError:
 252         break
 253     yacc.parse(s)
 254
 255
 256 Bug Reports and Patches
 257 =======================
 258 Because of the extremely specialized and advanced nature of PLY, I
 259 rarely spend much time working on it unless I receive very specific
 260 bug-reports and/or patches to fix problems. I also try to incorporate
 261 submitted feature requests and enhancements into each new version.  To
 262 contact me about bugs and/or new features, please send email to
 263 dave@dabeaz.com.
 264
 265 In 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