Chapter 12  Lexer and parser generators (ocamllex, ocamlyacc)

12.1  Overview of ocamllex

        ocamllex lexer.mll

12.1.1  Options

-o output-file

Specify the name of the output file produced by ocamllex. Default is lexer.ml, ocamllex being invoked as ocamllex lexer.mll.

-ml

Output code that does not use the Caml built-in automata interpreter. Instead, the automaton is encoded by Caml functions. This option is useful for debugging ocamllex, using it for production lexers is not recommended.

-q

Quiet mode. ocamllex normally outputs informational messages to standard output. They are suppressed if option -q is used.

-version

Print version and exit.

12.2  Syntax of lexer definitions

{ header }
let ident = regexp ...
rule entrypoint [arg1... argn] =
  parse regexp { action }
      | ...
      | regexp { action }
and entrypoint [arg1... argn] =
  parse ...
and ...
{ trailer }

12.2.1  Header and trailer

12.2.2  Naming regular expressions

12.2.3  Entry points

12.2.4  Regular expressions

' char '

A character constant, with the same syntax as Objective Caml character constants. Match the denoted character.

_

(Underscore.) Match any character.

eof

Match the end of the lexer input.
Note: On some systems, with interactive input, an end-of-file may be followed by more characters. However, ocamllex will not correctly handle regular expressions that contain eof followed by something else.

" string "

A string constant, with the same syntax as Objective Caml string constants. Match the corresponding sequence of characters.

[ character-set ]

Match any single character belonging to the given character set. Valid character sets are: single character constants ' c '; ranges of characters ' c₁ ' - '  c₂ ' (all characters between c₁ and c₂, inclusive); and the union of two or more character sets, denoted by concatenation.

[ ^ character-set ]

Match any single character not belonging to the given character set.

regexp₁ #  regexp₂

(Difference of character sets). Regular expressions regexp₁ and regexp₂ must be character sets defined with [… ] (or a a single character expression or underscore _). Match the difference of the two specified character sets.

regexp *

(Repetition.) Match the concatenation of zero or more strings that match regexp.

regexp +

(Strict repetition.) Match the concatenation of one or more strings that match regexp.

regexp ?

(Option.) Match either the empty string, or a string matching regexp.

regexp₁ |  regexp₂

(Alternative.) Match any string that matches either regexp₁ or regexp₂

regexp₁  regexp₂

(Concatenation.) Match the concatenation of two strings, the first matching regexp₁, the second matching regexp₂.

( regexp )

Match the same strings as regexp.

ident

Reference the regular expression bound to ident by an earlier let ident =  regexp definition.

regexp as  ident

Bind the substring matched by regexp to identifier ident.

12.2.5  Actions

Lexing.lexeme lexbuf

Return the matched string.

Lexing.lexeme_char lexbuf n

Return the n^th character in the matched string. The first character corresponds to n = 0.

Lexing.lexeme_start lexbuf

Return the absolute position in the input text of the beginning of the matched string. The first character read from the input text has position 0.

Lexing.lexeme_end lexbuf

Return the absolute position in the input text of the end of the matched string. The first character read from the input text has position 0.

entrypoint [exp₁... exp_n] lexbuf

(Where entrypoint is the name of another entry point in the same lexer definition.) Recursively call the lexer on the given entry point. Notice that lexbuf is the last argument. Useful for lexing nested comments, for example.

12.2.6  Variables in regular expressions

• A variable is a char variable when all its occurrences bind char occurrences in the previous sense.
• A variable is an option variable when the overall expression can be matched without binding this variable.

12.2.7  Reserved identifiers

12.3  Overview of ocamlyacc

        ocamlyacc options grammar.mly

12.4  Syntax of grammar definitions

%{
  header
%}
  declarations
%%
  rules
%%
  trailer

12.4.1  Header and trailer

12.4.2  Declarations

%token symbol …  symbol

Declare the given symbols as tokens (terminal symbols). These symbols are added as constant constructors for the token concrete type.

%token < type >  symbol …  symbol

Declare the given symbols as tokens with an attached attribute of the given type. These symbols are added as constructors with arguments of the given type for the token concrete type. The type part is an arbitrary Caml type expression, except that all type constructor names must be fully qualified (e.g. Modname.typename) for all types except standard built-in types, even if the proper open directives (e.g. open Modname) were given in the header section. That's because the header is copied only to the .ml output file, but not to the .mli output file, while the type part of a %token declaration is copied to both.

%start symbol …  symbol

Declare the given symbols as entry points for the grammar. For each entry point, a parsing function with the same name is defined in the output module. Non-terminals that are not declared as entry points have no such parsing function. Start symbols must be given a type with the %type directive below.

%type < type >  symbol …  symbol

Specify the type of the semantic attributes for the given symbols. This is mandatory for start symbols only. Other nonterminal symbols need not be given types by hand: these types will be inferred when running the output files through the Objective Caml compiler (unless the -s option is in effect). The type part is an arbitrary Caml type expression, except that all type constructor names must be fully qualified, as explained above for %token.

%left symbol …  symbol

%right symbol …  symbol

%nonassoc symbol …  symbol

