Comparisons » parser generator

Menhir Dypgen Elkhound Camlp4 Aurochs


 Ocamlyacc Menhir Dypgen Elkhound Camlp4 Aurochs
Handled grammar LALR(1) LR(1) ContextFree (GLR) ContextFree (GLR) LL(k) (k not well defined) PEG
Reentrant ??? Yes Yes ??? Yes Yes
Grammars in multiple files No Yes No ??? Yes No
Extensible (an action can change the grammar) No No Yes (moreover, the extension is « scoped ») No Yes No
State of development Production Production Beta Production Production release in 3.09, beta in 3.10 Production
Parametrized non terminal No Yes (parametrized by other symbols, terminal or not) No (except for priority) No No (except for levels and OPT or LIST0|1 construct) No
Nested or local non terminal definition No No No No Yes No
Splitting the definition of a non terminal (this is really useful when the grammar can be splitted in many files) No Yes Yes Yes Yes No
Grammars parametrized by Ocaml modules No Yes No No Yes No
Rule guarded by semantical value for terminal (allowing to use something like KWD('+') as a terminal) No No Yes No Yes No
Pattern matching on semantical value for terminal and non terminal (allowing a terminal like « expr_list([x]) » to mean an expressions list of size one in a rule) No No Yes No Yes No
Naming of semantical value in rules (to avoid the $1,$2, ... which are hard to maintain) No Yes Yes Yes Yes Yes
Partial action (action code in the middle of a rule) No No Yes No Yes (with a hack) No
Ambiguous grammars (this means you can get all parse-trees and usually implies that you can parse all context-free grammars) No No Yes Yes No No
Exception to reject a rule Meaningless for deterministic parsing Meaningless for deterministic parsing Yes No ??? No Yes
Priority Like yacc Like yacc Using arbitrary relations Using the order relation on integer + associativity direction Using levels (= a total and extensible order as a relation) + associativity direction By production order
Debugging grammar conflicts Hard Easy: conflict explicited in terms of the grammar Average (by printing the possible parse trees when many) Average (by printing the possible parse trees when many) Hard Average (use interactive mode)
The language used to write the parser generator C Ocaml Ocaml C++ Ocaml Ocaml

Calculator example

Ocamlyacc Menhir Dypgen Elkhound Camlp4 
%token LPAREN RPAREN
%token <float> NUM
%token PLUS MINUS MULTIPLY DIVIDE
%left PLUS MINUS
%left MULTIPLY DIVIDE
%left NEG
%start input
%type <unit> input
%%
exp:
NUM { $1 }
| exp PLUS exp { $1 +. $3 }
| exp MINUS exp { $1 -. $3 }
| exp MULTIPLY exp { $1 *. $3 }
| exp DIVIDE exp { $1 /. $3 }
| MINUS exp %prec NEG { -. $2 }
| LPAREN exp RPAREN { $2 };
Identical to ocamlyacc, menhir is mostly compatible with ocamlyacc. 
%token LPAREN RPAREN PLUS MINUS
%token TIMES DIV EOL
%token <int> INT
%relation pi<pt<pp 
%start <int> main 
%% 
main : expr EOL { $1 } 
expr : 
| INT { $1 } pi 
| MINUS expr(=pi) { -$2 } pi 
| LPAREN expr RPAREN { $2 } pi 
| expr(<=pp) PLUS expr(<pp) { $1 + $3 } pp 
| expr(<=pp) MINUS expr(<pp) { $1 - $3 } pp 
| expr(<=pt) TIMES expr(<pt) { $1 * $3 } pt 
| expr(<=pt) DIV expr(<pt) {$1 / $3 } pt

let expr = 
  Grammar.Entry.create gram "expr";;
EXTEND
expr:
  [ "add" LEFTA
    [ x = expr; "+"; y = expr -> x + y
    | x = expr; "-"; y = expr -> x - y ]
  | [ "-"; y = expr -> - y ]
  | "mult" RIGHTA
    [ x = expr; "*"; y = expr -> x * y
    | x = expr; "/"; y = expr -> x / y ]
  | "simple" NONA
    [ x = INT -> int_of_string x
    | "("; e = expr; ")" -> e ] ];
END;;

See also : http://www.lama.univ-savoie.fr/~raffalli/ocaml-parsing.html