File: tutorial003.html

package info (click to toggle)
ocaml-doc 3.09-1
links: PTS
area: non-free
in suites: etch, etch-m68k
size: 10,428 kB
ctags: 4,963
sloc: ml: 9,244; makefile: 2,413; ansic: 122; sh: 49; asm: 17
file content (827 lines) | stat: -rw-r--r-- 31,667 bytes
parent folder | download | duplicates (2)
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>

<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.06">
<TITLE>
 Grammars in Camlp4
</TITLE>
</HEAD>
<BODY TEXT=black BGCOLOR=white>
<A HREF="tutorial002.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial004.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>
<TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#2de52d"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc11"><B><FONT SIZE=6>Chapter&nbsp;3</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=6>Grammars in Camlp4</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<A NAME="c:tutgram"></A>
A grammar in Camlp4 is a value of type <CODE>Grammar.g</CODE>. It is created
by the function <CODE>Grammar.make</CODE> 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 <CODE>Plexer</CODE> and you can create an
instantiation by using <CODE>Plexer.gmake ()</CODE>.<BR>
<BR>


<A NAME="toc7"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc12"><B><FONT SIZE=5>3.1</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Grammar, entries: an example</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
You can create your grammar like this:
<PRE>
     # let gram = Grammar.gcreate (Plexer.gmake ());;
</PRE>
A grammar is composed of <CODE>entries</CODE>. Entries are values of type
<CODE>'a Grammar.Entry.e</CODE>. The <CODE>'a</CODE> type parameter represents the type
of values which the entry returns. To create an entry, use
<CODE>Grammar.Entry.create</CODE>, which has two parameters: 1/ the
associated grammar 2/ a string, the entry name, used for error
messages.<BR>
<BR>


An entry is a mutable value. When you create it, it is empty, its type
is <CODE>'_a Grammar.Entry.e</CODE> (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 <CODE>expr</CODE>:
<PRE>
     # let expr = Grammar.Entry.create gram "expr";;
</PRE>
Entries apply to char streams via the function
<CODE>Grammar.Entry.parse</CODE>. If you apply an empty entry (an entry just
created, for example), the exception <CODE>Stream.Failure</CODE> is raised.<BR>
<BR>


To define rules to an entry, you must use the statement
<CODE>EXTEND</CODE>. Note that <CODE>EXTEND</CODE> is not a syntactic construction
in OCaml: it is a syntax extension provided by Camlp4. The syntax of
<CODE>EXTEND</CODE> is:
<PRE>
     extend-statement ::=
        EXTEND
           list-of-entries-extensions
        END
</PRE>


Notice that <CODE>EXTEND</CODE> 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.<BR>
<BR>


An entry extension has the syntax:
<PRE>
     entry-extension ::=
        identifier : [ list-of-levels-separated-by-bars ] ;
</PRE>
The <EM>identifier</EM> is an entry name. An entry can have one or
several levels, representing precedences and associativity.<BR>
<BR>


A level has the syntax:
<PRE>
     level ::=
        [ list-of-rules-separated-by-bars ]

     rule ::=
        list-of-symbols-separated-by-semicolons -&gt; action
