左分解因子和左递归之间的区别

Question

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

Answer 1

这是我见过用这两个词的方式：

1. 左递归：当一个或多个作品可以从自己达到无消耗在中间的标记。
2. 左分解：转换过程，将语法从左递归形式转换为等价的非左递归形式。

Answer 2

left recursion：=当左手非终端与右手非终端相同时。 示例： A-> A & | B其中&是阿尔法。 我们可以使用重写这个生产来删除左边的ricursion。

A-> BA” A ' - > & A' |€

左因素意味着productn不应该不确定性。 。 例如： A-> & A | & B | & C

Answer 3

左分解是一种语法转换技术。它包括“分解”两个或更多产品共有的前缀。

例如，从去：

A - >αβ| αγ

到：

A - >αA '

A' - >β| γ

---

左递归是一个属性语法具有每当你可以从一个给定的可变（非终端）导出RHS具有相同变量开始，在一个或多个步骤。

例如：

A - > Aα

或

A - >乙α

乙 - >甲γ

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

---

的关系/这两个词之间的混淆可能是由事实上，这两个转换技术可能需要能够得到的预测自上而下解析器之前被应用到语法派生的。

Answer 4

左保留因子是消除在同一个非终端的两个生产中出现的常见左边因素。这样做是为了避免解析器回溯。假设解析器有预见性，请考虑此示例 -

A - > qB | qC
其中A，B，C是非终端并且q是句子。 在这种情况下，解析器会对两种产品中的哪一种产品感到困惑，并且可能需要回溯。左理后，语法转换TO-

A - > qD的

d - >乙| C

在这种情况下，带前视的解析器将始终选择正确的生产。

左递归是一种情况，当非终端生产中最左侧的非终端本身是非终端本身（直接左递归）或通过一些其他非终端定义时，重写为非终端本身，终端再次（间接左递归）。 考虑这些实施例 -

（1）A - > AQ（直接）

（2）A - >贝 乙 - >氩（间接）

左递归必须被删除，如果该分析器进行自上而下的分析

Answer 5

左递归： 文法留下，如果它有一个非终结符号A使得有一个推导递归A - >Aα| β其中α和β是不以A开头的末端和非末端序列。

设计自顶向下解析器时，如果语法中存在左递归，则解析器会陷入无限循环，这是因为A正试图匹配A本身，这是不可能的。 我们可以通过重写违规生产来消除上述左递归。AS-

A - >βA '

A' - >αA” | epsilon

左分解：左分解需要消除语法的非确定性。假设一个文法，S - > abS | aSb

这里，S在生产规则（S的两个替代选择）中导出相同的终端a，其遵循非确定性。我们可以重写生产推迟S的决定AS-

的S - >为 '

S' - > BS |锑

因此，S”可以被替换为bs或锑

Answer 6

左因素：

让定的文法： A - > AB1 | ab2 | ab3

1）我们可以看到，对于每一个生产，如果我们在这里选择任何生产，都会有一个共同的前缀&，我们不会确定我们不需要回溯。
2）它是非确定性的，因为我们无法选择任何生产，并且确信我们将通过制作正确的分析树来达到我们期望的字符串。 但是如果我们以确定性的方式重写语法，并且让我们足够灵活以使它可能没有回溯的任何字符串....它将是：

A→aA' ， A' - > b1 | B2 | b3 现在，如果我们被要求为字符串ab2 ......制作解析树，我们不需要回溯。因为当我们得到A时，我们总是可以选择正确的生产，因此我们将生成正确的分析树。

左递归：

A→Aa | b 这里很明显，如果我们选择第一个生产，A的左边的孩子总是A，这是左边的递归，因为A一遍又一遍地调用自己。 从这个语法生成的字符串是： 巴* 因为这不能是一个语法......我们通过书面消除左递归：

A - > BA“ A” - > E | aA' 现在我们不会有递归，并且我们也可以生成ba *。