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"))

--- a/solutions/cw2/lexer.sc	Thu Nov 10 23:49:29 2022 +0000
+++ b/solutions/cw2/lexer.sc	Tue Nov 15 11:34:33 2022 +0000
@@ -196,6 +196,11 @@
   }
 }
 
+def ders_simp(cs: List[Char], r: Rexp) : Rexp = cs match {
+  case Nil => r
+  case c::cs => ders_simp(cs, simp(der(c, r))._1)
+} 
+
 def lexing_simp(r: Rexp, s: String) = env(lex_simp(r, s.toList))
 
 // Language specific code
@@ -221,7 +226,7 @@
                   ("w" $ WHITESPACE) | 
                   ("i" $ ID) | 
                   ("n" $ NUM) |
-		  ("c" $ COMMENT)).%
+		              ("c" $ COMMENT)).%
 
 def esc(raw: String): String = {
   import scala.reflect.runtime.universe._
@@ -346,7 +351,10 @@
   case ALT(r1, r2) => 1 + size(r1) + size (r2)
   case SEQ(r1, r2) => 1 + size(r1) + size (r2)
   case STAR(r1) => 1 + size(r1)
+  case PLUS(r1) => 1 + size(r1)
   case NTIMES(r1, n) => 1 + size(r1)
+  case RECD(_, r1) => 1 + size(r1)
+  case RANGE(_) => 1
 }
 
 val reg = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
@@ -355,3 +363,10 @@
 size(simp(der('a', reg))._1) // 8
 size(simp(der('a', der('a', reg)))._1) // 8
 
+
+
+// python tests
+println(size(WHILE_REGS))
+println(size(ders_simp("r".toList, WHILE_REGS)))
+println(size(ID))
+println(size(ders_simp("read".toList, ID)))