# LL(1) Grammar L = Left-to-right scan R = Right-to-left parse ## [[cfg|CFG]] to LL(1) > [!info] Requirements for LL(1) Grammar > > 1. Remove any **[[cfg#ambiguity|ambiguity]]**. > 2. Eliminate any **left recursion**. > 3. Eliminate any **common left prefixes**. ### Eliminating Left Recursion Convert: $ A \rightarrow A\alpha_1 \mid A\alpha_2 \mid \dots \mid \beta_1 \mid \beta_2 \mid \dots $ into: $ \begin{cases} A & \rightarrow & \beta_1A' \mid \beta_2A' \mid \dots \\ A' & \rightarrow & \alpha_1A' \mid \alpha_2A' \mid \dots \mid \epsilon \end{cases} $ 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 $\epsilon$. ### Eliminating Common Left Prefixes Convert: $ A \rightarrow \alpha\beta_1 \mid \alpha\beta_2 \mid \dots $ into: $ \begin{cases} A & \rightarrow & \alpha A'\\ A' & \rightarrow & \beta_1 \mid \beta_2 \mid \dots \end{cases} $ 1. Notice all the possibilities of $A$ starts with $\alpha$. 2. Make $A \rightarrow \alpha A'$. 3. Make $A'$ possibilities that follow $\alpha$.