84 case object T_WHITESPACE extends Token |
84 case object T_WHITESPACE extends Token |
85 case object T_NUM extends Token |
85 case object T_NUM extends Token |
86 case class T_OP(s: String) extends Token |
86 case class T_OP(s: String) extends Token |
87 case object T_LPAREN extends Token |
87 case object T_LPAREN extends Token |
88 case object T_RPAREN extends Token |
88 case object T_RPAREN extends Token |
89 case class T_NT(s: String) extends Token |
89 case class NT(s: String) extends Token |
90 |
90 |
91 type Rule = (Rexp, List[Char] => Token) |
91 type Rule = (Rexp, List[Char] => Token) |
92 |
92 |
93 def error (s: String) = throw new IllegalArgumentException ("Cannot tokenize: " + s) |
93 def error (s: String) = throw new IllegalArgumentException ("Cannot tokenize: " + s) |
94 |
94 |
138 type Grammar = List[(String, List[Token])] |
138 type Grammar = List[(String, List[Token])] |
139 |
139 |
140 // grammar for arithmetic expressions |
140 // grammar for arithmetic expressions |
141 val grammar = |
141 val grammar = |
142 List ("E" -> List(T_NUM), |
142 List ("E" -> List(T_NUM), |
143 "E" -> List(T_NT("E"), T_OP("+"), T_NT("E")), |
143 "E" -> List(NT("E"), T_OP("+"), NT("E")), |
144 "E" -> List(T_NT("E"), T_OP("-"), T_NT("E")), |
144 "E" -> List(NT("E"), T_OP("-"), NT("E")), |
145 "E" -> List(T_NT("E"), T_OP("*"), T_NT("E")), |
145 "E" -> List(NT("E"), T_OP("*"), NT("E")), |
146 "E" -> List(T_LPAREN, T_NT("E"), T_RPAREN)) |
146 "E" -> List(T_LPAREN, NT("E"), T_RPAREN)) |
147 |
147 |
148 |
148 |
149 def chop[A](ts1: List[A], prefix: List[A], ts2: List[A]) : Option[(List[A], List[A])] = |
149 def chop[A](ts1: List[A], prefix: List[A], ts2: List[A]) : Option[(List[A], List[A])] = |
150 ts1 match { |
150 ts1 match { |
151 case Nil => None |
151 case Nil => None |
162 chop(ts, out, Nil) match { |
162 chop(ts, out, Nil) match { |
163 case None => None |
163 case None => None |
164 case Some((before, after)) => Some(before ::: in ::: after) |
164 case Some((before, after)) => Some(before ::: in ::: after) |
165 } |
165 } |
166 |
166 |
167 def parse1(g: Grammar, ts: List[Token]) : Boolean = { |
167 def parse(g: Grammar, ts: List[Token]) : Boolean = { |
168 //println(ts) |
168 //println(ts) |
169 if (ts == List(T_NT("E"))) true |
169 if (ts == List(NT("E"))) true |
170 else { |
170 else { |
171 val tss = for ((lhs, rhs) <- g) yield replace(ts, rhs, List(T_NT(lhs))) |
171 val tss = for ((lhs, rhs) <- g) yield replace(ts, rhs, List(NT(lhs))) |
172 tss.flatten.exists(parse1(g, _)) |
172 tss.flatten.exists(parse(g, _)) |
173 } |
173 } |
174 } |
174 } |
175 |
175 |
|
176 def parser(g: Grammar, rs: List[Rule], s: String) = { |
|
177 println("\n") |
|
178 parse(g, tokenizer(rs, s)) |
|
179 } |
|
180 |
176 |
181 |
177 println() ; parse1(grammar, tokenizer(lexing_rules, "2 + 3 * 4 + 1")) |
182 |
178 println() ; parse1(grammar, tokenizer(lexing_rules, "(2 + 3) * (4 + 1)")) |
183 parser(grammar, lexing_rules, "2 + 3 * 4 + 1") |
179 println() ; parse1(grammar, tokenizer(lexing_rules, "(2 + 3) * 4 (4 + 1)")) |
184 parser(grammar, lexing_rules, "(2 + 3) * (4 + 1)") |
|
185 parser(grammar, lexing_rules, "(2 + 3) * 4 (4 + 1)") |
180 |
186 |
181 |
187 |
182 |
188 |