\begin{frame}{LL$(1)$ Grammars and Parsing}
  \begin{block}{}
    A grammar is \alert{LL$(1)$} if its parser table contains in ever cell $[a \in T \cup \{\$\},B \in V]$
    at most one production rule.
  \end{block}
  \pause
  
  \begin{goal}{}
    An LL$(1)$ parser reads from \alert{L}eft to right,
    performs a \alert{L}eftmost derivation,
    and looks always at \alert{1} symbol of the input.
  \end{goal}
  \pause
  
  \begin{block}{}
  Given an LL$(1)$-grammar and parsing table.
  \pause\medskip
    
  To parse $a_1\cdots a_n$, we start with \alert{$\langle S\$,a_1\cdots a_n\$\rangle$}.
  \pause\medskip
  
  From a state \alert{$\langle v,w\rangle$} %, met $v\in(V\cup T)^*\$$ and $w\in T^*\$$,
  we can do the following steps:
  \begin{itemize}
  \pause  
    \item \alert{$\langle av',aw'\rangle$} becomes \alert{$\langle v',w'\rangle$}
  \pause  
    \item \alert{$\langle Bv',aw'\rangle$} becomes \alert{$\langle uv',aw'\rangle$} if \alert{$B\to u$} at position \alert{$[a,B]$}
  \pause  
    \item \alert{$\langle Bv',\$\rangle$} becomes \alert{$\langle v',\$\rangle$} if \alert{$B\to u$} at position \alert{$[\$,B]$}
  \pause  
    \item \alert{$\langle\$,\$\rangle$} results in \alert{\emph{accept}}
  \pause  
    \item In all other cases, $\langle v,w\rangle$ results in \alert{\emph{reject}}!
  \end{itemize}
  \end{block}  
\end{frame}