Parser Generators

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

(using menhir 2.1)

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
└──parser
   ├──dune
   ├──lex.mll
   ├──my_parser.ml
   └──par.mly

We use the name My_parser because the module Parser already exists in the standard library. For us, the dune file and my_parser.ml file are fixed:

dune:

(library (name my_parser) (libraries utils))
(menhir (modules par))
(ocamllex lex)

my_parser.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.

lex.mll:

{
open Par
}

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

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

par.mly

%{
open Utils
%}

%token EOF

%start <Ast.prog> { prog }

%%

prog:
  | EOF { Num 0 }

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

Note. We will presume that the abstract representation (in this case, prog as above) we want to target is in a file lib/utils/utils.ml.

The type prog is something you are either given, or which you should have determined before you started building a parser.⁶

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

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

%{
open Ast
%}

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

%token EOF

%start <Ast.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.

Updated par.mly:

%{
open Ast
%}

%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 <Ast.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 or %right TOKEN, depending on whether TOKEN should be left associative or right associative, and precendence is handled by the order the declarations are presented (just like in our precedence table).

Updated par.mly:

%{
open Ast
%}

%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 <Ast.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 = expr2 { Bop(op, e1, e2) }
  | e = num { e }
  | e = var { e }
  | LPAREN; e = expr; RPAREN { e }

num:
  | n = NUM { Num n }

var:
  | x = VAR { Var x }

Remark. If we want to follow the grammar exactly, we have to use what is called inlining for 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) }
  | e = num { e }
  | e = var { e }
  | 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 it, it won't do anything because we haven't specified the lexer, we haven't said which strings correspond to which tokens. We will deal with this in the next section.

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 Par
  }
  

• 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 }
    | "=" { 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 lex.mll:

{
open Par
}

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

rule read =
  parse
  | "let" { LET }
  | "=" { 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 }

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

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

and see that it has the value

Let
  ("x"
  , Num 2
  , Let
      ( "y"
      , Num 3
      , Add (Var "x", Var "y")
      )
  )

You'll use My_parser.parse as your parser for the mini-projects.