左因子分解与左递归之间的差异

Question

Left Factoring和之间有什么区别Left Recursion？据我所知,这Left factoring是一种预测自上而下的解析技术.但是当我听到这两个术语时,我感到困惑.

Answer 1

左因子分解是去除出现在同一非终端的两个产生中的共同左因子.这样做是为了避免解析器回溯.假设解析器具有预测,请考虑此示例 -

A - > qB | qC
其中A,B,C是非终端,q是句子.在这种情况下,解析器将会混淆选择哪两个产品,并且可能需要回溯.在左保理后,语法转换为 -

A - > qD

D - > B | C

在这种情况下,具有前瞻的解析器将始终选择正确的生产.

左递归是一种情况,当非终端生产中最左边的非终端是非终端本身(直接左递归)或通过一些其他非终端定义,再次重写到非终端(间接)左递归).考虑这些例子 -

(1)A - > Aq(直接)

(2)A - > Bq B - > Ar(间接)

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

Answer 2

Left Factoring是一种语法转换技术.它包括"分解"两个或多个作品共有的前缀.

例如,从:

A→αβ| αγ

至:

A→αA'

A'→β| γ

Left Recursion是一个语法所具有的属性,只要你可以在一个或多个步骤中从给定变量(非终端)派生以相同变量开头的rhs.

例如:

A→Aα

要么

A→Bα

B→Aγ

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

两个术语之间的关系/混淆可能源于这样的事实:在能够为其导出预测性自顶向下解析器之前,两种转换技术可能需要应用于语法.

Answer 3

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

1. 左递归:当一个或多个产品可以从它们自己到达时,其间没有消耗的代币.
2. 左分解:转换过程,将语法从左递归形式转换为等效的非左递归形式.

Answer 4

左因素:

让给定的语法:A - > ab1 | ab2 | AB3

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

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

左递归:

A - > Aa | b这里很清楚,如果我们选择第一个产品,A的左边的孩子将永远是A,这是左递归.因为,A一遍又一遍地呼唤自己.从这个语法生成的字符串是:ba*因为这不能用语法...我们通过编写来消除左递归:

A - > bA'A' - > E | aA'现在我们不会离开递归,也可以生成ba*.

Answer 5

左递归： \n如果语法具有非终结符 A 并且存在推导A -> A\xce\xb1 | ，则该语法是左递归的。\xce\xb2其中 \xce\xb1 和 \xce\xb2 是不以 A 开头的终结符和非终结符序列。

\n\n

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

\n\n

A -> \xce\xb2A'

\n\n

A' -> \xce\xb1A' | 厄普西隆

\n\n

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

\n\n

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

\n\n

S -> aS'

\n\n

S'-> bS | 锑

\n\n

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

\n