LL Parsers

LL Parsers implement a subset of CFGs which execute in O(n) time for an input of length n tokens, also known as predictive parsers.

Removal of Left Recursion
Given: $A \rightarrow A \alpha_1 \mid A \alpha_2 \mid \beta$
Replace $A$ productions by: $A \rightarrow \beta A'$,
where $A'$ is given by: $A' \rightarrow \alpha_1 A' \mid \alpha_2 A' \mid \varepsilon$
Example: $E \rightarrow E + T \mid T$ becomes:
$E \rightarrow T E'$
$E' \rightarrow + T E' \mid \varepsilon$

    E  -> T E'
    E' -> + T E' | e
    T  -> F T'
    T' -> * F T' | e
    F  -> ( E ) | id

Removal of left-recursion from precedence cascade grammar.

Left Factoring
Top-Down Parsing

LL(1) Grammars
FIRST & FOLLOW

Example Grammar
Recursive Descent

Recursive Descent Calculator: Fig4.1.c