当前位置：文档之家 › 第四章 语法分析——自上而下分析

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

  • 格式：doc
  • 大小：35.50 KB
  • 文档页数：2

下载文档原格式

  / 2

合集下载

第4章语法分析——自上而下分析

第4章语法分析——自上而下分析
<IF语句> if E then S1 else S2; <IF语句> if E then S1;
提取左因子后：
<IF语句> if E then S1 B; B else S2 |ε ;
第4章语法分析——自上而下分析
LL(1)分析条件：
是否满足：没有左递归，每个侯选式的首终结符集不相交这两个条 件，就一定能进行有效的自顶向下分析呢？
使A A。
如果是A A，则称为直接左递归，否则称为间接左递归。
例2：设有文法： (1) E->E+T|T
E E +T
(2) T->T*F|F
E +T
(3) F->(E)|i 现有输入串i*i+i, 其分析过程是：
E
+
T
…
产生的原因？
失败：由于使用最左推导，对左递归文法进 行自顶向下分析时，会导致死循环。
从推导的角度看，从开始符号出发，使用最左推导，试图 推导出与输入符号串相同的句子。
从语法树的角度看，从根节点出发，反复使用所有可能的 产生式，谋求输入串的匹配，试图向下构造一棵语法树， 其末端结点正好与输入符号串相同。
这是一个反复试探的过程。
第4章语法分析——自上而下分析
自顶向下分析面临的问题
第4章语法分析——自上而下分析
消除回溯的方法
反复使用“提取公共左因子”的方法来改造文法，使得文法 的每个非终结符号的各个候选式的首终结符两两不相交，来 避免回溯。
例：
设产生式为：
A→δα1|δα2|…|δαn 将其替换为：
AδA’
|…|α A’α1|α2
第4章语法分析——自上而下分析

语法分析-自上而下分析

语法分析-自上而下分析

经压缩后文法:
S→(abc|bc|c)S’ S’ →abc S’|ε
注意：由于对非终结符的排序不同,最后得到的文法在形 式上可能是不一样的,但是它们是等价的. 按S、Q、R排列, 代入后 S→Qc│c Q→Rb│b R→ Rbca│bca│ca│a 消除R中的直接左递归得 R→ bcaR’│caR’│aR’ R’→ bcaR’│
Z ·
c A d a Z · c A d a b
完成进一步推导Aab 检查,a-a匹配,b-d不匹配(失败) 但是还不能冒然宣布SL(G[Z]) 4. 回溯 即砍掉A的子树 改选A的第二右部 Aa 检查 a-a匹配 d-d匹配
分析工作要部 分地或全部地 退回去重做叫 回溯
建立语法树,末端结点为cad与输入cad相匹配, 建立了最左推导序列 EcAdcad ∴cadL(G(E))
2．回溯问题

什么是回溯?
分析工作要部分地或全部地退回去重做叫回溯

造成回溯的原因
公共左因子的存在 即A→1| 2 某个非终结符号的规则其右部有多个选择，形如
A → 1 | 2 | 3，根据所面临的输入符号不能 准确的确定所要选择时，就可能出现回溯。

回溯带来的问题
集合FIRST、FOLLOW： 1．FIRST集（与前同） 设α是文法G的一个符号串， α (VTVN)*,定义 FIRST（α）＝{a|α* a. . . , aVT} *ε,则εFIRST(α)。 特别若α
R→Sa|a
Q→Sab|ab|b
4.把Q代入S的右部选择 5.消除S的直接左递归
最后得到文法为:
S→Sabc|abc|bc|c S→(abc|bc|c)S’ S’ →abc S’|ε S→(abc|bc|c)S’ S’ →abc S’|ε

编译原理第4章 语法分析——自上而下分析

编译原理第4章 语法分析——自上而下分析

