\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$: \begin{itemize} \item there exists an algorithm and $C \ge 0$ such that \item for every word $w$, the algorithm determines in at most \begin{center} \alert{$C \cdot |w|^3$ steps} \end{center} whether $w \in L(G)$ and a derivation tree if $w \in L(G)$. \end{itemize} \end{frame}