Associate precedences and associativities to the given symbols. All symbols on the same line are given the same precedence. They have higher precedence than symbols declared before in a %left, %right or %nonassoc line. They have lower precedence than symbols declared after in a %left, %right or %nonassoc line. The symbols are declared to associate to the left (%left), to the right (%right), or to be non-associative (%nonassoc). The symbols are usually tokens. They can also be dummy nonterminals, for use with the %prec directive inside the rules.

The precedence declarations are used in the following way to resolve reduce/reduce and shift/reduce conflicts:

• Tokens and rules have precedences. By default, the precedence of a rule is the precedence of its rightmost terminal. You can override this default by using the %prec directive in the rule.
• A reduce/reduce conflict is resolved in favor of the first rule (in the order given by the source file), and ocamlyacc outputs a warning.
• A shift/reduce conflict is resolved by comparing the precedence of the rule to be reduced with the precedence of the token to be shifted. If the precedence of the rule is higher, then the rule will be reduced; if the precedence of the token is higher, then the token will be shifted.
• A shift/reduce conflict between a rule and a token with the same precedence will be resolved using the associativity: if the token is left-associative, then the parser will reduce; if the token is right-associative, then the parser will shift. If the token is non-associative, then the parser will declare a syntax error.
• When a shift/reduce conflict cannot be resolved using the above method, then ocamlyacc will output a warning and the parser will always shift.

12.4.3  Rules

nonterminal :
    symbol ... symbol { semantic-action }
  | ...
  | symbol ... symbol { semantic-action }
;

12.4.4  Error handling

12.5  Options

-bprefix

Name the output files prefix.ml, prefix.mli, prefix.output, instead of the default naming convention.

-v

Generate a description of the parsing tables and a report on conflicts resulting from ambiguities in the grammar. The description is put in file grammar.output.

-version

Print version and exit.

12.6  A complete example

        /* File parser.mly */
        %token <int> INT
        %token PLUS MINUS TIMES DIV
        %token LPAREN RPAREN
        %token EOL
        %left PLUS MINUS        /* lowest precedence */
        %left TIMES DIV         /* medium precedence */
        %nonassoc UMINUS        /* highest precedence */
        %start main             /* the entry point */
        %type <int> main
        %%
        main:
            expr EOL                { $1 }
        ;
        expr:
            INT                     { $1 }
          | LPAREN expr RPAREN      { $2 }
          | expr PLUS expr          { $1 + $3 }
          | expr MINUS expr         { $1 - $3 }
          | expr TIMES expr         { $1 * $3 }
          | expr DIV expr           { $1 / $3 }
          | MINUS expr %prec UMINUS { - $2 }
        ;

        (* File lexer.mll *)
        {
        open Parser        (* The type token is defined in parser.mli *)
        exception Eof
        }
        rule token = parse
            [' ' '\t']     { token lexbuf }     (* skip blanks *)
          | ['\n' ]        { EOL }
          | ['0'-'9']+ as lxm { INT(int_of_string lxm) }
          | '+'            { PLUS }
          | '-'            { MINUS }
          | '*'            { TIMES }
          | '/'            { DIV }
          | '('            { LPAREN }
          | ')'            { RPAREN }
          | eof            { raise Eof }

        (* File calc.ml *)
        let _ =
          try
            let lexbuf = Lexing.from_channel stdin in
            while true do
              let result = Parser.main Lexer.token lexbuf in
                print_int result; print_newline(); flush stdout
            done
          with Lexer.Eof ->
            exit 0

        ocamllex lexer.mll       # generates lexer.ml
        ocamlyacc parser.mly     # generates parser.ml and parser.mli
        ocamlc -c parser.mli
        ocamlc -c lexer.ml
        ocamlc -c parser.ml
        ocamlc -c calc.ml
        ocamlc -o calc lexer.cmo parser.cmo calc.cmo

12.7  Common errors

ocamllex: transition table overflow, automaton is too big

The deterministic automata generated by ocamllex are limited to at most 32767 transitions. The message above indicates that your lexer definition is too complex and overflows this limit. This is commonly caused by lexer definitions that have separate rules for each of the alphabetic keywords of the language, as in the following example.

rule token = parse
  "keyword1"   { KWD1 }
| "keyword2"   { KWD2 }
| ...
| "keyword100" { KWD100 }
| ['A'-'Z' 'a'-'z'] ['A'-'Z' 'a'-'z' '0'-'9' '_'] * as id
               { IDENT id}

To keep the generated automata small, rewrite those definitions with only one general “identifier” rule, followed by a hashtable lookup to separate keywords from identifiers:

{ let keyword_table = Hashtbl.create 53
  let _ =
    List.iter (fun (kwd, tok) -> Hashtbl.add keyword_table kwd tok)
              [ "keyword1", KWD1;
                "keyword2", KWD2; ...
                "keyword100", KWD100 ]
}
rule token = parse
  ['A'-'Z' 'a'-'z'] ['A'-'Z' 'a'-'z' '0'-'9' '_'] * as id
               { try
                   Hashtbl.find keyword_table id
                 with Not_found ->
                   IDENT id }

ocamllex: Position memory overflow, too many bindings

The deterministic automata generated by ocamllex maintains a table of positions inside the scanned lexer buffer. The size of this table is limited to at most 255 cells. This error should not show up in normal situations.