Parser Generators

If we want to use Menhir, we have to tell dune that. First, add the stanza

(using menhir 3.0)

to the end of the file dune-project.

You need to create four files with the following file structure in the lib directory of your project.

lib
├──dune
├──utils.ml
├──parser_example.ml
├──lexer.mll
└──parser.mly

dune:

(library (name parser_example))
(menhir (modules parser))
(ocamllex lexer)

utils.ml:

type bop = Add | Sub | Mul | Div

type expr =
  | Var of string
  | Num of int
  | Let of string * expr * expr
  | Bop of bop * expr * expr

type prog = expr

parse_example.ml:

let parse s =
  try Some (Parser.prog Lexer.read (Lexing.from_string s))
  with _ -> None

Remark: One of the benefits of using a parser generator is better error messages. We will not be using this feature in this course. If you were to use Menhir in a personal project, you would need to update the parse function to make use of the exceptions produced by Parser.prog.

The last two files are where the work happens. We can start with the following dummy files.

lexer.mll:

{
open Parser
}

let whitespace = [' ' '\t' '\n' '\r']+

rule read =
  parse
  | whitespace { read lexbuf }
  | eof { EOF }

parser.mly:

%{
open Utils
%}

%token EOF

%start <Utils.prog> prog

%%

prog:
  | EOF { Num 0 }

At this point, you should be able to dune build your project.

Now we need to populate our parser with the tokens of our PL. We also need to discuss the anatomy of the parser.mly file.

Our file begins with a header that can include arbitary OCaml code. For now we just open the module Utils so that we can refer to the prog and expr types in this file:

%{
open Utils
%}

Next follows a collection of declarations. This is where we will specify tokens, precedence, and associativity. We also declare our start symbol here (this is already done):

%token EOF

%start <Utils.prog> { prog }

%%

Our declarations end with the symbol %%. Everything that follows are rules, i.e., the production rules of our grammar. We will cover this in the next section.

For now, we'll populate the top of our file with token declarations, one for each terminal symbol in our grammar. The syntax is

%token NAME

and it is typical to choose an ALLCAPS name. There is already a token that we are using the represent the end of a file, which will appear in every parser we build. In the case of complex tokens, like numbers and variables, we also specify the type of thing the lexer will give us with the syntax

%token <type> NAME

With this, we can update parser.mly:

%{
open Utils
%}

%token LET
%token EQUALS
%token IN
%token PLUS
%token MINUS
%token TIMES
%token DIVIDE
%token <int> NUM
%token <string> VAR
%token LPAREN
%token RPAREN
%token EOF

%start <Utils.prog> prog

%%

prog:
  | EOF { Num 0 }

Determining the tokens you need to create is a matter of looking through the list of rules in the grammar, picking out all the terminal symbols, and giving them names.

At this point, if you try to dune build, you will see many warnings about unused tokens. This is because we haven't used any of the tokens in the rules of the grammar. We'll handle this in the next section.

Onto the most important part, describing the rules of the grammar. Menhir is designed so that its rules looks a whole lot like EBNF production rules. Let's look at the first two rules.

In EBNF:

<prog> ::= <expr>

<expr> ::= let <var> = <expr> in <expr>
         | <expr1>

in Menhir syntax:

prog:
  | e = expr; EOF { e }

expr:
  | LET; x = var; EQUALS; e1 = expr; IN; e2 = expr { Let(x, e1, e2) }
  | e = expr1 { e }

If we squint, we can see the similarities. The main differences in the Menhir syntax:

• The starting symbol should be followed with the special EOF (end-of-file) token. This ensures that Menhir knows that there is nothing left to parse after parsing an expression.
• symbols are separated by semicolons⁶
• terminal symbols are replaced with their associated tokens
• alternatives are followed by the values which should be returned if they are matched with (the parts in the curly braces)
• nonterminal symbols are given names which can be used in these returned values (like e1 = expr)

For example, we read the first alternative of the expr rule as:

• if I see the keyword let
• and then I see a variable x
• and then I see the symbol =
• and then I see a whole expression which parses to e1
• and then I see the keyword in
• and then I see a whole expression which parses to e2
• then the result of parsing should be Let(x, e1, e2).

Implementing the parser is a matter of translating these rules into Menhir syntax.

We also need to provide precedence and associativity declarations for our operators. The syntax is:

%left TOKEN
%right TOKEN

depending on whether TOKEN should be left associative or right associative, and precendence is handled by the order the declarations are presented. Precedences increases down the list, just like in our precedence table.

Futher updating parser.mly:

%{
open Utils
%}

%token LET
%token EQUALS
%token IN
%token PLUS
%token MINUS
%token TIMES
%token DIVIDE
%token <int> NUM
%token <string> VAR
%token LPAREN
%token RPAREN
%token EOF

