西北工业大学：《编译原理》课程教学资源（PPT课件）第4章 语法分析和语法分析程序（4.1）自顶向下的语法分析

第四章语法分析和语法分析程序 ·对象：单词流形式的源程序 ·任务：根据语法规则，分析源程序的语法结构， 同时进行语法检查 ·输出：语法树 假定：先不考虑语义问题 ·常见分析方法：自顶向下()和自底向上（个） ·↓：递归下降法，预测分析法(LL分析法) ·个：优先分析法，LR分析法

第四章 语法分析和语法分析程序 • 对象：单词流形式的源程序 • 任务：根据语法规则，分析源程序的语法结构， 同时进行语法检查 • 输出：语法树 • 假定：先不考虑语义问题 • 常见分析方法：自顶向下()和自底向上() • :递归下降法,预测分析法(LL分析法) • :优先分析法,LR分析法

4.1自顶向下的语法分析 ·↓：对已给的输入串w,试图自 例：E→TIEAT 上而下地建立一棵语法树；或 T-→FITMF F→(E)iA-→+- 者说，从S出发，为w构造一个 M->*|1(4.1) 最左推导若成功，则w∈L(G), 。 设w=j+i*i,每个产生式从左 否则拒绝. 至右试验.从E出发： 一般说来，在为W寻求最左推 导的每一步，都涉及使用何产 E→T→F→(E) 生式进行替换的问题.最简单 →i 的方法是，逐一试探！ →TMF→FMF→(E)MF 遗憾的是，逐一试探也不能完 →iMF→i*F 全解决问题.例如，在含有左 →i/F 递归的文法中，就会出现不能 →TMFMF→.. 终止的替换现象. →TMFMFMF

4.1 自顶向下的语法分析 • :对已给的输入串w,试图自 上而下地建立一棵语法树;或 者说,从S出发,为w构造一个 最左推导.若成功,则wL(G), 否则拒绝. • 一般说来,在为w寻求最左推 导的每一步,都涉及使用何产 生式进行替换的问题.最简单 的方法是,逐一试探. • 遗憾的是,逐一试探也不能完 全解决问题.例如,在含有左 递归的文法中,就会出现不能 终止的替换现象. • 例:E→T|EAT T→F|TMF F→(E)|i A→+|- M→* | / (4.1) • 设w=i+i*i,每个产生式从左 至右试验.从E出发: ETF(E) i TMFFMF(E)MF iMF i*F i/F TMFMF … TMFMFMF

自顶向分析方法的特点 1.若G有左递归，则分析不能正常进行.因此，↓分析 必须先消除文法的左递归； 2.分析过程是反复进行试探的过程，因此，难免会 出现大量的回溯.特别是当L(G)时，只有在穷 举完所有的试探后才能拒绝w. 由于回溯，就需将从出错点到迄今为止己做过的 大量工作废弃，显然会大大降低分析的效率.特 别是在语法分析阶段还往往要进行同步的语义 分析和处理，这些工作也就白做了.因此，消除回 溯是↓分析的另一目标. 3.当拒绝w时，只能知道w不是句子，不知出何错及 出在何处

自顶向下分析方法的特点 1.若G有左递归,则分析不能正常进行.因此, 分析 必须先消除文法的左递归; 2.分析过程是反复进行试探的过程,因此,难免会 出现大量的回溯.特别是当wL(G)时,只有在穷 举完所有的试探后才能拒绝w. 由于回溯,就需将从出错点到迄今为止已做过的 大量工作废弃,显然会大大降低分析的效率.特 别是在语法分析阶段还往往要进行同步的语义 分析和处理,这些工作也就白做了.因此,消除回 溯是分析的另一目标. 3.当拒绝w时,只能知道w不是句子,不知出何错及 出在何处

4.1.1消除文法的左递归 设文法是已简化的若文法含直 一般地，设文法中全部A-产 接左递归式： A-→Aa|B 生式为 (a∈V+),则类似正规式求解 A→Ac1Ao2.JAanl 方法，我们有A→B{o}(Ba*). 引入新的非终结符A',令其产生 BBm,其中，β不以A打 ou*,则有： 头，则消除直接左递归后的 产生式为A-→BA引.|BmA A→BA' A'→aAlE 由于 及A→C1A||CnA B不以A打头，A非左递归. 对P105的文法(4.1)，可改写为 上述方法可消除直接去递 归，但对于间接左递归的文 E→TE'E'→ATEl8T→FT T'-→MFT'8 F→(E) 法来说，需将原文法进行变 A→+ M-→*W 换后才适用.例如，S→ Ablc A→Sa,可将其变换为 S→Sablc,再使用上述方 法，得 S→cS S'-→abS

