OCamlyacc minimal parser
In this tutorial, we will build from scratch a simple parser that can recognize words (identifier) and int numbers. The parser will be tested on simple data, and recognized tokens will be displayed with their types. This tutorial is mainly to set the project up and assuring that compilations dependancies are met.
How ?
We will
use ocamlyacc and ocamllex as parser generators.
Files
A parser
built with OCamllex and
OCamlyacc is
usually made of 4 files:
The
types files:
simple_types.ml
An
.ml
file
containing all the type definition.
the
Yacc file:
simple_parser.mly
An
.mly
file,
with yacc syntax, containing yacc directives,
grammar and actions rules for the langage.
the
Lex file:
simple_lexer.mll
An
.mll
file,
with lex syntax, containing regexp for the langages
tokens.
the
driver file:
test.ml
An
.ml
file,
containing the Ocaml function that will call the
parser and process the result.
In the
lex and yacc files, comments are enclosed by "/*
... */" (as in C), while in the two others,
standard ocaml comments "(* ..*)" applies.
Depedancies
The
parser file (mly) depends and open the types file
(ml).
The
lexer file (mll) depends and opens the parser file
(mly).
Types declaration
The
first step when building a parser is to describe
the model of the data we are trying to parse. For
this parser, we only have two types: identificators
and int, that are summed in an union type,
an
expression.
Recursively, an expression can be composed of two
expression connected by the "+" sign. We declare
this with the usual ocaml syntax:
type
expression
= ExpInt
of int
| ExpIdent
of string
| Exp_Plus
of expression
* expression;;
Parser declaration
Parser header
We will
follow Ocamlyacc file sections for the
sections making up a parser file. In the Header
section, we only need to open the types
declarations and declare our simple parse error
function:
%{
(*
Ocamlyacc header *)
open Simple_types;;
let
parse_error
s =
print_endline
"Parse
error";
print_endline
s;
flush
stdout;;
%}
The
parse_error function will be automatically called
when the parser encounter a token he can't insert
in the parse tree.
Parser declarations
We must
first declare our terminals symbols (aka tokens),
by preceding their names with an "T" (for Token):
/* token declarations */
/* token declarations */
%token Tint
%token Tident
%token TEOL
%token TPlus
The use
of an uppercase letter is mandatory, as the parser
generator will build constructors for these tokens.
As two of our four tokens can hold values, we must
declare their type with an Ocaml type expression.
We'll see in the grammar rules how to access to a
token value, aka semantic value.
We can then declare the type of our non-terminal
symbols, here we will use
program as our
nonterminal and start type:
%type
expression list>
program
/* start symbol */
%start program
Here,
the lowercase "p" is mandatory. The starting symbol
will be the type returned by our parsing function,
hence our parsing function will have the
signature string
-> expression list.
Grammar rules
A
grammar rules describes how to derive semantic
values from the components(nonterminal or
terminals) to the non-terminal symbol. That is,
when we devise the expression "5+5", the associated
semantic value can be "10". In a yacc rules, this
could be expressed as :
exp:
...
| exp
PLUS
exp
{
$1
+.
$3
}
Meaning
that an exp
is made
(amongst other things) of two expressions connected
by a PLUS
token.
When yacc recognizes such an expression, he
associates to exp
the
result of the ocaml expression inserted within the
brackets, here an int derived from an addition.
Notice how $1
and
$3
refers
to the semantic values of the first and third
symbol from the grammar rules.
In our case, a "program" can either be an
nexpression
or
an nexpresion
program,
meaning that it is a list of at leat one element of
type
expression.
/* Ocamlyacc grammar
and action
rules */
program :
/* build a list from one element */
nexpression EOL {[$1]}
/* build a list from one element
and a list */
| nexpression program {($1)::$2}
;
nexpression:
value {$1}
| nexpression TPlus nexpression {Exp_Plus($1,$3)}
;
value:
Tint {ExpInt
$1}
| Tident {ExpIdent
$1}
;
}
The
ending colon is mandatory for each grammar rules.
The resulting yacc file will then be:
%{
%{
(*
Ocamlyacc header *)
open Simple_types;;
let
parse_error
s =
print_endline
"Parse
error";
print_endline
s;
flush
stdout;;
%}
/* Ocamlyacc declarations */
/* token declarations */
%token Tint
%token Tident
%token TEOL
%token TPlus
/* nonterminal declaration */
%type
expression list>
program
/* start symbol */
%start program
%%
/* Ocamlyacc grammar
and action
rules */
program :
/* build a list from one element */
nexpression EOL {[$1]}
/* build a list from one element
and a list */
| nexpression program {($1)::$2}
;
nexpression:
value {$1}
| nexpression TPlus nexpression {Exp_Plus($1,$3)}
;
value:
Tint {ExpInt
$1}
| Tident {ExpIdent
$1}
;
%%
Lexer declaration
We can
now describe how each terminal symbol should be
recognized from a string and this is the work of
the lexer, working the previously defined parser.
Therefore we start the lexer simple_types.mll
file
with the header:
{
open
Simple_parser;;
(*
Raised when parsing ends *)
exception
Eof;;
}
We have
four terminals: Tint,Tident,TEOL,TPlus.
For each of them, we have to give the regular
expression describing the input that should be
accepted as a token.
E.g. a Tint
represents
an int, and therefore the regular expression should
be ['0'-'9']+.
Once recognized, we have to instruct the lexer on
how to compile a string to a int,
by using the ocaml standard function
int_of_string.
From the in returned by this function, we can now
build a Tint
using
the constructor generated by the parser:
Tint(int_of_string(Lexing.lexeme
lexbuf)).
This is described in simple_lexer.mll
by the
declaration:
rule lexer = parse
(* eat blank characters
*)
['
' '\t' '\n']
{lexer
lexbuf}
| [';']
{TEOL}
| ['0'-
'9']+
{Tint
(
int_of_string(Lexing.lexeme
lexbuf))}
| ['a'-'z'
'A'-'Z' '$' '_']+
{Tident
(Lexing.lexeme
lexbuf)}
| ['+']
{TPlus}
(*
built-in regexp for handling end of file
*)
| eof {raise
Eof}
Hence,
the simple_lexer.mll
file
will be:
{
open Simple_parser;;
exception
Eof
}
rule lexer = parse
(* eat blank characters
*)
['
' '\t' '\n']
{lexer
lexbuf}
| [';']
{TEOL}
| ['0'-
'9']+
{Tint
(
int_of_string(Lexing.lexeme
lexbuf))}
| ['a'-'z'
'A'-'Z' '$' '_']+
{Tident
(Lexing.lexeme
lexbuf)}
| ['+']
{TPlus}
(*
built-in regexp for handling end of file
*)
| eof {raise
Eof}
The driver
We can
now use the generated parser in our application.
Here, we will build a simple test function that
will call the parser popping the next
expression
each
time it is called.
The
generated parser will export three useful
functions:Lexing.from_string,
Simple_lexer.lexer
and
Simple_parser.nexpression
(that is
the grammar axiom).
The basic code to use these functions is :
(*
Main file for simple test
*)
let
explore_expression
e = print_int
(List.length
e);print_string
"\n";;
let
parse
()
=
(* We build the lexer feeding it a
string*)
let buff
= Lexing.from_string("ab+cd+fr;
c+ef f;")
in
try
while (true)
do
let value =
Simple_parser.program
Simple_lexer.lexer
buff
(* pop the next expression from the string
*)
in explore_expression
value; (*
do something with it *)
done;
with
Failure("lexing:
empty token")
-> print_string
"Failure"
|
Simple_lexer.Eof
->
print_string
"\n";exit
0;;
let
_ =
parse ();;
Compilation and running
I
strongly recommend using Ocamlmakefile for
automatic make file generation. Once downloaded,
put it in your project folder then create the
file Makefile
with
SOURCES =
simple_types.ml
simple_parser.mly
simple_lexer.mll
test.ml
RESULT = test
MAKEFILE = OCamlMakefile
include
$(MAKEFILE)
Then
simply call make
the
generate the full application.
Files
sections
The yacc
file is usually divided in three sections:
%{
Header
(Ocaml
code)
%}
Ocamlyacc declarations
%%
Grammar rules
%%
Trailer (Ocaml
code)
Yacc header
Such as
%{
open Simple_types;;
let
parse_error
s =
print_endline
"Parse
error";
print_endline
s;
flush
stdout;;
%}
This
part will be transfered as is in the generated
parser. You can use it to put module opening
directives and functions definitions that can be
used in the actions in the grammar rules.
Summary
- Each token recognized in the lexer must be also declared in the parser by a %token directive
- The parser must declare a correctly typed start symbol
- Each token has an associated constructor to be used in the lexer rules
- Each non terminal must appear as a left-side of a grammar rule
- If a terminal doesn't appear in a righ-hand side of a grammar rule, it'll raise a parse error
- If a terminal doesn't appear in a lexer rule, it'll be ignored (globbed).
- Constructors defined in the types file should be used in grammar rules
- Generated constructors from the tokens shoulb be used in lexer rules