# HG changeset patch # User Christian Urban # Date 1668512073 0 # Node ID 904de68a27a42095aa248be5a1847fb71d7a4a51 # Parent b7a6436c7758415ae582cd868c0b40326f268963 updated diff -r b7a6436c7758 -r 904de68a27a4 hws/hw07.pdf Binary file hws/hw07.pdf has changed diff -r b7a6436c7758 -r 904de68a27a4 hws/hw07.tex --- 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! diff -r b7a6436c7758 -r 904de68a27a4 progs/parser-combinators/comb1.sc --- 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")) diff -r b7a6436c7758 -r 904de68a27a4 solutions/cw2/lexer.sc --- 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)))