ll1

LL(1) Grammar

L = Left-to-right scan

R = Right-to-left parse

CFG to LL(1)

Requirements for LL(1) Grammar

1. Remove any ambiguity.
2. Eliminate any left recursion.
3. Eliminate any common left prefixes.

Eliminating Left Recursion

Convert:

$$A\to A{\alpha }_1\mid A{\alpha }_2\mid \cdots \mid {\beta }_1\mid {\beta }_2\mid \dots$$

into:

$$\{\begin{array}{llc}A& \to & {\beta }_1{A}^{\prime }\mid {\beta }_2{A}^{\prime }\mid \dots \\ A^{\prime }& \to & {\alpha }_1{A}^{\prime }\mid {\alpha }_2{A}^{\prime }\mid \cdots \mid ϵ\end{array}$$

1. Observe that $A$ must start with $\beta$.
2. Make $A$ $\beta$ followed by another non-terminal. (make it right-recursive)
3. The other non-terminal may start with $\alpha$, or may be $ϵ$.

Eliminating Common Left Prefixes

Convert:

$$A\to \alpha {\beta }_1\mid \alpha {\beta }_2\mid \dots$$

into:

$$\{\begin{array}{llc}A& \to & \alpha A^{\prime }\\ A^{\prime }& \to & {\beta }_1\mid {\beta }_2\mid \dots \end{array}$$

1. Notice all the possibilities of $A$ starts with $\alpha$.
2. Make $A\to \alpha A^{\prime }$.
3. Make $A^{\prime }$ possibilities that follow $\alpha$.