byyl-ch4自顶向下语法分析方法

自动机、正则文法、正则表达式

的相互转化正则文法NFA正则表达式123456DFA最小化复习第五章语法分析5.1自顶向下分析法5.1.1自顶向下分析的思想5.1.2左递归和回溯性质5.1.3递归子程序法（递归下降分析法）5.1.4LL(1)分析法编译程序的功能和组织结构表处理词法分析源程序目标程序错误处理语法分析语义分析目标代码生成前端后端中间代码优化中间代码生成44

功能：根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。

基本任务：识别符号串S是否为某语法成分两大类分析方法：自顶向下分析自底向上分析语法分析概述5若ZS则SL(G[Z])否则SL(G[Z])+G[Z]存在主要问题:

左递归问题回溯问题

主要方法:

递归子程序法

LL分析法自顶向下分析算法的基本思想为：若ZS则SL(G[Z])否则SL(G[Z])+G[Z]自底向上分析算法的基本思想为：存在主要问题:

句柄的识别问题主要方法:

算法优先分析法

LR分析法自顶向下分析665.1.1自顶向下分析的思想5.1.2自顶向下分析存在的问题及解决方法5.1.3递归子程序法（递归下降分析法）5.1.4LL(1)分析法5.1.1自顶向下分析的思想77我们可以通过一例子来说明语法分析过程给定符号串S，若预测是某一语法成分，那么可根据该语法成分的文法,设法为S构造一棵语法树.若成功,则S最终被识别为某一语法成分,即

SL(G[Z])其中G[Z]为某语言成分的文法.若不成功,则SL(G[Z])88例：已知符号串S=cad

文法G[Z]:Z→cAdA→ab|a求解SL(G[Z])分析过程是设法建立一棵语法树,使语法树的末端结点与给定符号串相匹配.1.开始:令Z为根结点Z2.用Z的右部,符号串去匹配输入串

·ZcAd完成一步推导ZcAd

检查c-c匹配

A是非终结符,将匹配任务交给A993.选用A的右部符号串匹配输入串

A有两个右部,选第一个

·cAdabZ完成进一步推导Aab

检查,a-a匹配,b-d不匹配(失败)但是还不能冒然宣布SL(G[Z])4.回溯即砍掉A的子树改选A的第二右部·ZcAdaAa检查a-a匹配

d-d匹配建立语法树,末端结点为cad与输入cad相匹配,建立了推导序列ZcAdcad∴cadL(G(Z))S=cadG[Z]:Z→cAdA→ab|a分析工作要部分地或全部地退回去重做叫回溯自顶向下分析方法特点1.分析过程是带有预测的，对输入符号串要预测属于什么语法成分，然后根据该语法成分的文法建立语法树。2.分析过程是一种试探过程，是尽一切办法(选用不同规则)

设法建立语法树的过程，由于是试探过程，故难免有失败，所以分析过程需进行回溯，因此我们也称这种方法是带回溯的自顶向下分析方法。5.1.2自顶向下分析存在的问题及解决方法自顶向下分析方法的基本缺点：不能处理具有左递归性的文法自顶向下分析为什么不能处理左递归文法？文法G，存在U∈Vn，ifU==>U…,则G为左递归文法+1．左递归文法：左递归文法回溯问题1212在采用最左推导的自顶向下分析中，左递归的存在是十分有害的，例如，考虑文法G[S]：SSa|b，分析输入串baaa是否为文法的合法句子。按照自顶向下分析法，对输入串baaa的当前输入符b从开始符号S开始进行最左推导，若首次使用SSa则可能得到：

SSaSaaSaaaSaaaa如果文法具有间接左递归，则也将发生上述问题，只不过环的圈子兜的更大。要实行自顶向下分析，必须要消除文法的左递归，下面我们将介绍直接左递归的消除方法，在此基础上再介绍一般左递归的消除方法。自顶向下分析为什么不能处理左递归文法？1313将左递归规则改为右递归规则若：S→SS→则可改写为：S

