Commits

Jason R. Coombs committed df60658

Adding PLY 2.0 as released

  • Participants

Comments (0)

Files changed (104)

+September 8, 2006
+
+                  Announcing :  PLY-2.0 (Python Lex-Yacc)
+
+                        http://www.dabeaz.com/ply
+
+I'm pleased to announce a significant new update to PLY---a 100% Python
+implementation of the common parsing tools lex and yacc.  PLY-2.0 features
+a completely new implementation of LALR(1) parsing that provides a
+significant speedup when generating the underlying parsing tables. This
+new implementation also (hopefully) fixes all outstanding bugs in LALR(1)
+parsing that were reported for previous versions of PLY-1.x.  
+
+Here are a few PLY highlights:
+
+  -  PLY is closely modeled after traditional lex/yacc.  If you know how 
+     to use these or similar tools in other languages, you will find
+     PLY to be comparable.
+
+  -  PLY provides very extensive error reporting and diagnostic
+     information to assist in parser construction.  The original
+     implementation was developed for instructional purposes.  As
+     a result, the system tries to identify the most common types
+     of errors made by novice users.
+
+  -  PLY provides full support for empty productions, error recovery,
+     precedence rules, and moderately ambiguous grammars.
+
+  -  Parsing is based on LR-parsing which is fast, memory efficient,
+     better suited to large grammars, and which has a number of nice
+     properties when dealing with syntax errors and other parsing 
+     problems. Currently, PLY can build its parsing tables using 
+     either SLR or LALR(1) algorithms. 
+
+  -  PLY can be used to build parsers for large programming languages.
+     Although it is not ultra-fast due to its Python implementation,
+     PLY can be used to parse grammars consisting of several hundred
+     rules (as might be found for a language like C).  The lexer and LR
+     parser are also reasonably efficient when parsing normal
+     sized programs.
+
+More information about PLY can be obtained on the PLY webpage at:
+
+                   http://www.dabeaz.com/ply
+
+PLY is freely available and is licensed under the terms of the Lesser
+GNU Public License (LGPL).
+
+Cheers,
+
+David Beazley (http://www.dabeaz.com)
+Version 2.0
+------------------------------
+09/07/06: beazley
+          Major cleanup and refactoring of the LR table generation code.  Both SLR
+          and LALR(1) table generation is now performed by the same code base with
+          only minor extensions for extra LALR(1) processing.
+
+09/07/06: beazley
+          Completely reimplemented the entire LALR(1) parsing engine to use the
+          DeRemer and Pennello algorithm for calculating lookahead sets.  This
+          significantly improves the performance of generating LALR(1) tables
+          and has the added feature of actually working correctly!  If you
+          experienced weird behavior with LALR(1) in prior releases, this should
+          hopefully resolve all of those problems.  Many thanks to 
+          Andrew Waters and Markus Schoepflin for submitting bug reports
+          and helping me test out the revised LALR(1) support.
+
+Version 1.8
+------------------------------
+08/02/06: beazley
+          Fixed a problem related to the handling of default actions in LALR(1)
+          parsing.  If you experienced subtle and/or bizarre behavior when trying
+          to use the LALR(1) engine, this may correct those problems.  Patch
+          contributed by Russ Cox.  Note: This patch has been superceded by 
+          revisions for LALR(1) parsing in Ply-2.0.
+
+08/02/06: beazley
+          Added support for slicing of productions in yacc.  
+          Patch contributed by Patrick Mezard.
+
+Version 1.7
+------------------------------
+03/02/06: beazley
+          Fixed infinite recursion problem ReduceToTerminals() function that
+          would sometimes come up in LALR(1) table generation.  Reported by 
+          Markus Schoepflin.
+
+03/01/06: beazley
+          Added "reflags" argument to lex().  For example:
+
+               lex.lex(reflags=re.UNICODE)
+
+          This can be used to specify optional flags to the re.compile() function
+          used inside the lexer.   This may be necessary for special situations such
+          as processing Unicode (e.g., if you want escapes like \w and \b to consult
+          the Unicode character property database).   The need for this suggested by
+          Andreas Jung.
+
+03/01/06: beazley
+          Fixed a bug with an uninitialized variable on repeated instantiations of parser
+          objects when the write_tables=0 argument was used.   Reported by Michael Brown.
+
+03/01/06: beazley
+          Modified lex.py to accept Unicode strings both as the regular expressions for
+          tokens and as input. Hopefully this is the only change needed for Unicode support.
+          Patch contributed by Johan Dahl.
+
+03/01/06: beazley
+          Modified the class-based interface to work with new-style or old-style classes.
+          Patch contributed by Michael Brown (although I tweaked it slightly so it would work
+          with older versions of Python).
+
+Version 1.6
+------------------------------
+05/27/05: beazley
+          Incorporated patch contributed by Christopher Stawarz to fix an extremely
+          devious bug in LALR(1) parser generation.   This patch should fix problems
+          numerous people reported with LALR parsing.
+
+05/27/05: beazley
+          Fixed problem with lex.py copy constructor.  Reported by Dave Aitel, Aaron Lav,
+          and Thad Austin. 
+
+05/27/05: beazley
+          Added outputdir option to yacc()  to control output directory. Contributed
+          by Christopher Stawarz.
+
+05/27/05: beazley
+          Added rununit.py test script to run tests using the Python unittest module.
+          Contributed by Miki Tebeka.
+
+Version 1.5
+------------------------------
+05/26/04: beazley
+          Major enhancement. LALR(1) parsing support is now working.
+          This feature was implemented by Elias Ioup (ezioup@alumni.uchicago.edu)
+          and optimized by David Beazley. To use LALR(1) parsing do
+          the following:
+
+               yacc.yacc(method="LALR")
+
+          Computing LALR(1) parsing tables takes about twice as long as
+          the default SLR method.  However, LALR(1) allows you to handle
+          more complex grammars.  For example, the ANSI C grammar
+          (in example/ansic) has 13 shift-reduce conflicts with SLR, but
+          only has 1 shift-reduce conflict with LALR(1).
+
+05/20/04: beazley
+          Added a __len__ method to parser production lists.  Can
+          be used in parser rules like this:
+
+             def p_somerule(p):
+                 """a : B C D
+                      | E F"
+                 if (len(p) == 3):
+                     # Must have been first rule
+                 elif (len(p) == 2):
+                     # Must be second rule
+
+          Suggested by Joshua Gerth and others.
+
+Version 1.4
+------------------------------
+04/23/04: beazley
+          Incorporated a variety of patches contributed by Eric Raymond.
+          These include:
+
+           0. Cleans up some comments so they don't wrap on an 80-column display.
+           1. Directs compiler errors to stderr where they belong.
+           2. Implements and documents automatic line counting when \n is ignored.
+           3. Changes the way progress messages are dumped when debugging is on. 
+              The new format is both less verbose and conveys more information than
+              the old, including shift and reduce actions.
+
+04/23/04: beazley
+          Added a Python setup.py file to simply installation.  Contributed
+          by Adam Kerrison.
+
+04/23/04: beazley
+          Added patches contributed by Adam Kerrison.
+ 
+          -   Some output is now only shown when debugging is enabled.  This
+              means that PLY will be completely silent when not in debugging mode.
+          
+          -   An optional parameter "write_tables" can be passed to yacc() to
+              control whether or not parsing tables are written.   By default,
+              it is true, but it can be turned off if you don't want the yacc
+              table file. Note: disabling this will cause yacc() to regenerate
+              the parsing table each time.
+
+04/23/04: beazley
+          Added patches contributed by David McNab.  This patch addes two
+          features:
+
+          -   The parser can be supplied as a class instead of a module.
+              For an example of this, see the example/classcalc directory.
+
+          -   Debugging output can be directed to a filename of the user's
+              choice.  Use
+
+                 yacc(debugfile="somefile.out")
+
+          
+Version 1.3
+------------------------------
+12/10/02: jmdyck
+          Various minor adjustments to the code that Dave checked in today.
+          Updated test/yacc_{inf,unused}.exp to reflect today's changes.
+
+12/10/02: beazley
+          Incorporated a variety of minor bug fixes to empty production
+          handling and infinite recursion checking.  Contributed by
+          Michael Dyck.
+
+12/10/02: beazley
+          Removed bogus recover() method call in yacc.restart()
+
+Version 1.2
+------------------------------
+11/27/02: beazley
+          Lexer and parser objects are now available as an attribute
+          of tokens and slices respectively. For example:
+ 
+             def t_NUMBER(t):
+                 r'\d+'
+                 print t.lexer
+
+             def p_expr_plus(t):
+                 'expr: expr PLUS expr'
+                 print t.lexer
+                 print t.parser
+
+          This can be used for state management (if needed).
+ 
+10/31/02: beazley
+          Modified yacc.py to work with Python optimize mode.  To make
+          this work, you need to use
+
+              yacc.yacc(optimize=1)
+
+          Furthermore, you need to first run Python in normal mode
+          to generate the necessary parsetab.py files.  After that,
+          you can use python -O or python -OO.  
+
+          Note: optimized mode turns off a lot of error checking.
+          Only use when you are sure that your grammar is working.
+          Make sure parsetab.py is up to date!
+
+10/30/02: beazley
+          Added cloning of Lexer objects.   For example:
+
+              import copy
+              l = lex.lex()
+              lc = copy.copy(l)
+
+              l.input("Some text")
+              lc.input("Some other text")
+              ...
+
+          This might be useful if the same "lexer" is meant to
+          be used in different contexts---or if multiple lexers
+          are running concurrently.
+                
+10/30/02: beazley
+          Fixed subtle bug with first set computation and empty productions.
+          Patch submitted by Michael Dyck.
+
+10/30/02: beazley
+          Fixed error messages to use "filename:line: message" instead
+          of "filename:line. message".  This makes error reporting more
+          friendly to emacs. Patch submitted by Fran�ois Pinard.
+
+10/30/02: beazley
+          Improvements to parser.out file.  Terminals and nonterminals
+          are sorted instead of being printed in random order.
+          Patch submitted by Fran�ois Pinard.
+
+10/30/02: beazley
+          Improvements to parser.out file output.  Rules are now printed
+          in a way that's easier to understand.  Contributed by Russ Cox.
+
+10/30/02: beazley
+          Added 'nonassoc' associativity support.    This can be used
+          to disable the chaining of operators like a < b < c.
+          To use, simply specify 'nonassoc' in the precedence table
+
+          precedence = (
+            ('nonassoc', 'LESSTHAN', 'GREATERTHAN'),  # Nonassociative operators
+            ('left', 'PLUS', 'MINUS'),
+            ('left', 'TIMES', 'DIVIDE'),
+            ('right', 'UMINUS'),            # Unary minus operator
+          )
+
+          Patch contributed by Russ Cox.
+
+10/30/02: beazley
+          Modified the lexer to provide optional support for Python -O and -OO
+          modes.  To make this work, Python *first* needs to be run in
+          unoptimized mode.  This reads the lexing information and creates a
+          file "lextab.py".  Then, run lex like this:
+
+                   # module foo.py
+                   ...
+                   ...
+                   lex.lex(optimize=1)
+
+          Once the lextab file has been created, subsequent calls to
+          lex.lex() will read data from the lextab file instead of using 
+          introspection.   In optimized mode (-O, -OO) everything should
+          work normally despite the loss of doc strings.
+
+          To change the name of the file 'lextab.py' use the following:
+
+                  lex.lex(lextab="footab")
+
+          (this creates a file footab.py)
+         
+
+Version 1.1   October 25, 2001
+------------------------------
+
+10/25/01: beazley
+          Modified the table generator to produce much more compact data.
+          This should greatly reduce the size of the parsetab.py[c] file.
+          Caveat: the tables still need to be constructed so a little more
+          work is done in parsetab on import. 
+
+10/25/01: beazley
+          There may be a possible bug in the cycle detector that reports errors
+          about infinite recursion.   I'm having a little trouble tracking it
+          down, but if you get this problem, you can disable the cycle
+          detector as follows:
+
+                 yacc.yacc(check_recursion = 0)
+
+10/25/01: beazley
+          Fixed a bug in lex.py that sometimes caused illegal characters to be
+          reported incorrectly.  Reported by Sverre J�rgensen.
+
+7/8/01  : beazley
+          Added a reference to the underlying lexer object when tokens are handled by
+          functions.   The lexer is available as the 'lexer' attribute.   This
+          was added to provide better lexing support for languages such as Fortran
+          where certain types of tokens can't be conveniently expressed as regular 
+          expressions (and where the tokenizing function may want to perform a 
+          little backtracking).  Suggested by Pearu Peterson.
+
+6/20/01 : beazley
+          Modified yacc() function so that an optional starting symbol can be specified.
+          For example:
+            
+                 yacc.yacc(start="statement")
+
+          Normally yacc always treats the first production rule as the starting symbol.
+          However, if you are debugging your grammar it may be useful to specify
+          an alternative starting symbol.  Idea suggested by Rich Salz.
+                      
+Version 1.0  June 18, 2001
+--------------------------
+Initial public offering
+
+		  GNU LESSER GENERAL PUBLIC LICENSE
+		       Version 2.1, February 1999
+
+ Copyright (C) 1991, 1999 Free Software Foundation, Inc.
+     59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ Everyone is permitted to copy and distribute verbatim copies
+ of this license document, but changing it is not allowed.
+
+[This is the first released version of the Lesser GPL.  It also counts
+ as the successor of the GNU Library Public License, version 2, hence
+ the version number 2.1.]
+
+			    Preamble
+
+  The licenses for most software are designed to take away your
+freedom to share and change it.  By contrast, the GNU General Public
+Licenses are intended to guarantee your freedom to share and change
+free software--to make sure the software is free for all its users.
+
+  This license, the Lesser General Public License, applies to some
+specially designated software packages--typically libraries--of the
+Free Software Foundation and other authors who decide to use it.  You
+can use it too, but we suggest you first think carefully about whether
+this license or the ordinary General Public License is the better
+strategy to use in any particular case, based on the explanations below.
+
+  When we speak of free software, we are referring to freedom of use,
+not price.  Our General Public Licenses are designed to make sure that
+you have the freedom to distribute copies of free software (and charge
+for this service if you wish); that you receive source code or can get
+it if you want it; that you can change the software and use pieces of
+it in new free programs; and that you are informed that you can do
+these things.
+
+  To protect your rights, we need to make restrictions that forbid
+distributors to deny you these rights or to ask you to surrender these
+rights.  These restrictions translate to certain responsibilities for
+you if you distribute copies of the library or if you modify it.
+
+  For example, if you distribute copies of the library, whether gratis
+or for a fee, you must give the recipients all the rights that we gave
+you.  You must make sure that they, too, receive or can get the source
+code.  If you link other code with the library, you must provide
+complete object files to the recipients, so that they can relink them
+with the library after making changes to the library and recompiling
+it.  And you must show them these terms so they know their rights.
+
+  We protect your rights with a two-step method: (1) we copyright the
+library, and (2) we offer you this license, which gives you legal
+permission to copy, distribute and/or modify the library.
+
+  To protect each distributor, we want to make it very clear that
+there is no warranty for the free library.  Also, if the library is
+modified by someone else and passed on, the recipients should know
+that what they have is not the original version, so that the original
+author's reputation will not be affected by problems that might be
+introduced by others.
+
+  Finally, software patents pose a constant threat to the existence of
+any free program.  We wish to make sure that a company cannot
+effectively restrict the users of a free program by obtaining a
+restrictive license from a patent holder.  Therefore, we insist that
+any patent license obtained for a version of the library must be
+consistent with the full freedom of use specified in this license.
+
+  Most GNU software, including some libraries, is covered by the
+ordinary GNU General Public License.  This license, the GNU Lesser
+General Public License, applies to certain designated libraries, and
+is quite different from the ordinary General Public License.  We use
+this license for certain libraries in order to permit linking those
+libraries into non-free programs.
+
+  When a program is linked with a library, whether statically or using
+a shared library, the combination of the two is legally speaking a
+combined work, a derivative of the original library.  The ordinary
+General Public License therefore permits such linking only if the
+entire combination fits its criteria of freedom.  The Lesser General
+Public License permits more lax criteria for linking other code with
+the library.
+
+  We call this license the "Lesser" General Public License because it
+does Less to protect the user's freedom than the ordinary General
+Public License.  It also provides other free software developers Less
+of an advantage over competing non-free programs.  These disadvantages
+are the reason we use the ordinary General Public License for many
+libraries.  However, the Lesser license provides advantages in certain
+special circumstances.
+
+  For example, on rare occasions, there may be a special need to
+encourage the widest possible use of a certain library, so that it becomes
+a de-facto standard.  To achieve this, non-free programs must be
+allowed to use the library.  A more frequent case is that a free
+library does the same job as widely used non-free libraries.  In this
+case, there is little to gain by limiting the free library to free
+software only, so we use the Lesser General Public License.
+
+  In other cases, permission to use a particular library in non-free
+programs enables a greater number of people to use a large body of
+free software.  For example, permission to use the GNU C Library in
+non-free programs enables many more people to use the whole GNU
+operating system, as well as its variant, the GNU/Linux operating
+system.
+
+  Although the Lesser General Public License is Less protective of the
+users' freedom, it does ensure that the user of a program that is
+linked with the Library has the freedom and the wherewithal to run
+that program using a modified version of the Library.
+
+  The precise terms and conditions for copying, distribution and
+modification follow.  Pay close attention to the difference between a
+"work based on the library" and a "work that uses the library".  The
+former contains code derived from the library, whereas the latter must
+be combined with the library in order to run.
+
+		  GNU LESSER GENERAL PUBLIC LICENSE
+   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
+
+  0. This License Agreement applies to any software library or other
+program which contains a notice placed by the copyright holder or
+other authorized party saying it may be distributed under the terms of
+this Lesser General Public License (also called "this License").
+Each licensee is addressed as "you".
+
+  A "library" means a collection of software functions and/or data
+prepared so as to be conveniently linked with application programs
+(which use some of those functions and data) to form executables.
+
+  The "Library", below, refers to any such software library or work
+which has been distributed under these terms.  A "work based on the
+Library" means either the Library or any derivative work under
+copyright law: that is to say, a work containing the Library or a
+portion of it, either verbatim or with modifications and/or translated
+straightforwardly into another language.  (Hereinafter, translation is
+included without limitation in the term "modification".)
+
+  "Source code" for a work means the preferred form of the work for
+making modifications to it.  For a library, complete source code means
+all the source code for all modules it contains, plus any associated
+interface definition files, plus the scripts used to control compilation
+and installation of the library.
+
+  Activities other than copying, distribution and modification are not
+covered by this License; they are outside its scope.  The act of
+running a program using the Library is not restricted, and output from
+such a program is covered only if its contents constitute a work based
+on the Library (independent of the use of the Library in a tool for
+writing it).  Whether that is true depends on what the Library does
+and what the program that uses the Library does.
+  
+  1. You may copy and distribute verbatim copies of the Library's
+complete source code as you receive it, in any medium, provided that
+you conspicuously and appropriately publish on each copy an
+appropriate copyright notice and disclaimer of warranty; keep intact
+all the notices that refer to this License and to the absence of any
+warranty; and distribute a copy of this License along with the
+Library.
+
+  You may charge a fee for the physical act of transferring a copy,
+and you may at your option offer warranty protection in exchange for a
+fee.
+
+  2. You may modify your copy or copies of the Library or any portion
+of it, thus forming a work based on the Library, and copy and
+distribute such modifications or work under the terms of Section 1
+above, provided that you also meet all of these conditions:
+
+    a) The modified work must itself be a software library.
+
+    b) You must cause the files modified to carry prominent notices
+    stating that you changed the files and the date of any change.
+
+    c) You must cause the whole of the work to be licensed at no
+    charge to all third parties under the terms of this License.
+
+    d) If a facility in the modified Library refers to a function or a
+    table of data to be supplied by an application program that uses
+    the facility, other than as an argument passed when the facility
+    is invoked, then you must make a good faith effort to ensure that,
+    in the event an application does not supply such function or
+    table, the facility still operates, and performs whatever part of
+    its purpose remains meaningful.
+
+    (For example, a function in a library to compute square roots has
+    a purpose that is entirely well-defined independent of the
+    application.  Therefore, Subsection 2d requires that any
+    application-supplied function or table used by this function must
+    be optional: if the application does not supply it, the square
+    root function must still compute square roots.)
+
+These requirements apply to the modified work as a whole.  If
+identifiable sections of that work are not derived from the Library,
+and can be reasonably considered independent and separate works in
+themselves, then this License, and its terms, do not apply to those
+sections when you distribute them as separate works.  But when you
+distribute the same sections as part of a whole which is a work based
+on the Library, the distribution of the whole must be on the terms of
+this License, whose permissions for other licensees extend to the
+entire whole, and thus to each and every part regardless of who wrote
+it.
+
+Thus, it is not the intent of this section to claim rights or contest
+your rights to work written entirely by you; rather, the intent is to
+exercise the right to control the distribution of derivative or
+collective works based on the Library.
+
+In addition, mere aggregation of another work not based on the Library
+with the Library (or with a work based on the Library) on a volume of
+a storage or distribution medium does not bring the other work under
+the scope of this License.
+
+  3. You may opt to apply the terms of the ordinary GNU General Public
+License instead of this License to a given copy of the Library.  To do
+this, you must alter all the notices that refer to this License, so
+that they refer to the ordinary GNU General Public License, version 2,
+instead of to this License.  (If a newer version than version 2 of the
+ordinary GNU General Public License has appeared, then you can specify
+that version instead if you wish.)  Do not make any other change in
+these notices.
+
+  Once this change is made in a given copy, it is irreversible for
+that copy, so the ordinary GNU General Public License applies to all
+subsequent copies and derivative works made from that copy.
+
+  This option is useful when you wish to copy part of the code of
+the Library into a program that is not a library.
+
+  4. You may copy and distribute the Library (or a portion or
+derivative of it, under Section 2) in object code or executable form
+under the terms of Sections 1 and 2 above provided that you accompany
+it with the complete corresponding machine-readable source code, which
+must be distributed under the terms of Sections 1 and 2 above on a
+medium customarily used for software interchange.
+
+  If distribution of object code is made by offering access to copy
+from a designated place, then offering equivalent access to copy the
+source code from the same place satisfies the requirement to
+distribute the source code, even though third parties are not
+compelled to copy the source along with the object code.
+
+  5. A program that contains no derivative of any portion of the
+Library, but is designed to work with the Library by being compiled or
+linked with it, is called a "work that uses the Library".  Such a
+work, in isolation, is not a derivative work of the Library, and
+therefore falls outside the scope of this License.
+
+  However, linking a "work that uses the Library" with the Library
+creates an executable that is a derivative of the Library (because it
+contains portions of the Library), rather than a "work that uses the
+library".  The executable is therefore covered by this License.
+Section 6 states terms for distribution of such executables.
+
+  When a "work that uses the Library" uses material from a header file
+that is part of the Library, the object code for the work may be a
+derivative work of the Library even though the source code is not.
+Whether this is true is especially significant if the work can be
+linked without the Library, or if the work is itself a library.  The
+threshold for this to be true is not precisely defined by law.
+
+  If such an object file uses only numerical parameters, data
+structure layouts and accessors, and small macros and small inline
+functions (ten lines or less in length), then the use of the object
+file is unrestricted, regardless of whether it is legally a derivative
+work.  (Executables containing this object code plus portions of the
+Library will still fall under Section 6.)
+
+  Otherwise, if the work is a derivative of the Library, you may
+distribute the object code for the work under the terms of Section 6.
+Any executables containing that work also fall under Section 6,
+whether or not they are linked directly with the Library itself.
+
+  6. As an exception to the Sections above, you may also combine or
+link a "work that uses the Library" with the Library to produce a
+work containing portions of the Library, and distribute that work
+under terms of your choice, provided that the terms permit
+modification of the work for the customer's own use and reverse
+engineering for debugging such modifications.
+
+  You must give prominent notice with each copy of the work that the
+Library is used in it and that the Library and its use are covered by
+this License.  You must supply a copy of this License.  If the work
+during execution displays copyright notices, you must include the
+copyright notice for the Library among them, as well as a reference
+directing the user to the copy of this License.  Also, you must do one
+of these things:
+
+    a) Accompany the work with the complete corresponding
+    machine-readable source code for the Library including whatever
+    changes were used in the work (which must be distributed under
+    Sections 1 and 2 above); and, if the work is an executable linked
+    with the Library, with the complete machine-readable "work that
+    uses the Library", as object code and/or source code, so that the
+    user can modify the Library and then relink to produce a modified
+    executable containing the modified Library.  (It is understood
+    that the user who changes the contents of definitions files in the
+    Library will not necessarily be able to recompile the application
+    to use the modified definitions.)
+
+    b) Use a suitable shared library mechanism for linking with the
+    Library.  A suitable mechanism is one that (1) uses at run time a
+    copy of the library already present on the user's computer system,
+    rather than copying library functions into the executable, and (2)
+    will operate properly with a modified version of the library, if
+    the user installs one, as long as the modified version is
+    interface-compatible with the version that the work was made with.
+
+    c) Accompany the work with a written offer, valid for at
+    least three years, to give the same user the materials
+    specified in Subsection 6a, above, for a charge no more
+    than the cost of performing this distribution.
+
+    d) If distribution of the work is made by offering access to copy
+    from a designated place, offer equivalent access to copy the above
+    specified materials from the same place.
+
+    e) Verify that the user has already received a copy of these
+    materials or that you have already sent this user a copy.
+
+  For an executable, the required form of the "work that uses the
+Library" must include any data and utility programs needed for
+reproducing the executable from it.  However, as a special exception,
+the materials to be distributed need not include anything that is
+normally distributed (in either source or binary form) with the major
+components (compiler, kernel, and so on) of the operating system on
+which the executable runs, unless that component itself accompanies
+the executable.
+
+  It may happen that this requirement contradicts the license
+restrictions of other proprietary libraries that do not normally
+accompany the operating system.  Such a contradiction means you cannot
+use both them and the Library together in an executable that you
+distribute.
+
+  7. You may place library facilities that are a work based on the
+Library side-by-side in a single library together with other library
+facilities not covered by this License, and distribute such a combined
+library, provided that the separate distribution of the work based on
+the Library and of the other library facilities is otherwise
+permitted, and provided that you do these two things:
+
+    a) Accompany the combined library with a copy of the same work
+    based on the Library, uncombined with any other library
+    facilities.  This must be distributed under the terms of the
+    Sections above.
+
+    b) Give prominent notice with the combined library of the fact
+    that part of it is a work based on the Library, and explaining
+    where to find the accompanying uncombined form of the same work.
+
+  8. You may not copy, modify, sublicense, link with, or distribute
+the Library except as expressly provided under this License.  Any
+attempt otherwise to copy, modify, sublicense, link with, or
+distribute the Library is void, and will automatically terminate your
+rights under this License.  However, parties who have received copies,
+or rights, from you under this License will not have their licenses
+terminated so long as such parties remain in full compliance.
+
+  9. You are not required to accept this License, since you have not
+signed it.  However, nothing else grants you permission to modify or
+distribute the Library or its derivative works.  These actions are
+prohibited by law if you do not accept this License.  Therefore, by
+modifying or distributing the Library (or any work based on the
+Library), you indicate your acceptance of this License to do so, and
+all its terms and conditions for copying, distributing or modifying
+the Library or works based on it.
+
+  10. Each time you redistribute the Library (or any work based on the
+Library), the recipient automatically receives a license from the
+original licensor to copy, distribute, link with or modify the Library
+subject to these terms and conditions.  You may not impose any further
+restrictions on the recipients' exercise of the rights granted herein.
+You are not responsible for enforcing compliance by third parties with
+this License.
+
+  11. If, as a consequence of a court judgment or allegation of patent
+infringement or for any other reason (not limited to patent issues),
+conditions are imposed on you (whether by court order, agreement or
+otherwise) that contradict the conditions of this License, they do not
+excuse you from the conditions of this License.  If you cannot
+distribute so as to satisfy simultaneously your obligations under this
+License and any other pertinent obligations, then as a consequence you
+may not distribute the Library at all.  For example, if a patent
+license would not permit royalty-free redistribution of the Library by
+all those who receive copies directly or indirectly through you, then
+the only way you could satisfy both it and this License would be to
+refrain entirely from distribution of the Library.
+
+If any portion of this section is held invalid or unenforceable under any
+particular circumstance, the balance of the section is intended to apply,
+and the section as a whole is intended to apply in other circumstances.
+
+It is not the purpose of this section to induce you to infringe any
+patents or other property right claims or to contest validity of any
+such claims; this section has the sole purpose of protecting the
+integrity of the free software distribution system which is
+implemented by public license practices.  Many people have made
+generous contributions to the wide range of software distributed
+through that system in reliance on consistent application of that
+system; it is up to the author/donor to decide if he or she is willing
+to distribute software through any other system and a licensee cannot
+impose that choice.
+
+This section is intended to make thoroughly clear what is believed to
+be a consequence of the rest of this License.
+
+  12. If the distribution and/or use of the Library is restricted in
+certain countries either by patents or by copyrighted interfaces, the
+original copyright holder who places the Library under this License may add
+an explicit geographical distribution limitation excluding those countries,
+so that distribution is permitted only in or among countries not thus
+excluded.  In such case, this License incorporates the limitation as if
+written in the body of this License.
+
+  13. The Free Software Foundation may publish revised and/or new
+versions of the Lesser General Public License from time to time.
+Such new versions will be similar in spirit to the present version,
+but may differ in detail to address new problems or concerns.
+
+Each version is given a distinguishing version number.  If the Library
+specifies a version number of this License which applies to it and
+"any later version", you have the option of following the terms and
+conditions either of that version or of any later version published by
+the Free Software Foundation.  If the Library does not specify a
+license version number, you may choose any version ever published by
+the Free Software Foundation.
+
+  14. If you wish to incorporate parts of the Library into other free
+programs whose distribution conditions are incompatible with these,
+write to the author to ask for permission.  For software which is
+copyrighted by the Free Software Foundation, write to the Free
+Software Foundation; we sometimes make exceptions for this.  Our
+decision will be guided by the two goals of preserving the free status
+of all derivatives of our free software and of promoting the sharing
+and reuse of software generally.
+
+			    NO WARRANTY
+
+  15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO
+WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW.
+EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR
+OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY
+KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE
+LIBRARY IS WITH YOU.  SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME
+THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
+
+  16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN
+WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY
+AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU
+FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR
+CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE
+LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING
+RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A
+FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF
+SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
+DAMAGES.
+
+		     END OF TERMS AND CONDITIONS
+
+           How to Apply These Terms to Your New Libraries
+
+  If you develop a new library, and you want it to be of the greatest
+possible use to the public, we recommend making it free software that
+everyone can redistribute and change.  You can do so by permitting
+redistribution under these terms (or, alternatively, under the terms of the
+ordinary General Public License).
+
+  To apply these terms, attach the following notices to the library.  It is
+safest to attach them to the start of each source file to most effectively
+convey the exclusion of warranty; and each file should have at least the
+"copyright" line and a pointer to where the full notice is found.
+
+    <one line to give the library's name and a brief idea of what it does.>
+    Copyright (C) <year>  <name of author>
+
+    This library is free software; you can redistribute it and/or
+    modify it under the terms of the GNU Lesser General Public
+    License as published by the Free Software Foundation; either
+    version 2.1 of the License, or (at your option) any later version.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+
+    You should have received a copy of the GNU Lesser General Public
+    License along with this library; if not, write to the Free Software
+    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+Also add information on how to contact you by electronic and paper mail.
+
+You should also get your employer (if you work as a programmer) or your
+school, if any, to sign a "copyright disclaimer" for the library, if
+necessary.  Here is a sample; alter the names:
+
+  Yoyodyne, Inc., hereby disclaims all copyright interest in the
+  library `Frob' (a library for tweaking knobs) written by James Random Hacker.
+
+  <signature of Ty Coon>, 1 April 1990
+  Ty Coon, President of Vice
+
+That's all there is to it!
+
+
+PLY (Python Lex-Yacc)                   Version 2.0  (September 8, 2006)
+
+David M. Beazley (dave@dabeaz.com)
+
+Copyright (C) 2001-2006   David M. Beazley
+
+This library is free software; you can redistribute it and/or
+modify it under the terms of the GNU Lesser General Public
+License as published by the Free Software Foundation; either
+version 2.1 of the License, or (at your option) any later version.
+
+This library is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+Lesser General Public License for more details.
+
+You should have received a copy of the GNU Lesser General Public
+License along with this library; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+See the file COPYING for a complete copy of the LGPL.
+
+Introduction
+============
+
+PLY is a 100% Python implementation of the common parsing tools lex
+and yacc.   Although several other parsing tools are available for
+Python, there are several reasons why you might want to consider PLY:
+
+ -  The tools are very closely modeled after traditional lex/yacc.
+    If you know how to use these tools in C, you will find PLY
+    to be similar.
+
+ -  PLY provides *very* extensive error reporting and diagnostic 
+    information to assist in parser construction.  The original
+    implementation was developed for instructional purposes.  As
+    a result, the system tries to identify the most common types
+    of errors made by novice users.  
+
+ -  PLY provides full support for empty productions, error recovery,
+    precedence specifiers, and moderately ambiguous grammars.
+
+ -  Parsing is based on LR-parsing which is fast, memory efficient, 
+    better suited to large grammars, and which has a number of nice
+    properties when dealing with syntax errors and other parsing problems.
+    Currently, PLY builds its parsing tables using the SLR algorithm which 
+    is slightly weaker than LALR(1) used in traditional yacc. 
+
+ -  PLY uses Python introspection features to build lexers and parsers.  
+    This greatly simplifies the task of parser construction since it reduces 
+    the number of files and eliminates the need to run a separate lex/yacc 
+    tool before running your program.
+
+ -  PLY can be used to build parsers for "real" programming languages.
+    Although it is not ultra-fast due to its Python implementation,
+    PLY can be used to parse grammars consisting of several hundred
+    rules (as might be found for a language like C).  The lexer and LR 
+    parser are also reasonably efficient when parsing typically
+    sized programs.
+
+The original version of PLY was developed for an Introduction to
+Compilers course where students used it to build a compiler for a
+simple Pascal-like language.  Their compiler had to include lexical
+analysis, parsing, type checking, type inference, and generation of
+assembly code for the SPARC processor.  Because of this, the current
+implementation has been extensively tested and debugged.  In addition,
+most of the API and error checking steps have been adapted to address
+common usability problems.
+
+How to Use
+==========
+
+PLY consists of two files : lex.py and yacc.py.  To use the system,
+simply copy these files to your project and import them like standard
+Python modules.
+
+The file doc/ply.html contains complete documentation on how to use
+the system.
+
+The example directory contains several different examples including a
+PLY specification for ANSI C as given in K&R 2nd Ed.   
+
+A simple example is found at the end of this document
+
+Requirements
+============
+PLY requires the use of Python 2.0 or greater.  It should work on
+just about any platform.
+
+Resources
+=========
+
+More information about PLY can be obtained on the PLY webpage at:
+
+     http://www.dabeaz.com/ply
+
+For a detailed overview of parsing theory, consult the excellent
+book "Compilers : Principles, Techniques, and Tools" by Aho, Sethi, and
+Ullman.  The topics found in "Lex & Yacc" by Levine, Mason, and Brown
+may also be useful.
+
+Acknowledgments
+===============
+
+A special thanks is in order for all of the students in CS326 who
+suffered through about 25 different versions of these tools :-).
+
+The CHANGES file acknowledges those who have contributed patches.
+
+Elias Ioup did the first implementation of LALR(1) parsing in PLY-1.x. 
+Andrew Waters and Markus Schoepflin were instrumental in reporting bugs
+and testing a revised LALR(1) implementation for PLY-2.0.
+
+Special Note for PLY-2.x
+========================
+PLY-2.0 is the first in a series of PLY releases that will be adding a
+variety of significant new features.  The first release in this series
+(Ply-2.0) should be 100% compatible with all previous Ply-1.x releases
+except for the fact that Ply-2.0 features a correct implementation of
+LALR(1) table generation.  
+
+If you have suggestions for improving PLY in future 2.x releases, please
+contact me.   - Dave
+
+Example
+=======
+
+Here is a simple example showing a PLY implementation of a calculator with variables.
+
+# -----------------------------------------------------------------------------
+# calc.py
+#
+# A simple calculator with variables.
+# -----------------------------------------------------------------------------
+
+tokens = (
+    'NAME','NUMBER',
+    'PLUS','MINUS','TIMES','DIVIDE','EQUALS',
+    'LPAREN','RPAREN',
+    )
+
+# Tokens
+
+t_PLUS    = r'\+'
+t_MINUS   = r'-'
+t_TIMES   = r'\*'
+t_DIVIDE  = r'/'
+t_EQUALS  = r'='
+t_LPAREN  = r'\('
+t_RPAREN  = r'\)'
+t_NAME    = r'[a-zA-Z_][a-zA-Z0-9_]*'
+
+def t_NUMBER(t):
+    r'\d+'
+    try:
+        t.value = int(t.value)
+    except ValueError:
+        print "Integer value too large", t.value
+        t.value = 0
+    return t
+
+# Ignored characters
+t_ignore = " \t"
+
+def t_newline(t):
+    r'\n+'
+    t.lineno += t.value.count("\n")
+    
+def t_error(t):
+    print "Illegal character '%s'" % t.value[0]
+    t.skip(1)
+    
+# Build the lexer
+import lex
+lex.lex()
+
+# Precedence rules for the arithmetic operators
+precedence = (
+    ('left','PLUS','MINUS'),
+    ('left','TIMES','DIVIDE'),
+    ('right','UMINUS'),
+    )
+
+# dictionary of names (for storing variables)
+names = { }
+
+def p_statement_assign(p):
+    'statement : NAME EQUALS expression'
+    names[p[1]] = p[3]
+
+def p_statement_expr(p):
+    'statement : expression'
+    print p[1]
+
+def p_expression_binop(p):
+    '''expression : expression PLUS expression
+                  | expression MINUS expression
+                  | expression TIMES expression
+                  | expression DIVIDE expression'''
+    if p[2] == '+'  : p[0] = p[1] + p[3]
+    elif p[2] == '-': p[0] = p[1] - p[3]
+    elif p[2] == '*': p[0] = p[1] * p[3]
+    elif p[2] == '/': p[0] = p[1] / p[3]
+
+def p_expression_uminus(p):
+    'expression : MINUS expression %prec UMINUS'
+    p[0] = -p[2]
+
+def p_expression_group(p):
+    'expression : LPAREN expression RPAREN'
+    p[0] = p[2]
+
+def p_expression_number(p):
+    'expression : NUMBER'
+    p[0] = p[1]
+
+def p_expression_name(p):
+    'expression : NAME'
+    try:
+        p[0] = names[p[1]]
+    except LookupError:
+        print "Undefined name '%s'" % p[1]
+        p[0] = 0
+
+def p_error(p):
+    print "Syntax error at '%s'" % p.value
+
+import yacc
+yacc.yacc()
+
+while 1:
+    try:
+        s = raw_input('calc > ')
+    except EOFError:
+        break
+    yacc.parse(s)
+
+
+Bug Reports and Patches
+=======================
+Because of the extremely specialized and advanced nature of PLY, I
+rarely spend much time working on it unless I receive very specific
+bug-reports and/or patches to fix problems. I also try to incorporate
+submitted feature requests and enhancements into each new version.  To
+contact me about bugs and/or new features, please send email to
+dave@dabeaz.com.
+
+-- Dave
+
+
+
+
+
+
+
+
+
+The PLY to-do list:
+
+1. More interesting parsing examples.
+
+2. Work on the ANSI C grammar so that it can actually parse C programs.  To do this,
+   some extra code needs to be added to the lexer to deal with typedef names and enumeration
+   constants.
+
+3. More tests in the test directory.
+
+4. Performance improvements and cleanup in yacc.py.
+
+5. More documentation (?).
+

File doc/ply.html

+<html>
+<head>
+<title>PLY (Python Lex-Yacc)</title>
+</head>
+<body bgcolor="#ffffff">
+
+<h1>PLY (Python Lex-Yacc)</h1>
+
+<b>
+David M. Beazley <br>
+dave@dabeaz.com<br>
+</b>
+
+<p>
+<b>PLY Version: 2.0</b>
+<p>
+
+<h2>Introduction</h2>
+
+PLY is a pure-Python implementation of the popular compiler
+construction tools lex and yacc. The main goal of PLY is to stay
+fairly faithful to the way in which traditional lex/yacc tools work.
+This includes supporting the LALR(1) parsing as well as providing
+extensive input validation, error reporting, and diagnostics.  Thus,
+if you've used yacc in another programming language, it should be
+relatively straightforward to use PLY.  
+
+<p>
+Early versions of PLY were developed to support an Introduction to
+Compilers Course I taught at the University of Chicago.  In this course,
+students built a fully functional compiler for a simple Pascal-like
+language.  Their compiler, implemented entirely in Python, had to
+include lexical analysis, parsing, type checking, type inference,
+nested scoping, and code generation for the SPARC processor.
+Approximately 30 different compiler implementations were completed in
+this course.  Most of PLY's interface and operation has been motivated by common
+usability problems encountered by students.
+
+<p>
+Because PLY was primarily developed as an instructional tool, you will
+find it to be <em>MUCH</em> more picky about token and grammar rule
+specification than most other Python parsing tools.  In part, this
+added formality is meant to catch common programming mistakes made by
+novice users.  However, advanced users will also find such features to
+be useful when building complicated grammars for real programming
+languages.  It should also be noted that PLY does not provide much in
+the way of bells and whistles (e.g., automatic construction of
+abstract syntax trees, tree traversal, etc.). Nor would I consider it
+to be a parsing framework.  Instead, you will find a bare-bones, yet
+fully capable lex/yacc implementation written entirely in Python.
+
+<p>
+The rest of this document assumes that you are somewhat familar with
+parsing theory, syntax directed translation, and compiler construction tools such
+as lex and yacc. If you are unfamilar with these topics, you will
+probably want to consult an introductory text such as "Compilers:
+Principles, Techniques, and Tools", by Aho, Sethi, and Ullman.  O'Reilly's "Lex
+and Yacc" by John Levine may also be handy.
+
+<h2>PLY Overview</h2>
+
+PLY consists of two separate modules; <tt>lex.py</tt> and
+<tt>yacc.py</tt>.  <tt>lex.py</tt> is used to break input text into a
+collection of tokens specified by a collection of regular expression
+rules.  <tt>yacc.py</tt> is used to recognize language syntax that has
+been specified in the form of a context free grammar. <tt>yacc.py</tt> uses LR parsing and generates its parsing tables
+using either the SLR (the default) or LALR(1) table generation algorithms.
+
+<p>
+The two tools are meant to work together.  Specifically,
+<tt>lex.py</tt> provides an external interface in the form of a
+<tt>token()</tt> function that returns the next valid token on the
+input stream.  <tt>yacc.py</tt> calls this repeatedly to retrieve
+tokens and invoke grammar rules.  The output of <tt>yacc.py</tt> is
+often an Abstract Syntax Tree (AST).  However, this is entirely up to
+the user.  If desired, <tt>yacc.py</tt> can also be used to implement
+simple one-pass compilers.
+
+<p>
+Like its Unix counterpart, <tt>yacc.py</tt> provides most of the
+features you expect including extensive error checking, grammar
+validation, support for empty productions, error tokens, and ambiguity
+resolution via precedence rules.  The primary difference between
+<tt>yacc.py</tt> and Unix <tt>yacc</tt> is that <tt>yacc.py</tt> uses the SLR parsing 
+algorithm instead of LALR(1) as the default.  For simple grammars, SLR is often
+sufficient.  However, LALR(1) support can be enabled as an option.
+
+<p>
+It is important to note that PLY relies on reflection (introspection)
+to build its lexers and parsers.  Unlike traditional lex/yacc which
+require a special input file that is converted into a separate source
+file, the specifications given to PLY <em>are</em> valid Python
+programs.  This means that there are no extra source files nor is
+there a special compiler construction step (e.g., running yacc to
+generate Python code for the compiler).  Since the generation of the
+parsing tables is relatively expensive, PLY caches the results and
+saves them to a file.  If no changes are detected in the input source,
+the tables are read from the cache. Otherwise, they are regenerated.
+
+<h2>Lex Example</h2>
+
+<tt>lex.py</tt> is used to write tokenizers.  To do this, each token
+must be defined by a regular expression rule.  The following file
+implements a very simple lexer for tokenizing simple integer expressions:
+
+<blockquote>
+<pre>
+# ------------------------------------------------------------
+# calclex.py
+#
+# tokenizer for a simple expression evaluator for
+# numbers and +,-,*,/
+# ------------------------------------------------------------
+import lex
+
+# List of token names.   This is always required
+tokens = (
+   'NUMBER',
+   'PLUS',
+   'MINUS',
+   'TIMES',
+   'DIVIDE',
+   'LPAREN',
+   'RPAREN',
+)
+
+# Regular expression rules for simple tokens
+t_PLUS    = r'\+'
+t_MINUS   = r'-'
+t_TIMES   = r'\*'
+t_DIVIDE  = r'/'
+t_LPAREN  = r'\('
+t_RPAREN  = r'\)'
+
+# A regular expression rule with some action code
+def t_NUMBER(t):
+    r'\d+'
+    try:
+         t.value = int(t.value)    
+    except ValueError:
+         print "Line %d: Number %s is too large!" % (t.lineno,t.value)
+	 t.value = 0
+    return t
+
+# Define a rule so we can track line numbers
+def t_newline(t):
+    r'\n+'
+    t.lineno += len(t.value)
+
+# A string containing ignored characters (spaces and tabs)
+t_ignore  = ' \t'
+
+# Error handling rule
+def t_error(t):
+    print "Illegal character '%s'" % t.value[0]
+    t.skip(1)
+
+# Build the lexer
+lex.lex()
+
+</pre>
+</blockquote>
+To use the lexer, you first need to feed it some input text using its <tt>input()</tt> method.  After that, repeated calls to <tt>token()</tt> produce tokens.   The following code shows how this works:
+
+<blockquote>
+<pre>
+
+# Test it out
+data = '''
+3 + 4 * 10
+  + -20 *2
+'''
+
+# Give the lexer some input
+lex.input(data)
+
+# Tokenize
+while 1:
+    tok = lex.token()
+    if not tok: break      # No more input
+    print tok
+</pre>
+</blockquote>
+
+In the example, the <tt>tokens</tt> list defines all of the possible
+token names that can be produced by the lexer.  This list is always required
+and is used to perform a variety of validation checks.  Following the <tt>tokens</tt>
+list, regular expressions are written for each token.  Each of these
+rules are defined by making declarations with a special prefix <tt>t_</tt> to indicate that it
+defines a token.  For simple tokens, the regular expression can
+be specified as strings such as this (note: Python raw strings are used since they are the
+most convenient way to write regular expression strings):
+
+<blockquote>
+<pre>
+t_PLUS = r'\+'
+</pre>
+</blockquote>
+
+In this case, the name following the <tt>t_</tt> must exactly match one of the
+names supplied in <tt>tokens</tt>.   If some kind of action needs to be performed,
+a token rule can be specified as a function.  For example:
+
+<blockquote>
+<pre>
+def t_NUMBER(t):
+    r'\d+'
+    try:
+         t.value = int(t.value)
+    except ValueError:
+         print "Number %s is too large!" % t.value
+	 t.value = 0
+    return t
+</pre>
+</blockquote>
+
+In this case, the regular expression rule is specified in the function documentation string. 
+The function always takes a single argument which is an instance of 
+<tt>LexToken</tt>.   This object has attributes of <tt>t.type</tt> which is the token type,
+<tt>t.value</tt> which is the lexeme, and <tt>t.lineno</tt> which is the current line number.
+By default, <tt>t.type</tt> is set to the name following the <tt>t_</tt> prefix.  The action
+function can modify the contents of the <tt>LexToken</tt> object as appropriate.  However, 
+when it is done, the resulting token should be returned.  If no value is returned by the action
+function, the token is simply discarded and the next token read.
+
+<p>
+The rule <tt>t_newline()</tt> illustrates a regular expression rule
+for a discarded token.  In this case, a rule is written to match
+newlines so that proper line number tracking can be performed.
+By returning no value, the function causes the newline character to be 
+discarded.   The tokenizer is, however, monitoring the line number attribute for changes. 
+
+<p>
+The special <tt>t_ignore</tt> rule is reserved by <tt>lex.py</tt> for characters
+that should be completely ignored in the input stream. 
+Usually this is used to skip over whitespace and other non-essential characters. 
+Although it is possible to define a regular expression rule for whitespace in a manner
+similar to <tt>t_newline()</tt>, the use of <tt>t_ignore</tt> provides substantially better
+lexing performance because it is handled as a special case and is checked in a much
+more efficient manner than the normal regular expression rules.
+
+<p>
+Finally, the <tt>t_error()</tt>
+function is used to handle lexing errors that occur when illegal
+characters are detected.  In this case, the <tt>t.value</tt> attribute contains the
+rest of the input string that has not been tokenized.  In the example, we simply print
+the offending character and skip ahead one character by calling <tt>t.skip(1)</tt>.
+
+<p>
+To build the lexer, the function <tt>lex.lex()</tt> is used.  This function
+uses Python reflection (or introspection) to read the the regular expression rules
+out of the calling context and build the lexer. Once the lexer has been built, two functions can
+be used to control the lexer.
+
+<ul>
+<li><tt>lex.input(data)</tt>.   Reset the lexer and store a new input string.
+<li><tt>lex.token()</tt>.  Return the next token.  Returns a special <tt>LexToken</tt> instance on success or
+None if the end of the input text has been reached.
+</ul>
+
+The code at the bottom of the example shows how the lexer is actually used.  When executed,
+the following output will be produced:
+
+<blockquote>
+<pre>
+$ python example.py
+LexToken(NUMBER,3,2)
+LexToken(PLUS,'+',2)
+LexToken(NUMBER,4,2)
+LexToken(TIMES,'*',2)
+LexToken(NUMBER,10,2)
+LexToken(PLUS,'+',3)
+LexToken(MINUS,'-',3)
+LexToken(NUMBER,20,3)
+LexToken(TIMES,'*',3)
+LexToken(NUMBER,2,3)
+</pre>
+</blockquote>
+
+<h2>Lex Implementation Notes</h2>
+
+<ul>
+<li><tt>lex.py</tt> uses the <tt>re</tt> module to do its patten matching.  When building the master regular expression,
+rules are added in the following order:
+<p>
+<ol>
+<li>All tokens defined by functions are added in the same order as they appear in the lexer file.
+<li>Tokens defined by strings are added by sorting them in order of decreasing regular expression length (longer expressions
+are added first).
+</ol>
+<p>
+Without this ordering, it can be difficult to correctly match certain types of tokens.  For example, if you 
+wanted to have separate tokens for "=" and "==", you need to make sure that "==" is checked first.  By sorting regular
+expressions in order of decreasing length, this problem is solved for rules defined as strings.  For functions,
+the order can be explicitly controlled since rules appearing first are checked first.
+
+<P>
+<li>The lexer requires input to be supplied as a single input string.  Since most machines have more than enough memory, this 
+rarely presents a performance concern.  However, it means that the lexer currently can't be used with streaming data
+such as open files or sockets.  This limitation is primarily a side-effect of using the <tt>re</tt> module.
+
+<p>
+<li>
+To handle reserved words, it is usually easier to just match an identifier and do a special name lookup in a function
+like this:
+
+<blockquote>
+<pre>
+reserved = {
+   'if' : 'IF',
+   'then' : 'THEN',
+   'else' : 'ELSE',
+   'while' : 'WHILE',
+   ...
+}
+
+def t_ID(t):
+    r'[a-zA-Z_][a-zA-Z_0-9]*'
+    t.type = reserved.get(t.value,'ID')    # Check for reserved words
+    return t
+</pre>
+</blockquote>
+
+<p>
+<li>The lexer requires tokens to be defined as class instances with <tt>t.type</tt>, <tt>t.value</tt>, and <tt>t.lineno</tt>
+attributes.   By default, tokens are created as instances of the <tt>LexToken</tt> class defined internally to <tt>lex.py</tt>.
+If desired, you can create new kinds of tokens provided that they have the three required attributes.   However,
+in practice, it is probably safer to stick with the default.
+
+<p>
+<li>The only safe attribute for assigning token properties is <tt>t.value</tt>.   In some cases, you may want to attach
+a number of different properties to a token (e.g., symbol table entries for identifiers).  To do this, replace <tt>t.value</tt>
+with a tuple or class instance. For example:
+
+<blockquote>
+<pre>
+def t_ID(t):
+    ...
+    # For identifiers, create a (lexeme, symtab) tuple
+    t.value = (t.value, symbol_lookup(t.value))
+    ...
+    return t
+</pre>
+</blockquote>
+
+Although allowed, do NOT assign additional attributes to the token object.  For example,
+<blockquote>
+<pre>
+def t_ID(t):
+    ...
+    # Bad implementation of above
+    t.symtab = symbol_lookup(t.value)
+    ...
+</pre>
+</blockquote>
+
+The reason you don't want to do this is that the <tt>yacc.py</tt>
+module only provides public access to the <tt>t.value</tt> attribute of each token.
+Therefore, any other attributes you assign are inaccessible (if you are familiar
+with the internals of C lex/yacc, <tt>t.value</tt> is the same as <tt>yylval.tok</tt>).
+
+<p>
+<li>To track line numbers, the lexer internally maintains a line
+number variable.  Each token automatically gets the value of the
+current line number in the <tt>t.lineno</tt> attribute. To modify the
+current line number, simply change the <tt>t.lineno</tt> attribute
+in a function rule (as previously shown for
+<tt>t_newline()</tt>).  Even if the resulting token is discarded,
+changes to the line number remain in effect for subsequent tokens.
+
+<p>
+<li>To support multiple scanners in the same application, the <tt>lex.lex()</tt> function
+actually returns a special <tt>Lexer</tt> object.   This object has two methods 
+<tt>input()</tt> and <tt>token()</tt> that can be used to supply input and get tokens.  For example:
+
+<blockquote>
+<pre>
+lexer = lex.lex()
+lexer.input(sometext)
+while 1:
+    tok = lexer.token()
+    if not tok: break
+    print tok
+</pre>
+</blockquote>
+
+The functions <tt>lex.input()</tt> and <tt>lex.token()</tt> are bound to the <tt>input()</tt> 
+and <tt>token()</tt> methods of the last lexer created by the lex module. 
+
+
+<p>
+<li>To reduce compiler startup time and improve performance, the lexer can be built in optimized mode as follows:
+
+<blockquote>
+<pre>
+lex.lex(optimize=1)
+</pre>
+</blockquote>
+
+When used, most error checking and validation is disabled.   This provides a slight performance
+gain while tokenizing and tends to chop a few tenths of a second off startup time.  Since it disables
+error checking, this mode is not the default and is not recommended during development.  However, once
+you have your compiler fully working, it is usually safe to disable the error checks.
+
+<p>
+<li>You can enable some additional debugging by building the lexer like this:
+
+<blockquote>
+<pre>
+lex.lex(debug=1)
+</pre>
+</blockquote>
+
+<p>
+<li>To help you debug your lexer, <tt>lex.py</tt> comes with a simple main program which will either
+tokenize input read from standard input or from a file.  To use it, simply put this in your lexer:
+
+<blockquote>
+<pre>
+if __name__ == '__main__':
+     lex.runmain()
+</pre>
+</blockquote>
+
+Then, run you lexer as a main program such as <tt>python mylex.py</tt>
+
+<p>
+<li>The lexer should work properly with both Unicode strings given as token and pattern matching rules as
+well as for input text.
+
+<p>
+<li>If you need to supply optional flags to the re.compile() function, use the reflags option to lex.  For example:
+
+<blockquote>
+<pre>
+lex.lex(reflags=re.UNICODE)
+</pre>
+</blockquote>
+
+<p>
+<li>Since the lexer is written entirely in Python, its performance is
+largely determined by that of the Python <tt>re</tt> module.  Although
+the lexer has been written to be as efficient as possible, it's not
+blazingly fast when used on very large input files.  If
+performance is concern, you might consider upgrading to the most
+recent version of Python, creating a hand-written lexer, or offloading
+the lexer into a C extension module.  In defense of <tt>lex.py</tt>,
+it's performance is not <em>that</em> bad when used on reasonably
+sized input files.  For instance, lexing a 4700 line C program with
+32000 input tokens takes about 20 seconds on a 200 Mhz PC.  Obviously,
+it will run much faster on a more speedy machine.
+
+</ul>
+
+<h2>Parsing basics</h2>
+
+<tt>yacc.py</tt> is used to parse language syntax.  Before showing an
+example, there are a few important bits of background that must be
+mentioned.  First, <em>syntax</em> is usually specified in terms of a
+context free grammar (CFG).  For example, if you wanted to parse
+simple arithmetic expressions, you might first write an unambiguous
+grammar specification like this:
+
+<blockquote>
+<pre> 
+expression : expression + term
+           | expression - term
+           | term
+
+term       : term * factor
+           | term / factor
+           | factor
+
+factor     : NUMBER
+           | ( expression )
+</pre>
+</blockquote>
+
+In the grammar, symbols such as <tt>NUMBER</tt>, <tt>+</tt>, <tt>-</tt>, <tt>*</tt>, and <tt>/</tt> are known
+as <em>terminals</em> and correspond to raw input tokens.  Identifiers such as <tt>term</tt> and <tt>factor</tt> refer to more
+complex rules, typically comprised of a collection of tokens.  These identifiers are known as <em>non-terminals</em>.
+<P>
+The semantic behavior of a language is often specified using a
+technique known as syntax directed translation.  In syntax directed
+translation, attributes are attached to each symbol in a given grammar
+rule along with an action.  Whenever a particular grammar rule is
+recognized, the action describes what to do.  For example, given the
+expression grammar above, you might write the specification for a
+simple calculator like this:
+
+<blockquote>
+<pre> 
+Grammar                             Action
+--------------------------------    -------------------------------------------- 
+expression0 : expression1 + term    expression0.val = expression1.val + term.val
+            | expression1 - term    expression0.val = expression1.val - term.val
+            | term                  expression0.val = term.val
+
+term0       : term1 * factor        term0.val = term1.val * factor.val
+            | term1 / factor        term0.val = term1.val / factor.val
+            | factor                term0.val = factor.val
+
+factor      : NUMBER                factor.val = int(NUMBER.lexval)
+            | ( expression )        factor.val = expression.val
+</pre>
+</blockquote>
+
+A good way to think about syntax directed translation is to simply think of each symbol in the grammar as some
+kind of object.  The semantics of the language are then expressed as a collection of methods/operations on these
+objects. 
+
+<p>
+Yacc uses a parsing technique known as LR-parsing or shift-reduce parsing.  LR parsing is a
+bottom up technique that tries to recognize the right-hand-side of various grammar rules.
+Whenever a valid right-hand-side is found in the input, the appropriate action code is triggered and the
+grammar symbols are replaced by the grammar symbol on the left-hand-side. 
+
+<p>
+LR parsing is commonly implemented by shifting grammar symbols onto a stack and looking at the stack and the next
+input token for patterns.   The details of the algorithm can be found in a compiler text, but the
+following example illustrates the steps that are performed if you wanted to parse the expression 
+<tt>3 + 5 * (10 - 20)</tt> using the grammar defined above:
+
+<blockquote>
+<pre>
+Step Symbol Stack           Input Tokens            Action
+---- ---------------------  ---------------------   -------------------------------
+1    $                      3 + 5 * ( 10 - 20 )$    Shift 3
+2    $ 3                      + 5 * ( 10 - 20 )$    Reduce factor : NUMBER
+3    $ factor                 + 5 * ( 10 - 20 )$    Reduce term   : factor
+4    $ term                   + 5 * ( 10 - 20 )$    Reduce expr : term
+5    $ expr                   + 5 * ( 10 - 20 )$    Shift +
+6    $ expr +                   5 * ( 10 - 20 )$    Shift 5
+7    $ expr + 5                   * ( 10 - 20 )$    Reduce factor : NUMBER
+8    $ expr + factor              * ( 10 - 20 )$    Reduce term   : factor
+9    $ expr + term                * ( 10 - 20 )$    Shift *
+10   $ expr + term *                ( 10 - 20 )$    Shift (
+11   $ expr + term * (                10 - 20 )$    Shift 10
+12   $ expr + term * ( 10                - 20 )$    Reduce factor : NUMBER
+13   $ expr + term * ( factor            - 20 )$    Reduce term : factor
+14   $ expr + term * ( term              - 20 )$    Reduce expr : term
+15   $ expr + term * ( expr              - 20 )$    Shift -
+16   $ expr + term * ( expr -              20 )$    Shift 20
+17   $ expr + term * ( expr - 20              )$    Reduce factor : NUMBER
+18   $ expr + term * ( expr - factor          )$    Reduce term : factor
+19   $ expr + term * ( expr - term            )$    Reduce expr : expr - term
+20   $ expr + term * ( expr                   )$    Shift )
+21   $ expr + term * ( expr )                  $    Reduce factor : (expr)
+22   $ expr + term * factor                    $    Reduce term : term * factor
+23   $ expr + term                             $    Reduce expr : expr + term
+24   $ expr                                    $    Reduce expr
+25   $                                         $    Success!
+</pre>
+</blockquote>
+
+When parsing the expression, an underlying state machine and the current input token determine what to do next.  
+If the next token looks like part of a valid grammar rule (based on other items on the stack), it is generally shifted
+onto the stack.  If the top of the stack contains a valid right-hand-side of a grammar rule, it is
+usually "reduced" and the symbols replaced with the symbol on the left-hand-side.  When this reduction occurs, the
+appropriate action is triggered (if defined).  If the input token can't be shifted and the top of stack doesn't match
+any grammar rules, a syntax error has occurred and the parser must take some kind of recovery step (or bail out).
+
+<p>
+It is important to note that the underlying implementation is built around a large finite-state machine that is encoded
+in a collection of tables. The construction of these tables is quite complicated and beyond the scope of this discussion.
+However, subtle details of this process explain why, in the example above, the parser chooses to shift a token
+onto the stack in step 9 rather than reducing the rule <tt>expr : expr + term</tt>.
+
+<h2>Yacc example</h2>
+
+Suppose you wanted to make a grammar for simple arithmetic expressions as previously described.   Here is
+how you would do it with <tt>yacc.py</tt>:
+
+<blockquote>
+<pre>
+# Yacc example
+
+import yacc
+
+# Get the token map from the lexer.  This is required.
+from calclex import tokens
+
+def p_expression_plus(p):
+    'expression : expression PLUS term'
+    p[0] = p[1] + p[3]
+
+def p_expression_minus(p):
+    'expression : expression MINUS term'
+    p[0] = p[1] - p[3]
+
+def p_expression_term(p):
+    'expression : term'
+    p[0] = p[1]
+
+def p_term_times(p):
+    'term : term TIMES factor'
+    p[0] = p[1] * p[3]
+
+def p_term_div(p):
+    'term : term DIVIDE factor'
+    p[0] = p[1] / p[3]
+
+def p_term_factor(p):
+    'term : factor'
+    p[0] = p[1]
+
+def p_factor_num(p):
+    'factor : NUMBER'
+    p[0] = p[1]
+
+def p_factor_expr(p):
+    'factor : LPAREN expression RPAREN'
+    p[0] = p[2]
+
+# Error rule for syntax errors
+def p_error(p):
+    print "Syntax error in input!"
+
+# Build the parser
+yacc.yacc()
+
+# Use this if you want to build the parser using LALR(1) instead of SLR
+# yacc.yacc(method="LALR")
+
+while 1:
+   try:
+       s = raw_input('calc > ')
+   except EOFError:
+       break
+   if not s: continue
+   result = yacc.parse(s)
+   print result
+</pre>
+</blockquote>
+
+In this example, each grammar rule is defined by a Python function where the docstring to that function contains the
+appropriate context-free grammar specification.  Each function accepts a single
+argument <tt>p</tt> that is a sequence containing the values of each grammar symbol in the corresponding rule.  The values of
+<tt>p[i]</tt> are mapped to grammar symbols as shown here:
+
+<blockquote>
+<pre>
+def p_expression_plus(p):
+    'expression : expression PLUS term'
+    #   ^            ^        ^    ^
+    #  p[0]         p[1]     p[2] p[3]
+
+    p[0] = p[1] + p[3]
+</pre>
+</blockquote>
+
+For tokens, the "value" of the corresponding <tt>p[i]</tt> is the
+<em>same</em> as the <tt>p.value</tt> attribute assigned
+in the lexer module.  For non-terminals, the value is determined by
+whatever is placed in <tt>p[0]</tt> when rules are reduced.  This
+value can be anything at all.  However, it probably most common for
+the value to be a simple Python type, a tuple, or an instance.  In this example, we
+are relying on the fact that the <tt>NUMBER</tt> token stores an integer value in its value
+field.  All of the other rules simply perform various types of integer operations and store
+the result.
+
+<p>
+The first rule defined in the yacc specification determines the starting grammar
+symbol (in this case, a rule for <tt>expression</tt> appears first).  Whenever
+the starting rule is reduced by the parser and no more input is available, parsing 
+stops and the final value is returned (this value will be whatever the top-most rule
+placed in <tt>p[0]</tt>). Note: an alternative starting symbol can be specified using the <tt>start</tt> keyword argument to
+<tt>yacc()</tt>.
+
+<p>The <tt>p_error(p)</tt> rule is defined to catch syntax errors.  See the error handling section
+below for more detail.
+
+<p>
+To build the parser, call the <tt>yacc.yacc()</tt> function.  This function
+looks at the module and attempts to construct all of the LR parsing tables for the grammar
+you have specified.   The first time <tt>yacc.yacc()</tt> is invoked, you will get a message
+such as this:
+
+<blockquote>
+<pre>
+$ python calcparse.py
+yacc: Generating SLR parsing table...  
+calc > 
+</pre>
+</blockquote>
+
+Since table construction is relatively expensive (especially for large
+grammars), the resulting parsing table is written to the current
+directory in a file called <tt>parsetab.py</tt>.  In addition, a
+debugging file called <tt>parser.out</tt> is created.  On subsequent
+executions, <tt>yacc</tt> will reload the table from
+<tt>parsetab.py</tt> unless it has detected a change in the underlying
+grammar (in which case the tables and <tt>parsetab.py</tt> file are
+regenerated).   Note: The names of parser output files can be changed if necessary.  See the notes that follow later.
+
+<p>
+If any errors are detected in your grammar specification, <tt>yacc.py</tt> will produce
+diagnostic messages and possibly raise an exception.  Some of the errors that can be detected include:
+
+<ul>
+<li>Duplicated function names (if more than one rule function have the same name in the grammar file).
+<li>Shift/reduce and reduce/reduce conflicts generated by ambiguous grammars.
+<li>Badly specified grammar rules.
+<li>Infinite recursion (rules that can never terminate).
+<li>Unused rules and tokens
+<li>Undefined rules and tokens
+</ul>
+
+The next few sections now discuss a few finer points of grammar construction.
+
+<h2>Combining Grammar Rule Functions</h2>
+
+When grammar rules are similar, they can be combined into a single function.
+For example, consider the two rules in our earlier example:
+
+<blockquote>
+<pre>
+def p_expression_plus(p):
+    'expression : expression PLUS term'
+    p[0] = p[1] + p[3]
+
+def p_expression_minus(t):
+    'expression : expression MINUS term'
+    p[0] = p[1] - p[3]
+</pre>
+</blockquote>
+
+Instead of writing two functions, you might write a single function like this:
+
+<blockquote>
+<pre>
+def p_expression(p):
+    '''expression : expression PLUS term
+                  | expression MINUS term'''
+    if p[2] == '+':
+        p[0] = p[1] + p[3]
+    elif p[2] == '-':
+        p[0] = p[1] - p[3]
+</pre>
+</blockquote>
+
+In general, the doc string for any given function can contain multiple grammar rules.  So, it would
+have also been legal (although possibly confusing) to write this:
+
+<blockquote>
+<pre>
+def p_binary_operators(p):
+    '''expression : expression PLUS term
+                  | expression MINUS term
+       term       : term TIMES factor
+                  | term DIVIDE factor'''
+    if p[2] == '+':
+        p[0] = p[1] + p[3]
+    elif p[2] == '-':
+        p[0] = p[1] - p[3]
+    elif p[2] == '*':
+        p[0] = p[1] * p[3]
+    elif p[2] == '/':
+        p[0] = p[1] / p[3]
+</pre>
+</blockquote>
+
+When combining grammar rules into a single function, it is usually a good idea for all of the rules to have
+a similar structure (e.g., the same number of terms).  Otherwise, the corresponding action code may be more 
+complicated than necessary.  However, it is possible to handle simple cases using len().  For example:
+
+<blockquote>
+<pre>
+def p_expressions(p):
+    '''expression : expression MINUS expression
+                  | MINUS expression'''
+    if (len(p) == 4):
+        p[0] = p[1] - p[3]
+    elif (len(p) == 3):
+        p[0] = -p[2]
+</pre>
+</blockquote>
+
+<h2>Empty Productions</h2>
+
+<tt>yacc.py</tt> can handle empty productions by defining a rule like this:
+
+<blockquote>
+<pre>
+def p_empty(p):
+    'empty :'
+    pass
+</pre>
+</blockquote>
+
+Now to use the empty production, simply use 'empty' as a symbol.  For example:
+
+<blockquote>
+<pre>
+def p_optitem(p):
+    'optitem : item'
+    '        | empty'
+    ...
+</pre>
+</blockquote>
+
+<h2>Dealing With Ambiguous Grammars</h2>
+
+The expression grammar given in the earlier example has been written in a special format to eliminate ambiguity. 
+However, in many situations, it is extremely difficult or awkward to write grammars in this format.  A
+much more natural way to express the grammar is in a more compact form like this:
+
+<blockquote>
+<pre>
+expression : expression PLUS expression
+           | expression MINUS expression
+           | expression TIMES expression
+           | expression DIVIDE expression
+           | LPAREN expression RPAREN
+           | NUMBER
+</pre>
+</blockquote>
+
+Unfortunately, this grammar specification is ambiguous.  For example, if you are parsing the string
+"3 * 4 + 5", there is no way to tell how the operators are supposed to be grouped.
+For example, does this expression mean "(3 * 4) + 5" or is it "3 * (4+5)"?
+
+<p>
+When an ambiguous grammar is given to <tt>yacc.py</tt> it will print messages about "shift/reduce conflicts" 
+or a "reduce/reduce conflicts".   A shift/reduce conflict is caused when the parser generator can't decide
+whether or not to reduce a rule or shift a symbol on the parsing stack.   For example, consider
+the string "3 * 4 + 5" and the internal parsing stack:
+
+<blockquote>
+<pre>
+Step Symbol Stack           Input Tokens            Action
+---- ---------------------  ---------------------   -------------------------------
+1    $                                3 * 4 + 5$    Shift 3
+2    $ 3                                * 4 + 5$    Reduce : expression : NUMBER
+3    $ expr                             * 4 + 5$    Shift *
+4    $ expr *                             4 + 5$    Shift 4
+5    $ expr * 4                             + 5$    Reduce: expression : NUMBER
+6    $ expr * expr                          + 5$    SHIFT/REDUCE CONFLICT ????
+</pre>
+</blockquote>
+
+In this case, when the parser reaches step 6, it has two options.  One is to reduce the
+rule <tt>expr : expr * expr</tt> on the stack.  The other option is to shift the
+token <tt>+</tt> on the stack.   Both options are perfectly legal from the rules
+of the context-free-grammar.
+
+<p>
+By default, all shift/reduce conflicts are resolved in favor of shifting.  Therefore, in the above
+example, the parser will always shift the <tt>+</tt> instead of reducing.    Although this
+strategy works in many cases (including the ambiguous if-then-else), it is not enough for arithmetic
+expressions.  In fact, in the above example, the decision to shift <tt>+</tt> is completely wrong---we should have
+reduced <tt>expr * expr</tt> since multiplication has higher mathematical precedence than addition.
+
+<p>To resolve ambiguity, especially in expression grammars, <tt>yacc.py</tt> allows individual
+tokens to be assigned a precedence level and associativity.  This is done by adding a variable
+<tt>precedence</tt> to the grammar file like this:
+
+<blockquote>
+<pre>
+precedence = (
+    ('left', 'PLUS', 'MINUS'),
+    ('left', 'TIMES', 'DIVIDE'),
+)
+</pre>
+</blockquote>
+
+This declaration specifies that <tt>PLUS</tt>/<tt>MINUS</tt> have
+the same precedence level and are left-associative and that 
+<tt>TIMES</tt>/<tt>DIVIDE</tt> have the same precedence and are left-associative.
+Furthermore, the declaration specifies that <tt>TIMES</tt>/<tt>DIVIDE</tt> have higher
+precedence than <tt>PLUS</tt>/<tt>MINUS</tt> (since they appear later in the
+precedence specification).
+
+<p>
+The precedence specification is used to attach a numerical precedence value and associativity direction 
+to each grammar rule. <em>This is always determined by the precedence of the right-most terminal symbol.</em>  Therefore,
+if PLUS/MINUS had a precedence of 1 and TIMES/DIVIDE had a precedence of 2, the grammar rules
+would have precedence values as follows:
+
+<blockquote>
+<pre>
+expression : expression PLUS expression                 # prec = 1, left
+           | expression MINUS expression                # prec = 1, left
+           | expression TIMES expression                # prec = 2, left
+           | expression DIVIDE expression               # prec = 2, left
+           | LPAREN expression RPAREN                   # prec = unknown
+           | NUMBER                                     # prec = unknown
+</pre>
+</blockquote>
+
+When shift/reduce conflicts are encountered, the parser generator resolves the conflict by
+looking at the precedence rules and associativity specifiers.
+
+<p>
+<ol>
+<li>If the current token has higher precedence, it is shifted.
+<li>If the grammar rule on the stack has higher precedence, the rule is reduced.
+<li>If the current token and the grammar rule have the same precedence, the
+rule is reduced for left associativity, whereas the token is shifted for right associativity.
+<li>If nothing is known about the precedence, shift/reduce conflicts are resolved in
+favor of shifting (the default).
+</ol>
+
+<p>
+When shift/reduce conflicts are resolved using the first three techniques (with the help of
+precedence rules), <tt>yacc.py</tt> will report no errors or conflicts in the grammar. 
+
+<p>
+One problem with the precedence specifier technique is that it is sometimes necessary to
+change the precedence of an operator in certain contents.  For example, consider a unary-minus operator
+in "3 + 4 * -5".  Normally, unary minus has a very high precedence--being evaluated before the multiply.
+However, in our precedence specifier, MINUS has a lower precedence than TIMES.  To deal with this,
+precedence rules can be given for fictitious tokens like this:
+
+<blockquote>
+<pre>
+precedence = (
+    ('left', 'PLUS', 'MINUS'),
+    ('left', 'TIMES', 'DIVIDE'),
+    ('right', 'UMINUS'),            # Unary minus operator
+)
+</pre>
+</blockquote>
+
+Now, in the grammar file, we can write our unary minus rule like this:
+
+<blockquote>
+<pre>
+def p_expr_uminus(p):
+    'expression : MINUS expression %prec UMINUS'
+    p[0] = -p[2]
+</pre>
+</blockquote>
+
+In this case, <tt>%prec UMINUS</tt> overrides the default rule precedence--setting it to that
+of UMINUS in the precedence specifier.
+
+<p>
+At first, the use of UMINUS in this example may appear very confusing.
+UMINUS is not an input token or a grammer rule.  Instead, you should
+think of it as the name of a special marker in the precedence table.   When you use the <tt>%prec</tt> qualifier, you're simply
+telling yacc that you want the precedence of the expression to be the same as for this special marker instead of the usual precedence.
+
+<p>
+It is also possible to specify non-associativity in the <tt>precedence</tt> table. This would
+be used when you <em>don't</em> want operations to chain together.  For example, suppose
+you wanted to support a comparison operators like <tt>&lt;</tt> and <tt>&gt;</tt> but you didn't want to allow
+combinations like <tt>a &lt; b &lt; c</tt>.   To do this, simply specify a rule like this:
+
+<blockquote>
+<pre>
+precedence = (