A parser generator in Python: kwParsing

Introduction

The kjParsing package is a parser generator written in Python which generates parsers for use in Python.

These modules and their documentation and demo files may be of use for classes on parsing, compiling, or formal languages, and may also be helpful to people who like to create experimental interpreters or translators or compilers.

The package consists of three Python modules: kjParser, kjParseBuild, and kjSet. Together these modules are called the kjParsing package. The package also includes some documentation and demo files and a COPYRIGHT file which explains the conditions for copying and propagating this code and the fact that the author assumes no responsibility for any difficulties resulting from the use of this package by anyone (including himself).

What a Parser Does

Parsers generated by the kjParseBuild module may do three different sorts of actions:

>>> from DLispShort import LispG, Context

>>> LispG.DoParse1( ' ("list with string and int" 23) ', Context)

['list with string and int', 23]

>>>

>>> LispG.DoParse1( '(setq Variable (4 5 9))', Context)

[4, 5, 9]

>>> Context['Variable']

[4, 5, 9]

>>>

>>> LispG.DoParse1( '( (print Variable) (print "bye bye")  )', Context )

[4, 5, 9]

bye bye

[[4, 5, 9], 'bye bye']

>>>

To implement a parser using kjParseBuild you must define the grammar to parse and associate each rule and terminal of the grammar with an action which defines the computational meaning of each language construct.

The grammar generation process consists of two phases

           # from file DLispShort.py (with small differences)

     ( 1)  def GrammarBuild():

     ( 2)      import kjParseBuild

     ( 3)      LispG = kjParseBuild.NullCGrammar()

     ( 4)      LispG.SetCaseSensitivity(0) 

     ( 5)      DeclareTerminals(LispG)

     ( 6)      LispG.Keywords("setq print")

     ( 7)      LispG.punct("().")

     ( 8)      LispG.Nonterms("Value ListTail")

     ( 9)      LispG.comments([LISPCOMMENTREGEX])

     (10)      LispG.Declarerules(GRAMMARSTRING)

     (11)      LispG.Compile()

               print "dumping as binary to TESTLispG.mar"

     (12)      outfile = open("TESTLispG.mar", "w")

     (13)      LispG.MarshalDump(outfile)

     (14)      outfile.close()

     (15)      BindRules(LispG)

     (16)      return LispG

Defining a Grammar

Declaring Case Sensitivity and Comments

Some grammars are not case sensitive in recognizing keywords or identifiers. For example ANSI standard SQL (which is not case sensitive for keywords or identifiers) recognizes Select, select, SELECT, and SeLect all as the keyword SELECT. To specify the case sensitivity of the grammar for keywords only use

     GRAMMAROBJECT.SetCaseSensitivity(TrueOrFalse) 

Comments are patterns in the input string which are ignored (or more precisely interpreted as white space) by the language. To declare a sequence of regular expressions to be interpreted as a comment in a grammar use

    GRAMMAROBJECT.comments(LIST_OF_COMMENT_REGULAR_EXPR_STRINGS)

    LISPCOMMENTREGEX = ";.*"

Declaring Keywords, Punctuations, and Terminals

      GRAMMAROBJECT.Keywords( STRING )

To declare nonterminals for your grammar, similarly, use

      GRAMMAROBJECT.Nonterms( STRING )

Similarly, use

      GRAMMAROBJECT.punct( STRING )

If you have a lot of keywords, punctuations, or nonterminals you can make many separate calls to the appropriate declaration methods with different strings.

These declarations will cause the grammar to recognize the declared keyword strings (when separated from other strings by white space or punctuations) and punctuations as special tokens of the grammar at the lowest level of parsing. The parsing process derives nonterminals of the grammar at a higher level as discussed below.

A small difficulty with kjParseBuild is that the strings @R, ::, >>, and ## cannot be used as names of keywords for the grammar because they are used to specify rule syntax in the ``metagrammar''. If you need these in your grammar they may be implemented as ``trivial'' terminals. For example,

