【编译原理系列】自上而下分析法与 LL(1) 文法

以你之姓@ 2023-01-10 11:49 197阅读 0赞

# 自上而下分析 #

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

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

# 消除左递归 #

避免陷入**死循环**

## 消除直接左递归 ##

若文法G中的非终结符A，对某个文法符号序列α存在推导 A = + > A α A=^+>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 A=^+>A A=\+>A的推导，则无法消除左递归

步骤

*  合理排序非终结符：A1，A2，…，An;【通过两层for循环检验】
 *  然后用用 A j → δ 1 ∣ δ 2 ∣ … ∣ δ k Aj→δ1|δ2|…|δk Aj→δ1∣δ2∣…∣δk右部替换 A i → A j γ Ai→Ajγ Ai→Ajγ中的Aj得到 A i → δ 1 γ ∣ δ 2 γ ∣ … ∣ δ k γ Ai→δ1γ|δ2γ|…|δkγ 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)，进行终结符匹配

# 预测分析器 #

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70][]

## 预测分析表 ##

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集合为:

*   F I R S T ( α ) = \{ a ∣ α = ∗ > a … ， a ∈ T \} FIRST(α)=\\\{a|α=^\*>a…，a∈T\\\} FIRST(α)=\{ a∣α=∗>a…，a∈T\}，  
    若 α = ∗ > ε α=^\*>ε α=∗>ε，则 ε ∈ F I R S T ( α ) ε∈FIRST(α) ε∈FIRST(α)

**非终结符**A的FOLLOW集合如下:

*   F O L L O W （ A ） = \{ a ∣ S = ∗ > … A a … ， a ∈ T \} FOLLOW（A） = \\\{ a |S=^\*>…Aa…，a∈T\\\} FOLLOW（A）=\{ a∣S=∗>…Aa…，a∈T\}，  
    若A是某句型的最右符号，则 \# ∈ F O L L O W （ A ） \\\#∈FOLLOW（A） \#∈FOLLOW（A）

通俗地讲

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

#### FIRST集合计算 ####

**自下而上计算FIRST**

1.  若X∈T，则 F I R S T ( X ) = X FIRST(X)=\{X\} 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 = ∗ > δ A a S =^\*>δAa S=∗>δAa （a紧跟A之后），则  = > δ α B a =>δαBa =>δαBa a也紧跟B之后（A→αB）
    
    或者  = > δ α B β a = ∗ > δ α B a =>δαBβa =^\*>δαBa =>δα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.  若 ε ∈ F I R S T ( α ) ε∈FIRST(α) ε∈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

## 驱动器 ##

初始格局为: （#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→β
2.  α和β**最**多有一个可以**推导出ε**  
    向前看一个就不够了，任何属于FOLLOW（A）的终结符b(包括\#)，M\[A，b\]中有多重定义A→α和A→β
3.  若**β=\*>ε**,则**α不能导出以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)文法

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]: /images/20221119/506876d0f3dd48138474dd7d346ec982.png