parsing - 左分解与左递归之间的区别

Left Factoring和Left Recursion有什么区别？我知道Left factoring是一种预测性的自上而下的解析技术。但是，当我听到这两个词时，我会感到困惑。

最佳答案

左因子消除了出现在同一非终端的两个生成中的常见左因子。这样做是为了避免解析器回溯。假设解析器具有前瞻性，请考虑以下示例:

A -> qB | qC

其中A，B和C是非终结符，而q是句子。

在这种情况下，解析器在选择两个产品中的哪个产品时会感到困惑，并且可能必须回溯。左分解后，语法将转换为:

A -> qD
D -> B | C

在这种情况下，具有前瞻性的解析器将始终选择正确的产品。

左递归是指非终端生成中最左边的非终端是非终端本身(直接左递归)或通过其他一些非终端定义再次重写为非终端(间接)的情况左递归)。

考虑以下示例:

(1) A -> Aq (direct)

(2) A -> Bq
    B -> Ar (indirect)

如果解析器执行自上而下的解析，则必须删除左递归。