检查两个 yacc 语法是否等效-解网

问：

你已经编写了一个 yacc 语法（或者你选择的工具中的其他一些 LALR 语法），并且你已经决定要重构一些产品以提高效率、清晰度等等。例如，您有：

xs : xs ';' x
   | xs ';'
   | x

您想更清楚地说明可以有多个分号，因此将其重写为：

semi_plus : semi_plus ';'
          | ';'
xs : xs semi_plus x
   | x

好吧，所以，看起来很有道理......但是我真的正确地进行了重构吗？如果我能把这些声明传递给一个工具，告诉我语法是否等效，那就太好了。（现在，让我们只考虑我们是否承认相同的语言的问题。

一种下意识的反应是引用上下文无关语法等价是无法确定的。事实上，即使是确定CFG是否规则的问题也是无法确定的。但是 yacc 不识别 CFG：它识别确定性上下文自由语法，并且对于这些语法，已知等价是可判定的。但是有没有人实施过这些决策程序？

解析复杂性理论

事实上，您提供的文本“等效性是可判定的”的链接并没有提供与该问题相关的任何参考资料。事实上，当霍普克罗夫特和乌尔曼写下他们宏伟的著作时，还不知道两个DCFL的等价性是否可判定。这一事实直到 1997 年才得到证实，并且仍然不知道是否存在多项式时间算法。在某种程度上，你似乎混淆了正则性与DCFL：DFA的等价性很简单（算法在H&U iirc中），但DCFL可能不是正则的。

2赞 Edward Z. Yang 12/23/2016

谢谢你的修复 rici;我确实在某处读到DCFL / DPDA等价性是可确定的，但我一定粘贴了错误的链接。链接现已修复（根据 Bob Atkey 的建议，我决定直接链接到 Stirling 的证明）

答： 暂无答案

上一个：解析命令行输入文件名以检查内容的正确性

下一个：等待JS加载内容后如何解析HTML页面？

检查两个 yacc 语法是否等效

Checking if two yacc grammars are equivalent

评论