Binary file handouts/ho05.pdf has changed

--- a/handouts/ho05.tex	Tue Oct 20 00:01:56 2015 +0100
+++ b/handouts/ho05.tex	Fri Oct 23 00:16:00 2015 +0100
@@ -5,7 +5,7 @@
 
 \begin{document}
 
-\section*{Handout 6 (Parser Combinators)}
+\section*{Handout 6 (Grammars \& Parser)}
 
 While regular expressions are very useful for lexing and for recognising
 many patterns in strings (like email addresses), they have their limitations. For

--- a/progs/comb1.scala	Tue Oct 20 00:01:56 2015 +0100
+++ b/progs/comb1.scala	Fri Oct 23 00:16:00 2015 +0100
@@ -5,20 +5,24 @@
   def parse(ts: I): Set[(T, I)]
 
   def parse_all(ts: I) : Set[T] =
-    for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head
+    for ((head, tail) <- parse(ts); 
+        if (tail.isEmpty)) yield head
 }
 
-class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] {
+class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], 
+                                   q: => Parser[I, S]) extends Parser[I, (T, S)] {
   def parse(sb: I) = 
     for ((head1, tail1) <- p.parse(sb); 
          (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2)
 }
 
-class AltParser[I <% Seq[_], T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] {
+class AltParser[I <% Seq[_], T](p: => Parser[I, T], 
+                                q: => Parser[I, T]) extends Parser[I, T] {
   def parse(sb: I) = p.parse(sb) ++ q.parse(sb)   
 }
 
-class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] {
+class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], 
+                                   f: T => S) extends Parser[I, S] {
   def parse(sb: I) = 
     for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
 }
@@ -44,7 +48,7 @@
   }
 }
 
-
+// convenience
 implicit def string2parser(s : String) = StringParser(s)
 
 implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new {
@@ -63,16 +67,14 @@
     new SeqParser[String, String, String](s, r)
 }
 
-
-
-
+// palindromes
 lazy val Pal : Parser[String, String] = 
   (("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } ||
    ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "")
 
-println("Palindrom" + Pal.parse_all("ababbaba"))
+println("Palindrom: " + Pal.parse_all("ababbaba"))
 
-
+// well-nested parenthesis
 lazy val P : Parser[String, String] = 
   "(" ~ P ~ ")" ~ P ==> { case (((u, x), y), z) => "{" + x + "}" + z } || ""
 
@@ -80,6 +82,7 @@
 P.parse_all("(((()()))()))")
 P.parse_all(")(")
 
+// arithmetic expressions
 lazy val E: Parser[String, String] = 
   (F ~ "*" ~ F) ==> { case ((x, y), z) => x + y + z } || F  
 lazy val F: Parser[String, String] = 

Binary file slides/slides05.pdf has changed

--- a/slides/slides05.tex	Tue Oct 20 00:01:56 2015 +0100
+++ b/slides/slides05.tex	Fri Oct 23 00:16:00 2015 +0100
@@ -418,9 +418,9 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Grammars}
+\frametitle{CF Grammars}
 
-A (context-free) grammar \bl{$G$} consists of
+A \alert{\bf context-free grammar} \bl{$G$} consists of
 
 \begin{itemize}
 \item a finite set of nonterminal symbols (upper case)
@@ -569,19 +569,22 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Context Sensitive Grms}
+\frametitle{\begin{tabular}{c}Context Sensitive\\[-1mm] 
+             Grammars\end{tabular}}
 
+It is much harder to find out whether a string is parsed
+by a context sensitive grammar:
 
 \begin{center}
 \bl{\begin{tabular}{lcl}
-$S$ & $\Rightarrow$ &  $bSAA\;|\; \epsilon$\\
-$A$ & $\Rightarrow$ & $a$\\
-$bA$ & $\Rightarrow$ & $Ab$\\
+$S$ & $\rightarrow$ &  $bSAA\;|\; \epsilon$\\
+$A$ & $\rightarrow$ & $a$\\
+$bA$ & $\rightarrow$ & $Ab$\\
 \end{tabular}}
 \end{center}\pause
 
 \begin{center}
-\bl{$S \Rightarrow\ldots\Rightarrow^? "ababaa"$}
+\bl{$S \rightarrow\ldots\rightarrow^? "ababaa"$}
 \end{center}
 
 \end{frame}