</PRE>
A <EM>rule</EM> is like a pattern matching case: it can introduce
patterns variables which can be used in the <EM>action</EM> part. When
the rule is accepted, the action is executed. The type of the <EM>action</EM> is <CODE>'a</CODE> for an <CODE>'a entry</CODE>
(<CODE>'a Grammar.Entry.e</CODE>, more precisely).<BR>
<BR>


Let's define our <CODE>expr</CODE> to parse a simple computation of
arithmetic expression with addition, subtraction, multiplication and
division, integer constants and parentheses. This can be written:
<PRE>
       EXTEND
         expr:
           [ [ x = expr; "+"; y = expr -&gt; x + y
             | x = expr; "-"; y = expr -&gt; x - y ]
           | [ x = expr; "*"; y = expr -&gt; x * y
             | x = expr; "/"; y = expr -&gt; x / y ]
           | [ x = INT -&gt; int_of_string x
             | "("; e = expr; ")" -&gt; e ] ]
         ;
       END;;
</PRE>


The <CODE>expr</CODE> entry has now three levels. Grammar entries are
extensible at any time: you can extend <CODE>expr</CODE> again to add more
constructions. You can add more rules in already existing levels and
you can insert new levels. We see that further.<BR>
<BR>


Each level has its own associativity. You can specify left, right or
non-associative. By default, the associativity is left. See further.<BR>
<BR>


If you are in the OCaml toplevel and have tested this example, you can
see now that <CODE>expr</CODE> is of type <CODE>int</CODE> entry, since it
returns values of type <CODE>int</CODE>.<BR>
<BR>


You can try it out:
<PRE>
     # Grammar.Entry.parse expr (Stream.of_string "2 + 3");;
     - : int = 5
</PRE>
<PRE>
     # Grammar.Entry.parse expr (Stream.of_string "8 * (5 - 2)");;
     - : int = 24
</PRE>
And so on.<BR>
<BR>


What happens in case of syntax error? In the general case, the
exception <CODE>Stream.Error</CODE> is raised, enclosed in another exception
named <CODE>Exc_located</CODE> which indicates the location of the error in
the stream. Here, the right parenthesis is missing:
<PRE>
     # Grammar.Entry.parse expr (Stream.of_string "9 / (7 + 1 ");;
     Uncaught exception:
     Stdpp.Exc_located
      ((11, 12), Stream.Error "')' expected after [expr] (in [expr])").
</PRE>
If there are unexpected symbols after a correct expression, it is not
a parsing error, the parsing of the stream just stops and the trailing
symbols are ignored:
<PRE>
     # Grammar.Entry.parse expr (Stream.of_string "8 * (5 - 2) 7 foo");;
     - : int = 24
</PRE>
To ensure that there are no trailing tokens in the input stream, 
we can create another entry <CODE>expr_eoi</CODE> expecting an <CODE>expr</CODE>
followed by the end of the input <CODE>EOI</CODE>:
<PRE>
     # let expr_eoi = Grammar.Entry.create gram "expr_eoi";;
     # EXTEND expr_eoi: [ [ e = expr; EOI -&gt; e ] ]; END;;
</PRE>
Now:
<PRE>
     # Grammar.Entry.parse expr_eoi (Stream.of_string "8 * (5 - 2) 7 foo");;
     Uncaught exception:
     Stdpp.Exc_located
      ((12, 13),
       Stream.Error "end of input expected after [expr] (in [expr_eoi])").
</PRE>
<A NAME="toc8"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc13"><B><FONT SIZE=5>3.2</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Remark about the lexer</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
Notice that <CODE>"+"</CODE>, <CODE>"-"</CODE>, <CODE>"*"</CODE>, "/", <CODE>EOI</CODE> are
terminals in this grammar, but they are not specifically predefined in
Camlp4 grammar system: it depends on how the associated lexer
works. Remember: we used <CODE>Plexer.gmake ()</CODE> as associated lexer in
the present grammar. In another grammar, with another lexer, these
terminals might have no meaning.<BR>
<BR>


Before doing the extensions, the statement <CODE>EXTEND</CODE> first scan
all rules and, for each terminal, asks the lexer whether this terminal
is correct or not. It uses for that a function named <CODE>using</CODE>
defined in the lexer record type (see interface of module Token). This
function can be used also to update a list (or hashtable) of keywords
(in the case when there is a notion of keywords, what is not mandatory).<BR>
<BR>


Ok. But it is lexer stuff... We don't need to know about it for the
moment. However, it is interesting to know that in the predefined
lexer <CODE>Plexer.gmake ()</CODE>, this function <CODE>using</CODE> prints an
error message and raises an exception if a bad terminal is used in a
<CODE>EXTEND</CODE> statement:
<PRE>
        # EXTEND expr_eoi: [ [ AAA -&gt; 3 ] ]; END;;
        Lexer initialization error.
        The constructor "AAA" is not recognized by Plexer
        Uncaught exception: Failure "Grammar.extend".
</PRE>
<PRE>
        # EXTEND expr: [ [ x = expr; "a+b" -&gt; x + 1 ] ]; END;;
        Lexer initialization error.
        The token "a+b" does not respect Plexer rules
        Uncaught exception: Failure "Grammar.extend".
</PRE>
All this details are described in a chapter about lexers, in the
reference manual. See also the predefined modules Token and Plexer.<BR>
<BR>
<A NAME="toc9"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc14"><B><FONT SIZE=5>3.3</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Labelled levels and associativity</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
Now, we are going to extend <CODE>expr</CODE>. But as we defined it, it is
not possible to point the entries. To point them, we need labels.<BR>
<BR>


The syntax of a <EM>level</EM> is actually:
<PRE>
     level ::=
        optional-label optional-associativity
        [ list-of-rules-separated-by-bars ]
</PRE>
A label is a string. Any string you choose. The associativity is
either <CODE>LEFTA</CODE>, <CODE>RIGHTA</CODE> or <CODE>NONA</CODE>.<BR>
<BR>


Let's write <CODE>expr</CODE> again (we take a fresh entry, in order to start
with an empty entry) with labels and explicit associativity:
<PRE>
     # let expr = Grammar.Entry.create gram "expr";;
     # EXTEND
         expr:
           [ "add" LEFTA
             [ x = expr; "+"; y = expr -&gt; x + y
             | x = expr; "-"; y = expr -&gt; x - y ]
           | "mult" RIGHTA
             [ x = expr; "*"; y = expr -&gt; x * y
             | x = expr; "/"; y = expr -&gt; x / y ]
           | "simple" NONA
             [ x = INT -&gt; int_of_string x
             | "("; e = expr; ")" -&gt; e ] ]
         ;
       END;;
