LL(1) parsing

LL(1) parsing is a method of top-down parsing in which the parser decides which rule of the grammar to apply by looking at the next token of input and nothing more^[1]^[2]. The name describes it: the input is read from Left to right, a Leftmost derivation is produced, and 1 token of lookahead is used. The parser starts from the start symbol and repeatedly replaces the leftmost nonterminal by the right-hand side of a rule, choosing the rule from a table indexed by the nonterminal and the next token. The table is computed from two sets derived from the grammar, FIRST and FOLLOW. A grammar is LL(1) if no entry of the table holds more than one rule, and then parsing takes linear time and never backtracks. An LL(1) parser can be written as a table and a stack, or as a recursive-descent parser with one function per nonterminal, which is how many hand-written compilers parse. Grammars with left recursion, ambiguity or common prefixes are not LL(1) and have to be rewritten first.

§ 01

Definitions

For a string of grammar symbols $α$ , $FIRST (α)$ is the set of terminals that can begin a string derived from $α$ , and $α$ is nullable if it can derive the empty string. For a nonterminal $A$ , $FOLLOW (A)$ is the set of terminals that can appear immediately after $A$ in some sentential form, including the end marker $$$ if $A$ can end one^[4]:

FIRST (α) FOLLOW (A) = {a ∣ α \Rightarrow^{*} a β} = {a ∣ S $ \Rightarrow^{*} β A aγ}

A rule $A \to α$ should be chosen when the next token is in its predict set, which is $FIRST (α)$ , together with $FOLLOW (A)$ if $α$ is nullable. The grammar is LL(1) when the rules for each nonterminal have pairwise disjoint predict sets. For two rules $A \to α ∣ β$ this means

FIRST (α) \cap FIRST (β) = \emptyset and, if β \Rightarrow^{*} ε, FIRST (α) \cap FOLLOW (A) = \emptyset

LL( $k$ ) generalizes this to $k$ tokens of lookahead, with FIRST and FOLLOW sets of strings of length $k$ ^[1]^[2].

§ 02

Computing the sets

All three sets are least fixed points of simple equations and are computed by iterating until nothing changes. A nonterminal is nullable if one of its rules has a right-hand side made entirely of nullable symbols. $FIRST (A)$ contains the FIRST set of each right-hand side of $A$ , where the FIRST set of a sequence $X_{1} \dots X_{n}$ is the union of $FIRST (X_{i})$ for the prefix of symbols up to and including the first one that is not nullable. For every rule $A \to α B β$ , $FOLLOW (B)$ contains $FIRST (β)$ , and also $FOLLOW (A)$ if $β$ is nullable^[4].

Nullable, FIRST and FOLLOW by fixed-point iteration, and the LL(1) table.

(* Context-free grammars, the nullable, FIRST and FOLLOW sets, and the
   LL(1) parse table. Terminals are strings; "$" marks the end of input. *)
type sym = T of string | N of string
type grammar = { start : string; rules : (string * sym list) list }
 
module S = Set.Make (String)
 
let nonterminals g = List.sort_uniq compare (List.map fst g.rules)
 
(* Iterate a monotone update until nothing changes. *)
let fixpoint step =
  let changed = ref true in
  while !changed do changed := false; step changed done
 
let analyse g =
  let nullable = Hashtbl.create 16 and first = Hashtbl.create 16
  and follow = Hashtbl.create 16 in
  List.iter (fun a -> Hashtbl.replace first a S.empty; Hashtbl.replace follow a S.empty)
    (nonterminals g);
  Hashtbl.replace follow g.start (S.singleton "$");
  let is_nullable = function T _ -> false | N a -> Hashtbl.mem nullable a in
  (* FIRST of a sequence of symbols. *)
  let rec first_seq = function
    | [] -> S.empty
    | T t :: _ -> S.singleton t
    | N a :: rest ->
      let f = Hashtbl.find first a in
      if Hashtbl.mem nullable a then S.union f (first_seq rest) else f
  in
  let grow tbl a s changed =
    let old = Hashtbl.find tbl a in
    let n = S.union old s in
    if not (S.equal n old) then (Hashtbl.replace tbl a n; changed := true)
  in
  fixpoint (fun changed ->
      List.iter (fun (a, rhs) ->
          if List.for_all is_nullable rhs && not (Hashtbl.mem nullable a) then
            (Hashtbl.replace nullable a (); changed := true);
          grow first a (first_seq rhs) changed) g.rules);
  (* For A -> ... B beta: FIRST(beta) is in FOLLOW(B), and FOLLOW(A) too
     if beta is nullable. *)
  fixpoint (fun changed ->
      List.iter (fun (a, rhs) ->
          let rec walk = function
            | [] -> ()
            | T _ :: rest -> walk rest
            | N b :: rest ->
              grow follow b (first_seq rest) changed;
              if List.for_all is_nullable rest then grow follow b (Hashtbl.find follow a) changed;
              walk rest
          in
          walk rhs) g.rules);
  let predict (a, rhs) =
    if List.for_all is_nullable rhs then S.union (first_seq rhs) (Hashtbl.find follow a)
    else first_seq rhs
  in
  (is_nullable, first, follow, predict)
 
