Ocamlyacc

Menhir

Dypgen

Elkhound

Camlp4

Handled grammar

LALR(1)

LR(1)

ContextFree (GLR)

ContextFree (GLR)

LL(k) (k not well defined)

Reentrant

???

Yes

Yes

???

Yes

Grammars in multiple files

No

Yes

No

???

Yes

Extensible (an action can change the grammar)

No

No

Yes (moreover, the extension is « scoped »)

No

Yes

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)

Nested or local non terminal definition

No

No

No

No

Yes

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

Grammars parametrized by Ocaml modules

No

Yes

No

No

Yes

Rule guarded by semantical value for terminal (allowing to use something like KWD('+') as a terminal)

No

No

Yes

No

Yes

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

Naming of semantical value in rules (to avoid the $1,$2, ... which are hard to maintain)

No

Yes

Yes

Yes

Yes

Partial action (action code in the middle of a rule)

No

No

Yes

No

Yes (with a hack)

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

Exception to reject a rule

Meaningless for deterministic parsing

Meaningless for deterministic parsing

Yes

No ???

No

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

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

The language used to write the parser generator

C

Ocaml

Ocaml

C++

Ocaml

Calculator example

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

Lexer included

%start main
%relation pi %layout [' ' '\t']
%parser

main: expr "\n" { $1 }

expr:
| ['0'-'9']+ { int_of_string $1 } pi
| "-" expr(=pi) { -$2 } pi
| "(" expr ")" { $2 } pi
| expr(<=pp) "+" expr(<pp) { $1 + $3 } pp
| expr(<=pp) "-" expr(<pp) { $1 - $3 } pp
| expr(<=pt) "*" expr(<pt) { $1 * $3 } pt
| expr(<=pt) "/" 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;;