111 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
111 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
112 else SEQ(der(c, r1), r2) |
112 else SEQ(der(c, r1), r2) |
113 case STAR(r) => SEQ(der(c, r), STAR(r)) |
113 case STAR(r) => SEQ(der(c, r), STAR(r)) |
114 } |
114 } |
115 |
115 |
116 // returns the position and Token function of |
116 |
117 // the last Some-element in the list |
|
118 def last(stack: List[Option[TokenFun]]) : Option[(Int, TokenFun)] = stack match { |
|
119 case Nil => None |
|
120 case None::stack => last(stack) |
|
121 case Some(tf)::stack => Some(1 + stack.length, tf) |
|
122 } |
|
123 |
117 |
124 // calculates derivatives until all of them are zeroable |
118 // calculates derivatives until all of them are zeroable |
125 @tailrec |
119 @tailrec |
126 def munch(cs: List[Char], |
120 def munch(s: List[Char], |
|
121 pos: Int, |
127 rs: LexRules, |
122 rs: LexRules, |
128 stack: List[Option[TokenFun]]) : Option[(Int, TokenFun)] = (cs, rs) match { |
123 last: Option[(Int, TokenFun)]): Option[(Int, TokenFun)] = rs match { |
129 case (_, Nil) => last(stack) |
124 case Nil => last |
130 case (Nil, _) => last(stack) |
125 case rs if (s.length <= pos) => last |
131 case (c::cs, rs) => { |
126 case rs => { |
132 val ds = rs.map({case (r, tf) => (der(c, r), tf)}) |
127 val ders = rs.map({case (r, tf) => (der(s(pos), r), tf)}) |
133 val rs_nzero = ds.filterNot({case (r, _) => zeroable(r)}) |
128 val rs_nzero = ders.filterNot({case (r, _) => zeroable(r)}) |
134 val rs_nulls = ds.filter({case (r, _) => nullable(r)}) |
129 val rs_nulls = ders.filter({case (r, _) => nullable(r)}) |
135 val opt = Try(Some(rs_nulls.head._2)) getOrElse None |
130 val new_last = if (rs_nulls != Nil) Some((pos, rs_nulls.head._2)) else last |
136 munch(cs, rs_nzero, opt::stack) |
131 munch(s, 1 + pos, rs_nzero, new_last) |
137 } |
132 } |
138 } |
133 } |
139 |
134 |
140 // iterates the munching function and returns a Token list |
135 // iterates the munching function and returns a Token list |
141 def tokenize(s: String, rs: LexRules) : List[Token] = munch(s.toList, rs, Nil) match { |
136 def tokenize(s: String, rs: LexRules) : List[Token] = munch(s.toList, 0, rs, None) match { |
142 case None if (s == "") => Nil |
137 case None if (s == "") => Nil |
143 case None => List(T_ERR("Lexing error: $s")) |
138 case None => List(T_ERR("Lexing error: $s")) |
144 case Some((n, tf)) => { |
139 case Some((n, tf)) => { |
145 val (head, tail) = s.splitAt(n) |
140 val (head, tail) = s.splitAt(n + 1) |
146 tf(head)::tokenize(tail, rs) |
141 tf(head)::tokenize(tail, rs) |
147 } |
142 } |
148 } |
143 } |
149 |
144 |
150 val test_prog = """ |
145 val test_prog = """ |