4.1.1 消除文法的左递归 • 设文法是已简化的.若文法含直 接左递归式: A→A |  (V+) , 则类似正规式求解 方法,我们有A→  {} ( *). • 引入新的非终结符A’,令其产生 * ,则有: • A→ A’ A’→ A’| 由于 不以A打头,A非左递归. • 对P105的文法(4.1),可改写为 E→TE’ E’→ATE’| T→FT’ T’→MFT’| F→(E)|i A→+|- M→ *|/ • 一般地,设文法中全部A-产 生式为 A→A1|A2|…|An| 1|…| m,其中, i不以A打 头,则消除直接左递归后的 产生式为 A→1A’|…| mA’ 及 A’→ 1A’|…| nA’ • 上述方法可消除直接左递 归,但对于间接左递归的文 法来说,需将原文法进行变 换后才适用.例如, S → Ab|c A→Sa,可将其变换为 S →Sab|c,再使用上述方 法,得 S →cS’ S’ →abS’

消除文法左递归的矩阵方法 设文法的非终结符为X1, 该方程有解：X=BA* X2,,Xn,其中，X的产生式 为得到A*,由 可分为以Vw符和V-符打头 的两类.类似正规式方法，将 A*=I+A+A+A3+…=I+AA* 改写为‘+’，有 Z X=X1a1tX2a2rt+XnCni+B1其中 其中，1= 令A*= B:是以V符打头的产生式 之和，0可以为中 则有：X=BZ Z-I+AZ 这样，文法G可表示为 其中X的产生式以V符打头，而Z的 41C2u 产生式以@∈V*打头，因此将不含 0210202m 左递归. (X,X2,,X)=(X,X2,,Xn +,β2，βn) 注意，由此所得的文法含有无用符 0n0n2Cnm 号和无用产生式需化简 或：X=XA+B

消除文法左递归的矩阵方法 • 设文法的非终结符为 X1, X2, …, Xn, 其中,Xi的产生式 可分为以VN符和VT符打头 的两类.类似正规式方法,将 ‘|’改写为‘+’ ,有 Xi=X11i+X22i+…+Xnni+ i 其中,  i 是以VT符打头的产生式 之和, ki 可以为 这样,文法G可表示为 该方程有解: X=BA* 为得到A*,由 ( , , , ) ( , , , ) ( , , , ) 1 2 1 2 2 1 2 2 2 1 1 1 2 1 1 2 1 2 n n n n n n n X X Xn X X Xn +                         =         或: X=XA+B           =               = = + + + + = + n n n n Z Z Z Z I A A I A A A I AA        1 1 1 1 2 3 , , * * * 其中 令 则有: X=BZ Z=I+AZ 其中X的产生式以VT符打头,而Z的 产生式以ijV*打头,因此将不含 左递归. 注意,由此所得的文法含有无用符 号和无用产生式,需化简

