Describing the Grammar

The next thing we need to do is to specify the grammar of a JSON expression. menhir, like many parser generators, expresses grammars as context-free grammars. (More precisely, menhir supports LR(1) grammars, but we will ignore that technical distinction here.) You can think of a context-free grammar as a set of abstract names, called non-terminal symbols, along with a collection of rules for transforming a nonterminal symbol into a sequence of tokens and nonterminal symbols. A sequence of tokens is parsable by a grammar if you can apply the grammar’s rules to produce a series of transformations, starting at a distinguished start symbol that produces the token sequence in question.            

We’ll start describing the JSON grammar by declaring the start symbol to be the non-terminal symbol prog, and by declaring that when parsed, a prog value should be converted into an OCaml value of type Json.value option. We then end the declaration section of the parser with a %%:

%start <Json.value option> prog
%%

Once that’s in place, we can start specifying the productions. In menhir, productions are organized into rules, where each rule lists all the possible productions for a given nonterminal symbol. Here, for example, is the rule for prog:

prog:
  | EOF       { None }
  | v = value { Some v }
  ;

The syntax for this is reminiscent of an OCaml match expression. The pipes separate the individual productions, and the curly braces contain a semantic action: OCaml code that generates the OCaml value corresponding to the production in question. Semantic actions are arbitrary OCaml expressions that are evaluated during parsing to produce values that are attached to the non-terminal in the rule.   

We have two cases for prog: either there’s an EOF, which means the text is empty, and so there’s no JSON value to read, we return the OCaml value None; or we have an instance of the value nonterminal, which corresponds to a well-formed JSON value, and we wrap the corresponding Json.value in a Some tag. Note that in the value case, we wrote v = value to bind the OCaml value that corresponds to the variable v, which we can then use within the curly braces for that production.

Now let’s consider a more complex example, the rule for the value symbol:

value:
  | LEFT_BRACE; obj = object_fields; RIGHT_BRACE
    { `Assoc obj }
  | LEFT_BRACK; vl = array_values; RIGHT_BRACK
    { `List vl }
  | s = STRING
    { `String s }
  | i = INT
    { `Int i }
  | x = FLOAT
    { `Float x }
  | TRUE
    { `Bool true }
  | FALSE
    { `Bool false }
  | NULL
    { `Null }
  ;

According to these rules, a JSON value is either:  

• An object bracketed by curly braces

• An array bracketed by square braces

• A string, integer, float, bool, or null value

In each of the productions, the OCaml code in curly braces shows what to transform the object in question to. Note that we still have two nonterminals whose definitions we depend on here but have not yet defined: object_fields and array_values. We’ll look at how these are parsed next.

Parsing Sequences

The rule for object_fields follows, and is really just a thin wrapper that reverses the list returned by the following rule for rev_object_fields. Note that the first production in rev_object_fields has an empty left-hand side, because what we’re matching on in this case is an empty sequence of tokens. The comment (* empty *) is used to make this clear:   

object_fields: obj = rev_object_fields { List.rev obj };

rev_object_fields:
  | (* empty *) { [] }
  | obj = rev_object_fields; COMMA; k = ID; COLON; v = value
    { (k, v) :: obj }
  ;

The rules are structured as they are because menhir generates left-recursive parsers, which means that the constructed pushdown automaton uses less stack space with left-recursive definitions. The following right-recursive rule accepts the same input, but during parsing, it requires linear stack space to read object field definitions:  

(* Inefficient right-recursive rule *)
object_fields:
  | (* empty *) { [] }
  | k = STRING; COLON; v = value; COMMA; obj = object_fields
    { (k, v) :: obj }

Alternatively, we could keep the left-recursive definition and simply construct the returned value in left-to-right order. This is even less efficient, since the complexity of building the list incrementally in this way is quadratic in the length of the list:

(* Quadratic left-recursive rule *)
object_fields:
  | (* empty *) { [] }
  | obj = object_fields; COMMA; k = STRING; COLON; v = value
    { obj @ [k, v] }
  ;

