验证 2 个不同的 .y 文件之间的等价性
Validating the equivalence between 2 different .y files
我原来的 .y 文件导致一些 shift/reduce 和 reduce/reduce 冲突。
所以我改变了一些规则来消除这些冲突。而且我可以手动验证新旧版本之间的等价性。
但是，我想自动验证新版本是否等同于原始版本？怎么样？
一般情况下，无法自动证明等价性，因为两个CFG的等价性是不可判定的。可以在任何有关可计算性的教科书中找到这个众所周知的结果的证明。
有一些特殊情况是可判定的，但大多数不是特别有用。例如，您可以通过简单地枚举所有句子来证明两种有限语言的等价性。您可以通过构建各自的最小 DFA 并进行比较来证明两种正则语言的等价性。等等
在 yacc/bison 的情况下，如果您通过添加适当的优先级声明而不进行其他更改（"fix" 悬空 else 的经典方法，成功地减少了 "eliminating" shift-reduce 冲突问题），您可以简单地检查解析表（或 bison 的 --report 的输出以验证没有更改；也就是说，优先级声明编码了 bison 的默认冲突解决方案，因此只删除了警告。由于 reduce -reduce 冲突解决不受优先级影响，这不适用于删除 reduce-reduce 冲突警告的更改，但如果更改足够简单，您仍然可以基于比较生成的自动机手动构建证明。
我认为，即使您有证明，您也会想要进行详尽的测试。毕竟，证明中可能存在错误。
我原来的 .y 文件导致一些 shift/reduce 和 reduce/reduce 冲突。
所以我改变了一些规则来消除这些冲突。而且我可以手动验证新旧版本之间的等价性。
但是，我想自动验证新版本是否等同于原始版本？怎么样？
一般情况下，无法自动证明等价性，因为两个CFG的等价性是不可判定的。可以在任何有关可计算性的教科书中找到这个众所周知的结果的证明。
有一些特殊情况是可判定的，但大多数不是特别有用。例如，您可以通过简单地枚举所有句子来证明两种有限语言的等价性。您可以通过构建各自的最小 DFA 并进行比较来证明两种正则语言的等价性。等等
在 yacc/bison 的情况下，如果您通过添加适当的优先级声明而不进行其他更改（"fix" 悬空 else 的经典方法，成功地减少了 "eliminating" shift-reduce 冲突问题），您可以简单地检查解析表（或 bison 的 --report 的输出以验证没有更改；也就是说，优先级声明编码了 bison 的默认冲突解决方案，因此只删除了警告。由于 reduce -reduce 冲突解决不受优先级影响，这不适用于删除 reduce-reduce 冲突警告的更改，但如果更改足够简单，您仍然可以基于比较生成的自动机手动构建证明。
我认为，即使您有证明，您也会想要进行详尽的测试。毕竟，证明中可能存在错误。