You wrote the yacc grammar (or some other LALR grammar in the tool of your choice), and you decided that you want to reorganize some pieces for efficiency, clarity, etc. For example, you had:
xs : xs ';' x | xs ';' | x
You want to make it more obvious that there can be several semicolons, so you rewrite it as:
semi_plus : semi_plus ';' | ';' xs : xs semi_plus x | x
OK, so that looks plausible ... but did I do the refactoring right? It would be great if I could pass these declarations to a tool that would tell me if the grammars are equivalent or not. (For now, let's only consider the question of whether we recognize the same languages.)
One knee-jerk reaction is to quote that contextual free grammatical equivalence is unsolvable. In fact, even the problem of determining the correctness of CFG is insoluble . But yacc does not recognize CFG: it recognizes deterministic contextual free grammars, and for them it is known that equivalence is decidable . But has anyone followed any of these decision-making procedures?
complexity-theory parsing
Edward Z. Yang
source share