Declaring Terminals

        # from DLispShort.py

        def DeclareTerminals(Grammar):

   (1)      Grammar.Addterm("int", INTREGEX, intInterp)

   (2)      Grammar.Addterm("str", STRREGEX, stripQuotes)

   (3)      Grammar.Addterm("var", VARREGEX, echo)

Figure TermDef shows the declarations for installing the int, str, and var terminals in the grammar. This is given as a separate function because the declarations define both the syntax and semantics for the terminals, and therefore must be called both during grammar generation and after loading the generated grammar object. To declare a terminal for a grammar use

      GRAMMAROBJECT.Addterm(NAMESTR, REGEXSTR, FUNCTION)

      STRREGEX = '"[^\n"]*"'

Declaring Rules of the Grammar

# from DLispShort.py

GRAMMARSTRING ="""

       Value ::  ## indicates Value is the root nonterminal for the grammar

         @R SetqRule :: Value >> ( setq var Value )

         @R ListRule :: Value >> ( ListTail

         @R TailFull :: ListTail >> Value ListTail

         @R TailEmpty :: ListTail >> )

         @R Varrule :: Value >> var

         @R Intrule :: Value >> int

         @R Strrule :: Value >> str

         @R PrintRule :: Value >> ( print Value )

"""

To declare the rules of a grammar use the simple rule definition language which comes with kjParseBuild, for example as shown in Figure GramStr. Line 10 of Figure GrammarBuild uses the string defined in Figure GramStr to associate the rules with the grammar using

      GRAMMAROBJECT.DeclareRules(RULE_DEFINITION_STRING)

The rule definition language allows you to identify the root nonterminal of your grammar and specify a sequence of named derivation rules for the grammar. It also allows comments which start with ## and end with a newline. An acceptible string for the rule definition language looks like

