LR parsing

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.

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

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.

• ppxA preprocessor that rewrites the OCaml syntax tree between parsing and type checking. Derivers generate code from type declarations tagged [@@deriving name]; extension points expand nodes written [%name payload]. Neither sees any types.
• Brzozowski derivativeThe Brzozowski derivative of a regular expression r with respect to a character a is a regular expression for the strings w such that a w matches r. It is computed syntactically, by rules much like those of calculus, so a string can be matched by taking one derivative per character and checking whether the result matches the empty string. Up to simple algebraic identities a regular expression has finitely many derivatives, which are the states of a deterministic automaton, and the method extends directly to intersection and complement.
• Earley parsingEarley parsing is an algorithm that parses any context-free grammar, including ambiguous and left-recursive ones. For each position in the input it builds a set of items, grammar rules with a dot marking how much of the right-hand side has been recognized and the position where recognition began, using three operations: prediction adds the rules for a nonterminal the parser expects, scanning moves past a matching token, and completion advances the rules that were waiting for a nonterminal that has just been recognized. It runs in O(n³) time in general, O(n²) on unambiguous grammars and linear time on most grammars used in practice. Jay Earley published it in 1970.
• LL(1) parsingLL(1) parsing is top-down parsing that decides which grammar rule to apply by looking at a single token of input. It reads the input Left to right and builds a Leftmost derivation, choosing each rule from a table indexed by the nonterminal being expanded and the next token\; the table is computed from the FIRST and FOLLOW sets of the grammar, and a grammar is LL(1) when no entry holds two rules. LL(1) parsers run in linear time with no backtracking, and they correspond directly to recursive-descent parsers, one function per nonterminal. Left-recursive and ambiguous grammars are not LL(1) and must be rewritten.
• Parser combinatorA parser combinator is a higher-order function that builds a parser from smaller parsers: a sequence of two parsers, a choice between them, a repetition of one. Parsers are ordinary values in the host language, so a grammar is written as a program that is itself the parser, with no separate generator. Parser combinators produce recursive descent parsers; they cannot use left-recursive rules directly, and with unlimited backtracking can take exponential time, which memoization (packrat parsing) reduces to linear.
• Pratt parsingPratt parsing, or top-down operator precedence parsing, is a technique for parsing expressions in which every operator has a numeric binding power on each side, and a single recursive function parses an expression by consuming operators for as long as they bind more tightly than a given minimum. Prefix, infix, postfix, mixfix and bracketing operators are handled by attaching to each token a null denotation, its meaning at the start of an expression, and a left denotation, its meaning after one. The method handles any number of precedence levels and both associativities in linear time with one function instead of one grammar rule per level, and new operators can be added by extending a table. Vaughan Pratt introduced it in 1973.

• Parsing with MenhirA command-first tour of the OCaml parser generator: grammars, dune wiring, conflicts, parameterized rules, positions, and error messages.

1. [1]D. E. Knuth, “On the translation of languages from left to right”, Information and Control 8 (1965).
2. [2]F. DeRemer, Practical Translators for LR(k) Languages, PhD thesis, MIT (1969).
3. [3]F. Pottier, Y. Régis-Gianas, the Menhir reference manual.

last updated 25 September 2026