|
1 import scala.language.implicitConversions |
|
2 import scala.language.reflectiveCalls |
|
3 import scala.util._ |
|
4 import scala.annotation.tailrec |
|
5 |
|
6 sealed abstract class Rexp |
|
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 |
|
15 def charlist2rexp(s : List[Char]) : Rexp = s match { |
|
16 case Nil => EMPTY |
|
17 case c::Nil => CHAR(c) |
|
18 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
|
19 } |
|
20 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) |
|
21 |
|
22 |
|
23 implicit def RexpOps(r: Rexp) = new { |
|
24 def | (s: Rexp) = ALT(r, s) |
|
25 def % = STAR(r) |
|
26 def ~ (s: Rexp) = SEQ(r, s) |
|
27 } |
|
28 |
|
29 implicit def stringOps(s: String) = new { |
|
30 def | (r: Rexp) = ALT(s, r) |
|
31 def | (r: String) = ALT(s, r) |
|
32 def % = STAR(s) |
|
33 def ~ (r: Rexp) = SEQ(s, r) |
|
34 def ~ (r: String) = SEQ(s, r) |
|
35 } |
|
36 |
|
37 def Range(s : List[Char]) : Rexp = s match { |
|
38 case Nil => NULL |
|
39 case c::Nil => CHAR(c) |
|
40 case c::s => ALT(CHAR(c), Range(s)) |
|
41 } |
|
42 def RANGE(s: String) = Range(s.toList) |
|
43 |
|
44 def PLUS(r: Rexp) = SEQ(r, STAR(r)) |
|
45 |
|
46 val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_") |
|
47 val DIGIT = RANGE("0123456789") |
|
48 val ID = SYM ~ (SYM | DIGIT).% |
|
49 val NUM = PLUS(DIGIT) |
|
50 val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" |
|
51 val SEMI: Rexp = ";" |
|
52 val OP: Rexp = ":=" | "=" | "-" | "+" | "*" | "!=" | "<" | ">" |
|
53 val WHITESPACE = PLUS(RANGE(" \n")) |
|
54 val RPAREN: Rexp = ")" |
|
55 val LPAREN: Rexp = "(" |
|
56 val BEGIN: Rexp = "{" |
|
57 val END: Rexp = "}" |
|
58 |
|
59 //regular expressions ranked by position in the list |
|
60 val regs: List[Rexp] = |
|
61 List(KEYWORD, ID, OP, NUM, SEMI, LPAREN, RPAREN, BEGIN, END, WHITESPACE) |
|
62 |
|
63 def nullable (r: Rexp) : Boolean = r match { |
|
64 case NULL => false |
|
65 case EMPTY => true |
|
66 case CHAR(_) => false |
|
67 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
|
68 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
|
69 case STAR(_) => true |
|
70 } |
|
71 |
|
72 def zeroable (r: Rexp) : Boolean = r match { |
|
73 case NULL => true |
|
74 case EMPTY => false |
|
75 case CHAR(_) => false |
|
76 case ALT(r1, r2) => zeroable(r1) && zeroable(r2) |
|
77 case SEQ(r1, r2) => zeroable(r1) || zeroable(r2) |
|
78 case STAR(_) => false |
|
79 } |
|
80 |
|
81 def der (c: Char, r: Rexp) : Rexp = r match { |
|
82 case NULL => NULL |
|
83 case EMPTY => NULL |
|
84 case CHAR(d) => if (c == d) EMPTY else NULL |
|
85 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
|
86 case SEQ(r1, r2) => |
|
87 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
|
88 else SEQ(der(c, r1), r2) |
|
89 case STAR(r) => SEQ(der(c, r), STAR(r)) |
|
90 } |
|
91 |
|
92 // returns the position of the last Some-element in the list |
|
93 def last(stack: List[Option[Rexp]]) : Int = stack match { |
|
94 case Nil => 0 |
|
95 case None::stack => last(stack) |
|
96 case Some(r)::stack => 1 + stack.length |
|
97 } |
|
98 |
|
99 // calculates derivatives until all of them are zeroable |
|
100 @tailrec |
|
101 def munch(cs: List[Char], rs: List[Rexp], stack: List[Option[Rexp]]) : Int = (cs, rs) match { |
|
102 case (_, Nil) => last(stack) |
|
103 case (Nil, _) => last(stack) |
|
104 case (c::cs, rs) => { |
|
105 val ds = rs.map(der(c, _)) |
|
106 val rs_nzero = ds.filterNot(zeroable(_)) |
|
107 val rs_nulls = ds.filter(nullable(_)) |
|
108 val opt = Try(Some(rs_nulls.head)) getOrElse None |
|
109 munch(cs, rs_nzero, opt::stack) |
|
110 } |
|
111 } |
|
112 |
|
113 // iterates the munching function and prints |
|
114 // out the component strings |
|
115 @tailrec |
|
116 def tokenize(s: String, rs: List[Rexp]) : Unit = munch(s.toList, rs, Nil) match { |
|
117 case 0 if (s == "") => println("EOF") |
|
118 case 0 => println(s"Lexing error: $s") |
|
119 case n => { |
|
120 val (head, tail) = s.splitAt(n) |
|
121 print(s"|${head.replaceAll("\n","Ret")}|") |
|
122 tokenize(tail, rs) |
|
123 } |
|
124 } |
|
125 |
|
126 val test_prog = """ |
|
127 start := XXX; |
|
128 x := start; |
|
129 y := start; |
|
130 z := start; |
|
131 while 0 < x do { |
|
132 while 0 < y do { |
|
133 while 0 < z do { |
|
134 z := z - 1 |
|
135 }; |
|
136 z := start; |
|
137 y := y - 1 |
|
138 }; |
|
139 y := start; |
|
140 x := x - 1 |
|
141 }; |
|
142 write x; |
|
143 write y; |
|
144 write z |
|
145 """ |
|
146 |
|
147 tokenize(test_prog, regs) |