</PRE>
By the way, an useful function, especially in the toplevel, is
<CODE>Grammar.Entry.print</CODE>, which displays the contents of an entry (just the
rules, in fact):
<PRE>
     # Grammar.Entry.print expr;;
     [ "add" LEFTA
       [ SELF; "+"; SELF
       | SELF; "-"; SELF ]
     | "mult" RIGHTA
       [ SELF; "*"; SELF
       | SELF; "/"; SELF ]
     | "simple" NONA
       [ "("; SELF; ")"
       | INT ] ]
</PRE>
Notice that all <CODE>expr</CODE> have been replaced by <CODE>SELF</CODE>: this is
the same thing: when an entry calls itself, you can use either its
name or the keyword <CODE>SELF</CODE>. It represents either the current
level, the next level or the first level, depending on the associativity
and the position of the <CODE>SELF</CODE> in the rule (current or next level
if the <CODE>SELF</CODE> starts or ends the rule, first level otherwise).<BR>
<BR>


When you extend an entry, by default the first level of the extension
extends the first level of the entry:
<PRE>
     # EXTEND expr: [ [ x = expr; "plus1plus"; y = expr -&gt; x + 1 + y ] ]; END;;
</PRE>
This extended the first level, i.e. the one labelled <CODE>"add"</CODE>. Type
<CODE>Grammar.Entry.print expr</CODE> to see the result.<BR>
<BR>


You can extend any existing level and insert new levels. Actually, the
syntax of an entry extension is:
<PRE>
     entry-extension ::=
        optional-position
        identifier : [ list-of-levels-separated-by-bars ] ;

     position ::=
        FIRST | LAST | BEFORE label | AFTER label | LEVEL label
</PRE>
<A NAME="toc10"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc15"><B><FONT SIZE=5>3.4</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Extending a level</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
To extend some specified level, we can use <CODE>LEVEL</CODE> followed by
the label of the level to be extended:
<PRE>
     # let env = ref [];;
     # EXTEND
         expr: LEVEL "simple" [ [ x = LIDENT -&gt; List.assoc x !env ] ];
       END;;
</PRE>
You <CODE>Grammar.Entry.print expr</CODE> again to see the result.<BR>
<BR>


The symbol <CODE>LIDENT</CODE> is a constructor defined by our lexer Plexer.
It represents an identifier starting by a lowercase character. For
details, see the interface of the module Plexer (plexer.mli, given
also in the reference manual, chapter libraries).<BR>
<BR>


Just small tests:
<PRE>
     # Grammar.Entry.parse expr (Stream.of_string "foo + 1");;
     Uncaught exception: Stdpp.Exc_located ((3, 4), Not_found)
</PRE>
<PRE>
     # env := ("foo", 27) :: !env;;
     # Grammar.Entry.parse expr (Stream.of_string "foo + 1");;
     - : int = 28
</PRE>
<A NAME="toc11"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc16"><B><FONT SIZE=5>3.5</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Insert a level</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
To insert a level, you can use BEFORE or AFTER, relatively to an
existing level:
<PRE>
     # EXTEND
         expr: AFTER "mult"
           [ "power" RIGHTA
             [ x = expr; "**"; y = expr -&gt; int_of_float (float x ** float y) ] ]
         ;
       END;;
