编译原理教程_4 语法分析_不含多重定义入口

文章原稿
https://gitee.com/fakerlove/fundamentals-of-compiling

4. 语法分析

4.1 概述

4.1.1功能

编译程序的核心部分

根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。

4.1.2 基本任务

识别符号串S是否为该文法的某语法成分。

4.1.3 两大类方法

①自顶向下分析
基本思想：
②自底向上分析
基本思想：
对比：

4.1.4 理论基础

上下文无关文法和下推自动机PDA

上下文无关法已经讲过了

4.1.5 下推自动机PDA

1) 概念

下推自动机的定义：一个不确定的PDA可以表达成一个7元组： M = (Σ, Q, Γ, δ, q0, Z0, F) 其中，Σ 是输入符号的有穷集合； Q 是状态的有限集合； q0 ∈ Q 是初始状态； Γ 为下推存储器符号的有穷集合； Z0∈Γ 为最初出现在下推存储器顶端的开始符号; F 是终止状态集合，F ⊆ Q； δ 是从 Q×(Σ∪{ε})×Γ 到 Q×Γ* 的子集的映射。

映射关系 δ(q, a, Z) = {(q1, γ1), (q2, γ2), …, (qm, γm)} 其中, q1, q2, …, qm∈Q, a∈Σ, Z∈Γ, γ1, γ2,…,γm∈Γ*。 该映射的意思是：当PDA处于状态 q，面临输入符号 a时，自动机将进入到 qi, i = 1, 2, …, m 状态，并以 γi 来代替下推存储器（栈）顶端符号Z，同时将输入头 指向下一个字符 。当 Z 被 γi 取代时，γi 的符号按照 从左到右的顺序依次从下向上推入到存储器。

特殊情况下，δ(q, ε, Z)={(q1, γ1), (q2, γ2), …, (qm, γm)} 时，输入头位置不移动，只用于处理下推存储器内部 的操作，叫作 “ε移动”。

这些定义我看得快炸了，没理解这是什么意思。下面是一个图，可能比较直观的显示出，下推自动机与有限自动机的区别就是多出一个下推存储器。

以上的定义都是教材的内容，如果光看理论，我反正是一头雾水，不知所云。不过结合一个例子可能会有所理解。下面的例子是判断一个句子是否能够被下推自动机所接受。

2) 下推自动机接受的语言

下推自动机 M 所接受的语言定义为： T(M) = {x|x: (q0, Z0) (q, M γ), γ ∈Γ*, q ∈F }。下面通过这个例子来走一遍过程。看着下面这些符号实在是头大，不过通过具体的例子分析也不难理解。

对于输入 abbcbba 这个句子。下推自动机 是怎么样判断这个句子是否合法呢？它的处理步骤如下：

（一）、#是开始符号，0是初始状态。首先从输入带的第一个字符读入。输入了a，根据规则 1。将A压入栈。状态仍然为0；

（二）、状态为0，输入b。根据规则 2。将B压入栈，状态仍然为0.

（三）、状态为0，输入b。根据规则 2。将B压入栈，状态仍然为0.

（四）、状态为0，输入c。根据规则 3。将ε（空串）压入栈中，也就是什么都不做，状态变为1.

（五）、状态为1，输入b。根据规则 5。将B弹出栈，状态仍然为1.

（六）、状态为1，输入b。根据规则 5。将B弹出栈，状态仍然为1.

（七）、状态为1，输入b。根据规则 4。将A弹出栈，状态仍然为1。

到此为止，所有的字符读取完毕，此时检查到栈里面也只有开始字符，状态为1（中止状态）。因此abbcbba被此下推自动机所接受。

4.2 自顶向下分析

4.2.1 一般过程

给定符号串S，若预测它是某一语法成分，那么可根据该语法成分的文法，设法为S构造一棵语法树。
若成功，则S最终被识别为某一语法成分。即S∈L(G[Z]) 其中G[Z]为某语言成分的文法。
若不成功，则 S 不属于 L(G[Z]) 。

4.2.2 特点

1. 分析过程是带有 预测性 的。即要根据输入符号串中下一个单词，来预测之后的内容属于什么语法成分，然后用相应语法成分的文法建立语法树。
2. 分析过程是一种 试探 过程，是尽一切办法（选用不同规则）设法建立语法树的过程。由于是试探过程，故难免有失败，所以分析过程需进行回溯，因此我们也称这种方法是带回溯的自顶向下分析方法。
3. 最左推导可以编出程序来实现，但在实际上价值不大，效率低，代价高。

4.2.3 解决问题

1) 消除左递归⭐️

使用扩充的BNF表示来改写文法

消除直接左递归

通过以下两条规则，就能消除文法的直接左递归，并且保证文法的等价性：

改写规则：
（1）提因子
每当出现形如 U∷= x y | x w |….| x z的规则，则将其改写为：U∷= x ( y | w |….| z )
其中若还有形如y = y1 y2, w = y1 w2的情况，则继续改写为 U∷= x ( y1 ( y2 | w2 ) |….| z )