(* The table maps (nonterminal, lookahead) to the rules that apply. The
   grammar is LL(1) when no cell holds more than one rule. *)
let table g =
  let _, _, _, predict = analyse g in
  let t = Hashtbl.create 32 in
  List.iter (fun ((a, _) as r) ->
      S.iter (fun x ->
          let old = Option.value ~default:[] (Hashtbl.find_opt t (a, x)) in
          Hashtbl.replace t (a, x) (old @ [r])) (predict r)) g.rules;
  t
 
let conflicts g =
  Hashtbl.fold (fun k rs acc -> if List.length rs > 1 then (k, rs) :: acc else acc) (table g) []
  |> List.sort compare
 
let show_rhs = function
  | [] -> "ε"
  | rhs -> String.concat " " (List.map (function T t | N t -> t) rhs)
let show_rule (a, rhs) = a ^ " → " ^ show_rhs rhs
let show_set s = "{" ^ String.concat ", " (S.elements s) ^ "}"

The usual expression grammar, with the left recursion removed.

open Ll1
 
(* The expression grammar with left recursion removed. *)
let expr = { start = "E"; rules = [
    "E",  [N "T"; N "E'"];
    "E'", [T "+"; N "T"; N "E'"];
    "E'", [];
    "T",  [N "F"; N "T'"];
    "T'", [T "*"; N "F"; N "T'"];
    "T'", [];
    "F",  [T "("; N "E"; T ")"];
    "F",  [T "id"] ] }

Running it. Empty cells, shown as dots, are syntax errors.

E   nullable false FIRST {(, id}      FOLLOW {$, )}
E'  nullable true  FIRST {+}          FOLLOW {$, )}
T   nullable false FIRST {(, id}      FOLLOW {$, ), +}
T'  nullable true  FIRST {*}          FOLLOW {$, ), +}
F   nullable false FIRST {(, id}      FOLLOW {$, ), *, +}
     id       +        *        (        )        $        
E    T E'     .        .        T E'     .        .        
E'   .        + T E'   .        .        ε        ε        
T    F T'     .        .        F T'     .        .        
T'   .        ε        * F T'   .        ε        ε        
F    id       .        .        ( E )    .        .        
conflicts: 0

§ 03

The parser

The table-driven parser keeps a stack of grammar symbols that remain to be matched, initially just the start symbol. If the top of the stack is a terminal, it must equal the next token, and both are removed. If it is a nonterminal $A$ , the parser looks up $A$ and the next token in the table and replaces $A$ by the right-hand side of that rule. The input is accepted when the stack and the input are both empty. Each step either consumes a token or expands a nonterminal, and for a grammar without cycles of nullable rules the number of expansions between two tokens is bounded, so the parser runs in linear time^[4].

The table-driven parser, printing each step.

open Ll1
 
(* The table-driven parser: a stack of symbols still to be matched. A
   terminal on top must equal the next token; a nonterminal is replaced
   by the right-hand side that the table selects for the next token. *)