</PRE>
There is no limit to the number of levels: it is just a list. It is
also possible to use FIRST or LAST: they create levels in the
beginning or at the end.<BR>
<BR>
<A NAME="toc12"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc17"><B><FONT SIZE=5>3.6</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Infix operator</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
Inside an EXTEND statement you can use antiquotations in places where
strings are expected. The antiquotation is some expression between two
``dollar'' signs. A typical example is a function adding an infix
operator ``op'' at the level ``lev'':
<PRE>
     # let add_infix lev op =
         EXTEND
           expr: LEVEL $lev$
             [ [ x = expr; $op$; y = expr -&gt; &lt;:expr&lt; $lid:op$ $x$ $y$ &gt;&gt; ] ]
           ;
         END;;
</PRE>
This function can be called when you want to add your infix. The infix
becomes automatically a keyword (actually, it depends on the lexer
behaviour). It can be used also to define an infix macro in the OCaml
grammar (chapter&nbsp;<A HREF="tutorial007.html#c:tutext">7</A>).<BR>
<BR>
<A NAME="toc13"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc18"><B><FONT SIZE=5>3.7</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Attributed grammars</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
It is not possible to create attributed grammars, i.e. grammars with
parameters (in our terminology, entries with parameters). But entries
can return functions. Let us take another version where the entry
<CODE>expr</CODE> returns a function which takes an environment <CODE>env</CODE>:
<PRE>
     # let expr = Grammar.Entry.create gram "expr";;
     # EXTEND
         expr:
           [ "add" LEFTA
             [ x = expr; "+"; y = expr -&gt; fun env -&gt; x env + y env
             | x = expr; "-"; y = expr -&gt; fun env -&gt; x env - y env ]
           | "mult" RIGHTA
             [ x = expr; "*"; y = expr -&gt; fun env -&gt; x env * y env
             | x = expr; "/"; y = expr -&gt; fun env -&gt; x env / y env ]
           | "simple" NONA
             [ x = INT -&gt; fun env -&gt; int_of_string x
             | x = LIDENT -&gt; fun env -&gt; List.assoc x env
             | "("; e = expr; ")" -&gt; e ] ]
         ;
       END;;
</PRE><BR>
<DIV ALIGN=left>
To call the entry, we need now to add the environment (a list) as parameter:
</DIV>
<PRE>
     # Grammar.Entry.parse expr (Stream.of_string "foo + 1") [];;
     Uncaught exception: Not_found.
</PRE><BR>
<DIV ALIGN=left>
(since foo is not in the environment)
</DIV>
<PRE>
     # Grammar.Entry.parse expr (Stream.of_string "foo + 1") [("foo", 48)];;
     - : int = 49
</PRE><BR>
<DIV ALIGN=left>
We can improve the error message to display the unbound variable name:
</DIV>
<PRE>
     # EXTEND
         expr: LEVEL "simple"
           [ [ x = LIDENT -&gt;
                 fun env -&gt;
                   try List.assoc x env with
                     Not_found -&gt; failwith ("unbound variable " ^ x) ] ]
         ;
       END;;
</PRE>
Notice that there is already a rule <CODE>LIDENT</CODE> in the level
"simple" of <CODE>expr</CODE>. In this case, the <CODE>EXTEND</CODE> statement
replaces the old version by the new one and displays a warning. To
mask this message, one can set the variable
<CODE>Grammar.warning_verbose</CODE> to <CODE>false</CODE>.<BR>
<BR>


Now, it is more informative:
<PRE>
     # Grammar.Entry.parse expr (Stream.of_string "foo + 1") [];;
     Uncaught exception: Failure "unbound variable foo".
</PRE>
<A NAME="toc14"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc19"><B><FONT SIZE=5>3.8</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Source location</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
We can improve our above error system again, by telling the location
of the error. In our examples, we tested short texts, it is easy to
see the error, but if your grammar becomes very big and treats very
big input files, it is very important to know with precision where the
error happened in the source.<BR>
<BR>


An useful function for that is <CODE>Stdpp.raise_with_loc</CODE> taking an
input location and an exception as parameters. It raises the exception
<CODE>Stdpp.Exc_located</CODE> already seen some sections above.<BR>
<BR>


