为什么野牛不会自动转换语法？

Question

我正在学习词法分析器和解析器，所以我正在读这本经典书：flex＆bison（作者：John Levine，出版社：O'Reilly Media）。给出了一个野牛无法解析的例子：

phrase : cart_animal AND CART | work_animal AND PLOW
cart_animal-> HORSE | GOAT
work_animal -> HORSE | OX

我很清楚为什么不能这样做。实际上，它需要两个前瞻符号。

但是，通过简单的修改，它可以被解析：

phrase : cart_animal CART | work_animal PLOW
cart_animal-> HORSE AND | GOAT AND
work_animal -> HORSE AND | OX AND

我想知道为什么野牛在这种简单的情况下无法自动翻译语法？

Answer 1

因为像这样的简单案例非常人为，而在现实生活中的例子中，很难或不可能。

要明确的是，如果你有LR(k)的k>1语法并且你知道k的价值，那么你可以用一个机械变换来制作一个等效的LR(1)语法，而且你可以通过一些杂耍来修复减少动作，以便它们具有相同的效果（至少，只要它们不含副作用）。我不知道任何解析器生成器这样做，部分是因为正确翻译缩减操作将是棘手的，并且部分因为得到的LR（1）语法通常非常大，即使对于k的小值。

但是，正如我上面提到的，你需要知道k的值来执行这个转换，结果证明没有算法可以采用语法并告诉你它是否是LR(k)。所以你所能做的就是先尝试更大的k值，直到找到一个有效的，或者你决定放弃它。