10 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
10 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
11 case class STAR(r: Rexp) extends Rexp |
11 case class STAR(r: Rexp) extends Rexp |
12 case class RECD(x: String, r: Rexp) extends Rexp |
12 case class RECD(x: String, r: Rexp) extends Rexp |
13 case class CRANGE(cs: String) extends Rexp |
13 case class CRANGE(cs: String) extends Rexp |
14 case class PLUS(r: Rexp) extends Rexp |
14 case class PLUS(r: Rexp) extends Rexp |
|
15 case class OPT(r: Rexp) extends Rexp |
15 |
16 |
16 abstract class Val |
17 abstract class Val |
17 case object Empty extends Val |
18 case object Empty extends Val |
18 case class Chr(c: Char) extends Val |
19 case class Chr(c: Char) extends Val |
19 case class Seq(v1: Val, v2: Val) extends Val |
20 case class Seq(v1: Val, v2: Val) extends Val |
55 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
56 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
56 case STAR(_) => true |
57 case STAR(_) => true |
57 case RECD(_, r) => nullable(r) |
58 case RECD(_, r) => nullable(r) |
58 case CRANGE(_) => false |
59 case CRANGE(_) => false |
59 case PLUS(r) => nullable(r) |
60 case PLUS(r) => nullable(r) |
|
61 case OPT(_) => true |
60 } |
62 } |
61 |
63 |
62 // derivative of a regular expression w.r.t. a character |
64 // derivative of a regular expression w.r.t. a character |
63 def der (c: Char, r: Rexp) : Rexp = r match { |
65 def der (c: Char, r: Rexp) : Rexp = r match { |
64 case NULL => NULL |
66 case NULL => NULL |
70 else SEQ(der(c, r1), r2) |
72 else SEQ(der(c, r1), r2) |
71 case STAR(r) => SEQ(der(c, r), STAR(r)) |
73 case STAR(r) => SEQ(der(c, r), STAR(r)) |
72 case RECD(_, r1) => der(c, r1) |
74 case RECD(_, r1) => der(c, r1) |
73 case CRANGE(cs) => if (cs.contains(c)) EMPTY else NULL |
75 case CRANGE(cs) => if (cs.contains(c)) EMPTY else NULL |
74 case PLUS(r) => SEQ(der(c, r), STAR(r)) |
76 case PLUS(r) => SEQ(der(c, r), STAR(r)) |
|
77 case OPT(r) => ALT(der(c, r), NULL) |
75 } |
78 } |
76 |
79 |
77 // derivative w.r.t. a string (iterates der) |
80 // derivative w.r.t. a string (iterates der) |
78 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
81 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
79 case Nil => r |
82 case Nil => r |
109 if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) |
112 if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) |
110 case SEQ(r1, r2) => Seq(mkeps(r1), mkeps(r2)) |
113 case SEQ(r1, r2) => Seq(mkeps(r1), mkeps(r2)) |
111 case STAR(r) => Stars(Nil) |
114 case STAR(r) => Stars(Nil) |
112 case RECD(x, r) => Rec(x, mkeps(r)) |
115 case RECD(x, r) => Rec(x, mkeps(r)) |
113 case PLUS(r) => Stars(List(mkeps(r))) |
116 case PLUS(r) => Stars(List(mkeps(r))) |
|
117 case OPT(_) => Right(Empty) |
114 } |
118 } |
115 |
119 |
116 |
120 |
117 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match { |
121 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match { |
118 case (STAR(r), Seq(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) |
122 case (STAR(r), Seq(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) |
123 case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2)) |
127 case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2)) |
124 case (CHAR(_), Empty) => Chr(c) |
128 case (CHAR(_), Empty) => Chr(c) |
125 case (CRANGE(_), Empty) => Chr(c) |
129 case (CRANGE(_), Empty) => Chr(c) |
126 case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) |
130 case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) |
127 case (PLUS(r), Seq(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) |
131 case (PLUS(r), Seq(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) |
|
132 case (OPT(r), Left(v1)) => Left(inj(r, c, v1)) |
128 } |
133 } |
129 |
134 |
130 // main lexing function (produces a value) |
135 // main lexing function (produces a value) |
131 def lex(r: Rexp, s: List[Char]) : Val = s match { |
136 def lex(r: Rexp, s: List[Char]) : Val = s match { |
132 case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") |
137 case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") |
134 } |
139 } |
135 |
140 |
136 def lexing(r: Rexp, s: String) : Val = lex(r, s.toList) |
141 def lexing(r: Rexp, s: String) : Val = lex(r, s.toList) |
137 |
142 |
138 lexing(("ab" | "ab") ~ ("b" | EMPTY), "ab") |
143 lexing(("ab" | "ab") ~ ("b" | EMPTY), "ab") |
|
144 |
|
145 lexing(OPT("ab"), "ab") |
139 |
146 |
140 // some "rectification" functions for simplification |
147 // some "rectification" functions for simplification |
141 def F_ID(v: Val): Val = v |
148 def F_ID(v: Val): Val = v |
142 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) |
149 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) |
143 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) |
150 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) |
198 |
205 |
199 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList) |
206 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList) |
200 |
207 |
201 lexing_simp(("a" | "ab") ~ ("b" | ""), "ab") |
208 lexing_simp(("a" | "ab") ~ ("b" | ""), "ab") |
202 |
209 |
|
210 lexing_simp(OPT("ab"), "ab") |
|
211 |
203 // Lexing Rules for a Small While Language |
212 // Lexing Rules for a Small While Language |
204 |
213 |
205 val SYM = CRANGE("abcdefghijklmnopqrstuvwxyz") |
214 val SYM = CRANGE("abcdefghijklmnopqrstuvwxyz") |
206 val DIGIT = CRANGE("0123456789") |
215 val DIGIT = CRANGE("0123456789") |
207 val ID = SYM ~ (SYM | DIGIT).% |
216 val ID = SYM ~ (SYM | DIGIT).% |