注：
①若情况是 y x | w x |….| z x，则x 不是公因子，不进行提取。
②若有规则：U∷= x | x y，则应改写为：U∷= x ( y |ε)，而不是U∷= x (ε| y)。要尽量 将ε安排为最后的选项。
（2）改写直接左递归
若有文法规则：U∷= x | y |…| z | U v，就改写为U∷= ( x | y |…| z ) { v }

消除一般左递归

方法：
1.把G的非终结符整理成某种顺序A1，A2，……An ，使得
A1::= δ1|δ2|……|δk
A2::= A1r……
A3::= A2u |A1 v……
…….
注：即在后面（按序号排）规则的右部中包含前面规则左部的非终结符。

2.根据算法：

3.化简步骤2得到的文法。

2) 将左递归规则改为右递归规则

若有规则：P∷= P α | β
则可改写为：P ∷= β P’ ，P’ ∷= β P’ | ε

3) 消除回溯⭐️

回溯：分析工作要部分地或全部地退回去重做叫回溯。
回溯的条件：文法中，对于某个非终结符号的规则其 右部有多个选择，并根据所面临的输入符号不能准确地确定所要的产生式，就可能出现回溯。
例如：
U::= α1 | α2 | α3
回溯的坏处：效率严重低下，只有在理论上的意义而无实际意义。
避免回溯的方法
定义：设文法G（不具左递归性），U∈Vn
U::= α1 | α2 | α3
FIRST(αi) = {a | αi => a…, a ∈Vt }
方法：
要求文法满足：FIRST(αi ) ∩ FIRST(αj ) =φ (i ≠ j)
即：对文法中的任意一个Vn，其规则右部有多个选择时，由各选择推出的终结符号串的 头符号集合 要两两不相交。

消除回溯的方法
1.改写文法
做法：对具有多个右部的规则 反复 提取左因子
2.超前扫描
做法：当文法不满足避免回溯的条件时，即各选择的首符号相交时，可以采用超前扫描的方法，即 向前侦察 各输入符号串的第二个、第三个符号来确定要选择的目标。

4) 小结

为了实现不带回溯的自顶向下分析，对文法需要满足两个条件：
1、文法是非左递归的；
2、对文法的任一非终结符，若其规则右部有多个选择时，各选择所推出的终结符号串的首符号集合要两两不相交。

解决问题的方法：

消除左递归方法总结

• 对非终结符排序

• 处理第一个非终结符

  如果不存在直接左递归，照搬

• 若第二个非终结符，有中间某个候选式存在直接左递归，就把候选式替换为处理后的结果，再看有没有左递归

4.3 预测分析程序与LL(1)文法

LL(1)-自左向右扫描(L)、自左向右地分析和匹配输入串(L)、每进行一步推导，只需要向前查看一个输入符号（1）。其分析过程也表现为 最左推导 的性质

4.3.1 LL分析程序构造及分析过程⭐️

此过程由三部分组成：分析表、执行程序 (总控程序）、符号栈（分析栈）

分析表示例：

执行程序分析过程：

1. 把 # 和文法识别符号 E 推进栈，并读入输入串的第
   一个符号 a，重复下述过程直到正常结束或出错。
2. 根据栈顶符号 X 和当前输入符号a，执行如下操作：
   ①若X (∈Vt ) = a = #，分析成功，停止。E匹配输入串成功。
   ②若X (∈Vt ) = a≠#，把 X 退出栈，再读入下一个符号。
   ③若X (∈Vt ) ≠ a，转出错处理。
   ④若X∈Vn，查分析表 M：
   a) M [ X , a ] = X∷= U V W
   则将 X 弹出栈，将 U V W逆序入栈
   注：U在栈顶 （最左推导）
   b) M [ X , a ] = error 转出错处理
   c) M [ X , a ] = X:: =ε
   a为X的后继符号，则将X弹出栈（不读下一符号）继续分析。

4.3.2 LL(1)分析表的构造

设有文法G [ Z ] :
定义1 FitstVt集合：

定义2 FollowVt集合：

① 构造集合FIRST的算法

设α= X1 X2 … Xn , Xi∈Vn∪Vt
(1) 若Xi∈Vt，则 FIRST( Xi ) = { Xi }
(2) 若Xi∈Vn 且 Xi ∷= a…|ε， a∈Vt 则 FIRST( Xi ) = { a , ε}
(3) 若Xi∈Vn且Xi∷= y1 y2 …yk，则按如下顺序计算FIRST(Xi)
●若ε∈ FIRST(y1) 则将FIRST(y1) 加入 FIRST(Xi) ；
●若ε∈ FIRST(y1) 则将FIRST(y2) – {ε}加入FIRST(Xi)且若ε∈ FIRST(y2) 则将FIRST(y3) – {ε}加入FIRST(Xi)
…
ε∈ FIRST(yk-1) 则将FIRST(yk) – {ε}加入FIRST(Xi)
最后，若ε ∈FIRST(y1) ～ FIRST(yk) 则将ε加入FIRST(Xi)
这样，得到FIRST(Xi)，即可求出FIRST(α)。

