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
What ?
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
|