编译技术-第4章-语法分析(一)
- 格式：pptx
- 大小：1.01 MB
- 文档页数：76
下载文档原格式
合集下载
编译原理第4章习题答案
S-> S’ S’->(S)SS’| First( (S)SS’) = { （ } Follow(S)=Follow(S’)= { (, ),$ }
预测分析表
非终结符 S （ S->S’ ） S->S’ $ S->S’
S’
S’->(S)SS’
S’->
S’->
S’->
冲突
仔细分析后，发现该文法 S->S(S)S| 是二义性文法。 二义性文法不可能是LL(1)文法。 例如：( ) ( )
S->aS’ S’->aS’AS’|Ɛ A->+|*
First(S) = First(aS’)={a} First(S’)= First(aS’AS’) ∪ First(Ɛ)= {a} ∪{Ɛ}= {a, Ɛ} First(A) = { +,*}
Follow(S) ={$} 因为 S->aS’，所以把Follow(S)加入到Follow(S’)中。 因为 S’->aS’AS’的第一个S’ ，所以把First(AS’)={+,*}加入到Follow(S’)中。 因为 S’->aS’AS’的第二个S’ ，所以Follow(S)加入到Follow(S’)中。 所以，Follow(S’)= {$, +,*} 对 S’->aS’AS’的A ，当A后面的S’推导出非空时，把First(S’)-{Ɛ}={a}加入到Follow(A)中。 对 S’->aS’AS’的A ，当A后面的S’推导出空时，把Follow(S’)={$,+,*}加入到Follow(A)中。 所以，Follow(A)= {a, +,*,$} 对于S’->aS’AS’|Ɛ，因为First(aS’AS’) ∩Follow(S’)={a} ∩{$,+,*}=空集,所以没有冲突。 对于A->+|*，因为First(+) ∩First(*)={+} ∩{*}=空集,所以没有冲突。 所以该文法是LL(1)文法。
编译原理chapter4 语法分析
type array[simple] of type {注:A=type,a=array,
type→array[simple ] of type}
array[num dotdot num] of type
{注:A=simple, a=num
simple→num dotdot num }
array[num dotdot num] of simple
aSbAa (SbA) aSbbaa (ba) aabbaa (a)
S
a
A
S
S
b
A
a
aபைடு நூலகம்
ba
精品文档
7
4.2预测分析器 4 .2 .1 预测分析 预测分析的原理 4 .2 .2 递归预测分析器的构造 用一组递归过程实现预测分析，产生式的状 态转换图可作为编写递归过程的兰图。 4 .2 .3 非递归预测分析器的构造—LL(1) 对于每一步分析，分析表项M[A,a]=‘A ’ 表示：面对非终结符号精A品和文档向前看符号a应选 8
A 1 2 ... n
i,j(1 i,j n i<>j),从 i推导出来的第一个 终结符号集合（称为FIRST( i) ）和从 j推 导出来的第一个终结符号集合（称为FIRST( j) ）不相交，即， FIRST( i) FIRST( j)=
精品文档
12
定义4.1 令G[S]=(VT,VN,S,P),则
FIRST( )= a a*… a VT
例4.2 文法G[S]，其产生式如下:
S→aA|d A→bAS|ε （4.2)
若 w=abd，则构造最左推导的过程如下:
S aA {注：A=S，a=a，S→aA}
abAS {注：A=A，a=b，A→ bAS}
语法分析(1)
5
语言
• 语言：对字母表Σ来说，Σ*上的任意一个子集都
称为Σ上的一个语言，记为L(L Σ*)
• 句子：语言L的每一个字符串称为该语言的一个
语句或句子。 • 例：字母表{0，1}上的语言
{0，1} {00，11} {0，1，00，11} {0，1，00，11，01，10} {00，11}* {01，10}*
例：构造产生标识符的文法（续）
• 作为“标识符”的非终结符I，它或者是一 单个字母，或者为一字母后跟字母数字串， 即 I→L∣LS 因此，产生标识符的文法G[I]为： G=({a,b,…,z,0,…,9},{I,S,T,L,D},I,ξ)
ξ: I→L∣LS
S→T∣ST T→L∣D L→a∣b∣…∣z D→0∣1∣…∣9
构造产生标识符的文法标识符是以字母开头的字母数字串用l表示字母类非终结符用d表示数字类非终结符而用t表示字母或数字类非终结符则如果用s表示字母数字串类则t是一字母或数字st也是字母数字串即有stst产生式stst是一种左递归形式由它可以产生一串t
编译原理 第4讲 语法分析(1)
贾西平 Email: jiaxp@
M B DD … D A
中间位 最 高 位 最 低 位
14
例3.2
• 由于中间部分可出现任意位，所以 另引入了一个非终结符M，它包括 M 最高位和中间位部分。假定开始符 B DD … 为N，则可得到文法G[N]为： • G=({0,1,„,9},{N,A,M,B,D},N,ξ) ξ:N→A∣MA /*一位数字│多位数字*/ M→B∣MD /*仅两位数字(无中间位)│
17
推导符号
• 通常，用 1 n 表示：从1出发，经过 一步或若干步，可以推出n。 用 1 n 表示：从1出发，经过0步或 若干步，可以推出n。
编译原理第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(记为)。
编译原理张晶版 第四章 自上而下语法分析
1、消除左递归
•1) 什么是左递归 —左递归：文法存在产生式 P + Pa —直接左递归： P —间接左递归：P Pa Aa ,A + Pb
•2）消除左递归
—消除直接左递归 —消除间接左递归
第四章 自上而下语法分析（23）
第二节 自上而下分析法的一般问题 三、不带回溯的自上而下分析算法
2、消除直接左递归
第四章 自上而下语法分析（44）
第三节 预测分析程序与LL(1)文法 二、求串a的终结首符集和非终结符A的随符集
例：对如下文法G（已加上编号）
1. E
4. T 7. F
TE’
FT’ i
2. E’
5. T’ 8. F
+TE’
*FT’ (E)
3.E’
6.T’
e
e
求各非终结符号的终结首符集和随符集
第四章 自上而下语法分析（45）
第四章 自上而下语法分析（47）
第三节 预测分析程序与LL(1)文法 二、求串a的终结首符集和非终结符A的随符集
例：对如下文法G（已加上编号）
1. E
4. T 7. F
TE’
FT’ i
2. E’
5. T’ 8. F
+TBiblioteka ’*FT’ (E)3.E’
6.T’
e
e
求各非终结符号的终结首符集和随符集
第四章 自上而下语法分析（48）
第四章 自上而下语法分析（40）
第三节 预测分析程序与LL(1)文法 三、构造预测分析表
1. 基本思想 1)若A a是一个产生式，a ∈ First(a),那么当A 是栈顶符号且将读入a时，选择a取代A匹配成功的 希望最大，故,M[A,a]元素为A a 2)若A a而a=e,或a + e；当A是栈顶符号且将读 入a时，若a ∈ Follow(A),则栈顶的A应被e匹配； 此时读头不前进，让A的随符与读头下的符号进行 匹配，这样输入串匹配成功的可能最大，故M[A,a] 元素为A a(这里a=e或a + e)
917405-编译技术-电子教案-第4章-语法分析(一)
北京航空航天大学计算机学院
5
4.2 自顶向下分析
4.2.1 自顶向下分析的一般过程
给定符号串S，若预测是某一语法成分，则可根据该 语法成分的文法,设法为S构造一棵语法树， 若成功,则S最终被识别为某一语法成分,即
SL(G[Z])，其中G[Z]为某语法成分的文法 若不成功, 则 SL(G[Z])
• 可以通过一例子来说明语法分析过程
26
2.超前扫描
当文法不满足避免回溯的条件时，即各选择的首符号相 交时，可以采用超前扫描的方法，即向前侦察各输入符 号串的第二个、第三个符号来确定要选择的目标
这种方法是通过向前多看几个符号来确定所选择的目 标，从本质上来讲也有回溯的味道，因此比第一种方 法费时，但是假读仅仅是向前侦察情况，不作任何语 义处理工作。
a. 改写以后的文法消除了左递归。 b. 可以证明，改写前后的文法是等价的，表现在
L(G改前) = L(G改后)
如何改写文法能消除左递归，又前后等价， 可以给出两条规则:
北京航空航天大学计算机学院
12
规则一（提因子）
若：U∷=xy|xw|….|xz 则可改写为：U∷=x(y|w|….|z) 若：y=y1y2, w=y1w2 则 U∷=x(y1(y2|w2)|….|z)
改写文法： <程序> ∷= begin （<说明串>；<语句串> end | <语句串> end ）
引入 <程序*> <程序> ∷= begin <程序*> <程序*> ∷= <说明串>；<语句串> end | <语句串> end
北京航空航天大学计算机学院
编译原理Part4语法分析
ห้องสมุดไป่ตู้
同步符号集的选择
把FOLLOW(A)中的所有符号放入非终结符A的同步符号集。 如果我们跳读一些输入符号直至出现FOLLOW(A)中的同步 符号，把A从栈中弹出来，这样就可能使分析继续下去。 对于非终结符A来说，只用FOLLOW(A)作为它的同步符号 集是不够的。例如，如果分号作为语句的终结符，那么作为 语句开头的关键字就可能不在产生表达式的非终结符的FOL LOW集合中。这样，在一个赋值语句后少一个分号就可能 导致作为下一个语句开头的关键字被跳过
如果非终结符Ａ的所有候选首符集两两不相交，即Ａ的任何 两个不同候选αi和αｊ
FIRST(αi) ∩FIRST(αj)=Φ
那么当要求Ａ匹配输入串时，Ａ就能根据它所面临的第一个 输入符号ａ，准确的指派某一个候选前去执行任务。这个候 选就是那个终结首符集含ａ的α。
消除回溯、提取左因子
提取左因子的方法
假定Ａ的规则是： Ａ→δβ1 |δβ2 | … |δβn |γ1 |γ2 | … |γm
自顶向下分析的简单例子
假定文法G[S]，以及输入串x*y（记为α）。
S→xAy
A→**|*
初始化：
S
x*y
IP
第一步扩展
S
x*y
x
A
y
IP
自顶向下分析的简单例子
假定文法G[S]，以及输入串x*y（记为α）。
S→xAy
第二步扩展：
S
A→**|*
x*y
x
A
y
IP
**
回溯 S
x*y
x
A
y
IP
*
自顶向下分析方法的特点
通用的语法分析方法，用来分析任何文法，生成编译器时效率 太低 编译器使用的语法分析方法—处理文法的一些子类
同步符号集的选择
把FOLLOW(A)中的所有符号放入非终结符A的同步符号集。 如果我们跳读一些输入符号直至出现FOLLOW(A)中的同步 符号，把A从栈中弹出来，这样就可能使分析继续下去。 对于非终结符A来说，只用FOLLOW(A)作为它的同步符号 集是不够的。例如，如果分号作为语句的终结符，那么作为 语句开头的关键字就可能不在产生表达式的非终结符的FOL LOW集合中。这样，在一个赋值语句后少一个分号就可能 导致作为下一个语句开头的关键字被跳过
如果非终结符Ａ的所有候选首符集两两不相交，即Ａ的任何 两个不同候选αi和αｊ
FIRST(αi) ∩FIRST(αj)=Φ
那么当要求Ａ匹配输入串时，Ａ就能根据它所面临的第一个 输入符号ａ，准确的指派某一个候选前去执行任务。这个候 选就是那个终结首符集含ａ的α。
消除回溯、提取左因子
提取左因子的方法
假定Ａ的规则是： Ａ→δβ1 |δβ2 | … |δβn |γ1 |γ2 | … |γm
自顶向下分析的简单例子
假定文法G[S]，以及输入串x*y（记为α）。
S→xAy
A→**|*
初始化：
S
x*y
IP
第一步扩展
S
x*y
x
A
y
IP
自顶向下分析的简单例子
假定文法G[S]，以及输入串x*y（记为α）。
S→xAy
第二步扩展：
S
A→**|*
x*y
x
A
y
IP
**
回溯 S
x*y
x
A
y
IP
*
自顶向下分析方法的特点
通用的语法分析方法，用来分析任何文法，生成编译器时效率 太低 编译器使用的语法分析方法—处理文法的一些子类
编译原理---第4章-语法分析和语法分析程序
X
n
)
•
21 ....
22
...
2
n
(1
2
...
n
)
n1
n
2
...
nn
或表示为: X=XA+B，方程的解为: X=BA*
由于A*=A0+A1+A2+…=I+AA*
(r*=|rr*)
若令A*=Z，则对X=BA*可得X=BZ和Z=I+AZ
X会不会产生左递归？
Z会不会产生左递归？
8
2021/4/6
|2A' |…|mA'和A'1A' |2A' |…|nA' |
7
2021/4/6
4.1.1 消除文法的左递归
左递归的消除
从线性方程组到矩阵方程
从3类文法到2类文法
只关心产生式右部各符号串的首字符
对n个非终结符X1…Xn，得到矩阵方程
1112...1n
（X
1
X
2
...
X
n
)
（X
1
X
2
...
步骤分析栈余留输入串所用产生式11i匹配12tmft13etfm匹配1516etii匹配17分析成功414预测分析法46sfsfsfsf414预测分析法47步骤分析栈余留输入串所用产生式匹配10esf414预测分析法48步骤分析栈余留输入串所用产生式11ffs12ffii匹配13匹配15fsf16fs匹配17fs匹配19esf20ffs414预测分析法49步骤分析栈余留输入串所用产生式21ffii匹配22匹配24匹配26分析成功42自底向上的语法分析50例文法
17
《编译原理及实践教程》第4章自上而下语法分析
• 问题：
– 在上一章词法分析中讲解了如何判断源程序 中单词的正确性，并输出了正确的单词符号。 那么如何知道这些正确的单词是否能构成正 确的语法单位（表达式、语句或程序）呢？
• 语法分析的任务
– 在词法分析识别出正确的单词符号串的基础 上，根据语言定义的语法规则，从单词符号 串中分析并识别出各种语法成分，同时进行 语法检查和错误处理。
<IF语句> if E then S1 else S2 <IF语句> if E then S1 对输入符号串if (a>b) then x=3进行分析时， 当读入符号if时，不能马上确定用哪个候选 式。
β1
提取公共左因子后：
<IF语句> if E then S1 P P else S2 |ε
现有输入串i*i+i, 分析过程是：
思考：产生无限循环的原因？
对左递归文法使用最左推导。
失败：出现死循环
真正原因：文法的产生式有问题。
结论
1. 左递归和回溯问题的产生直接与描述 语言的文法有关 2. 应该改造文法，使其不含左递归和回 溯，才能进行确定的自上而下分析
问题的解决方法
• 消除回溯
改造为等价文法
• 问题2：左递归（无限循环）
左递归：文法中存在某个AVN，有A A。 直接左递归：有产生式A A E 间接左递归：（81页） + T E 例2：设有文法G(E)：
(1) E E+T | T (2) T T*F | F (3) F (E) | i E E … + + T T
• 例4.6 求下列文法中各个非终结符和各个 候选式的First集。 First(F) = { ( ，i }
– 在上一章词法分析中讲解了如何判断源程序 中单词的正确性，并输出了正确的单词符号。 那么如何知道这些正确的单词是否能构成正 确的语法单位（表达式、语句或程序）呢？
• 语法分析的任务
– 在词法分析识别出正确的单词符号串的基础 上，根据语言定义的语法规则，从单词符号 串中分析并识别出各种语法成分，同时进行 语法检查和错误处理。
<IF语句> if E then S1 else S2 <IF语句> if E then S1 对输入符号串if (a>b) then x=3进行分析时， 当读入符号if时，不能马上确定用哪个候选 式。
β1
提取公共左因子后：
<IF语句> if E then S1 P P else S2 |ε
现有输入串i*i+i, 分析过程是：
思考：产生无限循环的原因？
对左递归文法使用最左推导。
失败：出现死循环
真正原因：文法的产生式有问题。
结论
1. 左递归和回溯问题的产生直接与描述 语言的文法有关 2. 应该改造文法，使其不含左递归和回 溯，才能进行确定的自上而下分析
问题的解决方法
• 消除回溯
改造为等价文法
• 问题2：左递归（无限循环）
左递归：文法中存在某个AVN，有A A。 直接左递归：有产生式A A E 间接左递归：（81页） + T E 例2：设有文法G(E)：
(1) E E+T | T (2) T T*F | F (3) F (E) | i E E … + + T T
• 例4.6 求下列文法中各个非终结符和各个 候选式的First集。 First(F) = { ( ，i }
编译技术-第4章-语法分析(一)
对具有多个右部的规则反复提取左因子
例1 U∷=xV|xW
U, V, W∈Vn, x∈Vt+
改写为U∷=x(V|W) 更清楚地表示为：
U∷=xZ Z∷=V|W
注意：问题到此并没有结束，还需要 进一步检查V和W的首符号是否相交 若V∷=ab|cd FIRST(V) = {a,c}
W∷=de|fg FIRST(W) = {d,f} 只要不相交就可以根据输入符号确定 目标，若相交，则要代入，并再次提 取左因子。如：V::= ab w::= ac
3. 化简由2得到的文法即可。
例：文法G[s]为 S ∷= Qc|c Q ∷= Rb|b R ∷= Sa|a
该文法无直接左递归，但有间接左递归
SQc Rbc Sabc
∴ S+Sabc
非终结符顺序重新排列
R∷=Sa|a Q∷=Rb|b S∷=Qc|c
1. 检查规则R是否存在直接左递归
R∷=Sa|a Q∷=Rb|b S∷=Qc|c
如果文法具有间接左递归，则也将发生上述问题，只不 过环的圈子兜得更大。
要实行自顶向下分析，必须要消除文法的左递归，下面 将介绍直接左递归的消除方法，在此基础上再介绍一般左递 归的消除方法。
消除直接左递归
方法一，使用扩充的BNF表示来改写文法
例：(1) E∷=E+T|T E∷=T{+T} (2) T∷=T*F|T/F|F T ∷=F{*F|/F}
a. 改写以后的文法消除了左递归。 b. 可以证明，改写前后的文法是等价的，表现在
L(G改前) = L(G改后)
如何改写文法能消除左递归，又前后等价， 可以给出两条规则:
规则一（提因子）
若：U∷=xy|xw|….|xz 则可改写为：U∷=x(y|w|….|z) 若：y=y1y2, w=y1w2 则 U∷=x(y1(y2|w2)|….|z)
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
基本任务：识别符号串S是否为某语法成分。 两大类分析方法：
自顶向下分析 自底向上分析
自顶向下分析算法的基本思想为：
若Z + S 则 S L(G[Z]) 否则 S L(G[Z])
G[Z]
主要问题: ➢ 左递归问题 ➢ 回溯问题
▪ 主要方法: • 递归子程序法 • LL分析法
自底向上分析算法的基本思想为：
第四章 语法分析
• 语法分析的功能、基本任务 • 自顶向下分析法＞ • 自底向上分析法＞
复习：第一章 概述
编译过程是指将高级语言程序翻译为等价的目标程 序的过程。 习惯上是将编译过程划分为5个基本阶段：
词法分析 语法分析 语义分析、生成中间代码 代码优化 生成目标程序
4.1 语法分析概述
功能：根据文法规则，从源程序单词符号串中识别出语法 成分，并进行语法检查。
若有规则：U∷=x|xy 则可以改写为：U∷=x(y|ε) 注意：不应写成U∷=x(ε|y)
使用提因子法，不仅有助于消除直接左递归，而且有 助于压缩文件的长度，使我们能更有效地分析句子。
规则二
若有文法规则：U∷=x|y|……|z|Uv
其特点是：具有一个直接左递归的右部并位于最后， 这表明该语法类U是由x或y……或z其后随有零个 或多个v组成。
若Z + S
G[Z]
则 S L(G[Z]) 否则 S L(G[Z])
主要问题: ➢ 句柄的识别问题
▪ 主要方法: • 算符优先分析法 • LR分析法
4.2 自顶向下分析
4.2.1 自顶向下分析的一般过程
给定符号串S，若预测是某一语法成分，则可根据该 语法成分的文法,设法为S构造一棵语法树， 若成功,则S最终被识别为某一语法成分,即
Z · Z·
完成一步推导ZcAd
检查, c-c匹配
cAd
A是非终结符,将匹配任务交给A
S=cad G[Z]: Z∷=cAd A∷=ab|a
3. 选用A的右部符号串匹配输入串 A有两个右部,选第一个
完成进一步推导Aab 检查,a-a匹配,b-d不匹配(失败) 但是还不能冒然宣布SL(G[Z])
Z· cAd
UUv Uv v Uv vv …… ∴ 可以改写为U∷=(x|y|……|z){v}
通过以上两条规则，就能消除文法的直接左递归， 并保持文法的等价性。
方法二，将左递归规则改为右递归规则
规则三
若：P∷=P| 则可改写为：P ∷= P’
P’ ∷= P’| ε
规则一：（提因子） 规则二：U∷=x|y|……|z|Uv, 则U∷=(x|y|……|z){v} 规则三：右递归P∷=P| ，则P ∷= P’，P’ ∷= P’| ε
如果文法具有间接左递归，则也将发生上述问题，只不 过环的圈子兜得更大。
要实行自顶向下分析，必须要消除文法的左递归，下面 将介绍直接左递归的消除方法，在此基础上再介绍一般左递 归的消除方法。
消除直接左递归
方法一，使用扩充的BNF表示来改写文法
例：(1) E∷=E+T|T E∷=T{+T} (2) T∷=T*F|T/F|F T ∷=F{*F|/F}
a. 改写以后的文法消除了左递归。 b. 可以证明，改写前后的文法是等价的，表现在
L(G改前) = L(G改后)
如何改写文法能消除左递归，又前后等价， 可以给出两条规则:
规则一（提因子）
若：U∷=xy|xw|….|xz 则可改写为：U∷=x(y|w|….|z) 若：y=y1y2, w=y1w2 则 U∷=x(y1(y2|w2)|….|z)
ab
4. 回溯 即砍掉A的子树 改选A的第二右部
Aa 检查 a-a匹配 d-d匹配
Z· cAd
建立语法树,末端结点为cad,与输入cad相匹配, a 建立了推导序列 ZcAdcad ∴cadL(. 分析过程是带预测的，对输入符号串要预测属于什么 语法成分，然后根据该语法成分的文法建立语法树。
例1 E∷=E+T|T 右部无公因子，所以不能 用规则一。 为了使用规则二， 令E∷=T|E+T ∴由规则二可以得到
E∷=T{+T}
例2 T∷=T*F|T/F|F T∷=T(*F|/F) | F 规则一 T∷=F|T(*F|/F) T∷=F{(*F|/F)} 规则二
即T∷=F{*F|/F}
右递归： T ::= FT’ T’ ::= *FT’ | /FT’ | ε
2. 分析过程是一种试探过程，是尽一切办法(选用不同 规则) 来建立语法树的过程, 由于是试探过程, 难免 有失败, 所以分析过程需进行回溯, 因此也称这种方法 是带回溯的自顶向下分析方法。
3. 最左推导可以编写程序来实现, 但带溯的自顶向下分 析方法在实际上价值不大, 效率低。
4.2.2 自顶向下分析存在的问题及解决方法
1 、 左递归文法： 有如下文法： 令U是文法的任一非终结符，文法中有规则 U∷=U¨¨或者U U+ ¨¨ 这个文法是左递归的。
自顶向下分析的基本缺点是： 不能处理具有左递归性的文法
为什么？
如果在匹配输入串的过程中，假定正好轮到要用非终结 符U直接匹配输入串，即要用U的右部符号串U¨¨去匹配， 为了用U¨¨去匹配，又得用U去匹配，这样无限的循环下 去将无法终止。
SL(G[Z])，其中G[Z]为某语法成分的文法 若不成功, 则 SL(G[Z])
• 可以通过一例子来说明语法分析过程
例：
S = cad
G[Z]: Z∷=cAd A∷=ab|a
求解 SL(G[Z]) ?
分析过程是设法建立一 棵语法树,使语法树的末端结 点与给定符号串相匹配。
1. 开始:令Z为根结点 2. 用Z的右部符号串去匹配输入串
消除一般左递归 一般左递归也可以通过改写文法予以消除。
消除所有左递归的算法：
1. 把G的非终结符整理成某种顺序A1，A2，……An ，使得： A1 ::= δ1|δ2|……δk A2 ::= A1 r…… A3 ::= A2u | A1v….. …….
2. For i:=1 to n do begin for j :=1 to i-1 do 把每个形如Ai∷=Ajr的规则替换成 Ai ∷=(δ1|δ2|……|δk) r , 其中Aj ∷=δ1|δ2|……|δk是当前全部Aj 的规则; 消除Ai规则中的直接左递归 end
自顶向下分析 自底向上分析
自顶向下分析算法的基本思想为：
若Z + S 则 S L(G[Z]) 否则 S L(G[Z])
G[Z]
主要问题: ➢ 左递归问题 ➢ 回溯问题
▪ 主要方法: • 递归子程序法 • LL分析法
自底向上分析算法的基本思想为：
第四章 语法分析
• 语法分析的功能、基本任务 • 自顶向下分析法＞ • 自底向上分析法＞
复习：第一章 概述
编译过程是指将高级语言程序翻译为等价的目标程 序的过程。 习惯上是将编译过程划分为5个基本阶段：
词法分析 语法分析 语义分析、生成中间代码 代码优化 生成目标程序
4.1 语法分析概述
功能：根据文法规则，从源程序单词符号串中识别出语法 成分，并进行语法检查。
若有规则：U∷=x|xy 则可以改写为：U∷=x(y|ε) 注意：不应写成U∷=x(ε|y)
使用提因子法，不仅有助于消除直接左递归，而且有 助于压缩文件的长度，使我们能更有效地分析句子。
规则二
若有文法规则：U∷=x|y|……|z|Uv
其特点是：具有一个直接左递归的右部并位于最后， 这表明该语法类U是由x或y……或z其后随有零个 或多个v组成。
若Z + S
G[Z]
则 S L(G[Z]) 否则 S L(G[Z])
主要问题: ➢ 句柄的识别问题
▪ 主要方法: • 算符优先分析法 • LR分析法
4.2 自顶向下分析
4.2.1 自顶向下分析的一般过程
给定符号串S，若预测是某一语法成分，则可根据该 语法成分的文法,设法为S构造一棵语法树， 若成功,则S最终被识别为某一语法成分,即
Z · Z·
完成一步推导ZcAd
检查, c-c匹配
cAd
A是非终结符,将匹配任务交给A
S=cad G[Z]: Z∷=cAd A∷=ab|a
3. 选用A的右部符号串匹配输入串 A有两个右部,选第一个
完成进一步推导Aab 检查,a-a匹配,b-d不匹配(失败) 但是还不能冒然宣布SL(G[Z])
Z· cAd
UUv Uv v Uv vv …… ∴ 可以改写为U∷=(x|y|……|z){v}
通过以上两条规则，就能消除文法的直接左递归， 并保持文法的等价性。
方法二，将左递归规则改为右递归规则
规则三
若：P∷=P| 则可改写为：P ∷= P’
P’ ∷= P’| ε
规则一：（提因子） 规则二：U∷=x|y|……|z|Uv, 则U∷=(x|y|……|z){v} 规则三：右递归P∷=P| ，则P ∷= P’，P’ ∷= P’| ε
如果文法具有间接左递归，则也将发生上述问题，只不 过环的圈子兜得更大。
要实行自顶向下分析，必须要消除文法的左递归，下面 将介绍直接左递归的消除方法，在此基础上再介绍一般左递 归的消除方法。
消除直接左递归
方法一，使用扩充的BNF表示来改写文法
例：(1) E∷=E+T|T E∷=T{+T} (2) T∷=T*F|T/F|F T ∷=F{*F|/F}
a. 改写以后的文法消除了左递归。 b. 可以证明，改写前后的文法是等价的，表现在
L(G改前) = L(G改后)
如何改写文法能消除左递归，又前后等价， 可以给出两条规则:
规则一（提因子）
若：U∷=xy|xw|….|xz 则可改写为：U∷=x(y|w|….|z) 若：y=y1y2, w=y1w2 则 U∷=x(y1(y2|w2)|….|z)
ab
4. 回溯 即砍掉A的子树 改选A的第二右部
Aa 检查 a-a匹配 d-d匹配
Z· cAd
建立语法树,末端结点为cad,与输入cad相匹配, a 建立了推导序列 ZcAdcad ∴cadL(. 分析过程是带预测的，对输入符号串要预测属于什么 语法成分，然后根据该语法成分的文法建立语法树。
例1 E∷=E+T|T 右部无公因子，所以不能 用规则一。 为了使用规则二， 令E∷=T|E+T ∴由规则二可以得到
E∷=T{+T}
例2 T∷=T*F|T/F|F T∷=T(*F|/F) | F 规则一 T∷=F|T(*F|/F) T∷=F{(*F|/F)} 规则二
即T∷=F{*F|/F}
右递归： T ::= FT’ T’ ::= *FT’ | /FT’ | ε
2. 分析过程是一种试探过程，是尽一切办法(选用不同 规则) 来建立语法树的过程, 由于是试探过程, 难免 有失败, 所以分析过程需进行回溯, 因此也称这种方法 是带回溯的自顶向下分析方法。
3. 最左推导可以编写程序来实现, 但带溯的自顶向下分 析方法在实际上价值不大, 效率低。
4.2.2 自顶向下分析存在的问题及解决方法
1 、 左递归文法： 有如下文法： 令U是文法的任一非终结符，文法中有规则 U∷=U¨¨或者U U+ ¨¨ 这个文法是左递归的。
自顶向下分析的基本缺点是： 不能处理具有左递归性的文法
为什么？
如果在匹配输入串的过程中，假定正好轮到要用非终结 符U直接匹配输入串，即要用U的右部符号串U¨¨去匹配， 为了用U¨¨去匹配，又得用U去匹配，这样无限的循环下 去将无法终止。
SL(G[Z])，其中G[Z]为某语法成分的文法 若不成功, 则 SL(G[Z])
• 可以通过一例子来说明语法分析过程
例：
S = cad
G[Z]: Z∷=cAd A∷=ab|a
求解 SL(G[Z]) ?
分析过程是设法建立一 棵语法树,使语法树的末端结 点与给定符号串相匹配。
1. 开始:令Z为根结点 2. 用Z的右部符号串去匹配输入串
消除一般左递归 一般左递归也可以通过改写文法予以消除。
消除所有左递归的算法：
1. 把G的非终结符整理成某种顺序A1，A2，……An ，使得： A1 ::= δ1|δ2|……δk A2 ::= A1 r…… A3 ::= A2u | A1v….. …….
2. For i:=1 to n do begin for j :=1 to i-1 do 把每个形如Ai∷=Ajr的规则替换成 Ai ∷=(δ1|δ2|……|δk) r , 其中Aj ∷=δ1|δ2|……|δk是当前全部Aj 的规则; 消除Ai规则中的直接左递归 end