# HG changeset patch # User Christian Urban # Date 1605573376 0 # Node ID 0d3bc1d0d987bc0b0d5efa39b8c368bb9779796c # Parent 526e10d97435e42a81285d2be25cd441fb79dba4 updated diff -r 526e10d97435 -r 0d3bc1d0d987 progs/parser-combinators/c.sc --- a/progs/parser-combinators/c.sc Mon Nov 16 01:49:24 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,229 +0,0 @@ -// Parser Combinators: Simple Version -//==================================== -// -// Call with -// -// amm comb1.sc - - -// Note, in the lectures I did not show the implicit type constraint -// I : IsSeq, which means that the input type 'I' needs to be -// a sequence. - -type IsSeq[A] = A => Seq[_] - -abstract class Parser[I : IsSeq, T]{ - def parse(in: I): Set[(T, I)] - - def parse_all(in: I) : Set[T] = - for ((hd, tl) <- parse(in); - if tl.isEmpty) yield hd -} - -// parser combinators - -// alternative parser -class AltParser[I : IsSeq, T](p: => Parser[I, T], - q: => Parser[I, T]) extends Parser[I, T] { - def parse(in: I) = p.parse(in) ++ q.parse(in) -} - -// sequence parser -class SeqParser[I : IsSeq, T, S](p: => Parser[I, T], - q: => Parser[I, S]) extends Parser[I, (T, S)] { - def parse(in: I) = - for ((hd1, tl1) <- p.parse(in); - (hd2, tl2) <- q.parse(tl1)) yield ((hd1, hd2), tl2) -} - -// map parser -class MapParser[I : IsSeq, T, S](p: => Parser[I, T], - f: T => S) extends Parser[I, S] { - def parse(in: I) = for ((hd, tl) <- p.parse(in)) yield (f(hd), tl) -} - - - -// an example of an atomic parser for characters -case class CharParser(c: Char) extends Parser[String, Char] { - def parse(in: String) = - if (in != "" && in.head == c) Set((c, in.tail)) else Set() -} - - -// an atomic parser for parsing strings according to a regex -import scala.util.matching.Regex - -case class RegexParser(reg: Regex) extends Parser[String, String] { - def parse(in: String) = reg.findPrefixMatchOf(in) match { - case None => Set() - case Some(m) => Set((m.matched, m.after.toString)) - } -} - -// atomic parsers for numbers and "verbatim" strings -val NumParser = RegexParser("[0-9]+".r) -def StrParser(s: String) = RegexParser(Regex.quote(s).r) - - - -// 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) - - -// 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:_*)) -} - - -// more convenient syntax for parser combinators -implicit def ParserOps[I : IsSeq, T](p: Parser[I, T]) = new { - def ||(q : => Parser[I, T]) = new AltParser[I, T](p, q) - def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) - def map[S](f: => T => S) = new MapParser[I, T, S](p, f) -} - -// these implicits allow us to use an infix notation for -// sequences and alternatives; we also can write the usual -// map for a MapParser - - -// with this NumParserInt can now be written more conveniently -// as: - -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"b" ~ Pal ~ p"b").map{ case ((x, y), z) => s"$x$y$z" } || - p"a" || p"b" || p"" -} - -// examples -Pal.parse_all("abaaaba") -Pal.parse("abaaaba") - -println("Palindrome: " + Pal.parse_all("abaaaba")) - -// A parser for wellnested parentheses -// -// P ::= ( P ) P | epsilon -// -// (transforms '(' -> '{' , ')' -> '}' ) -lazy val P : Parser[String, String] = { - (p"(" ~ P ~ p")" ~ P).map{ case (((_, x), _), y) => "{" + x + "}" + y } || - p"" -} - -println(P.parse_all("(((()()))())")) -println(P.parse_all("(((()()))()))")) -println(P.parse_all(")(")) -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 } -lazy val T: Parser[String, Int] = { - (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")) -println(E.parse_all("4*(2+3)")) -println(E.parse_all("(4)*((2+3))")) -println(E.parse_all("4/2+3")) -println(E.parse("1 + 2 * 3")) -println(E.parse_all("(1+2)+3")) -println(E.parse_all("1+2+3")) - - -// with parser combinators (and other parsing algorithms) -// no left-recursion is allowed, otherwise the will loop - -lazy val EL: Parser[String, Int] = - ((EL ~ p"+" ~ EL).map{ case ((x, y), z) => x + z} || - (EL ~ p"*" ~ EL).map{ case ((x, y), z) => x * z} || - (p"(" ~ EL ~ p")").map{ case ((x, y), z) => y} || - NumParserInt) - -// this will run forever: -//println(EL.parse_all("1+2+3")) - - -// non-ambiguous vs ambiguous grammars - -// ambiguous -lazy val S : Parser[String, String] = - (p"1" ~ S ~ S).map{ case ((x, y), z) => x + y + z } || p"" - -//println(time(S.parse("1" * 10))) -//println(time(S.parse_all("1" * 10))) - -// non-ambiguous -lazy val U : Parser[String, String] = - (p"1" ~ U).map{ case (x, y) => x + y } || p"" - -//println(time(U.parse("1" * 10))) -//println(time(U.parse_all("1" * 10))) -println(U.parse("1" * 25)) - -U.parse("11") -U.parse("11111") -U.parse("11011") - -U.parse_all("1" * 100) -U.parse_all("1" * 100 + "0") - -// you can see the difference in second example -//S.parse_all("1" * 100) // succeeds -//S.parse_all("1" * 100 + "0") // fails - - -// A variant which counts how many 1s are parsed -lazy val UCount : Parser[String, Int] = - (p"1" ~ UCount).map{ case (_, y) => y + 1 } || p"".map{ _ => 0 } - -println(UCount.parse("11111")) -println(UCount.parse_all("11111")) - -// Two single character parsers -lazy val One : Parser[String, String] = p"a" -lazy val Two : Parser[String, String] = p"b" - -One.parse("a") -One.parse("aaa") - -// note how the pairs nest to the left with sequence parsers -(One ~ One).parse("aaa") -(One ~ One ~ One).parse("aaa") -(One ~ One ~ One ~ One).parse("aaaa") - -(One || Two).parse("aaa") - - - -// a problem with the arithmetic expression parser: it -// gets very slow with deeply nested parentheses - -println("Runtime problem") -println(E.parse("1")) -println(E.parse("(1)")) -println(E.parse("((1))")) -//println(E.parse("(((1)))")) -//println(E.parse("((((1))))")) -//println(E.parse("((((((1))))))")) -//println(E.parse("(((((((1)))))))")) -//println(E.parse("((((((((1)))))))")) diff -r 526e10d97435 -r 0d3bc1d0d987 slides/slides02.pdf Binary file slides/slides02.pdf has changed