→S’

S’→S’|ε证明的关键步骤：S

->Sα|βS->β|βα|βαα|βααα|……S->β(ε|α|αα|ααα|……)S->βS’,S’->ε|α|αα|ααα|……S->βS’,S’->ε|αS’①

消除直接左递归:1414文法E->E+T|TT->T*F|FF->(E)|i例2已知G[E]：

E->T*F|T/F|F

T->F|T*F|T/F

解：左递归改为右递归得：

E->T*F|T/F|F

T->FT’T’->*FT’|/FT’|ε消除左递归后：E->TE’,E’->+TE’|εT->FT’,T’->*FT’|εF->(E)|i1515②消除一般左递归基本思想先用代入法把间接左递归变成直接左递归，再消除直接左递归，最后去掉多余规则以化简文法。算法说明要求文法不能含有回路(即形如P+

P的推导)，并且不含作为规则的右部。1616算法描述消除所有左递归的算法1.把G的非终结符整理成某种顺序A1，A2，……An

，使得：

A1::=δ1|δ2|……δkA2::=A1r……A3::=A2u|

A1v…..…….2.Fori:=1tondobeginforj:=1toi-1do

把每个形如Ai→Ajr的规则替换成

Ai→(δ1|δ2|……δk)r

其中Aj→δ1|δ2|……δk是当前全部Aj

的规则消除Ai规则中的直接左递归

end3.化简由2得到的文法即可。间接左递归直接左递归消除直接左递归一般左递归也可以通过改写法予以消除。1717例：文法G[s]为

S→Qc|cQ→Rb|bR→Sa|a非终结符顺序重新排列R→Sa|aQ→Rb|bS→Qc|c该文法是无直接左递归，但有间接左递归

SQcRbcSabc∴SSabc+1.检查规则R是否存在直接左递归R→Sa|a2.把R代入Q的有关选择，改写规则QQ→Sab|ab|b3.检查Q是否直接左递归4.把Q代入S的右部选择S→Sabc|abc|bc|c5.消除S的直接左递归S→(abc|bc|c)S’S’→abcS’|ε最后得到文法为:S→(abc|bc|c)S’S’→abcS’|εQ→Sab|ab|bR→Sa|a1818最后得到的文法:S→(abc|bc|c)S’S’→abcS’|εQ→Sab|ab|bR→Sa|a可以看出其中关于Q和R的规则是多余的规则∴经过压缩后S→(abc|bc|c)S’S’→abcS’|ε可以证明改写前后的文法是等价的应该指出,由于对非终结符的排序不同,最后得到的文法在形式上可能是不一样的,但是不难证明它们的等价.2．回溯问题1919什么是回溯?分析工作要部分地或全部地退回去重做叫回溯造成回溯的条件：

文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。回溯带来的问题：严重的效率低，只有在理论上的意义而无实际意义U::=

1|

2|

3

2020效率低的原因1)语法分析要重做2)语法处理工作要推倒重来为避免回溯，对文法的要求是FIRST(αi)∩FIRST(αj)=φ(ij)非终结符的候选式的首符集两两不相交[定义]

设文法G（不具左递归性）

FIRST(α)={a|α

aβ，aVt，α,βV*}

若α

ε，则规定εFIRST(α)

符号串α的所有可能推导出的开头终结符或ε**2121例子设有文法G[S]:S->Aa|BbA->d|cAB->b|aB对S:FIRST(Aa)={d,c},FIRST(Bb)={a,b},FIRST(Aa)∩FIRST(Bb)=φ对A:FIRST(d)={d},FIRST(cA)={c},FIRST(d)∩FIRST(cA)=φ对B:FIRST(b)={b},FIRST(aB)={a},FIRST(b)∩FIRST(aB)=φ若给定w=abb则自顶而下分析对应的推导为:S=>Bb=>aBb=>abb2222消除回溯的途径：改写文法对具有多个右部的规则反复提取左因子例U→xV|xWU,V,W∈Vn,x∈Vt改写为U→x(V|W)更清楚表示

