Mercurial Mercurial > hg > afl-material / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
progs/comb1.scala
changeset 593 bb24d4e207b6
parent 590 c6a1e19e9801
child 594 d40d7d7b85bc
equal deleted inserted replaced
592:0d309fafa9f0 593:bb24d4e207b6 
    36   def parse(sb: String) = 
    36   def parse(sb: String) = 
    37     if (sb != "" && sb.head == c) Set((c, sb.tail)) else Set()
 
    37     if (sb != "" && sb.head == c) Set((c, sb.tail)) else Set()
 
    38 }
 
    38 }
 
    39 
    39 
    40 import scala.util.matching.Regex
 
    40 import scala.util.matching.Regex
 
    41 
       
    42 case class RegexParser(reg: Regex) extends Parser[String, String] {
 
    41 case class RegexParser(reg: Regex) extends Parser[String, String] {
 
    43   def parse(sb: String) = reg.findPrefixMatchOf(sb) match {
 
    42   def parse(sb: String) = reg.findPrefixMatchOf(sb) match {
 
    44     case None => Set()
 
    43     case None => Set()
 
    45     case Some(m) => Set((m.matched, m.after.toString))  
    44     case Some(m) => Set((m.matched, m.after.toString))  
    46   }
 
    45   }
 
    47 }
 
    46 }
 
    48 
    47 
    49 val NumParser = RegexParser("[0-9]+".r)
 
    48 val NumParser = RegexParser("[0-9]+".r)
 
    50 def StringParser(s: String) = RegexParser(s.r)
 
    49 def StringParser(s: String) = RegexParser(Regex.quote(s).r)
 
    51 
    50 
       
    51 val NumParserInt = NumParser ==> (s => s.toInt)
 
    52 
    52 
    53 // convenience
 
    53 // convenience
 
    54 implicit def string2parser(s: String) = StringParser(s)
 
    54 implicit def string2parser(s: String) = StringParser(s)
 
    55 //implicit def char2parser(c: Char) = CharParser(c)
 
    55 implicit def char2parser(c: Char) = CharParser(c)
 
    56 
    56 
    57 implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new {
 
    57 implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new {
 
    58   def | (q : => Parser[I, T]) = new AltParser[I, T](p, q)
 
    58   def | (q : => Parser[I, T]) = new AltParser[I, T](p, q)
 
    59   def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
 
    59   def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
 
    60   def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
 
    60   def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
 
    68     new SeqParser[String, String, S](s, q)
 
    68     new SeqParser[String, String, S](s, q)
 
    69   def ~ (r: String) = 
    69   def ~ (r: String) = 
    70     new SeqParser[String, String, String](s, r)
 
    70     new SeqParser[String, String, String](s, r)
 
    71 }
 
    71 }
 
    72 
    72 
    73 val c = new CharParser('c')
 
       
    74 lazy val cn = c ==> (c => c.toInt)
 
       
    75 val f = (c: Char) => c.toInt
 
       
    76 
    73 
    77 c.parse("cb")
 
       
    78 (c ==> f).parse("cb")
 
       
    79 
       
    80 // a parse palindromes
 
       
    81 lazy val Pal : Parser[String, String] = 
    74 lazy val Pal : Parser[String, String] = 
    82   (("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } ||
 
    75   (("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } |
 
    83    ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "a" || "b" || "")
 
    76    ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } | "a" | "b" | "")
 
    84 
    77 
    85 Pal.parse_all("abaaaba")
 
    78 Pal.parse_all("abaaaba")
 
       
    79 Pal.parse("abaaaba")
 
    86 
    80 
    87 println("Palindrome: " + Pal.parse_all("abaaaba"))
 
    81 println("Palindrome: " + Pal.parse_all("abaaaba"))
 
    88 
    82 
    89 // well-nested parenthesis parser
 
    83 // well-nested parenthesis parser
 
    90 lazy val P : Parser[String, String] = 
    84 lazy val P : Parser[String, String] = 
    91   "(" ~ P ~ ")" ~ P ==> { case (((u, x), y), z) => "{" + x + "}" + z } || ""
 
    85   "(" ~ P ~ ")" ~ P ==> { case (((_, x), _), y) => "{" + x + "}" + y } | ""
 
    92 
    86 
    93 P.parse_all("(((()()))())")
 
    87 P.parse_all("(((()()))())")
 
    94 P.parse_all("(((()()))()))")
 
    88 P.parse_all("(((()()))()))")
 
    95 P.parse_all(")(")
 
    89 P.parse_all(")(")
 
    96 P.parse_all("()")
 
    90 P.parse_all("()")
 
    97 
    91 
    98 // arithmetic expressions
 
    92 // arithmetic expressions
 
    99 
    93 
   100 lazy val E: Parser[String, Int] = 
    94 lazy val E: Parser[String, Int] = 
   101   (T ~ "+" ~ E) ==> { case ((x, y), z) => x + z } ||
 
    95   (T ~ "+" ~ E) ==> { case ((x, y), z) => x + z } |
 
   102   (T ~ "-" ~ E) ==> { case ((x, y), z) => x - z } || T 
    96   (T ~ "-" ~ E) ==> { case ((x, y), z) => x - z } | T 
   103 lazy val T: Parser[String, Int] = 
    97 lazy val T: Parser[String, Int] = 
   104   ((F ~ "*" ~ T) ==> { case ((x, y), z) => x * z } || F)
 
    98   (F ~ "*" ~ T) ==> { case ((x, y), z) => x * z } | F
 
   105 lazy val F: Parser[String, Int] = 
    99 lazy val F: Parser[String, Int] = 
   106   ("(" ~ E ~ ")") ==> { case ((x, y), z) => y } || NumParser
 
   100   ("(" ~ E ~ ")") ==> { case ((x, y), z) => y } | NumParserInt
 
   107 
   101 
   108 
   102 
   109 println(E.parse("4*2+3"))
 
   103 println(E.parse_all("4*2+3"))
 
       
   104 println(E.parse_all("4*(2+3)"))
 
   110 println(E.parse_all("4/2+3"))
 
   105 println(E.parse_all("4/2+3"))
 
   111 println(E.parse("1 + 2 * 3"))
 
   106 println(E.parse("1 + 2 * 3"))
 
   112 println(E.parse_all("(1+2)+3"))
 
   107 println(E.parse_all("(1+2)+3"))
 
   113 println(E.parse_all("1+2+3"))  
   108 println(E.parse_all("1+2+3"))  
   114 
   109 
   115 
   110 
   116 
   111 
   117 // no left-recursion allowed, otherwise will loop
 
   112 // no left-recursion allowed, otherwise will loop
 
   118 lazy val EL: Parser[String, Int] = 
   113 lazy val EL: Parser[String, Int] = 
   119   ((EL ~ "+" ~ EL) ==> { case ((x, y), z) => x + z} || 
   114   (EL ~ "+" ~ EL ==> { case ((x, y), z) => x + z} | 
   120    (EL ~ "*" ~ EL) ==> { case ((x, y), z) => x * z} ||
 
   115    EL ~ "*" ~ EL ==> { case ((x, y), z) => x * z} |
 
   121    ("(" ~ EL ~ ")") ==> { case ((x, y), z) => y} ||
 
   116    "(" ~ EL ~ ")" ==> { case ((x, y), z) => y} |
 
   122    NumParser)
 
   117    NumParserInt)
 
   123 
   118 
   124 //println(E.parse_all("1+2+3"))
 
   119 //println(EL.parse_all("1+2+3"))
 
   125 
   120 
   126 
   121 
   127 // a repetition parser
 
   122 // a repetition parser
 
   128 
   123 
   129 def RepParser[I  <% Seq[_], T](p: => Parser[I, T]): Parser[I, List[T]] = {
 
   124 def RepParser[I  <% Seq[_], T](p: => Parser[I, T]): Parser[I, List[T]] = {
 
   130   p ==> { case x => x :: Nil } ||
 
   125   p ==> { case x => x :: Nil } |
 
   131   p ~ RepParser(p) ==> { case (x, y) => x :: y }   
   126   p ~ RepParser(p) ==> { case (x, y) => x :: y }   
   132 }
 
   127 }
 
   133 
   128 
   134 
   129 
   135 // a repetition parser
 
   130 // a repetition parser
 
   138 
   133 
   139 
   134 
   140 
   135 
   141 // non-ambiguous vs ambiguous grammars
 
   136 // non-ambiguous vs ambiguous grammars
 
   142 lazy val S : Parser[String, String] =
 
   137 lazy val S : Parser[String, String] =
 
   143   ("1" ~ S ~ S) ==> { case ((x, y), z) => x + y + z } || ""
 
   138   ("1" ~ S ~ S) ==> { case ((x, y), z) => x + y + z } | ""
 
   144 
   139 
   145 S.parse("1" * 15)
 
   140 S.parse("1" * 15)
 
   146 
   141 
   147 lazy val U : Parser[String, String] =
 
   142 lazy val U : Parser[String, String] =
 
   148   ("1" ~ U) ==> { case (x, y) => x + y  } || ""
 
   143   ("1" ~ U) ==> { case (x, y) => x + y  } | ""
 
   149 
   144 
   150 U.parse("1" * 15)
 
   145 U.parse("1" * 15)
 
   151 
   146 
   152 U.parse("11")
 
   147 U.parse("11")
 
   153 U.parse("11111")
 
   148 U.parse("11111")
 
   155 
   150 
   156 U.parse_all("1" * 100)
 
   151 U.parse_all("1" * 100)
 
   157 U.parse_all("1" * 100 + "0")
 
   152 U.parse_all("1" * 100 + "0")
 
   158 
   153 
   159 lazy val UCount : Parser[String, Int] =
 
   154 lazy val UCount : Parser[String, Int] =
 
   160   ("1" ~ UCount) ==> { case (x, y) => y + 1 } || 
   155   ("1" ~ UCount) ==> { case (x, y) => y + 1 } | 
   161   "" ==> { (x) => 0 }
 
   156   "" ==> { (x) => 0 }
 
   162 
   157 
   163 UCount.parse("11111")
 
   158 UCount.parse("11111")
 
   164 UCount.parse_all("11111")
 
   159 UCount.parse_all("11111")
 
   165 
   160 
   175 
   170 
   176 (One ~ One).parse("111")
 
   171 (One ~ One).parse("111")
 
   177 (One ~ One ~ One).parse("111")
 
   172 (One ~ One ~ One).parse("111")
 
   178 (One ~ One ~ One ~ One).parse("1111")
 
   173 (One ~ One ~ One ~ One).parse("1111")
 
   179 
   174 
   180 (One || Two).parse("111")
 
   175 (One | Two).parse("111")
 
   181 
       
   182 
       
   183 for (x <- List(1, 2, 3, 4)) println(x)
 
       
   184 for (x <- List(1, 2, 3, 4); if (2 < x)) yield (x.toString + x.toString)
 
       
   185 for (x <- List("2", "1", "3", "4", "1")) yield (x + x + x)
 
       
   186 
       
   187 (1, "one", '1')._3
 
       
   188 for ((x, y) <- List((1, "one"), (2, "two"), (3, "three"), (4,"many")); if (y == "many"))
 
       
   189   yield (x.toString + y)
 
       
   190 
   176 
   191 
   177 
   192 
   178 
   193 // Example section for lazy evaluation
 
       
   194 def square(n: Int) = {
 
       
   195   n * n
 
       
   196 }
 
       
   197 
       
   198 square(4 + 3 + 5)
 
       
   199 
       
   200 def bar(): Int = {
 
       
   201   bar()
 
       
   202   3
 
       
   203 }
 
       
   204 
       
   205 //would loop
 
       
   206 square(bar())
 
       
   207 
       
   208 // lazy
 
       
   209 def foo(n: => Int) = {
 
       
   210   print("finished")
 
       
   211 }
 
       
   212 
       
   213 foo(bar())
 
       
   214
afl-material