33/216
\begin{frame}{Parsing}
\begin{goal}{}
\emph{Parsing} is the search for a derivation tree for a given word.
\end{goal}
\pause\bigskip

\begin{block}{Theorem}
For context-free grammars,
parsing is possible in \alert{$O(|w|^3)$} time.\\
(Here $|w|$ is the length of the input word.)
\end{block}
\pause\medskip

For every context-free grammar $G$,\\
there exists an algorithm and $C \ge 0$ such that for every
\begin{itemize}
\item word $w$,
\end{itemize}
the algorithm determines in at most \alert{$C \cdot |w|^3$ steps}
\begin{itemize}
\item whether $w \in L(G)$ (including a derivation tree if $w \in L(G)$).
\end{itemize}
\end{frame}