\begin{frame}{Left Factorisation}
  
  \begin{goal}{}
    \emph{Left factorisation}: rewrite rules \alert{$A \to uv \mid uw$} (\alert{$u\neq\lambda$}) 
    into
    \begin{talign}
      \alert{A \to uB} &&\text{ and } && \alert{B \to v \mid w}
    \end{talign}
    where $B$ is a fresh variable.
  \end{goal}
  \pause
  
  \begin{exampleblock}{}
    The grammar $S \to ab \mid ac$ is \emph{not} LL$(1)$:
    \begin{talign}
      \begin{array}{l|cccc}
      & a & b & c & \$ \\
      \hline
      S & ~S\to ab~ \\
      & ~S \to ac~
      \end{array}
    \end{talign}
  \end{exampleblock}
  \pause
  
  After left factorisation we get: \quad $S \to aA$ \quad $A \to b\mid c$
  \begin{exampleblock}{}
    The grammar $S \to aA$, $A \to b\mid c$ \emph{is} LL$(1)$:
    \begin{talign}
      \begin{array}{l|cccc}
      & a & b & c & \$ \\
      \hline
      S & ~S\to aA \\
      A & & ~A \to b~ & ~A \to c~
      \end{array}
    \end{talign}
  \end{exampleblock}
  
\end{frame}