# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1384212278 0
# Node ID ea8b94d4755ecd50e2b3668a80afaf9695f3ad33
# Parent  2e9134d25a2baf27ebd5c4def4ccc374bb4acda1
added

diff -r 2e9134d25a2b -r ea8b94d4755e handouts/ho06.pdf
Binary file handouts/ho06.pdf has changed
diff -r 2e9134d25a2b -r ea8b94d4755e progs/comb1.scala
--- a/progs/comb1.scala	Mon Nov 11 15:26:20 2013 +0000
+++ b/progs/comb1.scala	Mon Nov 11 23:24:38 2013 +0000
@@ -70,7 +70,7 @@
   (("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } ||
    ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "")
 
-Pal.parse_all("ababbaba")
+println("Palindrom" + Pal.parse_all("ababbaba"))
 
 
 lazy val P : Parser[String, String] = 
@@ -88,11 +88,11 @@
 lazy val T: Parser[String, String] = 
   ("(" ~ E ~ ")") ==> { case ((x, y), z) => x + y + z } || NumParser
 
-
+println(E.parse_all("1*2+3"))
+println(E.parse_all("1+2*3"))
 println(E.parse_all("1+2+3"))
 
 
-
 // non-ambiguous vs ambiguous
 lazy val U : Parser[String, String] =
   ("1" ~ U) ==> { case (x, y) => x + y } || ""
diff -r 2e9134d25a2b -r ea8b94d4755e progs/comb2.scala
--- a/progs/comb2.scala	Mon Nov 11 15:26:20 2013 +0000
+++ b/progs/comb2.scala	Mon Nov 11 23:24:38 2013 +0000
@@ -67,6 +67,9 @@
 lazy val F: Parser[String, Int] = 
   ("(" ~ E ~ ")") ==> { case ((x, y), z) => y} || NumParser
 
+println(E.parse_all("1*2+3"))
+println(E.parse_all("1+2*3"))
+println(E.parse_all("1+2+3"))
 println(E.parse_all("1+2+3"))
 println(E.parse_all("1+2*3+1"))
 
diff -r 2e9134d25a2b -r ea8b94d4755e slides/slides07.pdf
Binary file slides/slides07.pdf has changed
diff -r 2e9134d25a2b -r ea8b94d4755e slides/slides07.tex
--- a/slides/slides07.tex	Mon Nov 11 15:26:20 2013 +0000
+++ b/slides/slides07.tex	Mon Nov 11 23:24:38 2013 +0000
@@ -152,10 +152,32 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}
+
+A grammar for arithmetic expressions and numbers:
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\
+$N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1 \;|\: \ldots \;|\; 9$ 
+\end{tabular}}
+\end{center}
+
+Unfortunately left-recursive (and ambiguous).\medskip\\
+A problem for \alert{recursive descent parsers} (e.g.~parser combinators).
+\bigskip\pause
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
 \begin{frame}[t]
 \frametitle{\begin{tabular}{c}Numbers\end{tabular}}
 
-A grammar for numbers:
+
 
 \begin{center}
 \bl{\begin{tabular}{lcl}
@@ -163,15 +185,84 @@
 \end{tabular}}
 \end{center}
 
-Unfortunately left-recursive (and ambiguous).\medskip\\
-A problem for \alert{recursive descent parsers} (e.g.~parser combinators).
-\bigskip\pause
+A non-left-recursive, non-ambiguous grammar for numbers
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$N$ & $\rightarrow$ &  $0 \cdot N \;|\;1 \cdot N \;|\;\ldots\;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\
+\end{tabular}}
+\end{center}
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
-A non-left-recursive grammar for numbers
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Operator Precedences\end{tabular}}
+
+
+To disambiguate
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\
+\end{tabular}}
+\end{center}
+
+Decide how many precedence levels, say\medskip\\
+\hspace{5mm}highest for \bl{$()$}, medium for \bl{*}, lowest for \bl{+}
 
 \begin{center}
 \bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ &  $0 \cdot N \;|\;1 \cdot N \;|\ldots\;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\
+$E_{low}$ & $\rightarrow$ & $E_{med} \cdot + \cdot E_{low} \;|\; E_{med}$ \\
+$E_{med}$ & $\rightarrow$ & $E_{hi} \cdot * \cdot E_{med} \;|\; E_{hi}$\\
+$E_{hi}$ & $\rightarrow$ &  $( \cdot E_{low} \cdot ) \;|\;N$ \\
+\end{tabular}}
+\end{center}\pause
+
+\small What happens with \bl{$1 + 3  + 4$}?
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Removing Left-Recursion\end{tabular}}
+
+The rule for numbers is directly left-recursive:
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1\;\;\;\;(\ldots)$ 
+\end{tabular}}
+\end{center}
+
+Translate
+
+\begin{center}
+\begin{tabular}{ccc}
+\bl{\begin{tabular}{lcl}
+$N$ & $\rightarrow$ & $N \cdot \alpha$\\
+ &  $\;|\;$ & $\beta$\\
+ \\ 
+\end{tabular}} 
+& {\Large$\Rightarrow$} &
+\bl{\begin{tabular}{lcl}
+$N$ & $\rightarrow$ & $\beta \cdot N'$\\
+$N'$ & $\rightarrow$ & $\alpha \cdot N'$\\
+ &  $\;|\;$ & $\epsilon$ 
+\end{tabular}}
+\end{tabular}
+\end{center}\pause
+
+Which means
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1 \cdot N'$\\
+$N'$ & $\rightarrow$ & $N \cdot N' \;|\; \epsilon$\\
 \end{tabular}}
 \end{center}
 
@@ -196,10 +287,42 @@
 \bl{$A \rightarrow B\cdot C$}
 \end{center}
 
+No rule can contain \bl{$\epsilon$}.
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}$\epsilon$-Removal\end{tabular}}
+
+\begin{enumerate}
+\item If \bl{$A\rightarrow \alpha \cdot B \cdot \beta$} and \bl{$B \rightarrow \epsilon$} are in the grammar,
+then add \bl{$A\rightarrow \alpha \cdot \beta$} (iterate if necessary).
+\item Throw out all \bl{$B \rightarrow \epsilon$}.
+\end{enumerate}
+
+\small
+\begin{center}
+\begin{tabular}{ccc}
+\bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
+$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'$\\
+$N'$ & $\rightarrow$ & $N \cdot N'\;|\;\epsilon$ 
+\end{tabular}} &
+\bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
+$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
+$N'$ & $\rightarrow$ & $N \cdot N'\;|\;N\;|\;\epsilon$ 
+\end{tabular}}
+\end{tabular}
+\end{center}
 
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]