Assembling lists like this is a pretty common requirement in most realistic grammars, and the preceding rules (while useful for illustrating how parsing works) are rather verbose. Menhir features an extended standard library of built-in rules to simplify this handling. These rules are detailed in the Menhir manual and include optional values, pairs of values with optional separators, and lists of elements (also with optional separators).  

A version of the JSON grammar using these more succinct Menhir rules follows. Notice the use of separated_list to parse both JSON objects and lists with one rule:

%token <int> INT
%token <float> FLOAT
%token <string> STRING
%token TRUE
%token FALSE
%token NULL
%token LEFT_BRACE
%token RIGHT_BRACE
%token LEFT_BRACK
%token RIGHT_BRACK
%token COLON
%token COMMA
%token EOF
%start <Json.value option> prog
%%

prog:
  | v = value { Some v }
  | EOF       { None   } ;

value:
  | LEFT_BRACE; obj = obj_fields; RIGHT_BRACE { `Assoc obj  }
  | LEFT_BRACK; vl = list_fields; RIGHT_BRACK { `List vl    }
  | s = STRING                                { `String s   }
  | i = INT                                   { `Int i      }
  | x = FLOAT                                 { `Float x    }
  | TRUE                                      { `Bool true  }
  | FALSE                                     { `Bool false }
  | NULL                                      { `Null       } ;

obj_fields:
    obj = separated_list(COMMA, obj_field)    { obj } ;

obj_field:
    k = STRING; COLON; v = value              { (k, v) } ;

list_fields:
    vl = separated_list(COMMA, value)         { vl } ;

We can hook in menhir by adding a (menhir) stanza to our dune file, which tells the build system to switch to using menhir instead of ocamlyacc to handle files with the .mly suffix:   

(menhir
 (modules parser))

(ocamllex lexer)

(library
 (name json_parser)
 (modules parser lexer json)
 (libraries core))

OCaml Prelude

Let’s walk through the definition of a lexer section by section. The first section is an optional chunk of OCaml code that is bounded by a pair of curly braces:  

{
open Lexing
open Parser

exception SyntaxError of string
}

This code is there to define utility functions used by later snippets of OCaml code and to set up the environment by opening useful modules and define an exception, SyntaxError. Any OCaml functions you define here will be subsequently available in the remainder of the lexer definition.

Regular Expressions

The next section of the lexing file is a collection of named regular expressions. These look syntactically like ordinary OCaml let bindings, but really this is a specialized syntax for declaring regular expressions. Here’s an example:   

let int = '-'? ['0'-'9'] ['0'-'9']*

The syntax here is something of a hybrid between OCaml syntax and traditional regular expression syntax. The int regular expression specifies an optional leading -, followed by a digit from 0 to 9, followed by some number of digits from 0 to 9. The question mark is used to indicate an optional component of a regular expression; the square brackets are used to specify ranges; and the * operator is used to indicate a (possibly empty) repetition.

Floating-point numbers are specified similarly, but we deal with decimal points and exponents. We make the expression easier to read by building up a sequence of named regular expressions, rather than creating one big and impenetrable expression:

let digit = ['0'-'9']
let frac = '.' digit*
let exp = ['e' 'E'] ['-' '+']? digit+
let float = digit* frac? exp?

Finally, we define whitespace, newlines, and identifiers:

let white = [' ' '\t']+
let newline = '\r' | '\n' | "\r\n"
let id = ['a'-'z' 'A'-'Z' '_'] ['a'-'z' 'A'-'Z' '0'-'9' '_']*

The newline introduces the | operator, which lets one of several alternative regular expressions match (in this case, the various carriage-return combinations of CR, LF, or CRLF).

Lexing Rules

The lexing rules are essentially functions that consume the data, producing OCaml expressions that evaluate to tokens. These OCaml expressions can be quite complicated, using side effects and invoking other rules as part of the body of the rule. Let’s look at the read rule for parsing a JSON expression:  

