左因子分解与左递归的区别

Question

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

Answer 1

左因式分解消除了出现在同一非终结点的两个乘积中的公共左因数。这样做是为了避免解析器的回溯。假设解析器具有前瞻性，请考虑下面的示例：

A -> qB | qC    

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

在这种情况下，解析器将会对选择两个结果中的哪一个感到困惑，并且可能需要回溯。在左因式分解之后，语法转换为：

A -> qD
D -> B | C

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

左递归是当非终结符的产生中最左边的非终结符是非终结符本身时的情况(直接左递归)，或者通过一些其他非终结符定义，再次重写到非终结符(间接左递归)。

考虑以下示例：

(1) A -> Aq (direct)

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

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

Answer 2

左分解是一种语法转换技术。它包括“因式分解”前缀，这些前缀在两个或更多的产品中是通用的。

例如，来自：

A→αβ|αγ

至：

A→αA‘

A‘→β|γ

左递归是一种文法所具有的属性，只要你可以从一个给定的变量(非终结点)派生出一个以相同变量开始的rhs，在一个或多个步骤中。

例如：

A→Aα

或

A→Bα

B→Aγ

有一种名为消除左递归的语法转换技术，它提供了一种方法，可以在给定左递归语法的情况下生成另一种等价且不是左递归的语法。

这两个术语之间的关系/混淆可能源于这样一个事实，即这两种转换技术可能都需要应用于语法，然后才能为其推导出预测的自上而下的解析器。

Answer 3

这就是我看到的这两个术语的用法：

in-between.

• Left

1. 左递归:当一个或多个结果可以从自身到达而不消耗令牌时，in-between.
2. Left因子分解:一个转换过程，将语法从左递归形式转换为等效的非左递归形式。