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