左分解和左递归之间的区别 [英] Difference between Left Factoring and Left Recursion

问题描述

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

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是一个句子.

where A, B and 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
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).

考虑以下示例:

(1) A -> Aq (direct)

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

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

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

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