消除文法左递归的例子 例4.1S-→SaAb|aA-→Sc 展开矩阵，得 相应的矩阵为 S→aZ11 A→aZ12 a C Z11→aZ11lcZ28Z12→ (S,A)=(S,A④ +(a,φ) aZ12cZ22 Φ Z21→bZ11 Z22→8 Z 令Z= Z12 则 bZ12 文法中含有无用产生式，消 Zi2 除之.最后，有 (S,)=(a,φ） Z S->aZi Z11→aZ11 Z Z CZ21 8 Z21>bZ11

消除文法左递归的例子 例4.1 S→Sa | Ab | a A→Sc 相应的矩阵为 展开矩阵,得 S →aZ11 A →aZ12 Z11→aZ11 |cZ21| Z12→ aZ12 |cZ22 Z21 → bZ11 Z22 →  | bZ12 文法中含有无用产生式,消 除之.最后,有 S →aZ11 Z11→aZ11 |cZ21|  Z21 →bZ11                 +            =                =          =          = +           = 2 1 2 2 1 1 1 2 2 1 2 2 1 1 1 2 2 1 2 2 1 1 1 2 2 1 2 2 1 1 1 2 * ( , ) ( , ) , ( , ) ( , ) ( , ) Z Z Z Z b a c Z Z Z Z Z Z Z Z S A a Z Z Z Z b a c Z a b a c S A S A 令 则

4.1.1回溯的消除及LL(1)文法 为解决回溯问题，我们从句子的最 为得到w的剩余部分aa+…am.由最左 左推导开始讨论. 推导的定义，考虑A的所有产生式： 设G=(N,VT,P,S)为一CFG, W=a1a..a是Vr上的符号串，现需判 A→Y1IY2…|Ym 明是否是L(G)中的句子.为此，从 $开始进行最左推导.设经若干步 对于当前输入符号a,若只有一个 推导后我们得到 (称为候选式)使得从Yβ出发可以推 导出一个以ā打头的符号串： S→w,4βA∈VxB∈V(4.17 YB→a,… 且w1=a,a2a-,l≤i≤n 而其它的Y(kj),YkB都推导不出以 a打头的符号串，则选定产生式A→M 注意，i=1时，w=8,A=S 就是唯一可行的推导即 由假设可知，到目前为止，w的前缀w1 WEL(G)→选A-→Y正确； 已匹配，现在需对AB进行推导. 影(G→选任何产生式均不能匹 显然，若P中产生式能满足上述要求， 则回湖可消除

4.1.1 回溯的消除及LL(1)文法 • 为解决回溯问题,我们从句子的最 左推导开始讨论. • 设G=(VN,VT,P,S) 为一CFG, w=a1a2…an是VT上的符号串,现需判 明w是否是L(G)中的句子.为此,从 S开始进行最左推导.设经若干步 推导后我们得到 w a a a i n S w A A V V i N =       − ,1 (4.17) 1 1 2 1 * 1 * 且  注意,i=1时,w1=,A=S 由假设可知,到目前为止,w的前缀w1 已匹配,现在需对A进行推导. A m →  |  | |  1 2  对于当前输入符号ai,若只有一个 j (称为候选式)使得从j出发可以推 导出一个以ai打头的符号串:  j  * ai  而其它的k(kj), k 都推导不出以 ai打头的符号串,则选定产生式A→j 就是唯一可行的推导,即 wL(G)选A→j正确; wL(G)选任何产生式均不能匹 配 显然,若P中产生式能满足上述要求, 则回溯可消除 为得到w的剩余部分aiai+1…an.由最左 推导的定义,考虑A的所有产生式:

消除回溯的条件 。 由前面的讨论可知，要实现无回溯的↓分析，文法必须满足一 定的条件。为导出这些条件，我们定义候选式的终结首符集 FIRST(y)={a|Y→*aδ，a∈Vr,δeV*的并约定Y→*e 时，8∈FIRST(Y) 若对于A-产生式的每个候选式y(i=1,2,..,m)都推不出e,且 FIRST(y)互不相交，则当正扫描的当前输入符号为 aiEFIRST(M)时，唯一可用于推导的产生式只能是A→M. 例如，文法G1[S]:S→AAA→aAb|*,A-产生式有两个候选 式，且 FIRST(aAb)=fa) FIRST(*)=的，两集不 相交，设输入串为aa*bb*,其最左推导为S→AA(a)→aAbA (a)→aaAbbA(*)→aa*bbA()→aa*bb*(#) 注：上面第每步推导右侧括号内为当前扫描的输入符号，#为结 束符。 我们得到了一个无回溯的条件：FIRST(Yi)OFIRST(Y)=☑

消除回溯的条件 • 由前面的讨论可知，要实现无回溯的分析,文法必须满足一 定的条件。为导出这些条件,我们定义候选式的终结首符集 FIRST()={a | * a, aVT,V*} 并约定 * 时,FIRST() • 若对于A-产生式的每个候选式i(i=1,2,…,m)都推不出 , 且 FIRST(i ) 互不相交,则当正扫描的当前输入符号为 aiFIRST(j)时,唯一可用于推导的产生式只能是A→j. • 例如,文法G1[S]: S→AA A→aAb | *, A-产生式有两个候选 式, 且 FIRST(aAb)={a} FIRST(*)={*},两集不 相交,设输入串为aa*bb*,其最左推导为 SAA (a) aAbA (a) aaAbbA (*) aa*bbA (*)aa*bb* (#) 注:上面第每步推导右侧括号内为当前扫描的输入符号,#为结 束符. • 我们得到了一个无回溯的条件: FIRST(i) FIRST(j)=

消除回溯的条件 然而还存在另外一种情况，可能存在某个候选式Y,Y1→*8， 即ε∈FIRST(y)(这样的是唯一的(？！))，此时，为匹配当前扫 描的符号a就可能有两种选择，一是存在某yj,使y推导出以a 打头的符号串，另一种选择是让A推导出Y,再让y推导出， 最后再让跟随在A后的符号串推导出以a打头的符号串. 若这两种选择都可行，则回溯不可避免.因此，就必须要求 当Y:→*ε时，跟在A后的符号串不能推导出其它Y所能推导 出的首终结符的符号串.为此，我们定义可紧跟在A后的所有 终结符之集 F0LL0W(A)={aS#→*cAaδ，aeVU{#},,6eV*] 其中，当A为一句型的尾符号时，#EFOLLOW(A). 现在，我们可把无回溯的另一条件描述为：若Y→*ε，则 FOLL0W(A)与其它的Y互不相交：FOLLOW(A)OFIRST(y)=O

消除回溯的条件 • 然而还存在另外一种情况,可能存在某个候选式i, i*, 即FIRST(i)(这样的是唯一的(?!)),此时,为匹配当前扫 描的符号a就可能有两种选择,一是存在某j,使j推导出以a 打头的符号串,另一种选择是让A推导出i,再让i推导出， 最后再让跟随在A后的符号串推导出以a打头的符号串. • 若这两种选择都可行,则回溯不可避免. 因此,就必须要求 当i *时,跟在A后的符号串不能推导出其它j 所能推导 出的首终结符的符号串.为此,我们定义可紧跟在A后的所有 终结符之集 FOLLOW(A)={a | S#*Aa, aVT{#}, ,V*} 其中,当A为一句型的尾符号时,#FOLLOW(A). • 现在,我们可把无回溯的另一条件描述为: 若i*,则 FOLLOW(A)与其它的j互不相交: FOLLOW(A)FIRST(j)=

消除回溯的条件 例S-→aA|bA-→cAS 8 FIRST(cAS)={c}FOLLOW(A) FIRST(S)#={a,b,粉两个集合不相交，故可进行无回溯的 ↓分析.设输入串w=aca#,其推导过程如下： S#台aA# 当前输入符a属于FIRST(aA),用S→aA推导 =→acAS# 当前输入符c属于FIRST(cAS),用A→cAS推导 →acS# 当前输入符a属于FOLLOW(A),用A→推导 →acaA# 当前输入符a属于FIRST(aA),用SaA推导 →aca# 当前输入符#属于FOLLOW(A),用A-→推导，成功. 最后，我们将消除回溯的条件归纳为，对G中每个A∈V,A-产生 式中任何两个候选式Y,Y5,均满足： (1)FIRST(yi)OFIRST(Yi)= (ij1≤i,j≤m) (2)Y,Y中，至多有一个能推导出； (3)若y→*ε，则FIRST(ym⌒FOLLOW(A)=☑(i=1,2,.,mij) 。 注：条件(2)可省略.即(1)→(2) 我们把满足上述条件的文法称为LL(1)文法

消除回溯的条件 • 例 S→aA | b A→cAS |  FIRST(cAS)={c} FOLLOW(A) =FIRST(S){#}={a,b,#} 两个集合不相交, 故可进行无回溯的 分析.设输入串w=aca#,其推导过程如下: S#aA# 当前输入符a属于FIRST(aA),用S→aA推导 acAS# 当前输入符c属于FIRST(cAS),用A→cAS推导 acS# 当前输入符a属于FOLLOW(A),用A→推导. acaA# 当前输入符a属于FIRST(aA),用S→aA推导 aca# 当前输入符#属于FOLLOW(A),用A→推导,成功。 • 最后,我们将消除回溯的条件归纳为,对G中每个AVT,A-产生 式中任何两个候选式i,j,均满足: (1)FIRST(i) FIRST(j)=  (ij 1i,jm) (2) i,j中,至多有一个能推导出; (3)若j*,则FIRST(i)FOLLOW(A)= (i=1,2,…,m ij) • 注: 条件(2)可省略. 即(1) (2) • 我们把满足上述条件的文法称为LL(1)文法