Grammars in Camlp4

Chapter 2

Grammars in Camlp4

A grammar in Camlp4 is a value of type Grammar.g. It is created by the function Grammar.make which takes a lexer as parameter (see also the functorial interface, another way to create a grammar). Let's ignore for the moment how to create lexers and let's just take a lexer provided in Camlp4, which is the default OCaml lexer. It is in the module Plexer and you can create an instantiation by using Plexer.make ().

2.1

Grammar, entries: an example

You can create your grammar like this:

     # let gram = Grammar.create (Plexer.make ());;

A grammar is composed of entries. Entries are values of type 'a Grammar.Entry.e. The 'a type parameter represents the type of values which the entry returns. To create an entry, use Grammar.Entry.create, which has two parameters: 1/ the associated grammar 2/ a string, the entry name, used for error messages.

An entry is a mutable value. When you create it, it is empty, its type is '_a Grammar.Entry.e (not generalized, you cannot create entries returning polymorphic values), the type parameter being set when the entry is extended, showing then the type of its results. Let's take an entry expr:

     # let expr = Grammar.Entry.create gram "expr";;

Entries apply to char streams via the function Grammar.Entry.parse. If you apply an empty entry (an entry just created, for example), the exception Stream.Failure is raised.

To define rules to an entry, you must use the statement EXTEND. Note that EXTEND is not a syntactic construction in OCaml: it is a syntax extension provided by Camlp4. The syntax of EXTEND is:

     extend-statement ::=
        EXTEND
           list-of-entries-extensions
        END

Notice that EXTEND is an expression (i.e. not a declaration): it can be evaluated at toplevel, but also inside a function: in this case, the syntax extension takes place when the function is called.

An entry extension has the syntax:

     entry-extension ::=
        identifier : [ list-of-levels-separated-by-bars ] ;

The identifier is an entry name. An entry can have one or several levels, representing precedences and associativity.

A level has the syntax:

     level ::=
        [ list-of-rules-separated-by-bars ]

     rule ::=
        list-of-symbols-separated-by-semicolons -> action

A rule is like a pattern matching case: it can introduce patterns variables which can be used in the action part. When the rule is accepted, the action is executed. The type of the action is 'a for an 'a entry ('a Grammar.Entry.e, more precisely).

Let's define our ex