let run g tokens =
  let t = table g in
  let words l = String.concat " " (List.map (function T x | N x -> x) l) in
  let rec loop stack input =
    let show action =
      Printf.printf "%-14s %-20s %s\n" (words stack) (String.concat " " input) action in
    match stack, input with
    | [], [ "$" ] -> show "accept"
    | T x :: rest, y :: ys when x = y -> show ("match " ^ x); loop rest ys
    | N a :: rest, y :: _ ->
      (match Hashtbl.find_opt t (a, y) with
       | Some [ ((_, rhs) as r) ] -> show (show_rule r); loop (rhs @ rest) input
       | _ -> show (Printf.sprintf "error: no rule for %s on %s" a y))
    | _, y :: _ -> show ("error: unexpected " ^ y)
    | _, [] -> assert false
  in
  Printf.printf "%-14s %-20s %s\n" "stack" "input" "action";
  loop [ N g.start ] (tokens @ [ "$" ])

Parsing id + id * id, and a syntax error.

stack          input                action
E              id + id * id $       E → T E'
T E'           id + id * id $       T → F T'
F T' E'        id + id * id $       F → id
id T' E'       id + id * id $       match id
T' E'          + id * id $          T' → ε
E'             + id * id $          E' → + T E'
+ T E'         + id * id $          match +
T E'           id * id $            T → F T'
F T' E'        id * id $            F → id
id T' E'       id * id $            match id
T' E'          * id $               T' → * F T'
* F T' E'      * id $               match *
F T' E'        id $                 F → id
id T' E'       id $                 match id
T' E'          $                    T' → ε
E'             $                    E' → ε
               $                    accept
--
stack          input                action
E              id + * id $          E → T E'
T E'           id + * id $          T → F T'
F T' E'        id + * id $          F → id
id T' E'       id + * id $          match id
T' E'          + * id $             T' → ε
E'             + * id $             E' → + T E'
+ T E'         + * id $             match +
T E'           * id $               error: no rule for T on *

The sequence of rules chosen is a leftmost derivation, and it spells out the parse tree from the top down, left to right. The parser detects an error as soon as the input read so far cannot be the beginning of any sentence of the language: here, on the * that follows +.

The parse tree that the parser built for id + id * id. The nonterminals E′ and T′ come from the removal of left recursion\; they make the tree deeper than the expression's structure, and turning the tree into a syntax tree requires some reshaping.

§ 04

Recursive descent

An LL(1) table is a compact description of a program with one procedure per nonterminal. The procedure for $A$ looks at the next token, chooses the rule the table would choose, and then, for each symbol of its right-hand side in order, either matches a terminal or calls the procedure of a nonterminal. The call stack of this recursive-descent parser plays the role of the explicit stack^[4]^[5]. Written by hand, the tail rules such as $E^{'} \to + T E^{'} ∣ ε$ become loops, which also give the operators their usual left associativity.

A recursive-descent parser for the same grammar, producing a syntax tree.

(* Recursive descent: one function per nonterminal, choosing a rule by
   looking at the next token. The tail rules E' and T' become loops,
   which also make + and * associate to the left. *)
type ast = Id of string | Add of ast * ast | Mul of ast * ast
 