rule read =
  parse
  | white    { read lexbuf }
  | newline  { next_line lexbuf; read lexbuf }
  | int      { INT (int_of_string (Lexing.lexeme lexbuf)) }
  | float    { FLOAT (float_of_string (Lexing.lexeme lexbuf)) }
  | "true"   { TRUE }
  | "false"  { FALSE }
  | "null"   { NULL }
  | '"'      { read_string (Buffer.create 17) lexbuf }
  | '{'      { LEFT_BRACE }
  | '}'      { RIGHT_BRACE }
  | '['      { LEFT_BRACK }
  | ']'      { RIGHT_BRACK }
  | ':'      { COLON }
  | ','      { COMMA }
  | _ { raise (SyntaxError ("Unexpected char: " ^ Lexing.lexeme lexbuf)) }
  | eof      { EOF }

The rules are structured very similarly to pattern matches, except that the variants are replaced by regular expressions on the left-hand side. The right-hand side clause is the parsed OCaml return value of that rule. The OCaml code for the rules has a parameter called lexbuf that defines the input, including the position in the input file, as well as the text that was matched by the regular expression.  

The first white { read lexbuf } calls the lexer recursively. That is, it skips the input whitespace and returns the following token. The action newline { next_line lexbuf; read lexbuf } is similar, but we use it to advance the line number for the lexer using the utility function that we defined at the top of the file. Let’s skip to the third action:

| int { INT (int_of_string (Lexing.lexeme lexbuf)) }

This action specifies that when the input matches the int regular expression, then the lexer should return the expression INT (int_of_string (Lexing.lexeme lexbuf)). The expression Lexing.lexeme lexbuf returns the complete string matched by the regular expression. In this case, the string represents a number, so we use the int_of_string function to convert it to a number.

There are actions for each different kind of token. The string expressions like "true" { TRUE } are used for keywords, and the special characters have actions, too, like '{' { LEFT_BRACE }.

Some of these patterns overlap. For example, the regular expression "true" is also matched by the id pattern. ocamllex used the following disambiguation when a prefix of the input is matched by more than one pattern:

• The longest match always wins. For example, the first input trueX: 167 matches the regular expression "true" for four characters, and it matches id for five characters. The longer match wins, and the return value is ID "trueX".

• If all matches have the same length, then the first action wins. If the input were true: 167, then both "true" and id match the first four characters; "true" is first, so the return value is TRUE.

File "parser.mly", line 4, characters 16-18:
Warning: the token ID is unused.

Recursive Rules

Unlike many other lexer generators, ocamllex allows the definition of multiple lexers in the same file, and the definitions can be recursive. In this case, we use recursion to match string literals using the following rule definition:   

and read_string buf =
  parse
  | '"'       { STRING (Buffer.contents buf) }
  | '\\' '/'  { Buffer.add_char buf '/'; read_string buf lexbuf }
  | '\\' '\\' { Buffer.add_char buf '\\'; read_string buf lexbuf }
  | '\\' 'b'  { Buffer.add_char buf '\b'; read_string buf lexbuf }
  | '\\' 'f'  { Buffer.add_char buf '\012'; read_string buf lexbuf }
  | '\\' 'n'  { Buffer.add_char buf '\n'; read_string buf lexbuf }
  | '\\' 'r'  { Buffer.add_char buf '\r'; read_string buf lexbuf }
  | '\\' 't'  { Buffer.add_char buf '\t'; read_string buf lexbuf }
  | [^ '"' '\\']+
    { Buffer.add_string buf (Lexing.lexeme lexbuf);
      read_string buf lexbuf
    }
  | _ { raise (SyntaxError ("Illegal string character: " ^ Lexing.lexeme lexbuf)) }
  | eof { raise (SyntaxError ("String is not terminated")) }

This rule takes a buf : Buffer.t as an argument. If we reach the terminating double quote ", then we return the contents of the buffer as a STRING.

The other cases are for handling the string contents. The action [^ '"' '\\']+ { ... } matches normal input that does not contain a double quote or backslash. The actions beginning with a backslash \ define what to do for escape sequences. In each of these cases, the final step includes a recursive call to the lexer.

That covers the lexer. Next, we need to combine the lexer with the parser to bring it all together.