%left PLUS, MINUS
%left TIMES, DIVIDE

%start <Utils.prog> prog

%%

prog:
  | e = expr; EOF { e }

expr:
  | LET; x = var; EQUALS; e1 = expr; IN; e2 = expr { Let(x, e1, e2) }
  | e = expr1 { e }

%inline bop:
  | PLUS { Add }
  | MINUS { Sub }
  | TIMES { Mul }
  | DIVIDE { Div }

expr1:
  | e1 = expr1; op = bop; e2 = expr1 { Bop(op, e1, e2) }
  | n = num { Num n }
  | v = var { Var v }
  | LPAREN; e = expr; RPAREN { e }

num:
  | n = NUM { n }

var:
  | x = VAR { x }

Remark: If we want to follow the grammar exactly, we have to inline the binary operators. Menhir is not smart enough to recognize that bop expands to operators with declared precendence. We use the keyword %inline to tell Menhir essentially to immediately substitute bop in the grammar itself.

It's equivalent to having the rule:

expr1:
  | e1 = expr1; PLUS; e2 = expr2 { Bop(Add, e1, e2) }
  | e1 = expr1; MINUS; e2 = expr2 { Bop(Sub, e1, e2) }
  | e1 = expr1; TIMES; e2 = expr2 { Bop(Mul, e1, e2) }
  | e1 = expr1; DIVIDE; e2 = expr2 { Bop(Div, e1, e2) }
  | n = num { Num n }
  | v = var { Var v }
  | LPAREN; e = expr; RPAREN { e }

but with far less typing.

At this point, you should be able to dune build your project. That said, if you try to use Parser_example.parse, it won't do anything because we haven't specified the lexer. That is, we haven't said which strings correspond to which tokens.

The last thing we need to do: populate the lexer. We won't discuss the anatomy of the lex.mll file in too much detail because it will stay fairly fixed for us in this course.

• There is a header (it will always be the same):

  {
  open Parser
  }
  

• There are identifiers, which are regular expressions for defining the structure of more complex tokens.⁷ These were included in the definition of the grammar above:

  let whitespace = [' ' '\t' '\n' '\r']+
  let num = '-'? ['0'-'9']+
  let var = ['a'-'z' '_'] ['a'-'z' 'A'-'Z' '0'-'9' '_' '\'']*
  

• There is a rule which describes which strings correspond to which tokens:

  rule read =
    parse
    | "let" { LET }
    | "in" { IN }
    | "=" { EQUALS }
    | "+" { PLUS }
    | "-" { MINUS }
    | "*" { TIMES }
    | "/" { DIVIDE }
    | num { NUM (int_of_string (Lexing.lexeme lexbuf)) }
    | var { VAR (Lexing.lexeme lexbuf) }
    | "(" { LPAREN }
    | ")" { RPAREN }
    | whitespace { read lexbuf }
    | eof { EOF }
  

  Without going into too much detail, what's going on with num and var: the expression Lexing.lexeme lexbuf is the lexeme (i.e., the string) which corresponds to the complex token being read. For example, if "123 abc" is given, then "123" is the lexeme Lexing.lexeme lexbuf when "123" is grouped by the lexer. We want to give the parser a number not a string so we convert it with string_of_int.

All together, the updated lexer.mll:

{
open Parser
}

let whitespace = [' ' '\t' '\n' '\r']
let num = '-'? ['0'-'9']+
let var = ['a'-'z' '_'] ['a'-'z' 'A'-'Z' '0'-'9' '_' '\'']*

rule read =
  parse
  | "let" { LET }
  | "in" { IN }
  | "=" { EQUALS }
  | "+" { PLUS }
  | "-" { MINUS }
  | "*" { TIMES }
  | "/" { DIVIDE }
  | "(" { LPAREN }
  | ")" { RPAREN }
  | num { NUM (int_of_string (Lexing.lexeme lexbuf)) }
  | var { VAR (Lexing.lexeme lexbuf) }
  | whitespace { read lexbuf }
  | eof { EOF }

Important: The order in which you list lexemes matters. The ones that are listed first are matched first. This implies, for example, that "let" will never be read as a variable name, because it will always first be read as the keyword let. In pratice, this basically means put your keywords and symbols first and everything else after.

At this point, you should be able to dune build your project.

If all goes well you should be able to open dune utop and evaluate

parse "let x = 2 in let y = 3 in x + y"

and see that it has the value:

Some
 (Parser_example__.Utils.Let ("x", Parser_example__.Utils.Num 2,
   Parser_example__.Utils.Let ("y", Parser_example__.Utils.Num 3,
    Parser_example__.Utils.Bop (Parser_example__.Utils.Add,
     Parser_example__.Utils.Var "x", Parser_example__.Utils.Var "y"))))

Don't worry too much about the module names in the output. You'll use parse as your parser for the mini-projects.