U→xZZ→V|W注意：问题到此并没有结束，还需要进一步检查V和W的首符号是否相交若V∷=ab|cdFIRST(V)={a,c}W∷=de|fgFIRST(W)={d,f}只要不相交就可以根据输入符号确定目标，若相交，则要代入，并再次提取左因子。如：V::=abw::=ac

则：Z::=a(b|c)5.1.3递归子程序法（递归下降分析法）递归下降分析法也称递归子程序法，是一种直观易于构造的自顶向下分析方法。分析过程则通过自上而下一级一级地调用子程序来实现，所以称为递归下降分析法。思想对文法中的每个非终结符编写一个处理子程序，处理子程序的代码结构由相应的非终结符的规则右部来决定：规则右部的终结符号与输入符号相匹配，非终结符与相应的子程序调用相对应，非终结符对应的各个候选式与分支结构相对应。限制：对文法要求高，必须满足LL(1)文法；由于递归调用多，速度慢，占用空间多。尽管这样,它还是许多高级语言的编译系统经常采用的语法分析方法。扩展的巴科斯范式(EBNF)EBNF是在BNF基础上扩展如下三组符号：“{}”：表示花括号内的语法成分可以重复；“[]”：表示方括号内的成分是可选项；“()”：表示括号内的成分优先。用EBNF改写文法对于非终结符A的一组形如Ax|y||z|Aa的规则，可表示成A(x|y||z){a}。例如，对于规则EE+T|T，可以写成ET{+T}。例设有文法G[E]：

EE+T|E-T|TTT*F|T/F|FFPF|PP(E)|i用EBNF表示消除左递归得到文法G[E]：

ET{(+|-)T}TF{(*|/)F}

FP{P}P(E)|i

T->FT’

T’->*FT’|/FT’|ε递归子程序E的递归子程序E(){T();while(w==“+”||w==“-”){get_w();T();}}T的递归子程序T(){F();while(w==“*”||w==“/”){get_w();F();}}F的递归子程序F(){P();while(w==“”){get_w();P();}}P的递归子程序P(){if(w==“(”){get_w();E();if(w==“)”)get_w();elseerror();}elseif(w==“i”)get_w();elseerror();}另一个例子对于文法G[E]：

EE+T|TTT*F|FF(E)|i经消除左递归后得到G[E]：

ETEE+TE|TFTT*FT|F(E)|iE的递归子程序E(){T();E();}E的递归子程序E(){if(w==“+”){get_w();T();E();}}T的递归子程序T(){F();T();}T的递归子程序T(){if(w==“*”){get_w();F();T();}}F的递归子程序F(){if(w==“(”){get_w();E();if(w==“)”)get_w();elseerror();}elseif(w==“i”)get_w();elseerror();}5.1.4LL(1)分析法3636LL－自左向右扫描输入串。分析过程表现为最左推导的性质。每步推导只需向前查看一个符号。一种自顶向下分析方法通常把按LL(1)方法完成语法分析任务的程序叫LL(1)分析程序或者LL(1)分析器。此过程有三部分组成:分析表执行程序(总控程序）符号栈（分析栈）#执行程序分析表#符号栈输入串在实际语言中，每一种语法成分都有确定的左右界符，为了研究问题方便，统一以‘＃’表示。1、LL分析程序构造及分析过程3737M[A,a]=A→αi

表示当要用A去匹配输入串时，且当前输入符号为a时，可用A的第i个选择去匹配。即当αi≠ε时，有αia…;

当αi＝ε时，则a为A的后继符号。*M[A,a]=error

表示当用A去匹配输入串时，若当前输入符号为a，则不能匹配，表示无Aa…,或a不是A的后继符号.*（1）分析表：二维矩阵MA→αiαi∈V*M[A,a]=或A∈Vnerrora∈Vtor#（2）符号栈:用于存放分析过程中的文法符号。分析栈初始化时，在栈底压入一个”#”，然后再压入文法开始符号。（2）符号栈:有四种情况#E符号栈

开始状态E#xxxxxx#

工作状态#…..X符号栈X….#a……#查分析表得：X∈Vn,M[X,a]=X∷=αiX

a…X∈Vt,X=a+XX::=iaXerrora

出错状态#…..X符号栈X….#a……#查分析表得：X∈Vn,M[X,a]=error

无X

a…X∈Vt,Xa+

结束状态#符号栈##4141执行程序主要实现如下操作:1.分析开始时候进行有关的初始化工作。把#和文法识别符号E推进栈,并读入输入串的第一个符a,重复下述过程直到正常结束或出错.2.设分析到的某一步，分析栈当前的栈顶符号X和当前输入符号a,执行如下操作:若X∈VT:(1)若X=a=#，分析成功，停止。E匹配输入串成功.(2)若X=a≠#，则从栈顶弹出X，输入串的分析指针指向下一个输入符号。(3)若X≠a，则表示发现错误，调相应的出错处理程序（3）执行程序:据分析表和分析栈控制对输入符号串的分析和识别#…..X符号栈X….#a……#4242

若X∈Vn，查分析表M，根据M[X,a]的内容决定：

a)

