8.第四章自顶向下的语法分析(1)

2020/5/3,1,第4章自顶向下的语法分析（1）,语法分析(SyntaxAnalysis)文法的改造问题自顶向下(TopDown)的分析推导(Derivation),2020/5/3,2,4.1语法分析的任务,语法分析(SyntaxAnalysis)检查扫描器输出的单词序列是否符合该语言的文法(句子)，并分析组成此句子的语法成分完成语法分析的程序叫做(语法)分析器ParserSyntaxAnalyzer,2020/5/3,3,4.1语法分析的任务,扫描器,分析器,语义处理,单词符号,语法树,源程序,输入：Token序列输出语法成分及组成表现形式：语法树错误报告出错处理:定位、续编译,2020/5/3,4,语法分析方法,文法产生语言,自动机识别语言,2020/5/3,5,4.2自顶向下分析面临的问题与CFG的改造,一、自顶向下的分析从文法的开始符号出发，寻求所给的输入符号串的最左推导从树根S开始，构造所给输入符号串的语法树例：G为：SxAyA*|*，输入串：x*y,SxAy,x*y,S,2020/5/3,6,二、重要概念回顾,推导:(依据:)最左(Left-most)推导最左分析左句型最左推导对应最右归约,EE+Ea1+Ea1+E*Ea1+a2*Ea1+a2*a3,EE+EE+E*EE+E*a3E+a2*a3a1+a2*a3,最右(Right-most)推导最右分析规范推导、规范句型(右句型)最右推导对应最左归约(规范归约),二义性(先天二义性语言、二义性文法),2020/5/3,7,三、重要问题虚假匹配,x*y发现不匹配,需要回退(回溯),S,S,S,输入串x*ySxAyA*|*,S,xAy,x*y匹配成功,xAy,2020/5/3,8,三、重要问题回溯,S,x*y,SxAy,x*y,发现不匹配,需要回退,xAy,x*y,S,S,x*y匹配成功,2020/5/3,9,三、重要问题二义性及其消除,EE+E|E-E|E*E|E/E|(E)|id对同一句子存在两棵语法分析树，哪个是对的？,2020/5/3,10,三、重要问题二义性及其消除,二义性文法EE+E|E-E|E*E|E/E|(E)|id非二义性文法EE+T|E-T|TTT*F|T/F|FF(E)|id改造方法：引入语法变量，使文法含有更多的信息,2020/5/3,11,三、重要问题二义性及其消除,再例：If语句SifEthenSSifEthenSelseSSother设执行下列语句前b=0,Ifa0thenifa0thenb=1elseb=-1当a=1时,b=1;当a=-1时，执行后b=-1Ifa0thenifa0thenb=1elseb=-1当a=1时,b=1;当a=-1时，执行后b=0,一个句子有两棵不同的语法树,SSEESSIfa0thenifa0thenb=1elseb=-1SSEESSIfa0thenifa0thenb=1elseb=-1,2020/5/3,13,三、重要问题二义性及其消除,1.重写文法SU|MUifEthenSUifEthenMelseUMifEthenMelseM|other2.设置一个规则实现“就近”、“最长”匹配原则,改造1,改造2,STS|CSCifEthenTCSelse,CCondition,TElse,每个else与前面最近的没有配对的then配对，即出现在then和else之间的语句必须是配对的,按照“改造1”构造的语法树,SUSMEEMMIfa0thenifa0thenb=1elseb=-1,MifEthenMelseM|other,按照“改造2”构造的语法树,SST(最长)CCEESSIfa0thenifa0thenb=1elseb=-1,STS|CSCifEthenTCSelse,按照“改造2”构造的语法树,STS(非最长)CCEESSIfa0thenifa0thenb=1elseb=-1,STS|CSCifEthenTCSelse,三、重要问题二义性及其消除,SSST(最长)T(最长)SCCCCifEthenifEthenSelseifEthenSelseifEthenS,STS|CSCifEthenTCSelse,2020/5/3,18,三、重要问题左递归及其消除,例：文法SSay|*与它的句子*ayay,*ayay,S*不对！,SSaySayaySayayaySayayayay,一个无限循环！,2020/5/3,19,三、重要问题左递归及其消除,例简单算术表达式的文法左递归EE+T|E-T|T|-ETT*F|T/F|FFFP|PP(E)|id|const|FUN(L)FUNabs|sin|cos|ln|log|exp|sqrtLE|E,LVNE,T,F,P,FUN,LVTid,const,+,-,*,/,(,),abs,sin,cos,log,ln,exp,sqrtSE,2020/5/3,20,三、重要问题左递归及其消除,无法根据左递归文法进行自顶向下的分析Aa1a2aian直接左递归AA当前变量输入指针(栈顶、最左变量),间接左递归A+A左递归的消除方法将AA|替换为AA和AA,2020/5/3,21,例：表达式文法直接左递归的消除,EE+TTTT*FFF(E)id,ETEE+TE|TFTT*FTF(E)id,2020/5/3,22,例：间接左递归的消除,SAc|cABb|bBSa|a将B的定义代入A产生式得：ASab|ab|b将A的定义代入S产生式得:SSabc|abc|bc|c消除直接左递归：SabcS|bcS|cSSabcS|删除“多余的”产生式：ASab|ab|b和BSa|a结果：SabcS|bcS|cSSabcS|,2020/5/3,23,消除左递归的一般方法,对产生式组AA1|A2|An|1|2|m用如下产生式组替换A1B|2B|mBB1B|2B|nB|其中：B为新变量，相当于A消除左递归的算法见P70的算法为非终结符编号，再采用代入法将间接左递归变为直接左递归，消除直接左递归,2020/5/3,24,三、重要问题提取左因子,例：if语句的原始文法SifEthenS|ifEthenSelseS|other遇到if时难以判断用哪一个产生式进行匹配（推导）存在左因子ifEthenS提取左因子SifEthenSS|otherS|elseS,2020/5/3,25,三、重要问题提取左因子,将形如A1|2|m|1|2|p的规则改写为AA|1|2|p和A1|2|m结果：SifEthenSS|otherS|elseS,STS|CS|otherCifEthenTCSelse,2020/5/3,26,四、CFG的使用限制,没有一种方法能够有效地分析所有上下文无关文法存在无法处理的型文法(CFG)每种方法能够处理一部分上下文无关文法每种方法都有适用范围,2020/5/3,27,五、常用文法与分析方法,LL文法和LR文法都是CFG的子集(无二义性)可用不同的文法来描述同一语言对于不同的文法，可用不同的分析方法LL文法递归下降分析法、预测分析法多用于编译的手工实现LR文法LR分析法多用于编译的自动生成,2020/5/3,28,4.3自顶向下的分析方法,基本思想寻找输入符号串的最左推导试图根据当前输入单词确定使用哪个产生式基本过程从S出发，构造输入符号串(Token)的最左派生从根开始，按与最左推导相对应的顺序，构造输入符号串(Token)的语法分析树,2020/5/3,29,例符号串id+id*id的分析,ETEE+TETFTT*FTF(E)id,EE+TTTT*FFF(E)id,按照最左推导过程，构造语法树,id+id*id的最左推导与语法树的生成,id,id,id,1、ETE,2、TFT,3、Fid,4、T,5、E+TE,6、TFT,7、Fid,8、T*FT,9、Fid,10、T,11、E,ETEE+TETFTT*FTF(E)id,id+id*id的最左推导再现,ETEETEFTETFTidTEFididETid+TEE+TEid+FTETFTid+idTEFidid+id*FTET*FTid+id*idTEFidid+id*idETid+id*idE,ETEE+TETFTT*FTF(E)id,2020/5/3,32,候选式的确定与回溯(Backtracking),给定文法ScAdAab|e?句子cad是该文法定义语言的句子,出现一次虚假的匹配，并且立即发现cad不是合法句子,2020/5/3,33,候选式的确定与回溯(Backtracking),给定文法ScAdAab|e?句子ced是该文法定义语言的句子,当需要用A派生时，可以根据输入符号e唯一的确定A的候选式,2020/5/3,34,候选式的确定与回溯(Backtracking),给定文法ScAdAab|a?句子cad是该文法定义语言的句子,当需要用A派生时，无法根据输入符号a唯一的确定A的候选式,2020/5/3,35,候选式的确定与回溯(Backtracking),给定文法ScABdAab|Ba?句子cad是该文法定义语言的句子,当需要用A派生时，因为A使得无法根据输入符号a唯一的确定A的候选式,2020/5/3,36,候选式的确定与回溯(Backtracking),给定文法ScABdAba|Ba?句子cad是该文法定义语言的句子,当需要用A派生时,虽然有A,仍然可以根据输入符号a唯一的确定A的候选式,2020/5/3,37,候选式的确定与回溯(Backtracking),句子cad是该文法定义语言的句子？对给定文法ScAdAab|a，分析需要回溯对给定文法ScABdAab|Ba，分析需要回溯对给定文法ScABdAba|Ba，分析不需要回溯原因何在？,2020/5/3,38,候选式的确定与回溯(Backtracking),当要进行某个语法变量的推导时，希望能够根据当前符号确定候选式。如果有几个候选式（右部）左端第一个符号相同，则分析程序无法根据当前输入符号选择产生式，只能试探希望：寻找一类文法，我们可以方便地根据当前输入符合确定正确的候选式,2020/5/3,39,4.3.1FIRST和FOLLOW集,对于(VTVN)*定义:的首符号集FIRST()=a|*a，aVT*对于AVN定义A的后续符号集：FOLLOW(A)=a|S*Aa，aVT,2020/5/3,40,求FIRST(X)的算法,1)对xVT，FIRST(x)=x；2)对XVN，取FIRST(X)的初值：a|XaP；XPFIRST(X)=a|XaP；XP,3)对XVN，重复如下过程，直到所有FIRST集不变若XYP，且YVN，则FIRST(X)=FIRST(X)(FIRST(Y)-)；若XY1YnP，且Y1.Yi-1*，则对k=1到i-1:FIRST(X)=FIRST(X)(FIRST(Yk)-)；若Y1.Yn*，则FIRST(X)=FIRST(X),2020/5/3,42,例表达式文法的语法符号的FIRST集,FIRST(F)=(,idFIRST(T)=FIRST(F)=(,idFIRST(E)=FIRST(T)=(,idFIRST(E)=+，FIRST(T)=*,FIRST(+)=+,FIRST(*)=*FIRST()=(FIRST()=)FIRST(id)=id,ETEE+TE|TFTT*FT|F(E)|id,2020/5/3,43,求FIRST()的算法,令=X1Xn初值FIRST()=FIRST(X1)-;k=1;循环whileFIRST(Xk)结束处理ifk=n&FIRST(Xn)thenFIRST()=FIRST(),2020/5/3,44,求FOLLOW(A)的算法,令#为句子的结束符，对于所有非终结符,重复进行以下计算1)将#加入到FOLLOW(S)2)若AB，则FOLLOW(B)=FOLLOW(B)(FIRST()3)如果AB或AB，且*，AB，则FOLLOW(B)=FOLLOW(B)FOLLOW(A),2020/5/3,45,例表达式文法的语法变量的FOLLOW集,FOLLOW(E)=#,),ETEE+TE|TFTT*FT|F(E)|id,FIRST(F)=（,idFIRST(T)