4、自上而下分析法与 LL(1) 文法.md

# 自上而下分析

自上而下分析是一种**试探**的过程，是反复使用不同产生式谋求与输入序列匹配的过程

当既有左递归又有左因子的时候，**先消除左递归**

# 消除左递归

避免陷入**死循环**

## 消除直接左递归
若文法G中的非终结符A，对某个文法符号序列α存在推导$A=^+>Aα$，则称G是**左递归**的。若G中有形如A→Aα的产生式，则称该产生式对A**直接左递归**

* 首先，整理A产生式为如下形式:
	`A→ Aα1|Aα2|...|Aαm|β1|β2|...|βn`
* 其中αi非空[若αi为空，则形成一个有环的A产生式]，βj均不以A开始。然后用下述产生式代替A产生式：
	`A → β1 A' |β2 A' | ...|βn A'   `
	`A'→ α1 A' | α2 A' | ... | αm A' |ε`


## 消除文法左递归

核心思想：
* 将不是直接左递归的非终结符右部展开到其他产生式中

* 但是若G产生句子的过程中出现$A=^+>A$的推导，则无法消除左递归

步骤
* 合理排序非终结符：A1，A2，…，An;【通过两层for循环检验】
* 然后用用$Aj→δ1|δ2|…|δk$右部替换$Ai→Ajγ$中的Aj得到$Ai→δ1γ|δ2γ|…|δkγ$;再消除Ai产生式中的直接左递归;

如`S→Aa|b A→Ac|Sd|ε`

* 将S的右部展开在A中，得到：`A→Ac|Aad|bd|ε`

* 消除新产生式中的直接左递归，得到：`S→ Aa | b` `A→ bdA' | A'` `A'→ cA' | adA' | ε`

# 提取左因子

避免**回溯**

将：`A → αβ1|αβ2`，替换为：`A →αA' A'→β1|β2`

# 递归下降分析

1. 直接以程序的方式**模拟**产生式产生语言的过程
2. 每个**产生式**对应一个**子程序**，产生式右边的**非终结符**对应**子程序调用**，**终结符**则**与输入序列匹配**
3. 它对**文法的限制**是**不能有公共左因子和左递归**；
4. 它是一种**非形式化的方法，**只要能写出子程序，用什么样的方法和步骤均可

对比
* 优点：简单灵活、容易构造
* 缺点：程序与文法直接相关，对文法的任何改变均需对程序进行相应的修改
* 适合规模比较小的语言

稳妥的笨方法：

1. 构造文法的**状态转换图**并且**化简**

   - 标记为A的边可等价为**标记ε的边转向A转换图**的初态
   - **$ε$边连接的两个状态**可以合并
   - **标记相同**的路径可以合并
   - **不可区分**的状态可以合并

2. 将转换图转化为**EBNF**表示

   EBNF：扩展BNF（和正规式一样，为了表示方便加入的+、？、[]等等）

   ①${ }$：**重复0或若干次**（while）
   ② [ ]：可选择（if或while）
   ③ |：括弧( )之内的或关系（case）
   ④ ( )：改变运算的优先级和结合性

3. 从EBNF构造子程序

**构造递归下降字程序：**

* 首先设计两个变量lookahead（当前的下一输入的终结符）和eof（输入结束标志）

* 另外设计一个函数match(t)，进行终结符匹配

# 预测分析器

预测分析器是下推自动机的一个具体实现

栈中的内容是符号；而在移进-归约分析器的栈中内容是状态

<img src="https://img-blog.csdnimg.cn/20210124000323440.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70"  width="45%"/>


## 预测分析表

M[A, a]的内容：
* 若当前栈顶是非终结符A，下一输入终结符是a，则M[A, a]指示下一步动作；其中A为行下标，a为列下标

格局
* 格局是一个三元组（栈内容，当前剩余输入，改变格局的动作）