We could directly raise this exception <CODE>Exc_located</CODE> but
<CODE>raise_with_loc</CODE> has the advantage to just re-raise the exception
parameter when it is already <CODE>Exc_located</CODE>, which is useful to
propagate exceptions without stacking
<CODE>Exc_located</CODE>.<BR>
<BR>


The input location of a rule is in the variable <CODE>loc</CODE> always
available in the action part:
<PRE>
     # EXTEND
         expr: LEVEL "simple"
           [ [ x = LIDENT -&gt;
                 fun env -&gt;
                   try List.assoc x env with
                     Not_found -&gt;
                       Stdpp.raise_with_loc loc
                         (Failure ("unbound variable " ^ x)) ] ]
         ;
       END;;
</PRE>
<PRE>
     # Grammar.Entry.parse expr (Stream.of_string "3 + foo + 1") [];;
     Uncaught exception:
     Stdpp.Exc_located ((4, 7), Failure "unbound variable foo").
</PRE>
We are going to extend now our entry <CODE>expr</CODE> with a "let" construction,
which can extend the environment.<BR>
<BR>


This is an occasion to introduce the notion of meta symbols in entry rules.<BR>
<BR>
<A NAME="toc15"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc20"><B><FONT SIZE=5>3.9</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Meta symbols: lists, options, levels</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
It is possible to use some meta symbols in rules:
<UL><LI>
list of symbols, possibly empty:<BR>
<CODE>      LIST0 &lt;symbol&gt;</CODE>
<LI>list of symbols with a separator, possibly empty:<BR>
<CODE>      LIST0 &lt;symbol&gt; SEP &lt;symbol&gt;</CODE>
<LI>list of symbols with at least one element:<BR>
<CODE>      LIST1 &lt;symbol&gt;</CODE>
<LI>list of symbols with a separator and at least one element:<BR>
<CODE>      LIST1 &lt;symbol&gt; SEP &lt;symbol&gt;</CODE>
<LI>optional symbol:<BR>
<CODE>      OPT &lt;symbol&gt;</CODE>
<LI>levels:<BR>
<CODE>      [ &lt;rule-list&gt; ]</CODE>
</UL>
Now, we can write a let statement, which calls an non empty list of
bindings separated by the keyword <CODE>"and"</CODE>:
<PRE>
     # let binding = Grammar.Entry.create gram "let_binding";;
     # EXTEND
         expr: FIRST
           [ [ "let"; r = LIST1 binding SEP "and"; "in"; e = expr -&gt;
                 fun env -&gt;
                   let new_env =
                     List.fold_right (fun b new_env -&gt; b env :: new_env)
                       r env
                   in
                   e new_env ] ]
          ;
          binding:
            [ [ p = LIDENT; "="; e = expr -&gt; fun env -&gt; (p, e env) ] ]
          ;
       END;;
</PRE><BR>
<DIV ALIGN=left>
Let us define an useful function to test our entries:
</DIV>
<PRE>
     # let apply e s = Grammar.Entry.parse e (Stream.of_string s) [];;
</PRE><BR>
<DIV ALIGN=left>
Here are some examples:
</DIV>
<PRE>
     # apply expr "let a = 25 and b = 12 in a + b";;
     - : int = 37

     # apply expr "let a = 25 and b = a + 5 in a + b";;
     Uncaught exception:
     Stdpp.Exc_located ((19, 20), Failure "unbound variable a").

     # apply expr "let a = 25 in let b = a + 5 in a + b";;
     - : int = 55
</PRE>
<A NAME="toc16"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc21"><B><FONT SIZE=5>3.10</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Local and global entries</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
We have now three entries: <CODE>expr_eoi</CODE>, <CODE>expr</CODE> and <CODE>binding</CODE>.<BR>
<BR>


In big grammars, we often have to create a lot of small entries,
forcing us to define them with <CODE>Grammar.Entry.create</CODE>. It is not
practical for several reasons: 1/ it is tedious 2/ we generally don't
need to access all of them directly 3/ the ones which are not
eventually extended (which may happen when you perfect your grammar)
remain of type <CODE>_'a</CODE> entry which cause <CODE>ocamlc</CODE> to fail at
end of the module.<BR>
<BR>


