equal
deleted
inserted
replaced
137 |
137 |
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 ("F" -> List(T_NUM), |
|
143 "E" -> List(T_NUM), |
143 "E" -> List(NT("E"), T_OP("+"), NT("E")), |
144 "E" -> List(NT("E"), T_OP("+"), NT("E")), |
144 "E" -> List(NT("E"), T_OP("-"), NT("E")), |
145 "E" -> List(NT("E"), T_OP("-"), NT("E")), |
145 "E" -> List(NT("E"), T_OP("*"), NT("E")), |
146 "E" -> List(NT("E"), T_OP("*"), NT("E")), |
146 "E" -> List(T_LPAREN, NT("E"), T_RPAREN)) |
147 "E" -> List(T_LPAREN, NT("E"), T_RPAREN)) |
147 |
148 |
163 case None => None |
164 case None => None |
164 case Some((before, after)) => Some(before ::: in ::: after) |
165 case Some((before, after)) => Some(before ::: in ::: after) |
165 } |
166 } |
166 |
167 |
167 def parse(g: Grammar, ts: List[Token]) : Boolean = { |
168 def parse(g: Grammar, ts: List[Token]) : Boolean = { |
168 //println(ts) |
169 println(ts) |
169 if (ts == List(NT("E"))) true |
170 if (ts == List(NT("E"))) true |
170 else { |
171 else { |
171 val tss = for ((lhs, rhs) <- g) yield replace(ts, rhs, List(NT(lhs))) |
172 val tss = for ((lhs, rhs) <- g) yield replace(ts, rhs, List(NT(lhs))) |
172 tss.flatten.exists(parse(g, _)) |
173 tss.flatten.exists(parse(g, _)) |
173 } |
174 } |
178 parse(g, tokenizer(rs, s)) |
179 parse(g, tokenizer(rs, s)) |
179 } |
180 } |
180 |
181 |
181 |
182 |
182 |
183 |
183 parser(grammar, lexing_rules, "2 + 3 * 4 + 1") |
184 parser(grammar, lexing_rules, "2 + 3 * 4 + 1") |
184 parser(grammar, lexing_rules, "(2 + 3) * (4 + 1)") |
185 parser(grammar, lexing_rules, "(2 + 3) * (4 + 1)") |
185 parser(grammar, lexing_rules, "(2 + 3) * 4 (4 + 1)") |
186 parser(grammar, lexing_rules, "(2 + 3) * 4 (4 + 1)") |
186 |
187 |
187 |
188 |
188 |
189 |