证明存在左递归的文法一定不是LL(1)文法

首先，LL(1)文法要求每个非终结符的任意两个产生式的首字符集合都不相交。而对于存在左递归的文法，例如以下文法：

A -> Aa | b

该文法存在左递归，因为在第一条产生式中，非终结符A出现在了产生式右部的首位。而对于该文法，我们可以推导出：

FIRST(A) = {b, a}

因为在第一条产生式中，A可以推导出a，而在第二条产生式中，A可以推导出b。因此，对于该文法，存在两个产生式的首字符集合相交，即{b}。

因此，可以证明存在左递归的文法一定不是LL(1)文法。

相关问题

证明存在左因子的文法一定不是LL(1)文法

### 回答1：
要证明存在左因子的文法一定不是LL(1)文法，可以通过反证法。假设存在一个文法G，它存在左因子，但是它是LL(1)文法。那么，对于任意非终结符A和终结符a，都有且只有一个产生式A → α，使得FIRST(α) ∩ FIRST(a) ≠ ∅ 或者 α可以推导出ε。

由于G存在左因子，所以对于某个非终结符A，存在两个产生式A → αβ和A → αγ，其中β和γ是不同的符号串。假设在LL(1)分析G的时候，我们要分析的符号串的第一个终结符是a。根据LL(1)文法的定义，我们需要根据输入符号预测应该使用哪个产生式进行推导。但是，根据上面的假设，无论我们选择A → αβ还是A → αγ作为产生式，都会导致FIRST(αβ) ∩ FIRST(a) ≠ ∅ 或者 FIRST(αγ) ∩ FIRST(a) ≠ ∅，因为β和γ是不同的符号串，它们的FIRST集合可能有交集。这就违反了LL(1)文法的定义，因为LL(1)文法要求对于任意非终结符A和终结符a，都有且只有一个产生式A → α，使得FIRST(α) ∩ FIRST(a) ≠ ∅ 或者 α可以推导出ε。

因此，假设不成立，存在左因子的文法一定不是LL(1)文法。

### 回答2：
证明存在左因子的文法一定不是LL(1)文法的原因如下：

LL(1)文法是一种自上而下的语法分析方法，其中的LL表示从左向右扫描句子，同时递归地对句子进行左推导，1表示在每个步骤中只需要查看一个输入符号。LL(1)文法要求文法的每个产生式都不能存在相同的左部的左因子。

假设存在一个文法G，其中某个产生式A -> αβ和A -> αγ存在共同的左因子α，其中β和γ是不同的产生式。根据这个产生式，我们可以看到在使用LL(1)分析算法时无法按照一个输入符号进行决策，因为无法确定应该选择哪个产生式。这违反了LL(1)文法的要求。

为了解决这个问题，我们可以对文法进行修改，消除左因子。例如，我们可以将产生式A -> αβ和A -> αγ进行重写，使其变为A -> αA'，A' -> β | γ。通过这样的修改，原本存在的左因子α被移动到了右部，从而满足了LL(1)文法的要求。

综上所述，存在左因子的文法一定不是LL(1)文法，因为LL(1)文法要求每个产生式的左部都不能有相同的左因子。

LL（1）型文法消除左递归应该怎么做呢

消除左递归的步骤如下：

1. 把文法拆分成两个集合：左递归集合和非左递归集合。

2. 对于左递归的产生式，进行消除。假设文法中存在以下产生式左递归：

A → Aα1 | Aα2 | … | Aαm | β1 | β2 | … | βn

首先，将β1、β2、…、βn中不含A的产生式提取出来，形成新的产生式B → β1 | β2 | … | βn。将原产生式修改为：

A → Aα1 | Aα2 | … | Aαm | BB1 | BB2 | … | BBn

接下来，对于左递归的产生式A → Aα1 | Aα2 | … | Aαm，按照以下公式进行修改：

A → β1A’ | β2A’ | … | βnA’
A’ → α1A’ | α2A’ | … | αmA’ | ε

其中，β1、β2、…、βn是不含A的产生式，α1、α2、…、αm是任意串，ε是空串。

3. 消除左递归后，可能会产生左公因子。需要将这些左公因子提取出来，形成新的非终结符和产生式，原有的产生式需要做相应的修改。

4. 对文法进行求FIRST集和FOLLOW集的计算。

5. 构造LL(1)分析表。

注意事项：

1. 消除左递归时，需要保持文法的动态特性。例如，对于以下文法：

A → AB
A → a
B → CD
B → b
C → c
D → d

如果将B → CD的左递归消除得到B → bC’，再将C’ → DC’ | ε的左递归消除得到C’ → cD’，那么产生式A → AB经过消除左递归后变成了A → aB，丧失了原有的动态定义。

2. 在消除左递归时，需要注意保证消除后的文法与原有文法等价。如果存在不等价的情况，则需要重新选择消除左递归的方法。