6 

     6 \usepackage{../grammar}

    31   Office: & N7.07 (North Wing, Bush House)\\

    31   Office: & N\liningnums{7.07} (North Wing, Bush House)\\

   121 \item you consume one or more token from the\\ 

   121 \item you consume one or more tokens from the\\ 

   230 \begin{center}

   230 \bl{\begin{plstx}[margin=3cm]

   231 \bl{\begin{tabular}{lcl}

   231 : \meta{S} ::= \liningnums{1}\cdot\meta{S}\cdot \meta{S} | \epsilon\\

   232 $S$ & $\rightarrow$ &  $1 \cdot S \cdot S$\\

   232 \end{plstx}}

   233         & $|$ & $\epsilon$

   233 

   234 \end{tabular}}

   234 \bl{\begin{plstx}[margin=3cm]

   235 \end{center}\bigskip

   235 : \meta{U} ::= \liningnums{1}\cdot\meta{U} | \epsilon\\

   236 

   236 \end{plstx}}

   237 \begin{center}

   238 \bl{\begin{tabular}{lcl}

   239 $U$ & $\rightarrow$ &  $1 \cdot U$\\

   240         & $|$ & $\epsilon$

   241 \end{tabular}}

   242 \end{center}

   280 \mode<presentation>{

   274 \begin{frame}[c]

   281 \begin{frame}[c]

   275 \frametitle{Arithmetic Expressions}

   282 \frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}

   288 $E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\

   322 $\meta{N}$ & $::=$ & $\meta{N} \cdot \meta{N} \;|\; 0 \;|\; 1\;\;\;\;(\ldots)$ 

   289 $N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1 \;|\: \ldots \;|\; 9$ 

   290 \end{tabular}}

   291 \end{center}

   292 

   293 Unfortunately it is left-recursive (and ambiguous).\medskip\\

   294 A problem for \alert{recursive descent parsers} (e.g.~parser combinators).

   295 \bigskip\pause

   296 

   297 \end{frame}}

   298 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   299 

   300 

   301 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   302 \mode<presentation>{

   303 \begin{frame}[t]

   304 \frametitle{\begin{tabular}{c}Numbers\end{tabular}}

   305 

   306 

   307 

   308 \begin{center}

   309 \bl{\begin{tabular}{lcl}

   310 $N$ & $\rightarrow$ &  $N \cdot N \;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\

   311 \end{tabular}}

   312 \end{center}

   313 

   314 A non-left-recursive, non-ambiguous grammar for numbers:

   315 

   316 \begin{center}

   317 \bl{\begin{tabular}{lcl}

   318 $N$ & $\rightarrow$ &  $0 \cdot N \;|\;1 \cdot N \;|\;\ldots\;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\

   319 \end{tabular}}

   320 \end{center}

   321 

   322 

   323 \end{frame}}

   324 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   325 

   326 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   327 \mode<presentation>{

   328 \begin{frame}[c]

   329 \frametitle{\begin{tabular}{c}Removing Left-Recursion\end{tabular}}

   330 

   331 The rule for numbers is directly left-recursive:

   332 

   333 \begin{center}

   334 \bl{\begin{tabular}{lcl}

   335 $N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1\;\;\;\;(\ldots)$ 

   344 $N$ & $\rightarrow$ & $N \cdot \alpha$\\

   331 $\meta{N}$ & $::=$ & $\meta{N} \cdot \alpha$\\

   350 $N$ & $\rightarrow$ & $\beta \cdot N'$\\

   337 $\meta{N}$ & $::=$ & $\beta \cdot \meta{N}'$\\

   351 $N'$ & $\rightarrow$ & $\alpha \cdot N'$\\

   338 $\meta{N}'$ & $::=$ & $\alpha \cdot \meta{N}'$\\

   357 Which means

   344 Which means in this case:

   361 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1 \cdot N'$\\

   348 $\meta{N}$ & $\rightarrow$ & $0 \cdot \meta{N}' \;|\; 1 \cdot \meta{N}'$\\

   362 $N'$ & $\rightarrow$ & $N \cdot N' \;|\; \epsilon$\\

   349 $\meta{N}'$ & $\rightarrow$ & $\meta{N} \cdot \meta{N}' \;|\; \epsilon$\\

   363 \end{tabular}}

   350 \end{tabular}}

   364 \end{center}

   351 \end{center}

   365 

   352 

   366 

   353 

   367 \end{frame}}

   354 \end{frame}

   368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   355 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   369 

   356 

   370 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   357 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   371 \mode<presentation>{

   358 \begin{frame}[c]

   372 \begin{frame}[c]

   359 \frametitle{Operator Precedences}

   373 \frametitle{\begin{tabular}{c}Operator Precedences\end{tabular}}

   380 $E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\

   366 $\meta{E}$ & $::=$ &  $\meta{E} \cdot + \cdot \meta{E} \;|\;\meta{E} \cdot * \cdot \meta{E} \;|\;( \cdot \meta{E} \cdot ) \;|\;\meta{N}$ \\

   385 \hspace{5mm}highest for \bl{$()$}, medium for \bl{*}, lowest for \bl{+}

   371 highest for \bl{$()$}, medium for \bl{*}, lowest for \bl{+}

   389 $E_{low}$ & $\rightarrow$ & $E_{med} \cdot + \cdot E_{low} \;|\; E_{med}$ \\

   375 $\meta{E}_{low}$ & $::=$ & $\meta{E}_{med} \cdot + \cdot \meta{E}_{low} \;|\; \meta{E}_{med}$ \\

   390 $E_{med}$ & $\rightarrow$ & $E_{hi} \cdot * \cdot E_{med} \;|\; E_{hi}$\\

   376 $\meta{E}_{med}$ & $::=$ & $\meta{E}_{hi} \cdot * \cdot \meta{E}_{med} \;|\; \meta{E}_{hi}$\\

   391 $E_{hi}$ & $\rightarrow$ &  $( \cdot E_{low} \cdot ) \;|\;N$ \\

   377 $\meta{E}_{hi}$ & $::=$ &  $( \cdot \meta{E}_{low} \cdot ) \;|\;\meta{N}$ \\

   396 \end{frame}}

   382 \end{frame}

   397 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   383 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   398 

   384 

   399 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   385 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   400 \mode<presentation>{

   386 \begin{frame}[c]

   401 \begin{frame}[c]

   387 \frametitle{Chomsky Normal Form}

   402 \frametitle{\begin{tabular}{c}Chomsky Normal Form\end{tabular}}

   407 \bl{$A \rightarrow a$}

   392 \bl{$\meta{A} ::= a$}

   413 \bl{$A \rightarrow B\cdot C$}

   398 \bl{$\meta{A} ::= \meta{B}\cdot \meta{C}$}

   418 \end{frame}}

   403 \end{frame}

   426 \item If \bl{$A\rightarrow \alpha \cdot B \cdot \beta$} and \bl{$B \rightarrow \epsilon$} are in the grammar,

   411 \item If \bl{$A::= \alpha \cdot B \cdot \beta$} and \bl{$B ::= \epsilon$} are in the grammar,

   427 then add \bl{$A\rightarrow \alpha \cdot \beta$} (iterate if necessary).

   412 then add \bl{$A::= \alpha \cdot \beta$} (iterate if necessary).

   428 \item Throw out all \bl{$B \rightarrow \epsilon$}.

   413 \item Throw out all \bl{$B ::= \epsilon$}.

   435 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'$\\

   420 $N$ & $::=$ & $0 \cdot N' \;|\; 1\cdot N'$\\

   436 $N'$ & $\rightarrow$ & $N \cdot N'\;|\;\epsilon$\\

   421 $N'$ & $::=$ & $N \cdot N'\;|\;\epsilon$\\

   445 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\

   430 $N$ & $::=$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\

   446 $N'$ & $\rightarrow$ & $N \cdot N'\;|\;N\;|\;\epsilon$\\

   431 $N'$ & $::=$ & $N \cdot N'\;|\;N\;|\;\epsilon$\\

   448 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\

   433 $N$ & $::=$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\

   449 $N'$ & $\rightarrow$ & $N \cdot N'\;|\;N$\\

   434 $N'$ & $::=$ & $N \cdot N'\;|\;N$\\

   457 $N$ & $\rightarrow$ & $0 \cdot N\;|\; 1\cdot N\;|\;0\;|\;1$\\

   442 $N$ & $::=$ & $0 \cdot N\;|\; 1\cdot N\;|\;0\;|\;1$\\

   458 \end{tabular}}

   443 \end{tabular}}

   459 

   444 

   460 \end{center}

   445 \end{center}

   461 \end{frame}

   446 \end{frame}

   462 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   447 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   463 

   448 

   464 

   449 

   465 

   450 

   466 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   451 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   467 \mode<presentation>{

   452 \begin{frame}[c]

   468 \begin{frame}[c]

   453 \frametitle{CYK Algorithm}

   469 \frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}

   475 $S$ & $\rightarrow$ &  $N\cdot P$ \\

   459 $\meta{S}$ & $::=$ &  $\meta{N}\cdot \meta{P}$ \\

   476 $P$ & $\rightarrow$ &  $V\cdot N$ \\

   460 $\meta{P}$ & $::=$ &  $\meta{V}\cdot \meta{N}$ \\

   477 $N$ & $\rightarrow$ &  $N\cdot N$ \\

   461 $\meta{N}$ & $::=$ &  $\meta{N}\cdot \meta{N}$ \\

   478 $N$ & $\rightarrow$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\

   462 $\meta{N}$ & $::=$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\

   479 $V$ & $\rightarrow$ &  $\texttt{trains}$ 

   463 $\meta{V}$ & $::=$ &  $\texttt{trains}$ 

   485 \end{frame}}

   469 \end{frame}

   486 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   470 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   487 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   471 

   488 \mode<presentation>{

   472 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   489 \begin{frame}[c]

   473 \begin{frame}[c]

   490 \frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}

   474 \frametitle{CYK Algorithm}

   496 \item grammars need to be transferred into CNF

   480 \item grammars need to be transformed into CNF

   497 \end{itemize}

   481 \end{itemize}

   498 

   482 

   499 \end{frame}}

   483 \end{frame}

   548 \textit{Stmt} & $\rightarrow$ &  $\texttt{skip}$\\

   532 \textit{Stmt} & $::=$ &  $\texttt{skip}$\\

   555 \textit{Stmts} & $\rightarrow$ &  \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\

   539 \textit{Stmts} & $::=$ &  \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\

   557 \textit{Block} & $\rightarrow$ &  \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\

   541 \textit{Block} & $::=$ &  \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\

   559 \textit{AExp} & $\rightarrow$ & \ldots\\

   543 \textit{AExp} & $::=$ & \ldots\\

   560 \textit{BExp} & $\rightarrow$ & \ldots\\

   544 \textit{BExp} & $::=$ & \ldots\\