42

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

4

7 回答 7

66

左因子分解是删除出现在相同非终结符的两个产生式中的常见左因子。这样做是为了避免解析器进行回溯。假设解析器具有前瞻功能，请考虑以下示例：

A -> qB | qC

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

在这种情况下，解析器将困惑于选择两个产生式中的哪一个，并且可能不得不回溯。左因式分解后，语法转换为：

A -> qD
D -> B | C

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

左递归是当非终结符的产生中最左边的非终结符是非终结符本身（直接左递归）或通过其他一些非终结符定义，再次重写为非终结符（间接左递归）。

考虑这些例子：

(1) A -> Aq (direct)

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

如果解析器执行自顶向下解析，则必须删除左递归。

于 2014-09-09T17:32:17.233 回答
26

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

例如，从：

A → α β | α γ

至：

A → α A'

A' → β | γ

左递归是语法具有的一种属性，只要您可以从给定变量（非终结符）派生出以相同变量开头的 rhs，在一个或多个步骤中。

例如：

A → A α

或者

A → B α

B → A γ

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

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

于 2014-06-20T20:39:20.870 回答
11

这是我看到使用的两个术语的方式：

  1. 左递归：当一个或多个产品可以从它们自身到达且中间没有代币消耗时。
  2. 左因式分解：一个转换过程，将语法从左递归形式转变为等价的非左递归形式。
于 2013-03-04T06:44:31.227 回答
8

左因素：

让给定的语法：A-->ab1 | ab2 | ab3

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

A --> aA', A' --> b1 | b2| b3

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

左递归：

一个--> Aa | b 这里很明显，如果我们选择第一个产生式，A 的左孩子将永远是 A，这是左递归。因为，A 一遍又一遍地调用自己。从这个语法生成的字符串是：ba* 因为这不能在语法中......我们通过编写来消除左递归：

A --> bA' A' --> E | aA' 现在我们将没有左递归，而且我们可以生成 ba* 。

于 2015-08-26T07:23:17.910 回答
4

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

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

A -> βA'

A' -> αA' | ε

左因子分解：需要左因子分解来消除语法的不确定性。假设一个语法，S -> abS | 锑

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

S -> aS'

S' -> bS | 锑

因此，S' 可以替换为 bS 或 Sb

于 2015-03-22T21:37:00.160 回答
2

这是区分这两个术语的简单方法：

  • 左递归：当产品的最左边元素是生产元素本身（非终端元素）时。

例如A -> Aα / Aβ

  • 左因子分解：当一个产生式的最左边的元素（终端元素）在同一个产生式中重复时。

例如A -> αB / αC

此外， 如果语法是左递归的，它可能会导致无限循环，因此我们需要消除左递归。

如果语法是左因子，它会使解析器感到困惑，因此我们也需要删除左因子。

于 2020-01-23T09:52:03.440 回答
0

左递归：= 当左手非终端与右手非终端相同时。示例：A->A&|B 其中 & 是 alpha。我们可以像这样重写这个产生式来删除左递归。

A->BA' A'->&A'|€</p>

左因子意味着产品不应该是不确定的。. 示例：A->&A|&B|&C

于 2013-03-11T18:09:26.417 回答