To avoid that, it is possible to ask <CODE>EXTEND</CODE> to automatically
define all these small entries. It actually works the wrong way round:
you have to define the list of the entries which are globally defined.
The other ones (the ones which are ``extended'' in the statement) are
locally defined. Actually, the definition of <CODE>EXTEND</CODE> is:
<PRE>
     extend-statement ::=
        EXTEND
           optional-global
           list-of-entries-extensions
        END

     global ::=
        GLOBAL : list-of-entries ;
</PRE>
Warning: this statement is a little bit complicated to read:
<CODE>GLOBAL</CODE> introduces the list of entries which have been <EM>defined</EM>
previously. It means that all other entries in the <CODE>EXTEND</CODE>
statement are automatically locally defined. Therefore, by default, if
there is no <CODE>GLOBAL</CODE>, it must be read: ``all entries are global''.<BR>
<BR>


In our example, if we want that only <CODE>expr_eoi</CODE> be defined and be
visible, we can add the <CODE>GLOBAL</CODE> entry with only <CODE>expr_eoi</CODE>:
in this case, <CODE>expr</CODE> and <CODE>binding</CODE> are locally defined and
therefore not extensible.<BR>
<BR>


To be sure that we don't use the previously defined <CODE>expr</CODE> and
<CODE>binding</CODE> by quitting the toplevel and entering it again.
Don't forget the:
<PRE>
     #load "camlp4o.cma";;
     #load "pa_extend.cmo";;
</PRE><BR>
<DIV ALIGN=left>
And now:
</DIV>
<PRE>
     # let gram = Grammar.gcreate (Plexer.gmake ());;
     # let expr_eoi = Grammar.Entry.create gram "expr_eoi";;
     # EXTEND
         GLOBAL: expr_eoi;
         expr_eoi:
           [ [ e = expr; EOI -&gt; e ] ]
         ;
         expr:
           [ [ "let"; r = LIST1 binding SEP "and"; "in"; e = expr -&gt;
                 fun env -&gt;
                   let new_env =
                     List.fold_right (fun b new_env -&gt; b env :: new_env)
                       r env
                   in
                   e new_env ]
           | "add" LEFTA
             [ x = expr; "+"; y = expr -&gt; fun env -&gt; x env + y env
             | x = expr; "-"; y = expr -&gt; fun env -&gt; x env - y env ]
           | "mult" RIGHTA
             [ x = expr; "*"; y = expr -&gt; fun env -&gt; x env * y env
             | x = expr; "/"; y = expr -&gt; fun env -&gt; x env / y env ]
           | "simple" NONA
             [ x = INT -&gt; fun env -&gt; int_of_string x
             | x = LIDENT -&gt;
                 (fun env -&gt; try List.assoc x env with
                    Not_found -&gt;
                      Stdpp.raise_with_loc loc
                        (Failure ("unbound variable " ^ x)))
             | "("; e = expr; ")" -&gt; e ] ]
         ;
         binding:
           [ [ p = LIDENT; "="; e = expr -&gt; fun env -&gt; (p, e env) ] ]
         ;
       END;;
</PRE>
<PRE>
     # let apply e s = Grammar.Entry.parse e (Stream.of_string s) [];;

     # apply expr_eoi "let a = 25 and b = 12 in a + b";;
     - : int = 37

     # apply expr_eoi "let a = 25 and b = 12 in a + b foo bar";;
     Uncaught exception:
     Stdpp.Exc_located
       ((31, 34),
          Stream.Error "end of input expected after [expr] (in [expr_eoi])")
</PRE>
<A NAME="toc17"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc22"><B><FONT SIZE=5>3.11</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Deleting a rule</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
To delete a rule, use the statement <CODE>DELETE_RULE</CODE>. Its syntax is:
<PRE>
     delete-rule ::=
        DELETE_RULE entry : list-of-symbols-separated-by-semicolons END
</PRE>
It deletes the first rule found in the levels of <CODE>entry</CODE> matching
the list of symbols.<BR>
<BR>


For example, in the above example, you can delete the ``addition''
rule of the entry <CODE>expr</CODE>, by typing:
<PRE>
     # DELETE_RULE expr: SELF; "+"; SELF END;;