Note that punctuations for the grammar you are defining are not punctuations for the rule definition language (which has none), so they must be separated from other tokens by white space. The keyword for the rule definition language @R, ::, >> must also be separated from other tokens by whitespace in the rule definition string. Furthermore, all punctuations, keywords, nonterminals, and terminals used in the rules must be declared for the grammar before the grammar is compiled (if one isn't the compilation will fail with an error).

As a bit of sugar you may break up the declarations of rules.

    LispG.DeclareRules("Value::\n")

    LispG.DeclareRules("  @R SetqRule :: Value >> ( setq var Value )\n")

    LispG.DeclareRules("  @R ListRule :: Value >> ( ListTail\n")

    ...

A Brief Discussion of Derivations

For a more precise definition of the derivation of a language string from a grammar see the ``further readings'' below. For illustrative purposes, and to help explain how to define semantics functions, consider the following derivation of the string

(1)    Value1 

(2)    ( ListTail1                        (ListRule)

(3)    ( Value2 ListTail2                 (TailFull)

(4)    ( 123 ListTail2                    (Intrule)

(5)    ( 123 Value3 ListTail3             (TailFull)

(6)    ( 123 ( setq x Value4 ) ListTail3  (SetqRule)

(7)    ( 123 ( setq x "this" ) ListTail3  (StrRule)

(8)    ( 123 ( setq x "this" ) )          (TailEmpty)

Compiling the Grammar Syntax, and Storing the Compilation

      GRAMMAROBJECT.Compile()

If the compilation succeeds you may use

      GRAMMAROBJECT.MarshalDump( OUTPUTFILE )

Nevertheless, compilation of the grammar by itself does not yeild a grammar that will do any useful parsing [Actually, it will do ``parsing'' using default actions (implemented as a function which simply return the list argument).] Rules must be associated with computational actions before useful parsing can be done.

Defining a Semantics

Two sorts of objects require semantic actions that define their meaning: rules and terminals. All semantic actions must be defined as Python functions and bound in the grammar before parsing can be performed.

Before you can define the semantics of your language in Python you better have a pretty good idea of what the components of the language are supposed to represent, of course. Using your intuitive understanding of the language you can:

Having determined the intuitive semantics of the language you may now specify implement the semantic functions and bind them in your grammar.

Semantics for Terminals

To define the meaning of a terminal you must create a Python function that translates a string (which the parser has recognized as an instance of the terminal) into an appropriate value. For instance, when the LispG grammar recognizes a string

      "this is a string"

        # from DLispShort.py

        def stripQuotes( str ):

            return str[1:len(str)-1]

The binding of interpretation functions to terminal names is performed by the Addterm method previously mentioned. For example, line 2 of Figure TermDef associates the stripQuotes function to the nonterminal named str.

All functions passed to Addterm should take a single string argument which represents the recognized string, and return a value which represents the semantic interpretation for the input string.

Semantics for Rules

The semantics of rules is more interesting since they may have side effects and require the kind of recursive thinking that gives most people headaches. The semantics for rules are specified by functions. To perform the semantic action associated with a rule, the ``reduction function'' should perform any side effects (to the computational context or externally) and return a result value that represents the interpretation for the nonterminal at the head of the rule.

      # from DLispShort.py

      def EchoValue( list, Context ):

          return list[0]

      

      def VarValue( list, Context ):

          varName = list[0]

          if Context.has_key(varName):

             return Context[varName]

          else:

             raise NameError, "no such lisp variable in context "+varName

      

      def NilTail( list, Context ):

          return []

      

      def AddToList( list, Context ):

          return [ list[0] ] + list[1]

      

      def MakeList( list, Context ):

          return list[1]

      

      def DoSetq( list, Context):

          Context[ list[2] ] = list[3]

          return list[3]

      

      def DoPrint( list, Context ):

          print list[2]

          return list[2]

        # from DLispShort.py

        def BindRules(LispG):

            LispG.Bind( "Intrule", EchoValue )

            LispG.Bind( "Strrule", EchoValue )

            LispG.Bind( "Varrule", VarValue )

            LispG.Bind( "TailEmpty", NilTail )

            LispG.Bind( "TailFull", AddToList )

            LispG.Bind( "ListRule", MakeList )

            LispG.Bind( "SetqRule", DoSetq )

            LispG.Bind( "PrintRule", DoPrint )

Each ``reduction function'' for a rule must take two arguments: a list representing the body of the rule and a context structure which represents the computational context of the computation. The list argument will have the same length as the body of the rule, counting the keywords and punctuations as well as the terminals and nonterminals.

For example the SetqRule has a body with five tokens,

      @R SetqRule :: Value >> ( setq var Value )

      list = [ '(', 'SETQ', VARIABLE_NAME, VALUE_RESULT, ')' ]

More generally, the parser will call reduction functions for rules with a list representing the ``interpreted body of the rule'' where

To determine how to implement the semantics of a rule you must refer to the semantic decisions you made earlier. For example, above we specified that the setq construct should bind the variable name recieved ( list[2]) to the value ( list[3]) in the Context, and return the value ( list[3]) as the result of the expression. Translated into the more concise language of Python this is exactly what DoSetq shown in Figure RedFun does.

To bind a rule name to a (previously declared) reduction function use

      GRAMMAROBJECT.Bind( RULENAME, FUNCTION )

A Bit on the Parsing Process

The following is not a precise definition of the actions of a Parser, but it may help you understand how the parsing process works and the order in which rules are recognized and functions are evaluated.

Figure Parse illustrates the sequence of reduction actions performed by LispG when parsing the input string (123 (setq x "this")). We can think of this parse as ``reversing'' the derivation process shown in Figure Derive using the rule reduction functions to obtain semantic interpretations for the nonterminals.

At the lowest level of parsing a lexical analyser examines the unread portion of the input string tries to match a prefix of the input string with a keyword or a regular expression for a terminal (ignoring comments and whitespace, except as separators). The analyser ``passes'' the recognized token to the higher level parser together with its interpreted value. The interpreted value of a terminal is determined by using the appropriate interpretation function and the interpreted value of a keyword is simply its name (in upper case, if the grammer is not case sensitive). For example the LispG lexical analyser recognizes '(' as a keyword with the value '(' and "this" as an instance of the nonterminal str with the value 'this'.

The higher level parser accepts tokens T from the lexical analyser and does one of two things with them

Figure Parse shows ``reduction'' steps and not the ``shifts'', and glosses over the lexical analysis and other nuances, but it illustrates the idea of the parsing process nonetheless. For example at step 2 the parse recognizes the last token on the stack S (an instance of the "str" terminal with value "this") as matching the body of StrRule, and replaces it with the an instance of the nonterminal Value with value determined by the reduction of StrRule. In this case StrRule is associated with the reduction function EchoValue, so the result of the reduction is given by EchoValue( 'this', C ) where C is the context structure for the Parse.

At Step 3 the most recent entries of S

      V = ['(', 'SETQ', 'x', Value4, ')']

      Value3 = DoSet( V, C )

Parsing with a Grammar

Before you can perform a parse you probably must create a computational context for the parse. In the case of LispG the context is simply a dictionary so we may initialize

      Context = {}

There are two methods which provide the primary interfaces for the parsing process for a grammar.

      RESULT = GRAMMAROBJECT.Parse1(STRING, CONTEXT)

      (RESULT, CONTEXT) = GRAMMAROBJECT.Parse(STRING, CONTEXT)

Storing and Reloading a Grammar Object

The process of compiling a grammar may take significant time and consume significant quantities of memory. To free up memory from structures in a compilable grammar object that aren't needed after compilation use GRAMMAR.CleanUp().

Once you have debugged the syntax and semantics of your grammar you may store syntactic information for the grammar using the Reconstruct method already mentioned. The declarations created by Reconstruct only defines the syntax for the grammar. The semantics must be rebound separately. But it is much better to use UnMarshalGram as shown below, which stores the grammar in a binary format.

For example, lines 12 through 14 of Figure GrammarBuild create a file TESTLispG.py containing a function GRAMMAR() which will reconstruct the syntax for the LispG grammar.

        # from DLispShort.py



def unMarshalLispG():

    import kjParser

    infile = open("TESTLispG.mar", "r")

    LispG = kjParser.UnMarshalGram(infile)

    infile.close()

    DeclareTerminals(LispG)

    BindRules(LispG)

    return LispG

        import DLispShort

        LGrammar = DLispShort.unMarshalLispG()

Figure Load shows a function LoadLispG that reloads the syntactic portion of LispG from TESTLispG.mar. To rebind the semantics as well the function re-declares the terminals and re-binds the rules to make the reconstructed LispG suitable for use in parsing.

Errors raised

You may see the following errors:

Possible Gotchas

This package has a number of known deficiencies, and there are probably many that are yet to be discovered.

Syntax errors are not reported nicely. Sorry.

Currently, there is no way to to resolve grammar ambiguities. For example a C construct

if (x)

   if (y)

      x = 0;

   else

      y = 1;

Keywords of the meta-grammar cannot name tokens of the object grammar (see footnote above).

If you want keywords to be recognized without case sensitivity you must declare G.SetCaseSensitivity(0) before any keyword declarations.

Name and regular expression collisions are not always checked and reported. If you name two rules the same, for example, you may get undefined behavior.

The lexical analysis implementation is not as fast as it could be (of course). It also sees all white space as a `single space' so, for example, if indentation is significant in your grammar (as in Python) you'll need a different lexical analyzer. Also if x=+y means something different from x = + y (as it did in the original C, I believe) you may have trouble. Happily the lexical component can be easily ``plug replaced'' by another implementation if needed.

Also, the system currently only handles SLR grammars (as defined by Aho and Ullman), as mentioned above. If you get a NonSLRError during grammar compilation you need a better parser generator. I may provide one, if I have motivation and time.

I know of no outright bugs. Trust me, they're there. Please find them for me and tell me about them. I'm not a big expert on parsing so I'm sure I've made some errors, particularly at the lexical level.

Further Reading

A standard reference for parsing and compiler, interpreter, and translator implementation is Principles of Compiler Design, by Aho and Ullman (Addison Wesley).

feedback
home
Gadfly home