1 import scala.language.implicitConversions |
1 import scala.language.implicitConversions |
2 import scala.language.reflectiveCalls |
2 import scala.language.reflectiveCalls |
|
3 |
|
4 /* Note, in the lectures I did not show the type consraint |
|
5 * I <% Seq[_] , which means that the input type I can be |
|
6 * treated, or seen, as a sequence. */ |
3 |
7 |
4 abstract class Parser[I <% Seq[_], T] { |
8 abstract class Parser[I <% Seq[_], T] { |
5 def parse(ts: I): Set[(T, I)] |
9 def parse(ts: I): Set[(T, I)] |
6 |
10 |
7 def parse_all(ts: I) : Set[T] = |
11 def parse_all(ts: I) : Set[T] = |
65 new SeqParser[String, String, S](s, q) |
69 new SeqParser[String, String, S](s, q) |
66 def ~ (r: String) = |
70 def ~ (r: String) = |
67 new SeqParser[String, String, String](s, r) |
71 new SeqParser[String, String, String](s, r) |
68 } |
72 } |
69 |
73 |
70 // palindromes |
74 // a parse palindromes |
71 lazy val Pal : Parser[String, String] = |
75 lazy val Pal : Parser[String, String] = |
72 (("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } || |
76 (("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } || |
73 ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "") |
77 ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "") |
74 |
78 |
75 println("Palindrom: " + Pal.parse_all("ababbaba")) |
79 println("Palindrom: " + Pal.parse_all("ababbaba")) |
76 |
80 |
77 // well-nested parenthesis |
81 // well-nested parenthesis parser |
78 lazy val P : Parser[String, String] = |
82 lazy val P : Parser[String, String] = |
79 "(" ~ P ~ ")" ~ P ==> { case (((u, x), y), z) => "{" + x + "}" + z } || "" |
83 "(" ~ P ~ ")" ~ P ==> { case (((u, x), y), z) => "{" + x + "}" + z } || "" |
80 |
84 |
81 P.parse_all("(((()()))())") |
85 P.parse_all("(((()()))())") |
82 P.parse_all("(((()()))()))") |
86 P.parse_all("(((()()))()))") |
83 P.parse_all(")(") |
87 P.parse_all(")(") |
|
88 P.parse_all("()") |
84 |
89 |
85 // arithmetic expressions |
90 // arithmetic expressions |
86 lazy val E: Parser[String, String] = |
91 lazy val E: Parser[String, String] = |
87 (F ~ "*" ~ F) ==> { case ((x, y), z) => x + y + z } || F |
92 (F ~ "*" ~ F) ==> { case ((x, y), z) => x + y + z } || F |
88 lazy val F: Parser[String, String] = |
93 lazy val F: Parser[String, String] = |
91 lazy val T: Parser[String, String] = |
96 lazy val T: Parser[String, String] = |
92 ("(" ~ E ~ ")") ==> { case ((x, y), z) => x + y + z } || NumParser |
97 ("(" ~ E ~ ")") ==> { case ((x, y), z) => x + y + z } || NumParser |
93 |
98 |
94 println(E.parse_all("1*2+3")) |
99 println(E.parse_all("1*2+3")) |
95 println(E.parse_all("1+2*3")) |
100 println(E.parse_all("1+2*3")) |
96 println(E.parse_all("1+2+3")) |
101 println(E.parse_all("(1+2)+3")) |
|
102 println(E.parse_all("1+2+3")) // this is not parsed, because of |
|
103 // how the grammar is set up |
97 |
104 |
98 |
105 // non-ambiguous vs ambiguous grammars |
99 // non-ambiguous vs ambiguous |
|
100 lazy val U : Parser[String, String] = |
106 lazy val U : Parser[String, String] = |
101 ("1" ~ U) ==> { case (x, y) => x + y } || "" |
107 ("1" ~ U) ==> { case (x, y) => x + y } || "" |
102 |
108 |
103 U.parse_all("1" * 100 + "0") |
109 U.parse_all("1" * 100 + "0") |
104 |
110 |
105 lazy val S : Parser[String, String] = |
111 lazy val S : Parser[String, String] = |
106 ("1" ~ S ~ S) ==> { case ((x, y), z) => x + y + z } || "" |
112 ("1" ~ S ~ S) ==> { case ((x, y), z) => x + y + z } || "" |
107 |
113 |
108 S.parse_all("1" * 15) |
114 S.parse_all("1" * 15) |
|
115 |
|
116 |
|
117 |
|
118 |
|
119 |
|
120 |
|
121 |
|
122 |
|
123 |
|
124 |
|
125 |
|
126 |
|
127 |
|
128 |
|
129 |
|
130 |
|
131 |
|
132 |
|
133 |
|
134 |
|
135 |
|
136 |
|
137 |
|
138 |
|
139 |
|
140 |
|
141 |
|
142 |
|
143 |