左因子分解与左向递归的区别 [英] Difference between Left Factoring and Left Recursion

问题描述

左因子和左循环之间有什么区别？我理解左因子分解是一种自顶向下的解析技术。但是当我听到这两个术语时，我很困惑。

What is the difference between Left Factoring and Left Recursion ? I understand that Left factoring is a predictive top down parsing technique. But I get confused when I hear these two terms.

推荐答案

左因子分解是去除了两个生成中常见的左因子相同的非终端。这是为了避免解析器的回溯。假设解析器具有前瞻性，考虑这个例子 -

Left factoring is removing the common left factor that appears in two productions of the same non-terminal. It is done to avoid back-tracing by the parser. Suppose the parser has a look-ahead ,consider this example-

A - > qB | qC

其中A，B，C是非终端，q是一个句子。
在这种情况下，解析器将被混淆，选择两个产品中的哪一个，它可能必须回溯。离开分解后，语法转换为 -

A -> qB | qC
where A,B,C are non-terminals and q is a sentence. In this case, the parser will be confused as to which of the two productions to choose and it might have to back-trace. After left factoring, the grammar is converted to-

A - > qD

A -> qD

D - > B | C

D -> B | C

在这种情况下，具有前瞻性的解析器将总是选择正确的作品。

In this case, a parser with a look-ahead will always choose the right production.

左递归是当非终端的产生中的最左边的非终端是非终端自身（直接向左递归）或通过一些其它非终端定义，再次重写到非终端（间接向左递归）。
考虑这些例子 -

Left recursion is a case when the left-most non-terminal in a production of a non-terminal is the non-terminal itself( direct left recursion ) or through some other non-terminal definitions, rewrites to the non-terminal again(indirect left recursion). Consider these examples -

（1）A - > Aq（直接）

(1) A -> Aq (direct)

）A - > Bq
B - > Ar（indirect）

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

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

Left recursion has to be removed if the parser performs top-down parsing

这篇关于左因子分解与左向递归的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！