</PRE>
<A NAME="toc18"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc23"><B><FONT SIZE=5>3.12</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Parsed language</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
The grammar entries levels are just improved streams parsers. Streams
parsers use recursive descendant parsing (something close to LL(1) but
actually a little less powerful). The improvements are:
<UL><LI>left factorization: you can e.g. then write a rule
``if..then'' and a rule ``if..then..else'' starting with the same
symbols, it works.<BR>
<BR>
<LI>automatic treatment of associativity and level precedence, as we
just saw.</UL>
There is no left factorization between different entries, or in
different levels in the same entry.<BR>
<BR>


This is often a problem. This example does not work:<BR>
<BR>


<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD ALIGN=left NOWRAP>       <EM>x</EM> ::= <EM>y</EM> <CODE>|</CODE> <EM>z</EM></TD>
</TR>
<TR><TD ALIGN=left NOWRAP>       <EM>y</EM> ::= <CODE>A</CODE> <CODE>B</CODE> <CODE>|</CODE> <CODE>...</CODE></TD>
</TR>
<TR><TD ALIGN=left NOWRAP>       <EM>z</EM> ::= <CODE>A</CODE> <CODE>C</CODE> <CODE>|</CODE> <CODE>...</CODE></TD>
</TR></TABLE><BR>


The input <CODE>"A C"</CODE> raises <CODE>Stream.Error</CODE>. There is no simple
solution to this problem, but there is a solution (not very clean,
actually): create a entry from a parser (it is possible via the
function <CODE>Grammar.Entry.of_parser</CODE>). This parser must scan the
stream using <CODE>Stream.npeek</CODE> until the number of necessary tokens
allows to make the difference; return unit or raise
<CODE>Stream.Failure</CODE> according to the cases.<BR>
<BR>
<A NAME="toc19"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc24"><B><FONT SIZE=5>3.13</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Functorial interface</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
There is another way to create a grammar: using the functional
interface. See the module <CODE>Grammar</CODE>. In this case, grammars are
no more values, but modules. The extension of a grammar is done by the
keyword <CODE>GEXTEND</CODE> followed by the grammar module name.<BR>
<BR>


The differences are the following:
<UL><LI>OCaml normal typing ensures that entries call only entries of the
same grammar, because each grammar module defines its own entry type.
In the non-functorial interface, this is checked at execution time.<BR>
<BR>
<LI>The input of the function <CODE>Entry.parse</CODE> is a value of type
<CODE>parsable</CODE>, instead of the direct character stream. You must
create a parsable value from a character stream by the function
<CODE>parsable</CODE>. This ensures that there is no lack of tokens when
calling <CODE>Entry.parse</CODE> several times. In the normal interface,
when calling <CODE>Grammar.Entry.parse</CODE> with a char stream, the
grammar system may ask the lexer for a token which may not be used
(depending on the entries rules), but lost when restarting from the
character stream.</UL>
Use the normal interface or the functorial interface is a question of
personal taste.<BR>
<BR>
<A NAME="toc20"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc25"><B><FONT SIZE=5>3.14</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Writing a lexer</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
If you want to write your own lexer, a simple solution is to take the
sources of the provided lexer (plexer.ml) and make your changes in it.<BR>
<BR>


Otherwise you can read the section ``writing a lexer'' in the
reference manual.<BR>
<BR>
<A NAME="toc21"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc26"><B><FONT SIZE=5>3.15</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Grammar for OCaml syntax</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
The command camlp4 uses to parse OCaml files: for that, it uses
extensible grammars described in the present chapter (a grammar with
extensible entries). The main entries of the grammar of OCaml are
accessible and therefore extensible: for expressions, for patterns,
for structures, signatures, and so on. All are defined in the provided
module <CODE>Pcaml</CODE>. See chapter <A HREF="tutorial007.html#c:tutext">7</A>, the reference manual,
chapter of library modules or look at the interface
<CODE>pcaml.mli</CODE>.<BR>
<BR>


But we are not yet ready to write syntax extensions for OCaml: we
first need to create syntax trees which are returned by these entries.<BR>
<BR>


The way to create OCaml syntax trees is explained in the following
chapters, the first one being about another feature of Camlp4: the
<CODE>quotations</CODE>.
<BR>
<BR>
<I><FONT COLOR=maroon>
<br>
For remarks about Camlp4, write to:
<img src="http://cristal.inria.fr/~ddr/images/email.jpg" alt=email align=top>
</FONT></I><HR>
<A HREF="tutorial002.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial004.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>