② 构造集合FOLLOW的算法

设S, A, B∈Vn,
算法：连续使用以下规则，直至FOLLOW集合不再扩大：
(1) 若S为识别符号，则把“ # ”加入FOLLOW(S)中；
(2) 若A∷=αBβ(β≠ε)，则把FIRST(β)-{ε}加入FOLLOW(B)；
(3) 若A∷=αB 或A∷=αBβ， 且β =*> ε则把FOLLOW(A)加入FOLLOW(B) 中去。
注意：FOLLOW集合中不能有ε!!!

③构造分析表

基本思想:
当文法中某一非终结符呈现在栈顶时，根据当前的输入符号，分析表应指示要用该非终结符里的哪一条规则去匹配输入串（即进行下一步最左推导）。
算法：

LL(1)文法：对于能用上述算法构造分析表的文法我们称为LL(1)文法，即M [ A , a ] 只对应一条规则或Error。
定义：一个文法G，其分析表M不含多重定义入口（即分析表中无两条以上规则），则称它是一个LL(1)

对于某些文法（非LL(1)文法），有些M[A,a]中可能有若干条规则，这称为分析表的多重定义或者多重入口。
也就是说：如果G是左递归或二义的，那么M至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表M。
反之，一个文法G的预测分析表M不含多重定义入口，当且仅当该文法为LL(1)的。
改写：
只有部分文法可以从非LL(1)文法改写为LL(1)文法。
LL分析的错误恢复：
当符号栈顶的终结符和下一个输入符号不匹配，或栈顶是非终结符A，输入符号a，而M [ A , a ]为空白（即error）时，则分析发现错误。
错误恢复的基本思想：跳过一些输入符号，直
到期望的同步符号之一出现为止。同步符号是指可重新开始继续分析的输入符号。
非终结符A的同步符号集：FOLLOW(A)∪FIRST(A)∪语句开头的关键字集合
终结符在栈顶而不能匹配：弹出该终结符并发出错误信息信息后继续分析。（把所有其他符号均作为该符号的同步集合元素）

包含左递归和公共左因子的文法肯定不是LL(1)文法

4.3.3 首符号集和后继符号集的求法

1) First集(首符号集)

注：（1）ay是由x经过0到多步推出来的 且a是终结符号，若x是终结符号，First( x ) = { x };
举例：

2) Follow集(后继符号集,跟随符集)

（1）定义

1.例如：再求FOLLOW( T )的时候，在产生式右边寻找含有T的产生式，并且把它的右边的终结符号写入集合中。

例题：

注解：对于文法开始符号，#都要加进去。

3) 构造首符号集

构造符号的FIRST集步骤：
构造文法符号穿的FIRST的步骤

注：步骤2的j， 1<=j<i.
例题：

四、构造非终结符号的FOLLOW集

说明：比如求FOLLOW(E) ,

1. 从产生式右侧找E，在第5个产生式。
2. 注意形式F -> ( E ) | i,满足形式2，）加入集合中。

求FOLLOW( F ) :
1.找到3式：根据步骤2，FIRST( T ， )加入结合 ，（*）
2.找到4式：因为空串在FIRST( T ， )，所以FOLLOW（T , ）加入集合中，（*，），#，+）；
1
2
3

4.4 递归下降分析法⭐️

4.4.1 思想

为文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，按LL(1)形式唯一确定选择哪个候选式进行推导，若遇到某候选式为ε，认为其自动匹配。把这些递归过程组合起来就构成了文法的递归下降分析程序。

注：绝大多数程序设计语言可用CFG来描述，CFG的特点在于其递归性，因此适合使用递归下降程序来分析

4.4.2 实现

• 使用LL(1)文法

  先将文法消除左递归、提取公共左因子，使之成为LL(1)文法，后将每个非终结符对应一个递归过程，过程体是按照相应产生式的右部符号串顺序编写。每匹配一个终结符，则再读入下一个符号，对产生式右部的每个非终结符，则调用相应的过程。注：使用递归实际上与下推栈的原理相同。

• 使用BNF范式

  先将文法改写为BNF形式，后再书写递归子程序。

4.4.3 缺点

1）对文法的要求高，必须满足LL(1)文法。

2）高深度的递归调用会影响语法分析的效率，速度慢，占空间多

4.5 递归子程序法

对语法的每一个 非终结符 都编一个分析程序。当根据文法和当时的输入符号预测到要用某个非终结符去匹配输入串时，就调用该非终结符的分析序。
过程意义：递归子程序法对应的是 最左推导 过程
优点与缺点：
优点：
①结构、层次清晰，可读性好
②易于手工实现
③时空效率较高
主要缺点：更多的手工编写和调试工作

算法框图示例：

注：
①子程序出口前要读符号
②子程序定义时若需要调用其它子程序，调用前要先读符号。