编译技术-第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)
编译原理-语法分析
03
自顶向下的语法分析方法简单直观，易于实现，但可能存在 左递归和回溯的问题。
自底向上的语法分析
01
自底向上的语法分析方法从源代码中的每个符号出发
，逐步归约到文法的起始符号。
02
该方法通常采用LR(0)、SLR(1)、LALR(1)等算法进行
实现。
03
自底向上的语法分析方法可以避免回溯问题，但需要
• 随着人工智能和机器学习技术的不断发展，可以利用这些技术来辅助语法分析 过程，提高语法分析的准确性和效率。例如，可以使用机器学习算法来自动识 别和处理语法规则和歧义问题。
• 另外，随着软件工程和代码质量的重视程度不断提高，对编译器和语法分析器 的要求也越来越高。未来的研究需要更加注重编译器和语法分析器的可维护性 和可扩展性，以满足不断变化的软件需求。
词法分析的算法
自底向上算法
自底向上算法是从源代码的左向右进行扫描，并从下到上构建语法结构。常见 的自底向上算法有预测分析法和移进-规约法。
自顶向下算法
自顶向下算法是从语法结构的顶层开始，向下进行推导，直到找到与源代码相 匹配的语法结构。常见的自顶向下算法有规范分析法和贪婪分析法。
语法分析概述
语法分析是编译过程的核心环节，其任务是将源代码分解成一系列的语法 结构，以便后续的语义分析和代码生成。
自底向上的算法，通过构建归 约表进行移进和规约操作。
LALR(1)算法
扩展的LR(0)算法，能够处理 更广泛的文法，生成更小的归 约表。
03
语义分析
语义分析概述
01
Байду номын сангаас02
03
语义分析是编译过程的 一个阶段，它是在语法
分析之后进行的。
语义分析的主要任务是 检查源代码的语义是否 正确，例如变量是否已 经声明，类型是否匹配
自顶向下的语法分析方法简单直观，易于实现，但可能存在 左递归和回溯的问题。
自底向上的语法分析
01
自底向上的语法分析方法从源代码中的每个符号出发
，逐步归约到文法的起始符号。
02
该方法通常采用LR(0)、SLR(1)、LALR(1)等算法进行
实现。
03
自底向上的语法分析方法可以避免回溯问题，但需要
• 随着人工智能和机器学习技术的不断发展，可以利用这些技术来辅助语法分析 过程，提高语法分析的准确性和效率。例如，可以使用机器学习算法来自动识 别和处理语法规则和歧义问题。
• 另外，随着软件工程和代码质量的重视程度不断提高，对编译器和语法分析器 的要求也越来越高。未来的研究需要更加注重编译器和语法分析器的可维护性 和可扩展性，以满足不断变化的软件需求。
词法分析的算法
自底向上算法
自底向上算法是从源代码的左向右进行扫描，并从下到上构建语法结构。常见 的自底向上算法有预测分析法和移进-规约法。
自顶向下算法
自顶向下算法是从语法结构的顶层开始，向下进行推导，直到找到与源代码相 匹配的语法结构。常见的自顶向下算法有规范分析法和贪婪分析法。
语法分析概述
语法分析是编译过程的核心环节，其任务是将源代码分解成一系列的语法 结构，以便后续的语义分析和代码生成。
自底向上的算法，通过构建归 约表进行移进和规约操作。
LALR(1)算法
扩展的LR(0)算法，能够处理 更广泛的文法，生成更小的归 约表。
03
语义分析
语义分析概述
01
Байду номын сангаас02
03
语义分析是编译过程的 一个阶段，它是在语法
分析之后进行的。
语义分析的主要任务是 检查源代码的语义是否 正确，例如变量是否已 经声明，类型是否匹配
编译原理第四章答案
“编译技术”第四章作业4-1 已知文法G[C]：C→iEtS|iEtSeSE→ a|bS→ a+b|a*b(1)提取左公共因子；(2)计算修改后文法的每个非终结符的FIRST集和FOLLOW集；(3)给出递归下降分析程序。
(3)递归下降分析程序void match(token t){if(lookahead=='t')lookahead = nexttoken;else error;}void C(){if(lookahead=='i'){match('i');E();if(lookahead=='t'){match('t');S();Cprime();}else error;}else error;}void Cprime(){if(lookahead=='e'){match('e');S();}}void E(){if(lookahead=='a')match('a');else if(lookahead=='b')match('b');else error;}void S(){if(lookahead=='a'){match('a');Sprime();}}void Sprime(){if (lookahead=='+'){match('+');if(lookahed=='b'){match('b');}else error();}else if(lookahead=='*'){match('*');if(lookahead=='b'){match('b');}else error();}}4-2 已知文法G[Z]：Z→Az|bA→ Za|a(1)删除左递归；(2)计算修改后文法的每个非终结符的FIRST集和FOLLOW集；(3)给出递归下降分析程序。
编译原理第四章语法分析-自上而下分析
• 例 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 化简由（２）所得的文法。即去除那些从开始符号出发永 远无法到达的非终结符的产生规则。
编译第4章
• 无符号整数
– 数字（数字）* – 〈无符号整数〉→d|d〈无符号整数〉
20
4.2.3 正规文法和正规式的等价性
一、正规文法、正规集与正规式三个概念间关系
盛 威 网 ： 专 业 的 计 算 机 学 习 网 站
一个正规语言可以用正规文法定义，也可以 用正规式定义，对任意一个正规文法，存在一个 定义同一个语言的正规式；同样，对每个正规式， 存在一个生成同一语言的正规文法；有些正规语 言很容易用文法定义，有些则用正规式定义更容 易；两者之间是可以转换的，结构上具有等价性。 由正规文法或正规式定义的正规语言的集合构成 正规集。
§4.3 有穷自动机（FA）
盛 威 网 ： 专 业 的 计 算 机 学 习 网 站
a 0
1
a
b
b 2
a b
3
a,b
对于符号串abaab
对于符号串abab
30
有穷自动机（FA）
• 有穷自动机是一种识别装臵，它能准确地识别正规 集，即识别正规文法所定义的语言和正规式所表示 的集合。为词法分析程序的自动构造寻找特殊的方 法和工具。 • 有穷自动机是一种数学模型，具有有限数目的内部 状态，系统可以根据当前所处的状态和面临的输入 字符决定系统的后继行为。其当前状态概括了过去 输入处理的信息。
盛 威 网 ： 专 业 的 计 算 机 学 习 网 站
正规式产生式
正规文法
规则1 规则2
规则3
A→ xy A→ x*y
A→ x|y
A→xB,B→y
A→xB A→y B→xB B→y
A→x,A→y
其中B为一新非终结符
23
盛 威 网 ： 专 业 的 计 算 机 学 习 网 站
编译技术原理及方法 课件 第四章 语法分析1
具体的说，语法分 析是在单词流的基础 上建立一个层次结构
标识符 a
——语法树
=
表达式
标识符 +
表达式
b
标识符 *ቤተ መጻሕፍቲ ባይዱ标识符
c
d
4-1语法分析概述
一、语法分析的主要任务
举例 a=b+c*d
语法分析 任务：将词法分析后所有单词组成句子，根据不同高级语言
不同语法规则来分析这些句子乃至程序是否正确。
如果写成 a=b+-c*d 会不会发现？
cad
S
i
ScAd c A d cabd a b
4-1语法分析概述 二、自顶向下语法分析概述
2、分析方法
若按自上而下语法分析程序的步骤进行分析判断，其过程如下：
P: S∷=cAd A∷=ab|a
（3）此时子树A最左端末结点a 与i所指的符号a匹配。于是 再调整i使其指向下一输入符 号d，并试图用A的最右末端 结点b与之匹配。但它们不 匹配，因此，子树A的匹配 失败，这意味着选用A的第 一个候选式对此时的情况不 适合，不能构造出输入串x 的语法树。
4-2自顶向下语法分析
4.2.1消除回溯和左递归
一、消除回溯
2、运气不好的情况——同一个非终结符的不同候选式的不以终 结符号开头 ： 通过求FIRST集分析路标
不难总结出，构造FIRST集的方法步骤如下—— 对任一符号X（X∈VN∪VT），构造FIRST(X)时，只要连续使用下列规则，直至每个FIRST
ScAd c
A
d
4-1语法分析概述 二、自顶向下语法分析概述
2、分析方法
若按自上而下语法分析程序的步骤进行分析判断，其过程如下：
P: S∷=cAd A∷=ab|a
- 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