编译原理复习二：Top-Down分析LL(1)文法的判断与LL(1)分析表的构造（附题目与答案超详细）

àì夳堔傛蜴生んèń 2023-09-30 19:32 2阅读 0赞

> **需要原卷和答案请点赞关注收藏后评论区留言私信~~~**
> 
> **有问题可以在评论区讨论~~~**

## 一、LL(1)文法的定义 ##

LL(1)文法：从文法的开始符，向下推导，推出句子。

对文法G的句子进行确定的自顶向下语法分析的充分必要条件是，G的任意两个具有相同左部的

产生式A—>α|β 满足下列条件：

（1）如果α、β均不能推导出ε，则 FIRST(α) ∩ FIRST(β) = ∅。

（2）α 和 β 至多有一个能推导出 ε。

（3）如果 β \*═> ε，则 FIRST(α) ∩ FOLLOW(A) = ∅。

将满足上述条件的文法称为LL(1)文法。

因为自顶向下的语法处理不了左递归与左公因子，因此要先消除

1：消除左递归

由于自上而下的分析方法不允许文法含有左递归。

因此对于包含直接左递归和间接左递归的文法都要消除左递归。

直接消除左递归比较容易。

例如：

P->Pa | b

直接消除左递归

P->bP'

P'->aP' | ε

2：提左因子

如果不提左因子，当面临两个相同的前缀，不知道选择哪条，必然会产生回溯。为了消除回溯，我们需要提左因子。

## 二、LL(1)文法判断实战 ##

**Consider the following grammar G\[S\]:**

![5b3bc82606e8413abcd1581596e98037.png][]

*S→(L)|aS’*

*S’→S|ε*

*L→SL’*

*L’→SL’|ε*

首先我们要求出各个非终结符的first集和follow集，这个也不复杂，规则如下

> 计算单个文法符号X的FIRST(X)时，不断应用以下规则，直到没有新的终结符或者是ε加入。  
> （1）如果X是终结符号，那么FIRST(X)=\{X\}  
> （2）如果X是非终结符号，且X->ε是一个产生式，那么ε在FIRST(X)中。  
> （3）如果X是非终结符号，且X->Y1Y2…Yk是产生式  
> —如果ε在FIRST(Y1), FIRST(Y2),…, FIRST(Y i-1)中，那么FIRST(Yi)中的非ε元素，也在FIRST(X)中。  
> —如果ε在FIRST(Y1), FIRST(Y2),…, FIRST(Yk)中，那么ε在FIRST(X)中。(PS:注意这里是k，也就是说要所有都能推出 ε 才能说明 ε 在FIRST(X)

follow集求解规则如下

> 将右端结束标记 $ 放到FOLLOW(S)中，S是开始符号。  
> 按下面的两个规则不断迭代，直到没有新的终结符或者是ε加入。  
> ①如果存在产生式A->αBβ，那么FIRST(β)-\{ε\}【表示除了ε之外的符号】的符号都在FOLLOW(B)中。  
> ②如果存在产生式A->αB，或者A->αBβ且FIRST(β)包含ε，那么FOLLOW(A)中所有符号都加入到FOLLOW(B)中。

上述文法求解如下

![367eae152dc849fba4496b1d138a0822.png][]

接下来判断是不是LL(1)文法要求出select集，当然求出first和follow集之后求select集就简单多了

**select(X->Y)，先求first（Y），如果first（Y）存在\#∈first（Y）的情况，则再求follow（X），最后求两者的并集即可即可**

**LL(1)判断方法：如果相同产生式左部的Select集有交集，则该文法不为LL(1)文法**

上述文法判断结果如下：S’→S|ε : *ε in First(S’), and First(S’) ∩ Follow(S’)≠Φ,* So the grammar is not LL(1)

## 三、LL(1)分析表构造 ##

有了上面求出的first，follow，select集之后构造分析表就简单许多了，可以理解为根据select集构造分析表，结果如下

![9d3a2d6f4a8b4318bc11a32b0710ec3a.png][]

**创作不易 觉得有帮助请点赞关注收藏~~~**

[5b3bc82606e8413abcd1581596e98037.png]: https://img-blog.csdnimg.cn/5b3bc82606e8413abcd1581596e98037.png
[367eae152dc849fba4496b1d138a0822.png]: https://img-blog.csdnimg.cn/367eae152dc849fba4496b1d138a0822.png
[9d3a2d6f4a8b4318bc11a32b0710ec3a.png]: https://img-blog.csdnimg.cn/9d3a2d6f4a8b4318bc11a32b0710ec3a.png