87 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
87 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
88 else SEQ(der(c, r1), r2) |
88 else SEQ(der(c, r1), r2) |
89 case STAR(r) => SEQ(der(c, r), STAR(r)) |
89 case STAR(r) => SEQ(der(c, r), STAR(r)) |
90 } |
90 } |
91 |
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 |
92 |
99 // calculates derivatives until all of them are zeroable |
93 // calculates derivatives until all of them are zeroable |
100 @tailrec |
94 @tailrec |
101 def munch(cs: List[Char], rs: List[Rexp], stack: List[Option[Rexp]]) : Int = (cs, rs) match { |
95 def munch(s: List[Char], |
102 case (_, Nil) => last(stack) |
96 pos: Int, |
103 case (Nil, _) => last(stack) |
97 rs: List[Rexp], |
104 case (c::cs, rs) => { |
98 last: Option[Int]): Option[Int] = rs match { |
105 val ds = rs.map(der(c, _)) |
99 case Nil => last |
106 val rs_nzero = ds.filterNot(zeroable(_)) |
100 case rs if (s.length <= pos) => last |
107 val rs_nulls = ds.filter(nullable(_)) |
101 case rs => { |
108 val opt = Try(Some(rs_nulls.head)) getOrElse None |
102 val ders = rs.map(der(s(pos), _)) |
109 munch(cs, rs_nzero, opt::stack) |
103 val rs_nzero = ders.filterNot(zeroable(_)) |
|
104 val rs_nulls = ders.filter(nullable(_)) |
|
105 val new_last = if (rs_nulls != Nil) Some(pos) else last |
|
106 munch(s, 1 + pos, rs_nzero, new_last) |
110 } |
107 } |
111 } |
108 } |
112 |
109 |
113 // iterates the munching function and prints |
110 // iterates the munching function and prints |
114 // out the component strings |
111 // out the component strings |
115 @tailrec |
112 @tailrec |
116 def tokenize(s: String, rs: List[Rexp]) : Unit = munch(s.toList, rs, Nil) match { |
113 def tokenize(s: String, rs: List[Rexp]) : Unit = munch(s.toList, 0, rs, None) match { |
117 case 0 if (s == "") => println("EOF") |
114 case None if (s == "") => println("EOF") |
118 case 0 => println(s"Lexing error: $s") |
115 case None => println(s"Lexing error: $s") |
119 case n => { |
116 case Some(n) => { |
120 val (head, tail) = s.splitAt(n) |
117 val (head, tail) = s.splitAt(n + 1) |
121 print(s"|${head.replaceAll("\n","Ret")}|") |
118 print(s"|${head.replaceAll("\n","RET")}|") |
122 tokenize(tail, rs) |
119 tokenize(tail, rs) |
123 } |
120 } |
124 } |
121 } |
|
122 |
125 |
123 |
126 val test_prog = """ |
124 val test_prog = """ |
127 start := XXX; |
125 start := XXX; |
128 x := start; |
126 x := start; |
129 y := start; |
127 y := start; |