third_party/ply/README

   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