LR parsing

also: lr(1), lalr, lalr(1), shift/reduce conflict, reduce/reduce conflict, menhir

Bottom-up parsing driven by a table of states: the parser shifts tokens onto a stack, and reduces the top of the stack by a grammar rule when the next token says to. A grammar for which the table cannot be built without a choice has conflicts, reported as shift/reduce or reduce/reduce.

After reading 1 + 2 with * 3 next, an LR parser has two options: reduce 1 + 2 to an expression now, or shift the * and reduce later. The table says which, based on the state and one token of lookahead. When the grammar leaves both open, the table has a conflict.

An ambiguous expression grammar in Menhir, and the precedence declarations that resolve its conflicts.

%token <int> INT
%token PLUS TIMES EOF
%left PLUS        (* lower precedence, declared first *)
%left TIMES
%start <int> main
%type <int> expr
%%
main: e = expr EOF { e }
expr:
  | i = INT { i }
  | a = expr PLUS b = expr { a + b }
  | a = expr TIMES b = expr { a * b }

menhir 20231231 on the same file without the two %left lines.

Warning: 2 states have shift/reduce conflicts.
Warning: 4 shift/reduce conflicts were arbitrarily resolved.

With the %left lines there are none. The conflict between reducing PLUS and shifting TIMES goes to the higher precedence, and ties between an operator and itself go to the left, which is left associativity.

LALR(1), the table construction used by yacc and ocamlyacc, merges states that differ only in their lookaheads. That keeps the table small, and can create reduce/reduce conflicts a full LR(1) construction does not have. Menhir builds LR(1) tables and merges states only where no conflict results. OCaml's own parser has been generated by Menhir since 4.08.