ext/ply/README

   1 PLY (Python Lex-Yacc)                   Version 1.2  (November 27, 2002)
   2
   3 David M. Beazley
   4 Department of Computer Science
   5 University of Chicago
   6 Chicago, IL  60637
   7 beazley@cs.uchicago.edu
   8
   9 Copyright (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
  13 This library is free software; you can redistribute it and/or
  14 modify it under the terms of the GNU Lesser General Public
  15 License as published by the Free Software Foundation; either
  16 version 2.1 of the License, or (at your option) any later version.
  17
  18 This library is distributed in the hope that it will be useful,
  19 but WITHOUT ANY WARRANTY; without even the implied warranty of
  20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21 Lesser General Public License for more details.
  22
  23 You should have received a copy of the GNU Lesser General Public
  24 License along with this library; if not, write to the Free Software
  25 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  26
  27 See the file COPYING for a complete copy of the LGPL.
  28
  29 Introduction
  30 ============
  31
  32 PLY is a 100% Python implementation of the common parsing tools lex
  33 and yacc.   Although several other parsing tools are available for
  34 Python, 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
  68 The original version of PLY was developed for an Introduction to
  69 Compilers course where students used it to build a compiler for a
  70 simple Pascal-like language.  Their compiler had to include lexical
  71 analysis, parsing, type checking, type inference, and generation of
  72 assembly code for the SPARC processor.  Because of this, the current
  73 implementation has been extensively tested and debugged.  In addition,
  74 most of the API and error checking steps have been adapted to address
  75 common usability problems.
  76
  77 How to Use
  78 ==========
  79
  80 PLY consists of two files : lex.py and yacc.py.  To use the system,
  81 simply copy these files to your project and import them like standard
  82 Python modules.
  83
  84 The file doc/ply.html contains complete documentation on how to use
  85 the system.
  86
  87 The example directory contains several different examples including a
  88 PLY specification for ANSI C as given in K&R 2nd Ed.   Note: To use
  89 the examples, you will need to copy the lex.py and yacc.py files to
  90 the example directory.
  91
  92 A simple example is found at the end of this document
  93
  94 Requirements
  95 ============
  96 PLY requires the use of Python 2.0 or greater.  It should work on
  97 just about any platform.
  98
  99 Resources
 100 =========
 101
 102 More information about PLY can be obtained on the PLY webpage at:
 103
 104      http://systems.cs.uchicago.edu/ply
 105
 106 For a detailed overview of parsing theory, consult the excellent
 107 book "Compilers : Principles, Techniques, and Tools" by Aho, Sethi, and
 108 Ullman.  The topics found in "Lex & Yacc" by Levine, Mason, and Brown
 109 may also be useful.
 110
 111 Given that this is the first release, I welcome your comments on how
 112 to improve the current implementation.  See the TODO file for things that
 113 still need to be done.
 114
 115 Acknowledgments
 116 ===============
 117
 118 A special thanks is in order for all of the students in CS326 who
 119 suffered through about 25 different versions of these tools :-).
 120
 121 Example
 122 =======
 123
 124 Here 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
 132 tokens = (
 133     'NAME','NUMBER',
 134     'PLUS','MINUS','TIMES','DIVIDE','EQUALS',
 135     'LPAREN','RPAREN',
 136     )
 137
 138 # Tokens
 139
 140 t_PLUS    = r'\+'
 141 t_MINUS   = r'-'
 142 t_TIMES   = r'\*'
 143 t_DIVIDE  = r'/'
 144 t_EQUALS  = r'='
 145 t_LPAREN  = r'\('
 146 t_RPAREN  = r'\)'
 147 t_NAME    = r'[a-zA-Z_][a-zA-Z0-9_]*'
 148
 149 def 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
 159 t_ignore = " \t"
 160
 161 def t_newline(t):
 162     r'\n+'
 163     t.lineno += t.value.count("\n")
 164
 165 def t_error(t):
 166     print "Illegal character '%s'" % t.value[0]
 167     t.skip(1)
 168
 169 # Build the lexer
 170 import lex
 171 lex.lex()
 172
 173 # Precedence rules for the arithmetic operators
 174 precedence = (
 175     ('left','PLUS','MINUS'),
 176     ('left','TIMES','DIVIDE'),
 177     ('right','UMINUS'),
 178     )
 179
 180 # dictionary of names (for storing variables)
 181 names = { }
 182
 183 def p_statement_assign(t):
 184     'statement : NAME EQUALS expression'
 185     names[t[1]] = t[3]
 186
 187 def p_statement_expr(t):
 188     'statement : expression'
 189     print t[1]
 190
 191 def 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
 201 def p_expression_uminus(t):
 202     'expression : MINUS expression %prec UMINUS'
 203     t[0] = -t[2]
 204
 205 def p_expression_group(t):
 206     'expression : LPAREN expression RPAREN'
 207     t[0] = t[2]
 208
 209 def p_expression_number(t):
 210     'expression : NUMBER'
 211     t[0] = t[1]
 212
 213 def 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
 221 def p_error(t):
 222     print "Syntax error at '%s'" % t.value
 223
 224 import yacc
 225 yacc.yacc()
 226
 227 while 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