This PPT is about Chapter 4 of Compiler Principles, Syntax Analysis - Top-Down Analysis.

This PPT is about Chapter 4 of Compiler Principles, Syntax Analysis - Top-Down Analysis.

1. 第四章 语法分析——
自上而下分析

2. 4.1语法分析器的功能
语法分析是编译过程的核心部分。它的任务是在词法分
析识别出单词符号串的基础上，分析并判定程序的语法
结构是否符合语法规则。

3. 语法分析器的工作本质上就是按文法的产生式，识
别输入符号串是否为一个句子。并建立一棵与输入
串相匹配的语法分析树。
按照语法分析树的建立方法，可以把语法分析办法
分成两类：一类是自上而下分析法，另一类是自下
而上分析法

4. 4.2自上而下分析面临的问题
自上而下就是从文法的开始符号出发，向下推导，
推出句子。
自上而下分析的主旨是，对任何输入串，试图用一
切可能的办法，从文法开始符号（根结）出发，自
上而下地为输入串建立一棵语法树。或者说，为输
入串寻找一个最左推导。
这种分析过程本质上是一种试探过程，是反复使用
不同产生式谋求匹配输入串的过程。

5. 例4.1假定有文法
（1）S→xAy
(2）A→**|* （4 ．1）
以及输入串 x*y(记为α）。
为了自上而下构造 α的语法树，我们首先按文法的开始符号产生根结
s，并让指示器 IP指向输入串的第一个符号 x。然后，用 S的规则
（此处关于 S的规则仅有一条）把这棵树发展为
S
X A Y

6. 非终结符 A有两个候选，试着用它的第一个候选去匹配
输入串，于是把语法树发展为
子树A的最左子结和 IP所指的符号 *相符，然后我
们再把IP调为指向下一符号并让 A的第二个子结进入
工作。但 A的第二子结 *和当前所指的符号 y不一致。
因此，A告失败。这意味着 A的第一个候选此刻不适
用于构造 α的语法树。这时应该回头（回溯），看 A
是否还有别的候选。
S
X A Y
* *

7. 为了这种回溯，我们一方面应把 A的第一候选所
发展的子树注销掉，另一方面应把 IP恢复为进入
A时的原值，也就是让它重新指向第二个输入符
号，。现在我们试探 A的第二个候选，即考虑如下
的语法树：
X A Y
S
*

8. 由于子树 A只有一个子结，而且它和 IP所指的符
号相一致，于是， A完成了匹配任务。在 A获得
匹配后，指示器 IP应指向下一个未被触及符号 y。
在s的第二子结 A完成匹配后，接着就轮到第三
个子结y进行工作。
由于这个子结和最后一个输入符号相符，于是，我
们完成了为 α构造语法树的任务，证明了 α是一个
句子。

9. 自上而下分析法存在的困难
文法的左递归性问题
回溯
虚假匹配
难于知道输入串中出错的确切位置
效率很低，代价极高

10. 4.3 LL（1）分析法
LL(1)分析法又称预测分析法 , 是一种不带回
溯的非递归自上而下分析法。
LL(1)的含义: 第一个L表明自左至右扫描输
入串; 第二个L表明最左推导 ; 1表明向右查看一
个符号。

自上而下分析方法不允许文法含有任何左递归。
为构造不带回溯的自上而下分析算法，首先要
消除
文法的左递归性，并找出
克服回溯的充分必要条件。
消除
左递归和克服回溯

11. 左递归的
消除
直
接消除见诸于产生式中的左递归是 比较容易的。
假定关于非终结符 P的规则为： P→
P
α|β
其
中，
β不以P开头。
那么，我们可以把
P的规则
改写
为如下的非 直接左递归形式：
P→βP′
P'→αP'|ε

12. 例文法
E→E+T|T
T→T*F|F
F→(E)|i
消除
左递归
E→TE'
E'→+TE'|ε
T→FT'
T'→*FT'| ε
F→(E)|i

13. 一
般情况
P→Pα
1|Pα
2|...|Pα
m|β
1| β
2|...| β
n
消除P的左递归
P→ β
1P'| β
2P'|...| β
nP'
P'→ α
1 P'| α
2 P'|...|α
m P'| ε

14. 间
接左递归
例如文法 ：
S →Qc|c
Q →Rb|b
R →Sa|a
虽
不具有直接左递归，但
S,Q,R都
是左递归的，
例如有S=>Qc=>Rbc=>Sabc

15. 解
：将终结符排序为
R、Q、S。对于R不存在
直接左递归。
把R带入到Q中有关的候选式： Q  Sab|ab|b
现在Q同
样不含直接左递归，把它带入
S的有关候选式：
S Sabc|abc|bc|c
经消除S的
直接左递归后我们们得到 整个文法
S abcS’|bcS’|cS’
S’ abcS’|
Q  Sab|ab|b
R Sa|a
由于关于 Q,R的规则式
多余的则可化简
得到：S abcS’|bcS’|cS’
S’ abcS’|

16. 消除
左递归算法：
(1)把文法G的所有非终结符按任一
顺序排列成
P
1,P
2,...P
n；
按此
顺序执行
(2)FOR i:=1 TO n DO
BEGIN
FOR j:=1 TO i-1 DO
把
形如
P
i
→P
jγ的规则
改写成
Pi →δ
1
γ| δ
2
γ|...| δ
k
γ，
其中
P
j
→δ
1
|δ
2
|
...|
δ
k是关于Pj的所有规则
消除
关于
P
i规则的
直接左递归性
END

17. 提
左因子
A → δβ
1
|δβ
2
|...|δβ
n
|γ
1
| γ
2
|..|γ
m
改写
为
A → δ A' |γ
1| γ
2 |..|γ
m
A' →β
1|β
2|...|β
n

18. 首符
集
令G是一个不含左递归的文法，对 G的所有非终
结符的
每个候选
α定义它的终结首符
集
FIRST(α)
为：
FIRST(α)={a| α=>a...,a€V
T}
若α=>ε,则ε€ FIRST(α)
*
*

19. 如
果非终结符
A的所有候选首符
集两两不相 交，即
A的任何两个不同候选 α
i和α
j，有
FTRST(α
i） ∩ FIRST(α
j）=φ
那么
，当要求
A匹配输入串时， A就能根
据它所
面临的第一个输入符号 a，
准确地指派某一个候选
前去
执行任务。这个候选就是 那个终结首符 集含
a
的α。
[例]有产生式
B bBcA|b
由于FIRST(bBcA) FIRST(b) ={b}  
则
需要提取公共 左因子
将
产生式改写成：
B bC
C BcA|

20. LL（1）分析条
件

当一个文法不含左递归，并且
满足每个非终结的所
有候选首符
集两两不相交的条件，是不是就一定能
进行有效的自上而下分析了
呢？
如
果空字
ε属
于某个非终结符的候选首符 集，那么，
问题就
比较复杂。

21. 例4.4考虑文法（ 4 ．2）,对输入串 i＋i进行
自上而下分析
首先，从开始符号 E出发匹配输入串，面临的第一个输
入符号为 i，由于E只有一个候选 TE′，且i属
于
FIRS
T(TE′)，所以使用 E→TE'进行推导。
E→TE'
E'→+TE'|ε
T→FT'
T'→*FT'| ε
F→(E)|i

i + i
IP
E
T E'

22. 由于i ∈FIRST(FT')，所以用 F→i进行推
导，使输入串的第一个 i得到匹配。
i + i
IP
E
T E'
F T'

23. 由于i ∈FIRST(i)，所以用 Fi
→
进行推导，使输入串
的第一个 i得到匹配。
i + i
IP
E
T E'
F T'
i

24. 最后，我们可得到与 i＋i相匹配的语法分析树
E
T E'
F T'
i ε
+
T E'
F
i ε
T'
ε

25. 这是不是意味着，当非终结符 A面临输入符号 a，
且a不
属于
A的任意候选首符
集但
A的
某个候选
首符
集包含
ε时，就一定可以使 A自
动匹配？
不难发现，只有当 a是允许在文法的
某个句型中跟
在A后面的终结符时，
才可能允许
A自
动匹配，
否则，a在这
里的出现就是一种语法错 误。

26. 从T‘出发进行匹配，面临的输入符号为
＋。由于
+不
属
于T’的任一候选式的首符
集
,但有T‘→ε，所以我们不
妨
让
T’自
动得到匹配（即
T‘匹配于
空字
ε，注意这种
情况
下，输入符号并不 读进）。

i + i
IP
E
T E'
F T'
i ε

27. 当A面临输入符 a时, 若aFIRST(A)且
FIRST(A), 则考虑自
动匹配问题。 对于上 述算术
表
达式文法
,若
输入串为
i/i, 即使让T‘自
动匹配
,
“/”仍
不能与后面符号匹配
, 此时
没必要让
T’自
动匹
配。
结
论
: 只有在当前输入符能与 A后的第一个终结
符匹配成功时 ,才
让
A自
动得到匹配。这就要求分析前
先求出
紧跟在
A后的终结符 , 即FOLLOW(A)。

28. FOLLOW(A)的定义
对文法G[S]的任一非终结符 A, 定
义
FOLLOW(A)＝{a|S …Aa…,a V
∈
T
}
若S …A, 则规定
#FOLLOW(A)
即FOLLOW(A)是所有句
型
中
紧跟
在
A之
后的终结符 或
# 。0
 {因S S, 故#FOLLOW(S)}

29. 自
动匹配条件
当A面临输入符 a时,若
aFIRST(A)且FIRST(A), 则只有当
aFOLLOW(A)时,才
使
A自
动得到匹
配。
缺少任一条件
,均
不自动匹配。
若
输入符
aFIRST(A)且
aFOLLOW(A), 则当FIRST(A)时
仍需
进行试探 (回溯)。因此,对于存在-生
成式的非终结符 A,若
要进行不带回溯的
自 上 而 下 分 析 ,则FIRST(A)与
FOLLOW(A)应
互不相交
。

30. LL(1)文法
(1)文法不含左递归
(2)对于文法中
每一个非终结符
A的
各个产生式的候
选首符
集两两不相交，即，若
A →α
1|α
2|...|α
m，则
FIRST(α
i
)∩FIRST(α
j
)=Φ(i≠j)
(3)对文法中的
每个非终结符
A，
若它存在某个候选
首符
集包含
ε，则FIRST(A) ∩FOLLOW(A) =Φ

31. 4.4递归下
降分析程序的构造
是进行语法分析的一种方法，要求文法是 LL(1)文
法
实
现思想：
识别程序由一
组过程组成。每个过程对应于文法
的一个非终结符号。
每
一个过程的功能是：选 择正确的右部，扫描完
相应的
字。在右部中有非终结符号时，调用该终
结符号对应的过程
来完成。

34. 基本
架构
(1)
对于
每个非终结符号的产生式
U→u
1
|u
2
|…|u
n
处
理的方法如
下：
U( ){
ch=当前符号 ;
if(ch是u1符号串的第一个符号 ) 处
理
u1
else if(ch是u2符号串的第一个符号 ) 处
理
u2
……
elseerror() }

35. 由于
无回溯的文法 保证选择是唯一的。
当存在ε时，可以用 error()替
代为
{return;}这
样可
以
较晚发现错误。
约
定：进入这个过程时， 已读入
U的第一个符号到当
前符号。
离开这个过程时，下一个符号 已经被读到
当前符号。

36. 基本
架构
(2)
对于U的
每个右部
ui=x
1
x
2
…x
n
的处
理架构如下：
处
理
x
1
的程序
；
处
理
x
2的程序
；
… … …
处
理
x
n
的程序
；
如
果右部为空
ε，则不处
理。

37. 基本
架构
(3)
对于右部中的
每个符号
x
i
如
果
xi为终结符号：
if(x== 当前输入符号串中的符号 )
{NextCh()；return;}
else
出错处
理
如
果
x
i
为非终结符号，
直接调用相应的过程：
x
i
()

38. P74 过程对应于前
述的文法
E ->TE'
E'->+TE' |ε
T ->FT'
T'->*FT' |ε
F->(E) |i

39. 4.5预测分析程序
递归下
降分析法：采用递归过程。因此 实现分析程
序所使用的高
级语言必须支持 递归过程才行。
预测分析法是自
顶向下分析的另一种方法。
使用下推自
动机的方式实现。
使用一个二
维分析表和栈联合进行控制来实现分析。

40.  
i + * ( ) #
E E→TE'  
E→TE' 
E'
  E'→+TE'  
E'→ε E'→ε
T T→FT' 
T→FT'  
T'
 
T'→ε T'→*FT' 
T'→ε T'→ε
FF→i
   F→(E)  

41. a1a
2
…ai…an#
分析表M
控制
程序
输入串：
栈顶
#
x
1
…
x
j
输出
分析
栈
图4–4 LL(1)分析器

42. LL(1)分析器说明如下：
(1)输入串是
待分析的符号串
,它以
“#”作为结
束标志。
(注: # V
∈
T
但不是
文法符号 , 是由分析程序自
动添加的
)
(2)分析
栈
存
放分析过程中的文法符
号。分析开始时
栈底先放一个“
#”,再
压
入文法开始符 ; 当分析
栈中仅剩“
#”且
输入串指
针指向串尾的“
#”时, 分析成
功。

43. (3)分析表用一个
矩阵
M(二
维数
组) 表示,它
概括了文法的 全部信息。
矩阵
的每一行与文法的一个非终结符相
关
联
,而
每一列与文法的一个终结符或
“#”关
联。分析表 元素
M[A,a]中的
内
容
为一条
A的产生式 ,表明当A面临输
入符a时应
采用的候选式
;当
元素内容
为
空时
,表明A不应面临输入符 a,即输
入串含语法错
误。

44. (4) 控制
程序
根
据分析栈栈顶符号
x和当
前输入符 a决
定分析器的 动作
:

①
若x＝a＝“#”,则分析成功。

②
若x＝a≠“#”,即
栈顶符号
x与当前
输入符a匹配,则
将
x从
栈顶弹出
,输入
串指
针后移
, 继续
对下一个 字符进行分
析。

③
若x为非终结符 A,则查分析表
M[A,a]:
i.若M[A,a]为一产生式 ,则A自
栈
顶弹
出
,M[A,a]中产生式的右部符号 逆
序
压栈;若M[A,a]为A→ε,则只
将
A自
栈
顶弹
出。
ii.若M[A,a]为
空
,则发现语法错
误
,
调用出错处
理程序进行处 理。

46. 预测分析过程
下面用预测分析方法对输入串 i1 * i2+ i3 # 进行分析，
给
出栈的变化过程如下：

47. 构造预测分析表
从前面的
论述我们看到，预测分析过程的 总控程序
是
固定的。对于 某个文法，分析表是分析过程的核
心。
表中M[A,a]=‘A→X
1X
2…X
n’表示对应于 X
1X
2…X
n
字
的首终结符可以是
a。就是说 X
1X
2…X
n=>aw。
可以
通过这个方式 来确定分析表中的值。
(即：求
首终结符 )

48. 预测分析表的构造算法
对文法的
每个文法符号
X构造First(X)
对文法的
每个非终结符
A构造Follow(A)
对于
每一产生式
A
→α,
对于
每个终结符
a∈FIRST(α),将A
→α
填
入
M[A,
a]；
如
果
ε∈FIRST(α)，则对任何
元素
b∈FOLLOW
(A)

，
将
A
→α
填
入
M[A,b]；
将
所有无定义的
M[A,a]

标
上错误标志。

49. (1)FIRST集
的构造方法
对任一终结符 a, FIRST(a)={a}。
对每
个非终结符
X连续
使用下述规则
直
到
FIRST集
不再增大为止。

①
若
有
X→a…,把a加
入
FIRST(X);
若
有
X→ε,把ε加
入
FIRST(X);

②
若
有
X→Y…,Y V
∈
N
,把FIRST(Y)的
所有非ε元素都加
入
FIRST(X);
若
有
X→Y
1
Y
2
…Y
k
,而Y
1
~Y
i−1
都
有
ε,
则把FIRST(Y
j
) (j=1,2,…,i)的所有非
ε元素都加
入
FIRST(X);
特
别地
,若Y
1
～Y
k
均
有
ε产生式,
则把ε也
加入到
FIRST(X)。

51. 例1 试构造文法 G[E]的FIRST集。
G[E]: E→TE'
E'→+TE' |ε
T→FT'
T'→*FT' |ε
F→(E) i
∣
解: FIRST(E')={+,ε};
FIRST(T')={*,ε};
FIRST(F)＝{(, i };
由T→F…知,把FIRST(F)的所有
非ε
元 素 加
入
FIRST(T),故
FIRST(T)={(,i};
由E→T…知,把FIRST(T)的所有
非ε
元 素 加
入
FIRST(E),故
FIRST(E)={(,i}

52. 对文法G[S]的任何非终结符 A, 定义
FOLLOW(A)＝{a | S …Aa…, a V
∈
T
}
若S A, 则规定# FOLLOW(A)
∈
FOLLOW(A)是所有句
型中出现在 紧随
A
之
后的终结符 或
# 。

53. (2) FOLLOW集
构造方法
对文法每
个非终结符
A构造
FOLLOW(A)。
方法是
连续使用下述规则
,直
到
FOLLOW
集
不再增大为止。
①对文法开始符 S,把#加
入
FOLLOW(S)。
(由语句
括号“
#S#”中的S#得到)

②
若
有
A→B (可为
空
),
则
将
FIRST()\{ε}加
入
FOLLOW(B)。
③若 有A→B或A→B且 ε,
则把
FOLLOW(A)加
入到
FOLLOW(B)。

54. 例2 试构造文法 G[E]的FOLLOW集
。
G[E]: E→TE' E'→+TE' |ε
T→FT' T'→*FT' |ε
F→(E) | i
解:1)FOLLOW(E)={#};
2)由E→TE'知, FIRST(E')\{ε}属
于
FOLLOW(T), 即FOLLOW(T)＝
{+};
{由E'→+TE' |ε, FIRST(E')\{ε}属
于…
}
由T→FT'知, FIRST(T')\{ε}属
于
FOLLOW(F), 即FOLLOW(F)＝
{*};
{由T' →*FT'|ε知,FIRST(T')\{ε}属
于
…}
由F→(E) | i知, FIRST(')')属 于
FOLLOW(E), 即FOLLOW(E)＝
{),#};

55. 3)由E→TE'知,
FOLLOW(E)属
于
FOLLOW(E'),
即FOLLOW(E')＝{ ), # };
由E→TE'且E'→ε知,
FOLLOW(E)属
于
FOLLOW(T),
即FOLLOW(T)＝{+, ), #};
{由E'→+TE'知,
FOLLOW(E')属
于
FOLLOW(E')}
{由E'→+TE'且E'→ε知,
FOLLOW(E')属
于
FOLLOW(T) }

56. 由T→FT'知,
FOLLOW(T)属
于
FOLLOW(T')，
即FOLLOW(T')＝{ +, ), # };
由T→FT'且T' →ε知,
FOLLOW(T)属
于
FOLLOW(F),
即FOLLOW(F)＝{*, +, ), #}；
{由T'→*FT' 知,
FOLLOW(T')属
于
FOLLOW(T')}
{由T'→*FT'且T'→ε知,
FOLLOW(T')属
于
FOLLOW(F)}
{考虑F→(E)|i }

58. 错
误处理

63. 例题与
习题解答
[例1]试构造与下
列文法
G[S]等
价的无左递归文法。
G[S]: SSa|Nb|c (1)
N Sd|Ne|f (2)
对于（1）我们
引入新非终结符
S’
则： S NbS’ |cS’ [1]
S’ aS’| [2]
将

S代入 （2）
N Ne |NbS’d |cS’d |f
引
入新非终结符
N’
N cS’dN’ |fN’ [3]
N’ eN’ |bS’dN’ |  [4]

64. [例2]：文法G的规则
集为
;
P begin d : X end
X d : X | sY
Y : sY | 
做
出该文法
LL(1)分析表。
解
： 非终结符只有
P , X ,Y 只有FIRST(Y)含有 则
需
要求出
FOLLOW(Y)且
FOLLOW(Y) =FOLLOE(X)=end
则有LL(1)表：
begin d : end s #
P begind : X end
X d : X sY
Y :sY 

65. [例3]：
给出语言
L={1
n
a0
n
1
m
a0
m
|n>0, m>=0} 的LL(1)
文法G[S]并说明
其理由。
解
：观察句子
,发现可分成两部分 1
n
a0
n
和 1
m
a0
m
两
部分中符号的个
数
n和m没
有制约关系。则可改造成
下
列文法：
S AB
A 1A0 |1a0
B  1B0 |a
对于产生式 A  1A0 |1a0 两个候选式
FIRST(1A0)FIRST(1a0)={1}<> 所以上
边文法
不是LL(1)文法：
需左提公因子，得到：
S AB
A 1C
C  A0 |a0
B  1B0 |a 此文法
满足
LL(1)文法的要求。

66. [例4] 设
有文法：
G[S]:
SaBc | bAB
AaAb | b
Bb |  构造
其
LL(1)分析表，并分析符号串 baabbb是否是
该文发的句子。
解
：因为只有
FIRST(B)含有 所以只考虑：
FOLLOW(B)=FIRST(c) FOLLOW(S)={c, #} 该文法的 LL(1)
表
a b c #
S aBc bAB
A aAb b
B b  
符号串baabbb是否为句子的分析过程
步骤
符号栈
S 输入串 规则
1#S baabbb# SbAB
2#BAb baabbb#

67. 3#BA aabbb# AaAb
4#BbAa aabbb#
5#BbA abbb# AaBb
6#BbbAa abbb#
7#BbbA bbb# Ab
8#Bbbb bbb#
9#Bbb bb#
10#Bb b#
11#B # A
12# # 成功， STOP
分析成功 baabbb是该文法的一个句子。