17
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
分析输入串x*y(记为)。
x*y
S
IP x A y **
18
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
分析输入串x*y(记为)。
x*y
S
IP x A y **
19
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
(4.3)
虽没有直接左递归，但S、Q、R都是左递归的
SQcRbcSabc
一个文法消除左递归的条件
丌含以为右部的产生式
丌含回路
PP
30
例 文法G(S): S→Qc|c Q→Rb|b R→Sa|a
(4.3)
虽没有直接左递归，但S、Q、R都是左递归的
SQcRbcSabc
Q
Q
ⅹ
S
R
S→Qc|c Q→Rb|b R→Sa|a
35
例 考虑文法G(S)
S→Qc|c Q→Rb|b R→Sa|a
消除S的直接左递归后： S→abcS | bcS | cS S→abcS | Q→Sab |ab | b R→Sa|a
关于Q和R的觃则已是多余的，化简为：
S→abcS | bcS | cS
S→abcS |
(4.4)
36
注意，由于对非终结符排序的丌同，最 后所得的文法在形式上可能丌一样。但 丌难证明，它们都是等价的。
分析输入串x*y(记为)。
x*y
S
IP
15
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
分析输入串x*y(记为)。

语法分析自上而下分析

语法分析自上而下分析
（）， ∈V*， ∈V+ } 若S u A ,且 ε ，则#∈FOLLOW(A)
2019/9/8
中南大学软件学院 陈志刚
23
第四章 语法分析-自上而下分析
计算FIRST集
1.若XV,则FIRST(X)={X}
2.若XVN,且有产生式Xa…，则把a加入到 FIRST(X)中;若X也是一条产生式,则把也 加到FIRST(X)中.
2019/9/8
中南大学软件学院 陈志刚
20
第四章 语法分析-自上而下分析
1、LL(1)分析法的工作过程
开始往栈stack中放“＃”，然后把文件开 始符号压栈。预测分析程序总是按stack栈顶符 号X和当前输入符号a行事。 ① 若X=a=”#”，则分析成功，停止分析 ② 若X=a”#”，则把X从栈顶弹出，a指向下一个
2019/9/8
中南大学软件学院 陈志刚
6
第四章 语法分析-自上而下分析
4.2 自上而下分析面临的问题
顾名思义，自上而下就是从文法的开始符号出 发，向下推导，推出句子。 • 带回溯的分析方法 • 不带回溯的递归子程序（递归下降）分析方 法
自上而下分析的主旨： 对任意输入串，试图用一切可能的办法，从文 法开始符号（根结）出发，自上而下地为输入 串建立一棵语法树。或者说，为输入串寻找一 个最左推导。
中南大学软件学院 陈志刚
10
第四章 语法分析-自上而下分析
其次，由于回溯就碰到一大堆麻烦事情。如果 我们走了一大段错路，最后必须回头，那么， 就应把已经做的一大堆语义工作推倒重来。
第三，在上述的自上而下分析过程中，当一个 非终结符用某一个候选匹配成功时，这种成功 可能仅是暂时的。
第四，当最终报告分析不成功时，我们难于知 道输入串中出错的确切位置。

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

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

