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

消除文法左递归的例子 例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)=