若M[X,a]中为一个规则，则将X弹出栈，并将此规则右部的符号序列按倒序压入分析栈。

注：U在栈顶（最左推导）

b)若M[X,a]为空，则表示出错，调出相应的出错处理程序。

3、反复执行2）。4343分析表注：矩阵元素空白表示Error例：文法G[E] E::=E+T|T T::=T*F|F F::=(E)|i请用自顶向下的方法分析是否字符串i+i*i∈L(G[E])。E::=TE’E’::=+TE’|εT::=FT’T’::=*FT’|εF::=(E)|i消除左递归i+*()#EE→TE’E→TE’E’E’→+TE’E’→εE’→εTT→FT’T→FT’T’T’→εT’→*FT’T’→εT’→εFF→iF→(E)4444输入串为:i+i*i#步骤 符号栈 读入符号 剩余符号串 使用规则1.＃EE# i +i*i# 2.＃E’T TE’# i +i*i# E::=TE’3.＃E’T’FFT’E’#i +i*i# T::=FT’4.＃E’T’iiT’E’# i +i*i# F::=i5.＃E’T’T’E’# + i*i#(出栈，读下一个符号）6.＃E’ E’#

＋ i*i# T::=ε

7.＃E’T++TE’#

＋ i*i# E::=+TE’4545步骤 符号栈 读入符号 剩余符号串 使用规则8. ＃E’T i *i# 9. ＃E’T’F i *i# T::=FT’10. ＃E’T’i i *i# F::=i11. ＃E’T’ * i# 12. ＃E’T’F* * i# T’::=*FT’13. ＃E’T’F i # 14. ＃E’T’i i # F::=i15. ＃E’T’ # 16. ＃E’ # T’::=ε

17. ＃ # E’::=ε

输入串为:i+i*i#4646推导过程：

E

TE'

FT'E'iT'E'iE'

i+TE'i+FT'E'i+iT'E'

i+i*FT'E'i+i*iT'E'

i+i*iE'i+i*i最左推导。E::=TE’E::=+TE’|εT::=FT’T’::=*FT’|εF::=(E)|i2、分析表的构造：LL(1)分析器构造的核心。定义：FIRST(α)={a|α

aβ，aVt，α,βV*}

若α

ε，则规定εFIRST(α)该集合称为α的头符号集合**设有文法G[Z]:4747定义：

A∈VnFOLLOW(A)={a|ZμAβ且a∈Vt,a∈FIRST(β),μ∈Vt*,β∈V+}若ZμAβ,且β