FOLLOW(Y) =FOLLOE(X)=end
则有LL(1)表：
begin
d
:
end s #
P begind : X end
X
d:X
sY
Y
:sY
第四章 语法分析--自上而下分析
[例3]：给出语言L={1na0n1ma0m|n>0, m>=0} 的LL(1)文 法G[S]并说明其理由。 解：观察句子,发现可分成两部分 1na0n 和 1ma0m两部 分中符号的个数n和m没有制约关系。则可改造成下列 文法：
T FT’
T’ *FT’|
F (E)| i
我们构造每个非终结符的FIRST和FOLLOW集合
解：FIRST(E) = { (, i }
FOLLOW(E’) = {+, }
FOLLOW(E’) = { ), #}
FIRST(T) = {(, i }
FOLLOW(T) = {+, ), # }
第四章 语法分析--自上而下分析
例题与习题解答
[例1]试构造与下列文法G[S]等价的无左递归文法。
G[S]: SSa|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
5.1 自下而上分析基本问题 其基本问题包括下列问题：
5.1.1归约 5.1.2 规范归约简述
在这一部分应掌握短语和直接短语两个重要
概念
5.1.3 符号栈的使用与语法树的表示
第四章 语法分析--自上而下分析

编译原理第4章语法分析自上而下

编译原理第4章语法分析自上而下
Yn；当Y1 Y2 … Yi-1都ε时，(其中1≤i≤n)，则FIRST(Y1){ε}、FIRST(Y2) -{ε} 、…、FIRST(Yi-1)- {ε}，FIRST(Yi) 都包含在FIRST(X)中
(e) 当(d)中所有Yi * ε,(i=1,2,…n)，则 FIRST(X)=FIRST(Y1)∪FIRST(Y2)∪…∪FIRST(Yn)∪{ε}
一 . 自上而下语法分析方法
给定文法G和源程序串$。从G的开始符 号S出发，通过反复使用产生式对句型中的 非终结符进行替换(推导)，逐步推导出$ 。
是一种产生的方法，面向目标的方法。 分析的主旨是选择产生式的合适的侯选 式进行推导，逐步使推导结果与$匹配。
Ch4 语法分析 4.1 语法分析程序综述 4.1.2 语法分析的方法
计算Select集：
B ε | aD C AD | b
每个产生式的Select集合计算为:D aS | c
Select(SAB)= (first (AB) -{ε}) ∪Follow(S)={b,a,#}
Select(S bC)= first (bC)={b}
因为A B
Select(Aε)=(first (ε) -{}) ∪Follow (A)={c,a,#}
A ε | b B ε | aD C AD | b D aS | c
first(C)={first(A)-{}} ∪first(D) ∪first(b)={a,b, c}
first(D)={a} ∪{c}={a,c}
➢求出每个文法符号的FIRST集合后也就不难求出一个符号 串的FIRST集合
✓若符号串α∈V*，α=X1 X2 … Xn,当X1不能
∪{ε}
ε*,则置 ∈

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

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

解二： 规定顺序：S、Q、R
则等价的无左递归的文法： SQc | c QRb| b RbcaR’ | caR’ | aR’ R’bcaR’ |
RSa | a RQca | ca | a
RRbca|bca | ca | a
RbcaR’|caR’ | aR’ R’ bcaR’|
（因为不需要试探某个候选式，而是准确地指派 某个候选式）
17
终结首符集FIRST
令文法G不含左递归，对它的所有非终结符的每 个候选式定义终结首符集 FIRST(): * FIRST()={a | a , a∈VT }
特别地 * 若 ，则规定 ∈ FIRST()
显然， FIRST()是从推导出的所有可能的开头终 结符a或 。
3
§4.2 自上而下分析面临的问题
一、带‚回溯‛的自上而下分析方法：
自上而下分析方法，就是对任何输入串，试 图用一切可能的方法，从文法的开始符号出发， 自上而下地为输入串建立一个语法树（或最左推 导）。 这种分析过程实质上是一种试探过程，即反 复使用不同的产生式以求能匹配输入串。
4
例4.1 设有文法： SxAy
解： S iCtSA | a
A | eS
C b
22
4.3.3 LL（1）分析条件 当一个文法不含左递归，并且满足每个非终结 符的所有候选首符集两两不相交，是不是一定能进 行有效的自上而下的语法分析呢？
若存在 ∈ FIRST() ，则问题较复杂，需要进 一步考虑。 定义：非终结符A的 FOLLOW 集：
* FOLLOW（A）= { a| S …Aa… ，a∈VT } 特别地， * 若S …A，则规定，构造FIRST（X）
a) 若X∈VT，则 FIRST(X)={X}。

自上而下语法分析方法

自上而下语法分析方法

11
根据定义计算FIRST集
1.若XV,则FIRST(X)={X}. 2.若XVN,且有产生式Xa…，aV 则
把a加入到FIRST(X)中;若X是一条产 生式,则把也加到FIRST(X)中。 3.若XY…是一个产生式且YVN,则把 FIRST(Y)中的所有非元素都加到 FIRST(X)中;
12
23
G1[S]: S →xAy A →ab | a 输入串：
xay
G2[S]: S →aAS | b A →bAS | ε 输入串：
ab
左递归
G3[S]: S →Sa | b 输入串：
baa
公因子
24
4.2.1 消除左递归
1 消除直接左递归 消除直接左递归（改写为等价的右递归）
形如：A → A α|β α非， β不以A开始 改写为： A →βB（B为新增加的非终结符）
的右部由不同的VT开始。
7
G2[S]: S →Ap S → Bq 输入串：
A → cA
A →a
W=ccap
G2文法B 特→点d：B
B→b
(1)每个产生式的右部不全由VT开始。 (2)如果两个产生式有相同的左部，那么它们
的右部由不同的VT或VN开始。 (3)文法中无空产生式
8
FIRST集定义
令G是一个上下无关文法，对G的所有非终结符 的每个候选定义它的终结首符号集FIRST() 为：
*
FIRST () = {a | a..., a VT }
特别是，若
*
，则规定FIRST()。
9
G2[S]: S →Ap S → Bq
A → cA
A →a
• 如果非终结符A的所有候B 选→首b符集两两不相交， 即A的任B何→两个dB不同候选 i和 j

my第04章-语法分析：自上而下

my第04章-语法分析：自上而下

自上而下分析法的一般问题
3.
带回溯的自上而下分析法的缺陷 1）如果文法存在左递归，语法分析会无限循环下去。 2）若产生式存在多个候选式，选择哪个进行推导完全 是盲目的。 3）回溯会引起时间和空间的打量消耗 4）如果被识别的语句是错的，算法无法指出错误的确 切位置。
第四章 语法分析--自上而下分析
直接左递归，和非直接左递归的消除方法均在必须掌握之列。这里我们 切不可被形式描述消除左递归的算法吓倒，多做几个例题后再来理解是很 有好处的： [例4.3]： 考虑文法：SQc|c Q Rb|b R Sa|a 消除左递归。 解：将终结符排序为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的规则式多余的则可化简
本节要 掌握对给定文法构造出每个非终结符的 FIRST和FOLLOW集合。
第四章 语法分析--自上而下分析
掌握LL(1)预测分析表的构造，请参看4。5。1 预测分析程序的 工作过程（P76）和 4。5。2预测分析表的构造（P78）。 现在举一些例子帮助同学们理解： [例4.7 ]对于文法 ETE’ E’ +TE’| T FT’ T’ *FT’| F (E)| i 我们构造每个非终结符的FIRST和FOLLOW集合 解：FIRST(E) = { (, i } FOLLOW(E) ={ ), # } FIRST(E’) = {+, } FOLLOW(E’) = { ), #} FIRST(T) = {(, i } FOLLOW(T) = {+, ), # } FIRST(T’) = {*, } FOLLOW(T’) ={+ , ), # } FIRST(F) = {(, i } FOLLOW(F) ={*, +, ) , # } 在这里我们要注意FOLLOW(F)的求解过程其中： FOLLOW(F)=FIRST(T’)={*}; 因为T’ ,所以将FOLLOE(T)加 到FOLLOW(F)中 （由于TFT’), 则： FOLLOW(F)=FOLLOW(T)=FIRST(E‘)={+}

编译原理LL(K)

编译原理LL(K)
S a a A b c b a A S b c
S =>aAbc =>ababc 错误回退 ，再回退S 错误回退A，再回退
重复以上匹配过程，发现此时符号串abeB与abed 前3个符号均匹配，下面指针指向第四个符号d。 而符号串abeB 的第四个符号是B，若选择 B→ d 则得到下面语法树： S =>aB =>abeB =>abed
圆括号（ ③ 圆括号（ ） 利用圆括号可提出一个非终结符的多个产生式右部 的公共因子。例如， A→xy|xw|…|xz 可写成 A→x(y|w|…|z)
利用下面的两条规则，可把包含直接左递归 的产生式转换成用扩展BNF表示法表示的产生 式。
① 提公因子 每当一条产生式中有公因子可提的时候，就把它 提出来，若原产生式是 A→x|xy 则可写成 A→x(y|ε) A→x(y|ε)，这里把ε当作最后一个 候选式。 这样，把本来具有相同开始符号的候选式 变成了开始符号不同的候选式，从而避免了实现 分析过程中的逐个试探，并且有助于消除文法的 直接左递归，同时也压缩了文法的长度。
end; 消除Ui Ui产生式中的直接左递归 消除Ui产生式中的直接左递归 end; 化简改写之后的文法，删除多余产生式。 ③ 化简改写之后的文法，删除多余产生式。
确定的自顶向下语法分析
４．４
LL(k)文法 LL(k)文法
LL(k)文法是上下文无关文法的一个真子集。同时， LL(k)文法也是允许采用确定的从左至右扫描(输入 串)和自上而下分析技术的最大一类文法。 LL系指：自左至右扫描(输入串)，自上而下进行最 左推导。 分析过程中，如果每步仅利用当前的非终结符（事 实上已经位于栈顶）和至多向前查看k个输入符号 就能唯一确定采取什么动作 唯一确定采取什么动作，则这个文法称为LL(k) 唯一确定采取什么动作 文法。 下面主要讨论k=0,1时的情形。

第4章 自上而下语法分析方法

第4章 自上而下语法分析方法

教学内容
4.1 语法分析的任务和分析方法
4.2 自上而下分析的基本思想和面临的问题 4.3 左递归和回溯的消除 4.4 LL(1)分析法 4.5 不带回溯的自上而下分析方法 4.6 LL(1)分析中的错误处理 4.7 本章小结
4.1 语法分析的任务和分析方法
（1）语法分析器的任务
语法分析是编译过程的核心部分，其主要任务是：在词法分析的基
*
FIRST(ɑ)的直观意义
ɑ所有可能推导的开头终结符或可能的 ɛ 。
1、FIRST集及其计算方法
（2）FIRST集的计算方法
对G中的文法符号X，X∈VT∪VN，则FIRST(X)的计算方法为： ①若X∈VT，则 FIRST(X) ={ X };
构造文法G的等价文法G′，要求G′不含左递归。 解：根据直接左递归的一般消除方法，可得不含左递归的文法：
E (E)E | iE E EE | EE | *EE | /EE |
2、消除间接左递归
（1）引例
有文法G[S]:
S Qc | c Q Rb | b R Sa | a
*
A 1 | 2 | ...| m P
，对于输入
w a1a2 ...ai 1ai ...an VT* , 若有：
S a 1a 2 ...a i 1Aβ
则根据最左推导规则，当前应由非终结符A进行推导，为了不产生回溯，
此时A应能够明确地选择用哪个候选，如 γ j ，则
γ j ai
4.4 LL(1)分析法
从例4.6中可以看出，当非终结符A面临输入符号为a时，如果a不属 于A的任意候选的终结首符集，但是，若A的终结首符集中包含ε的话，我 们可以暂时让A自动获得匹配，即忽略掉当前的非终结符A，而让输入符

编译原理第四章语法分析-自上而下分析

编译原理第四章语法分析-自上而下分析

• 例 4.4
4.4 递归下降分析程序构造
• 递归下降分析器：
这个分析程序由一组递归过程组成的，每个过程对应 文法的一个非终结符。 E→TE’ E’→+TE’| T→FT’ T’→*FT’| F→(E)|i
PROCEDURE E BEGIN T ; E’ END PROCEDURE E’ IF SYM=‘＋’THEN BEGIN ADVANCE ; T ; E’ END
4.2 自上而下分析面临的问题
• 例4.1 假定有文法
(1) SxAy (2)A**|*
对输入串x*y，构造语法树。 • 构造过程：
(1)把S作为根 (2)用S的产生式构造子树 (3)让输入串指示器IP指向输入串的第一个符号。
S x A y x
S
A y x
S
A y
*
*
*
(4)调整输入串指示器IP与叶结点进行匹配。 (5)如果为非终结符，用A的下一个产生式构建子树。 (6)如果匹配成功则结束；否则，回溯到步骤(4)。
• 一个反例：
– 文法：SQc|c；QRb|b；RSa|a虽然不是直接 左递归，但S、Q、R都是左递归。
• 消除左递归算法：
– 算法的思想是：
• • • • 首先构造直接左递归； 再利用一般转换规则，消除直接左递归 化简文法。 下面算法在不含PP，也不含在右部产生式时可以消除 左递归。
• 消除一个文法的左递归算法：
(1) 把文法 G 的所有非终结符按任一种顺利排列成 P1…Pn；按此顺序执行； (2) FOR i:=1 TO n DO
BEGIN FOR j:=1 TO i-1 DO 把形如Pj+1→Pj 的规则改写成 Pj+11|1|…k| 。其中 Pj1|1|…k 是关于 Pj 的 所有规则； 消除关于Pi规则的直接左递归性。 END 化简由（２）所得的文法。即去除那些从开始符号出发永 远无法到达的非终结符的产生规则。

第四章 语法分析--自上而下分析

第四章 语法分析--自上而下分析
由于i First（FT’），所以用T FT’ 进行推导 由于i First（i），所以用F i推导
F
i+ i i
T’

+
F i
T
从T ’出发继续匹配，而输入字符 + 不 输入First（T’），但有T ’ ，所以 T’ 自动匹配
E’
i+ i

自动匹配的条件：当a是允许在文法的某个句 型中跟在A后的终结符时，A才能自动匹配。
P P A 1|2|…|n |1|2| … |m（每个不以开头） A|1|2| … |m 1|2|…|n
自动匹配——文法不含左递归，也满足任何非 终结符的所有首符集两两不相交的要求，要进 行有效的自上而下的语法分析，还要考虑空字 的自动匹配问题。
例子：对文法4.2 输入串i+i自上而下的分析： 由于E只有一个后选式TE’，i First E = i +i （TE’），所以用E TE’进行推导 T E’
= First（（）并First（i）={（， i}
T ::=FT’
FIRST（E’）= First（ + TE’ ）并 First（ ）
= {+， }
FIRST（T’）= First（ *FT’ ）并 First（ ）
= {*， }
提取公因子——将文法改造成任何非终结符的 所有首符集两两不相交的方法
4.2 自上而下分析面临的问题
• 自上而下分析的实质：从推导的角度看，
从文法的开始符号出发，自上而下，推出句子。 （一般是最左推导）
• 自上而下分析的主旨：对任何输入串，试
图尝试一切可能的办法，文法的开始符号（根 节点）出发，试图自上而下建立一个语法树， 其末端节点正好与输入符号串相同。

第四章语法分析-自上而下分析

第四章语法分析-自上而下分析

第四章语法分析—自上而下分析知识结构：带回溯分析法回溯自上而下分析面临的问题左递归问题的解决语法分析－求FIRST、FOLLOW集合的算法自上而下分析 LL(1)分析法证明LL(1)文法构造LL(1)分析表递归子程序的构造思想递归子程序法递归子程序的特点递归子程序的设计第一节语法分析综述一、语法分析的任务按照语言即定的语法规则，对字符串形式的源程序进行语法检查，并识别出相应的语法成分。

即语法结构是否符合语法规则。

二、语法分析器在编译程序中的地位（一遍扫描）三、语法分析方法通常把语法分析方法分为两大类，既自上而下分析与自下而上分析。

1、自上而下分析方法实际上是一种产生的方法，分析过程是一个推导过程。

⑴自上而下分析过程从文法G的开始符号S出发，通过反复使用产生式，逐步推导出与输入的符号串完全相匹配的句子。

采用最左推导，以文法开始符号为根结点，逐步为输入串自上而下地构造一棵语法树。

面临的输入符号为a，A所有的产生式：A→α1|α2|⋯|αn①若a∈FISRT(αi)，则指派去执行匹配任务。

②若a不属于任何一个候选首字符集，则：a、若ε属于某个FISRT(αi)且a∈FOLLOW(A)，则让A与ε自动匹配；b、否则，a的出现是一种错误。

例：设有文法G和输入符号串W：a*a+aG：S → aA∣aA → BaA∣εB → +∣ -∣*∣/推导过程：S⇒aA⇒aBaA⇒a*aA⇒a*aBaA⇒a*a+aA⇒a*a+a=W构造语法树：Sa AB a A* B a A⑵自上而下分析法自上而下分析法又可分为确定和不确定的两种。

①不确定的分析法（带回溯）是一种穷举的试探方法，效率低、代价高，极少使用。

②确定的分析法（不带回溯）实现方法简单、直观，便于手工构造或自动生成语法分析器，是目前常用的方法之一。

但是对文法有一定的限制。

2、自下而上分析法⑴自下而上分析过程分析过程是归约过程。

从给定的输入串W开始，不断寻找与文法G中某个产生式P的侯选式（右部）进行匹配，并用P代替也称为归约。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第四章语法分析——自上而下分析
【关键问题】
◇什么叫确定的自上而下语法分析？
◇自上而下语法分析是从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。

◇在确定的自上而下语法分析过程中，当以同一个非终结符为左部的产生式有多个不同右部时，如何选择用哪个产生式的右部替换当前的非终结符？
◇确定的自上而下语法分析对文法有何限制？
【学习目标】
确定的自上而下分析方法虽对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。

◇能够对一个给定的文法判断是否是LL(1)文法；
◇能构造预测分析表；
◇能用预测分析方法判断给定的输入符号串是否是该文法的句子；
◇能对某些非LL(1)文法做等价变换：
①消除左递归；
②提取左公共因子
【学习指南】
确定的自上而下分析由于实现方法简单、直观、便于手工构造，因此，仍是目前常用的语法分析方法之一，尤其对小型编译器的实现较为适合。

确定的自上而下分析要求文法是LL(1)的，所以，能否用确定的自上而下分析方法构造语法分析器，首先必须对所给文法进行判断。

由此构造LL(1) 分析器的关键问题是对文法的LL(1)判别。

判断LL(1)文法时用到文法符号串的开始符号集合（FIRST集）和非终结符的后跟符号集合（FOLLOW集）的计算。

本章的学习要求大家对给定的文法能熟练、准确地计算出产生式右部符号串的开始符号集合和每个非终结符的后跟符号集合，只有这两个集合的元素计算准确无误，才能对LL(1)文法的判断得出正确结论，从而正确构造LL(1)分析表。

对非LL(1)文法的等价变换特别要注意的是：消除了左递归、提取了左公共因子后不一定就能满足LL(1)文法的条件。

【难重点】
语法分析是编译程序的核心部分。

语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)，目前语法分析常用的方法有自上而下分析和自下而上分析两大类。

本章将主要介绍确定的自上而下分析思想和对文法的要求。

确定的自上而下分析要求文法满足LL(1)文法。

本章主要介绍内容为：
◇LL(1) 文法的定义和判别
◇非LL(1)文法的等价变换
◇确定的自上而下分析方法
◇预测分析方法
重点:
①LL(1)文法的定义和判别
②非LL(1)文法的等价变换
③预测分析方法
难点:
对一个文法如何判断是否是LL(1)文法。

在判断LL(1)文法时用到文法符号串的开始符号集合（FIRST 集）和非终结符后跟符号集合（FOLLOW集）的计算，由于概念不清或不够细心常常导致对这两个集合的计算出错。

【知识结构】
4.1语法分析器的功能
语法分析是编译过程的核心部分。

它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。

语言的语法结构用上下文无关文法描述。

语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子，或者从概念上讲就是要建立一棵与输入串相匹配的语法分析树。

4.2自上而下分析的问题
自上而下就是从文法的开始符号出发，向下推导，推出句子。

自上而下的主旨是对任何输入串试图用一切可能的办法，从文法开始符号出发，自上而下地为输入串建立一棵语法树。

或者说，为输入串寻找一个最左推导。

这种分析过程是一种试探过程，是带“回溯”的。

实现这种自上而下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。

每个子程序作为一个布尔过程。

这种分析法存在的困难和缺点是：
1．文法的左递归
使用自上而下分析法必须消除文法的左递归。

2．回溯
回溯会使整个过程既麻烦又费时间，应设法消除回溯。

3．虚假匹配
4.3LL(1)分析法
为构造不带回溯的自上而下分析算法，首先要消除文法的左递归，并找出克服回溯的充要条件。

4.3.1左递归的消除
假定关于非终结符P的规则为：
P→Pα|β
其中β不以P开头。

则可以改写为如下的非直接左递归形式：
P→βP′
P′→αP′|ε。