改变格局的动作：
* ① **匹配终结符**：若\^top=^ip(但≠#)，则pop且next(ip)
* ② **展开非终结符**：若^top= X且 M[X,^ip]=α(X→α)，则pop且push(α)
* ③ **报告分析成功**：若\^top=^ip=#，则分析成功并结束
* ④ **报告出错**：其它情况，调用错误恢复例程



### 构造预测分析表

1. 首先构造FIRST集合与FOLLOW集合
2. 然后根据两个集合构造预测分析表

 **文法符号序列**α的FIRST集合为:
*  $FIRST(α)=\{a|α=^*>a…，a∈T\}$，
 若$α=^*>ε$，则$ε∈FIRST(α)$

 **非终结符**A的FOLLOW集合如下:
 * $FOLLOW（A） = \{ a |S=^*>…Aa…，a∈T\}$，
 若A是某句型的最右符号，则$\#∈FOLLOW（A）$

通俗地讲
* α的FIRST集合就是**从α开始**可以导出的所有以终结符开头的序列中的**开头终结符**；
* 而A的FOLLOW集合，就是**从开始符号**可以导出的**所有含A的**文法符号序列中**紧跟A之后的终结符**

#### FIRST集合计算

**自下而上计算FIRST**

1. 若X∈T，则$FIRST(X)={X}$；
2. 若X是非终结符且有X→ε，则加入ε到FIRST(X)；
3. 若X是非终结符且有X→Y1Y2…Yk，并设Y0=ε，Yk+1=ε。那么对所有从0开始的j(0≤j≤k)，若a∈FIRST(Yj+1)且ε∈FIRST(Y1~Yj)【这里表示1到j都有ε】，则加入a到FIRST(X)。

说明
* FIRST(X1X2…Xn)是所有FIRST(Xi)(i=1,2,..,k)的并集，其中k为第一个具有性质**ε不属于FIRST（Xk）**或**k>n**的文法符号
* First集合里的符号一定是终结符，ε不是终结符，也不是非终结符，只是一个表示空的标志而已
* `T->array[num] of int`中`array`, `[`, `num`, `]`, `of`, `int`都是终结符

#### FOLLOW集合计算

**自上而下计算FOLLOW**

1. 加入#到FOLLOW(S)，其中S是开始符号，#是输入结束标记

2. 若有产生式A→αBβ，则除ε外，FIRST(β)的全体加入到FOLLOW(B)

3. 若有产生式A→αB或A→αBβ且ε∈FIRST(β)，则FOLLOW(A)的全体加入到FOLLOW(B)

   若 $S =^*>δAa$ （a紧跟A之后），则 $=>δαBa$ a也紧跟B之后（A→αB）

   或者 $=>δαBβa =^*>δαBa$ （A→αBβ）
   因为 ε∈FIRST(β) 使得B成为A产生式右部最右的文法符号，即 对任何a∈FOLLOW(A)，均有a∈FOLLOW(B)

**构造预测分析表：**

预测分析表的列都是**终结符**

1. 对文法的每个产生式A→α，执行2和3

2. 对FIRST(α)的每个终结符a，加入α到M[A，a]

   若当前栈顶为A，当前输入为a，则规则2表示下一步动作是展开A→α，因为a∈FIRST(α)，所以展开后下一次正好匹配a【这里α是aB…这样的表示，因为FIRST(α)里有a】

3. 若$ε∈FIRST(α)$，则对FOLLOW(A)的每个终结符b(包括#)加入α到M[A，b]

   若当前栈顶为A，当前输入为b且b∈FOLLOW(A)，则规则3表示下一步动作是展开A→ε，即栈顶弹出A，继续分析A之后的部分，因为b∈FOLLOW(A)，所以弹出A后下一次正好匹配A的后继b

4. M中其它没有定义的条目均是error

## 驱动器

```py
初始格局为: （#S，ω#，分析器的第一个动作）[其中ω是输入序列]
令ip指向ω#中的第一个终结符，top指向S;
  loop x:=top^; a:=ip^;
	if x ∈ T
	then  	if x=a 
			then pop(x); next(ip); -- 匹配终结符
      		else error(1);     -- 出错：栈顶终结符不是a
      		end if;
	else  	if   M[x, a] = X→Y1Y2...Yk
			then pop(X); push(YkYk-1...Y2Y1);--展开产生式
      		else error(2);     -- 出错：产生式不匹配
      		end if;
	end if;
	exit when x=# and a=#;           -- 分析成功
  end loop;
```

## LL(1)文法
文法G被称为是LL(1)文法，当且仅当为它构造的预测分析表中**不含多重定义的条目**；
* 由此分析表所组成的分析器被称为LL(1)分析器，它所分析的语言被称为LL(1)语言；
* 第一个L代表**从左到右扫描输入序列，**第二个L表示**产生最左推导**，1表示**在确定分析器的每一步动作时向前看一个终结符**

**任何二义文法都不是LL(1)文法**



### 证明是LL(1)文法
G是LL(1)的，当且仅当G的任何两个产生式A→α|β满足:
1. 对任何**终结符a**，α和β**不能同时推导出以a开始的串**
向前看一个就不够了，M[A，a]中有多重定义A→α和A→β
1. α和β**最**多有一个可以**推导出ε**
 向前看一个就不够了，任何属于FOLLOW（A）的终结符b(包括#)，M[A，b]中有多重定义A→α和A→β
1. 若**β=\*>ε**,则**α不能导出以FOLLOW(A)中终结符开始的任何串**

> 若条件3不满足，即存在终结符b，它既在FOLLOW(A)中，又在FIRST(α)中，
> 则步骤2把条目A→α加入到M[A，b]中，而步骤3又把条目A→β加入到M[A，b]中，即M[A，b] 中有多重定义A→α和A→β

所以**LL(1)文法既无左递归也无左因子**

缺点：

1. 文法难写，难懂
2. 适应范围有限，往往写不出有些语言的LL(1)文法

实际编译器中使用更多的是一类LL(1)文法的真超集——LR(1)文法