ε，则#FOLLOW(A)该集合称为A的后继符号集合或定义为：FOLLOW(A)={a|Z…Aa…，a∈Vt}A∈Vn,Z识别符号特殊地：若Z...A则#∈FOLLOW(A)*****4848设α=X1X2...Xn,Xi∈VnVt求FIRST(α)=?

首先求出组成α的每一个符号Xi的FIRST集合若Xi∈Vt，则FIRST(Xi)={Xi}(2)若Xi∈Vn且Xi→a…..|ε，a∈Vt

则FIRST(Xi)={a，ε}(Ⅰ)集合FIRST的算法4949(3)若Xi∈Vn且Xi→y1y2…yk，则按如下顺序计算FIRST(Xi)

若FIRST(Xi)

FIRST(y1)–{ε}；若ε∈FIRST(y1)则将FIRST(y2)-{ε}加入FIRST(Xi)；若ε∈FIRST(y1)ε∈FIRST(y2)则将FIRST(y3)-{ε}加入FIRST(Xi)........

若ε∈FIRST(yk-1)则将FIRST(yk)-{ε}加入FIRST(Xi)

若ε∈FIRST(y1)～FIRST(yk)

则将ε加入FIRST(Xi)

注意：要顺序往下做，一旦不满足条件，过程就要中断进行

得到FIRST(Xi)，即可求出FIRST(α)。5050(Ⅱ)构造集合FOLLOW的算法若S为识别符号,则把“#”加入FOLLOW(S)中(2)若A→αBβ(β≠ε),则把FIRST(β)-{ε}加入FOLLOW(B)(3)若A→αB或A→αBβ，且βε则把FOLLOW(A)加入FOLLOW(B)*注：FOLLOW集合中不能有ε设S,A,B∈Vn,算法：连续使用以下规则，直至FOLLOW集合不再扩大5151定义：给定上下文无关文法A→α，A∈Vn，αV*若α

ε，SELECT(A→α)=FIRST(α)若α

ε，SELECT(A→α)=FIRST(α)∪FOLLOW(A)**注：

SELECT集合中不能有ε由定义可见，SELECT(Ax)实际上是指在推导过程中，若采用规则Ax进行推导时，可能推导出的下一个终结符号组成的集合。5252(Ⅲ)构造分析表基本思想是:当文法中某一非终结符呈现在栈顶时,根据当前的输入符号,分析表应指示要用该非终结符里的哪一条规则取匹配输入串(即进行下一步最左推导)

根据这个思想,我们不难把构造分析表算法构造出来!终结符号非终结符号算法：设A→αi为文法中的任意一条规则，a为任一终结符或#。所谓构造分析表M就是定义M的各个元素，若已经对文法中的每一条规则都求出SELECT集，则分析表的构造算法为：1、若a∈SELECT（A→αi），则M[A,a]=A→αi

2、M中不能由1)定义的元素都是空白元素。或者理解为：1、若a∈FIRST（αi

），则A::=αi==>M[A,a]

表示：A在栈顶，输入符号是a，应选择αi

去匹配2、若αi=ε或αi