let parse (tokens : string list) =
  let toks = ref tokens in
  let peek () = match !toks with t :: _ -> t | [] -> "$" in
  let advance () = toks := List.tl !toks in
  let expect t = if peek () = t then advance () else failwith ("expected " ^ t) in
  let rec e () =                            (* E → T E' *)
    let l = ref (t ()) in
    while peek () = "+" do advance (); l := Add (!l, t ()) done;
    !l
  and t () =                                (* T → F T' *)
    let l = ref (f ()) in
    while peek () = "*" do advance (); l := Mul (!l, f ()) done;
    !l
  and f () =                                (* F → ( E ) | id *)
    match peek () with
    | "(" -> advance (); let x = e () in expect ")"; x
    | "$" -> failwith "unexpected end of input"
    | tok when tok <> ")" && tok <> "+" && tok <> "*" -> advance (); Id tok
    | tok -> failwith ("unexpected " ^ tok)
  in
  let x = e () in
  if peek () <> "$" then failwith ("unexpected " ^ peek ()); x
 
let rec show = function
  | Id x -> x
  | Add (a, b) -> "(+ " ^ show a ^ " " ^ show b ^ ")"
  | Mul (a, b) -> "(* " ^ show a ^ " " ^ show b ^ ")"

Running it.

a + b * c              (+ a (* b c))
a * b + c              (+ (* a b) c)
a - b                  error: unexpected -
a + b + c              (+ (+ a b) c)
( a + b ) * c          (* (+ a b) c)
a + * b                error: unexpected *
( a + b                error: expected )

Recursive descent is easy to write, to debug and to extend with semantic actions and good error messages, and it is how many production compilers parse. GCC replaced its generated C++ parser with a hand-written recursive-descent parser in 2004^[11], and Clang, the Go and Rust compilers and most JavaScript engines parse by recursive descent. For expressions with many precedence levels, recursive descent is often combined with Pratt parsing, which handles precedence and associativity with a table of binding powers instead of one procedure per level. Parser combinators are a library form of recursive descent.

§ 05

Grammars that are not LL(1)

A left-recursive rule such as $E \to E + T$ can never be LL( $k$ ) for any $k$ : every token that can begin $E + T$ can also begin $T$ , and a recursive-descent procedure for $E$ would call itself without consuming input. Two rules that share a prefix, such as $S \to if c then S ∣ if c then S else S$ , also conflict. The standard transformations remove these problems^[4]:

A \to A α ∣ β ⇝ A A^{'} \to β A^{'} \to α A^{'} ∣ ε

A \to γ α ∣ γ β ⇝ A A^{'} \to γ A^{'} \to α ∣ β

The first is left-recursion elimination and the second left factoring. An ambiguous grammar is not LL( $k$ ) for any $k$ , and no transformation of this kind removes the ambiguity of the dangling else: after left factoring, the conflict remains.

The conflicts in a left-recursive grammar and in the left-factored dangling else.

open Ll1
 
(* Left recursion: both rules for E start with whatever starts E. *)
let left_recursive = { start = "E"; rules = [
    "E", [N "E"; T "+"; N "T"];
    "E", [N "T"];
    "T", [T "id"] ] }
 
(* The dangling else, after left factoring. *)
let dangling_else = { start = "S"; rules = [
    "S",  [T "if"; T "c"; T "then"; N "S"; N "S'"];
    "S",  [T "a"];
    "S'", [T "else"; N "S"];
    "S'", [] ] }

Running it.

left recursion:
  M[E, id] = E → E + T  |  E → T
dangling else:
  M[S', else] = S' → else S  |  S' → ε

Parsers resolve the dangling else by always choosing $S^{'} \to else S$ when the next token is $else$ , which attaches each $else$ to the nearest $if$ . The conflict entry is removed from the table by hand.

§ 06

Expressive power

Every LL( $k$ ) grammar is unambiguous and is also LR( $k$ ), so LR parsing handles strictly more grammars^[8]^[3]. The LL( $k$ ) languages form a strict hierarchy: for every $k$ there are languages that are LL( $k + 1$ ) but not LL( $k$ )^[12]. Some deterministic languages are not LL( $k$ ) for any $k$ , such as ${a^{n} b^{n} ∣ n \geq 1} \cup {a^{n} c^{n} ∣ n \geq 1}$ , where a top-down parser would have to decide between the two forms before seeing any $b$ or $c$ ^[10]. Rosenkrantz and Stearns showed that, unlike for context-free grammars in general, it is decidable whether two LL( $k$ ) grammars generate the same language^[2].

Parr and Fisher's LL(*) removes the fixed bound on lookahead by running a finite automaton over the remaining input to choose a rule^[6], and ALL(*), used by ANTLR 4, performs that analysis while parsing and accepts any grammar without left recursion, returning one parse of an ambiguous input^[7].

§ 07

History

Recursive-descent parsing was used in compilers by the early 1960s\; Lucas described it in 1961 for a compiler of ALGOL 60^[9]. Lewis and Stearns defined LL( $k$ ) grammars in 1968 in their study of syntax-directed translation^[1], and Rosenkrantz and Stearns developed their theory in 1970^[2]. Knuth's paper “Top-down syntax analysis” of 1971 related them to LR grammars and to the parsing methods of the time^[3]. Wirth designed Pascal and its successors so that they could be parsed by recursive descent with one token of lookahead, and taught the method through his textbooks^[5]. The table-driven formulation with FIRST and FOLLOW sets became standard through compiler textbooks such as Aho and Ullman's^[4], and Parr's ANTLR brought LL parser generators into wide use from the 1990s^[6]^[7].