Binary file hws/hw07.pdf has changed

--- a/hws/hw07.tex	Thu Nov 10 23:49:29 2022 +0000
+++ b/hws/hw07.tex	Tue Nov 15 11:34:33 2022 +0000
@@ -13,9 +13,9 @@
 
 \begin{center}
 \begin{tabular}{lcl}
-$S$ & $\rightarrow$ &  $bSAA\;|\; \epsilon$\\
-$A$ & $\rightarrow$ & $a$\\
-$bA$ & $\rightarrow$ & $Ab$\\
+$S$ & $::=$ &  $bSAA\;|\; \epsilon$\\
+$A$ & $::=$ & $a$\\
+$bA$ & $::=$ & $Ab$\\
 \end{tabular}
 \end{center}
 
@@ -50,8 +50,8 @@
 
 \begin{center}
 \begin{tabular}{lcl}
-$A$ & $\rightarrow$ & $0A1 \;|\; BB$\\
-$B$ & $\rightarrow$ & $\epsilon \;|\; 2B$
+$A$ & $::=$ & $0A1 \;|\; BB$\\
+$B$ & $::=$ & $\epsilon \;|\; 2B$
 \end{tabular}
 \end{center}
 
@@ -62,14 +62,14 @@
 
 \begin{center}
 \begin{tabular}{l}
-$S \rightarrow \texttt{if0} \cdot E \cdot \texttt{then} \cdot S$\\
-$S \rightarrow \texttt{print} \cdot S$\\
-$S \rightarrow \texttt{begin} \cdot B\cdot \texttt{end}$\\
-$B \rightarrow S\cdot \texttt{;}$\\
-$B \rightarrow S\cdot \texttt{;} \cdot B$\\
-$S \rightarrow num$\\
-$E \rightarrow num$\\
-$B \rightarrow num$
+$S ::= \texttt{if0} \cdot E \cdot \texttt{then} \cdot S$\\
+$S ::= \texttt{print} \cdot S$\\
+$S ::= \texttt{begin} \cdot B\cdot \texttt{end}$\\
+$B ::= S\cdot \texttt{;}$\\
+$B ::= S\cdot \texttt{;} \cdot B$\\
+$S ::= num$\\
+$E ::= num$\\
+$B ::= num$
 \end{tabular}
 \end{center}
 
@@ -82,14 +82,37 @@
 
 \begin{center}
 \begin{tabular}{rl}
-(i)   & $S \rightarrow \texttt{if0} \cdot E\cdot \texttt{then} \cdot S\cdot \texttt{else} \cdot S$\\
-(ii)  & $B \rightarrow B \cdot B$\\
-(iii) & $E \rightarrow ( \cdot E \cdot )$\\
-(iv)  & $E \rightarrow E \cdot + \cdot E$
+(i)   & $S ::= \texttt{if0} \cdot E\cdot \texttt{then} \cdot S\cdot \texttt{else} \cdot S$\\
+(ii)  & $B ::= B \cdot B$\\
+(iii) & $E ::= ( \cdot E \cdot )$\\
+(iv)  & $E ::= E \cdot + \cdot E$
 \end{tabular}
 \end{center}
 
 
+\item Suppose the string $``9-5+2''$. Give all ASTs that
+  the following two grammars generate for this string.
+
+Grammar 1, where List is the starting symbol:
+
+\begin{center}
+\begin{tabular}{lcl}
+$List$ & $::=$ &  $List + Digit \mid List - Digit \mid Digit$\\
+$Digit$ & $::=$ & $0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9$
+\end{tabular}
+\end{center}
+
+Grammar 2, where String is the starting symbol:
+
+\begin{center}
+\begin{tabular}{@{}lcl@{}}
+  $String$ & $::=$ & $String + String \mid String - String \mid$\\
+  & & $0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9$
+\end{tabular}
+\end{center}
+
+
+                   
 %\item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, 
 %\texttt{abcfjz} would pass, but \texttt{acb} would not. Whitespace should be ignored---for example
 %\texttt{ab c d} should pass. The point is to try to get the regular expression as short as possible!

--- a/progs/parser-combinators/comb1.sc	Thu Nov 10 23:49:29 2022 +0000
+++ b/progs/parser-combinators/comb1.sc	Tue Nov 15 11:34:33 2022 +0000
@@ -50,6 +50,7 @@
     if (in != "" && in.head == c) Set((c, in.tail)) else Set()
 }
 
+CharParser('c').parse("abc")
 
 // an atomic parser for parsing strings according to a regex
 import scala.util.matching.Regex
@@ -65,23 +66,27 @@
 val NumParser = RegexParser("[0-9]+".r)
 def StrParser(s: String) = RegexParser(Regex.quote(s).r)
 
+NumParser.parse("a123a123bc") 
+StrParser("else").parse("eelsethen")
 
 
 // NumParserInt transforms a "string integer" into a propper Int
 // (needs "new" because MapParser is not a case class)
 
 val NumParserInt = new MapParser(NumParser, (s: String) => s.toInt)
-
+NumParserInt.parse("123abc")
 
 // the following string interpolation allows us to write 
 // StrParser(_some_string_) more conveniently as 
 //
 // p"<_some_string_>" 
 
+
 implicit def parser_interpolation(sc: StringContext) = new {
   def p(args: Any*) = StrParser(sc.s(args:_*))
 }
-           
+
+(p"else").parse("elsethen")           
 
 // more convenient syntax for parser combinators
 implicit def ParserOps[I : IsSeq, T](p: Parser[I, T]) = new {
@@ -90,6 +95,10 @@
   def map[S](f: => T => S) = new MapParser[I, T, S](p, f)
 }
 
+def toU(s: String) = s.map(_.toUpper)
+
+(p"ELSE").map(toU(_)).parse("ELSEifthen")  
+
 // these implicits allow us to use an infix notation for
 // sequences and alternatives; we also can write the usual
 // map for a MapParser
@@ -101,9 +110,11 @@
 val NumParserInt2 = NumParser.map(_.toInt)
 
 
+
+
 // A parser for palindromes (just returns them as string)
 lazy val Pal : Parser[String, String] = {
-  ((p"a" ~ Pal) ~ p"a").map{ case ((x, y), z) => s"$x$y$z" } || 
+   (p"a" ~ Pal ~ p"a").map{ case ((x, y), z) => s"$x$y$z" } || 
    (p"b" ~ Pal ~ p"b").map{ case ((x, y), z) => s"$x$y$z" } || 
     p"a" || p"b" || p""
 }  
@@ -130,7 +141,7 @@
 println(P.parse_all("()"))
 
 // A parser for arithmetic expressions (Terms and Factors)
-
+{
 lazy val E: Parser[String, Int] = {
   (T ~ p"+" ~ E).map{ case ((x, _), z) => x + z } ||
   (T ~ p"-" ~ E).map{ case ((x, _), z) => x - z } || T }
@@ -138,7 +149,7 @@
   (F ~ p"*" ~ T).map{ case ((x, _), z) => x * z } || F }
 lazy val F: Parser[String, Int] = {
   (p"(" ~ E ~ p")").map{ case ((_, y), _) => y } || NumParserInt }
-
+}
 println(E.parse_all("1+3+4"))
 println(E.parse("1+3+4"))
 println(E.parse_all("4*2+3"))