ε,而且a∈FOLLOW（s），则A::=αi==>M[A,a]，表示A已经匹配输入串成功，其后继符号终结符a由A后面的语法成分去匹配。3、把所有无定义的M[A,a]都标上error5353+5454解：1）求FIRST：FIRST(F)={(，i}FIRST(T’)={*,ε}FIRST(T)=FIRST(F)-{ε}={(，i}FIRST(E’)={+,ε}FIRST(E)=FIRST(T)-{ε}={(，i}∴FIRST(TE’)=FIRST(T)-{ε}={(，i}FIRST(+TE’)={+}FIRST(ε)={ε}FIRST(FT’)=FIRST(F)-{ε}={(，i}FIRST(（E）)={(}FIRST(i)={i}例：G[E]分析表的构造

E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i构造过程：1）求FIRST：2）求FOLLOW3）构造分析表5555E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iFOLLOW(E)={#,)}∵因为E是识别符号∴#∈FOLLOW(E)

又F→(E)∴)∈FOLLOW(E)FOLLOW(E’)={#,)}

∵E→TE’∴FOLLOW(E)加入FOLLOW(E’)FOLLOW(T)={+,),#}

∵E’→+TE’∴FIRST(E’)-{ε}加入FOLLOW(T)

又E’ε，∴FOLLOW(E’)加入FOLLOW(T)FOLLOW(T’)=FOLLOW(T)={+,),#}

∵T→FT’∴FOLLOW(T)加入FOLLOW(T’)FOLLOW(F)={*,+,),#}

∵T→FT’∴FOLLOW(F)=FIRST（T’）-{ε}*又T’ε∴FOLLOW(T)加入FOLLOW(F)2）求FOLLOWFIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)={(,i}FIRST(E’)={+,ε}FIRST(E)={(,i}5656E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i求SELECTFIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)={(,i}FIRST(E’)={+,ε}FIRST(E)={(,i}SELECT(E→TE’)={(,i}SELECT(E’→+TE’)={+}SELECT(E’→ε)={),#}

SELECT(T→FT’)={(,i}SELECT(T*FT)={*}SELECT(T’→ε)={+,),#}SELECT(F→(E)={(}SELECT(F→i)={i}FOLLOW(F)={*,+,),#}FOLLOW(T’)={+,),#}FOLLOW(T)={+,),#}FOLLOW(E’)={#,)}FOLLOW(E)={#,)}5757E’→εT’→εi+*()#EE’TT’FE→TE’E→TE’E’→+TE’E’→εT→FT’T→FT’T’→εT’→*FT’T’→εF→iF→(E)注意:用上述算法可以构造出任意给定文法的分析表,但不是所有文法都能构造出上述那种形状的分析表即M[A,a]=一条的规则或Error。对于能用上述算法构造分析表的文法我们称为LL(1)文法3）构造分析表FIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)=={(,i}FIRST(E’)={+,ε}FIRST(E)=={(,i}E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iFOLLOW(E)={#,)}FOLLOW(E’)={#,)}FOLLOW(T)={+,),#}FOLLOW(T’)={+,),#}FOLLOW(F)={*,+,),#}58582、若β==>ε,则FIRST(α)∩FOLLOW(A)=Ф*3、LL(1)文法定义：一个文法G，其分析表M不含多重定义入口(即分析表中无二条以上规则)，则称它是一个LL(1)文法.定理：文法G是LL(1)文法的充分必要条件是：对于G的每一个非终结符A的任意两条规则A::=α|β,下列条件成立：1、FIRST(α)∩FIRST(β)=ФSELECT(A→α)∩SELECT(A→β)=Ф或LL(1)文法及LL(1)语言的性质任何LL(1)文法都是无二义性的；若一文法中的非终结符含有左递归，则它必然是非LL(1)文法；非LL(1)语言是存在的；存在一种算法，它能判定任一文法是否为LL(1)文法；不存在这样的算法，它能判定上下文无关语言能否由LL(1)文法产生。6060解：1）求FIRST：FIRST(F)={(，i}FIRST(T’)={*,ε}FIRST(T)=FIRST(F)-{ε}={(，i}FIRST(E’)={+,ε}FIRST(E)=FIRST(T)-{ε}={(，i}∴FIRST(TE’)=FIRST(T)-{ε}={(，i}FIRST(+TE’)={+}FIRST(ε)={ε}FIRST(FT’)=FIRST(F)-{ε}={(，i}FIRST(（E）)={(}FIRST(i)={i}例：G[E]:E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i构造过程：1）求FIRST：6161E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iFOLLOW(E)={#,)}∵因为E是识别符号∴#∈FOLLOW(E)

又F→(E)∴)∈FOLLOW(E)FOLLOW(E’)={#,)}

∵E→TE’∴FOL