1 import Console._ |
|
2 |
|
3 // regular expressions including NOT |
|
4 abstract class Rexp { |
|
5 def ~ (right : Rexp) = SEQ(this, right) |
|
6 def || (right : Rexp) = ALT(this, right) |
|
7 } |
|
8 case object NULL extends Rexp |
|
9 case object EMPTY extends Rexp |
|
10 case class CHAR(c: Char) extends Rexp |
|
11 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
|
12 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
|
13 case class STAR(r: Rexp) extends Rexp |
|
14 case class NOT(r: Rexp) extends Rexp |
|
15 |
|
16 // some convenience for typing in regular expressions |
|
17 def charlist2rexp(s : List[Char]) : Rexp = s match { |
|
18 case Nil => EMPTY |
|
19 case c::Nil => CHAR(c) |
|
20 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
|
21 } |
|
22 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) |
|
23 |
|
24 |
|
25 // nullable function: tests whether the regular |
|
26 // expression can recognise the empty string |
|
27 def nullable (r: Rexp) : Boolean = r match { |
|
28 case NULL => false |
|
29 case EMPTY => true |
|
30 case CHAR(_) => false |
|
31 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
|
32 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
|
33 case STAR(_) => true |
|
34 case NOT(r) => !(nullable(r)) |
|
35 } |
|
36 |
|
37 // tests whether a regular expression |
|
38 // cannot recognise more |
|
39 def no_more (r: Rexp) : Boolean = r match { |
|
40 case NULL => true |
|
41 case EMPTY => false |
|
42 case CHAR(_) => false |
|
43 case ALT(r1, r2) => no_more(r1) && no_more(r2) |
|
44 case SEQ(r1, r2) => if (nullable(r1)) (no_more(r1) && no_more(r2)) else no_more(r1) |
|
45 case STAR(_) => false |
|
46 case NOT(r) => !(no_more(r)) |
|
47 } |
|
48 |
|
49 |
|
50 // derivative of a regular expression w.r.t. a character |
|
51 def der (c: Char, r: Rexp) : Rexp = r match { |
|
52 case NULL => NULL |
|
53 case EMPTY => NULL |
|
54 case CHAR(d) => if (c == d) EMPTY else NULL |
|
55 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
|
56 case SEQ(r1, r2) => |
|
57 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
|
58 else SEQ(der(c, r1), r2) |
|
59 case STAR(r) => SEQ(der(c, r), STAR(r)) |
|
60 case NOT(r) => NOT(der (c, r)) |
|
61 } |
|
62 |
|
63 def error (s: String) = "Could not lex " + s |
|
64 |
|
65 def munch(r: Rexp, s: List[Char], t: List[Char]) : Option[(List[Char], List[Char])] = { |
|
66 //println("Look at" + s); |
|
67 s match { |
|
68 case Nil if (nullable(r)) => Some(Nil, t) |
|
69 case Nil => None |
|
70 case c::s if (no_more(der (c, r)) && nullable(r)) => Some(c::s, t) |
|
71 case c::s if (no_more(der (c, r))) => None |
|
72 case c::s => munch(der (c, r), s, t ::: List(c)) |
|
73 } |
|
74 } |
|
75 |
|
76 def one_string (regs: List[Rexp], s: List[Char]) : Either[(List[Char], List[Char]), String] = { |
|
77 val somes = regs.map { munch(_, s, Nil) } .flatten |
|
78 if (somes == Nil) Right(error(s.mkString)) else Left(somes sortBy (_._1.length) head) |
|
79 } |
|
80 |
|
81 def tokenize (regs: List[Rexp], s: List[Char]) : List[String] = s match { |
|
82 case Nil => Nil |
|
83 case _ => one_string(regs, s) match { |
|
84 case Left((rest, s)) => { println("tokenized: " + s.mkString) ; s.mkString :: tokenize(regs, rest) } |
|
85 case Right(msg) => { println(msg); sys.exit() } |
|
86 } |
|
87 } |
|
88 |
|
89 |
|
90 // regular expression for specifying |
|
91 // ranges of characters |
|
92 def RANGE(s : List[Char]) : Rexp = s match { |
|
93 case Nil => NULL |
|
94 case c::Nil => CHAR(c) |
|
95 case c::s => CHAR(c) || RANGE(s) |
|
96 } |
|
97 |
|
98 //one or more |
|
99 def PLUS(r: Rexp) = r ~ STAR(r) |
|
100 |
|
101 <font color="red"> |
|
102 //some regular expressions |
|
103 val COLOUR = "BLACK" || "BLUE" || "CYAN" || "GREEN" || "MAGENTA" || "RED" || "WHITE" || "YELLOW" |
|
104 |
|
105 //BOLD || BLINK |
|
106 //INVISIBLE |
|
107 //RESET |
|
108 //REVERSED |
|
109 //UNDERLINED |
|
110 |
|
111 println(RED + BOLD + "test") |
|
112 println(RESET) |
|