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

《8.第四章自顶向下的语法分析(1).ppt》由会员分享，可在线阅读，更多相关《8.第四章自顶向下的语法分析(1).ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4章章 自顶向下的语法分析自顶向下的语法分析（1）语法分析语法分析(Syntax Analysis)文法的改造问题文法的改造问题自顶向下自顶向下(Top Down)的分析的分析推导推导(Derivation)2022/12/2914.1 语法分析的任务语法分析的任务n语法分析语法分析(Syntax Analysis)n检查扫描器输出的单词序列是否符合该语检查扫描器输出的单词序列是否符合该语言的文法言的文法(句子句子)，并分析组成此句子的语法，并分析组成此句子的语法成分成分n完成语法分析的程序叫做完成语法分析的程序叫做(语法语法)分析器分析器nParsernSyntax Analyzer20

2、22/12/2924.1 语法分析的任务语法分析的任务扫描器扫描器分析器分析器语义处理语义处理单词符号单词符号语法树语法树源程序源程序n输入：输入：TokenToken序列序列n输出输出uu语法成分及组成语法成分及组成uu表现形式：语法树表现形式：语法树uu错误报告错误报告n出错处理出错处理:定位、续编译定位、续编译2022/12/293语法分析方法语法分析方法 递归子程序法递归子程序法n自顶向下自顶向下 预测分析法预测分析法(LL(1)Top DownTop DownTop DownTop Down 算符优先分析法算符优先分析法n自底向上自底向上 LR(0)、SLR(1)LR(1)、LALR

3、Bottom UpBottom UpBottom UpBottom Up文法产生语言文法产生语言自动机识别语言自动机识别语言2022/12/2944.2 自顶向下分析面临的问题与自顶向下分析面临的问题与CFG的改造的改造n一、自顶向下的分析一、自顶向下的分析n从文法的开始符号出发，寻求所给的输入符从文法的开始符号出发，寻求所给的输入符号串的最左推导号串的最左推导n从树根从树根S开始，构造所给输入符号串的语法树开始，构造所给输入符号串的语法树n例：例：G为：为：SxAy A*|*，输入串：，输入串：x*yS S S SxAy x*yS S S Sx x x xA A A Ay y y y*202

4、2/12/295二、重要概念回顾二、重要概念回顾n推导推导:(依据依据:)n最左最左(Left-most)推导推导最左分析最左分析n左句型左句型n最左推导对应最右归约最左推导对应最右归约 EE+E a1+Ea1+E*Ea1+a2*Ea1+a2*a3 EE+EE+E*E E+E*a3E+a2*a3a1+a2*a3n最右最右(Right-most)推导推导最右分析最右分析n规范推导、规范句型规范推导、规范句型(右句型右句型)n最右推导对应最左归约最右推导对应最左归约(规范归约规范归约)n二义性二义性(先天二义性语言、二义性文法先天二义性语言、二义性文法)2022/12/296三、重要问题三、重要问

5、题虚假匹配虚假匹配x*y发现不匹配发现不匹配,需需要回退要回退(回溯回溯)S S S Sx x x xA A A Ay y y y*S S S Sx x x xA A A Ay y y y*S S S S 输入串输入串输入串输入串x*yx*yx*yx*ySxAySxAy A*|*A*|*S SxAyx*yx*y匹配成功匹配成功匹配成功匹配成功xAyxAy2022/12/297三、重要问题三、重要问题回溯回溯S x*yx*yx*yx*yS S S S xAyxAyx*yx*yx*yx*y发现不匹配发现不匹配发现不匹配发现不匹配,需要回退需要回退需要回退需要回退xAyx*yS S S Sx x x

6、 xA A A Ay y y y*S S S Sx x x xA A A Ay y y y*x*yx*y匹配成功匹配成功匹配成功匹配成功2022/12/298三、重要问题三、重要问题二义性二义性及其消除及其消除nEE+E|E-E|E*E|E/E|(E)|id对对同同一一句句子子存存在两棵语法分析树，哪个是对的？在两棵语法分析树，哪个是对的？E E E EE E E E*E E E EididididE E E EE E E E+ididididididididE E E EE E E E+E E E EE E E EE E E Eidididid*idididididididid2022/12

7、/299三、重要问题三、重要问题二义性及其消除二义性及其消除二义性文法二义性文法nEE+E|E-E|E*E|E/E|(E)|id非二义性文法非二义性文法nEE+T|E-T|TnTT*F|T/F|FnF(E)|id改造方法：引入语法变量，使文法含有更多的信息改造方法：引入语法变量，使文法含有更多的信息2022/12/2910三、重要问题三、重要问题二义性及其消除二义性及其消除再例：再例：If语句语句Sif E then SSif E then S else SSother设执行下列语句前设执行下列语句前b=0,If a0 then if a0 then b=1 else b=-1当当a=1时时,

8、b=1;当当a=-1时，执行后时，执行后b=-1If a0 then if a0 then b=1 else b=-1当当a=1时时,b=1;当当a=-1时，执行后时，执行后b=02022/12/2911一个句子有两棵不同的语法树一个句子有两棵不同的语法树SSE ES SIf a0 then if a0 then b=1 else b=-1SSE ES SIf a0 then if a0 then b=1 else b=-12022/12/2912三、重要问题三、重要问题二义性及其消除二义性及其消除n1.重写文法重写文法SU|MUif E then SUif E then M else UMi

9、f E then M else M|other2.设置一个规则设置一个规则实现实现“就近就近”、“最长最长”匹配原则匹配原则改造改造改造改造1 1 1 1改造改造改造改造2 2 2 2STS|CSSTS|CSCifCif E then E thenT CS elseCS elseC C C CConditionConditionConditionConditionT T T TElseElseElseElse每个每个elseelse与前面最近的没有配对的与前面最近的没有配对的thenthen配对，配对，即出现在即出现在thenthen和和elseelse之间的语句必须是配对的之间的语句必须是配

10、对的2022/12/2913按照按照“改造改造1”构造的语法树构造的语法树SUSMEEMMIf a0 then if a0 then b=1 else b=-1MifMif E then M else E then M else M|otherM|other2022/12/2914按照按照“改造改造2”构造的语法树构造的语法树SST(最长最长)CCEESSIf a0 then if a0 then b=1 else b=-1STS|CSSTS|CSCifCif E then E thenT CS elseCS else2022/12/2915按照按照“改造改造2”构造的语法树构造的语法树STS

11、(非最长非最长)CCEE SSIf a0 then if a0 then b=1 else b=-1STS|CSSTS|CSCifCif E then E thenT CS elseCS else2022/12/2916三、重要问题三、重要问题二义性及其消除二义性及其消除SS S T(最长最长)T(最长最长)SCC C Cif E then if E then S else if E then S else if E then SSTS|CSSTS|CSCifCif E then E thenT CS elseCS else2022/12/2917三、重要问题三、重要问题左递归及其消除左递归及

12、其消除n例：文法例：文法SSay|*与它的句子与它的句子*ayay*ayayayayS S*不对不对！S SSaySayaySayayaySayayayay一个无限一个无限循环！循环！2022/12/2918三、重要问题三、重要问题左递归及其消除左递归及其消除n例例 简单算术表达式的文法简单算术表达式的文法左递归左递归nEE+T|E-T|T|-EnTT*F|T/F|FnFFP|PnP(E)|id|const|FUN(L)nFUN abs|sin|cos|ln|log|exp|sqrtnLE|E,LnVNE,T,F,P,FUN,LnVTid,const,+,-,*,/,(,),abs,sin,c

13、os,log,ln,exp,sqrtnSE2022/12/2919三、重要问题三、重要问题左递归及其消除左递归及其消除n无法根据左递归文法进行自顶向下的分析无法根据左递归文法进行自顶向下的分析A a1a2aiann直接左递归直接左递归nA A 当前变量当前变量 输入指针输入指针(栈顶、最左变量栈顶、最左变量)n n间接左递归间接左递归间接左递归间接左递归uuA A+AAn n左递归的消除方法左递归的消除方法左递归的消除方法左递归的消除方法uu将将将将AA|AA|AA|AA|替换为替换为替换为替换为AAAAAAAA 和和和和 A A A A AAAA 2022/12/2920例：例：表达式文法直

14、接左递归的消除表达式文法直接左递归的消除E E+TTT T*FFF (E)idE T EE T EE E+T +T E E|T F TT F TT T*F T*F TF(E)F(E)idid2022/12/2921例：例：间接左递归的消除间接左递归的消除SAc|c ABb|b BSa|a将将B的定义代入的定义代入A产生式得：产生式得：ASab|ab|b将将A的定义代入的定义代入S产生式得产生式得:SSabc|abc|bc|c消除直接左递归：消除直接左递归：SabcS|bcS|cSSabcS|删除删除“多余的多余的”产生式：产生式：ASab|ab|b和和BSa|a 结果：结果：SabcS|bcS

15、|cSSabcS|2022/12/2922消除左递归的一般方法消除左递归的一般方法n对产生式组对产生式组nAA1|A2|An|1|2|m n用如下产生式组替换用如下产生式组替换nA1 B|2 B|m BnB1 B|2 B|n B|n其中：其中：B为新变量，相当于为新变量，相当于An消除左递归的算法见消除左递归的算法见P70的算法的算法n为非终结符编号，再采用代入法将间接左递归变为非终结符编号，再采用代入法将间接左递归变为直接左递归，消除直接左递归为直接左递归，消除直接左递归2022/12/2923三、重要问题三、重要问题提取左因子提取左因子n例：例：if语句的原始文法语句的原始文法nS if

16、E then S n|if E then S else S n|othern遇到遇到 if 时难以判断用哪一个产生式进行匹配（推导）时难以判断用哪一个产生式进行匹配（推导）n存在左因子存在左因子 if E then Sn提取左因子提取左因子nS if E then SS|othernS|else S2022/12/2924三、重要问题三、重要问题提取左因子提取左因子将形如将形如 A1|2|m|1|2|p的规则改写为的规则改写为AA|1|2|p和和 A1|2|mn结果：结果：nS if E then SS|othernS|else SSTS|CSSTS|CSSTS|CSSTS|CS|otherC

17、ifCifCifCif E then E then E then E thenT T CS elseCS elseCS elseCS else2022/12/2925四、四、CFG的使用限制的使用限制n没有一种方法能够有效地分析所有上下文没有一种方法能够有效地分析所有上下文无关文法无关文法n存在无法处理的型文法存在无法处理的型文法(CFG)n每种方法能够处理一部分上下文无关文法每种方法能够处理一部分上下文无关文法n每种方法都有适用范围每种方法都有适用范围2022/12/2926五、常用文法与分析方法五、常用文法与分析方法nLL文法和文法和 LR 文法都是文法都是CFG的子集的子集(无二义性无二

18、义性)n可用不同的文法来描述同一语言可用不同的文法来描述同一语言n对于不同的文法，可用不同的分析方法对于不同的文法，可用不同的分析方法nLL文法文法 递归下降分析法、预测分析法递归下降分析法、预测分析法n多用于编译的手工实现多用于编译的手工实现nLR文法文法 LR分析法分析法n多用于编译的自动生成多用于编译的自动生成2022/12/29274.3 自顶向下的分析方法自顶向下的分析方法n基本思想基本思想n寻找输入符号串的最左推导寻找输入符号串的最左推导n试图根据当前输入单词确定使用哪个产生式试图根据当前输入单词确定使用哪个产生式n基本过程基本过程n从从S出发，构造输入符号串出发，构造输入符号串(

19、Token)的最左派生的最左派生n从根开始，按与最左推导相对应的顺序，构造从根开始，按与最左推导相对应的顺序，构造输入符号串输入符号串(Token)的语法分析树的语法分析树2022/12/2928例例 符号串符号串 id+id*id的分析的分析E T E E+T E T F T T*F T F (E)idE E+TTT T*FFF (E)id按照最左推导过程，构造语法树按照最左推导过程，构造语法树2022/12/2929id+id*id的最左推导与语法树的生成的最左推导与语法树的生成i di di d1、ETEETE2 2、TFTTFT3 3、FidFid4 4、TT5 5、E+TEE+TE6

20、 6、TFTTFT7 7、FidFid8 8、T*FTT*FT9 9、FidFid1010、TT1111、EEE T E E+T E T F T T*F T F (E)id2022/12/2930id+id*id的最左推导再现的最左推导再现E TEE TE FTET FTidTEF id idET id+TEE+TE id+FTET FT id+idTEF id id+id*FTET*FT id+id*idTEF id id+id*idET id+id*id EE T E E+T E T F T T*F T F (E)id2022/12/2931候选式的确定与回溯候选式的确定与回溯(Backt

21、racking)n给定文法给定文法ScAdAab|e?句子句子cad是该文法定义语言的句子是该文法定义语言的句子cAdSba出现一次虚假的匹配，出现一次虚假的匹配，并且立即发现并且立即发现cad不是不是合法句子合法句子2022/12/2932候选式的确定与回溯候选式的确定与回溯(Backtracking)n给定文法给定文法ScAdAab|e?句子句子ced是该文法定义语言的句子是该文法定义语言的句子ecAdS当需要用当需要用A A派生时，派生时，可以可以根据输入符号根据输入符号e e唯唯一的确定一的确定A A的候选式的候选式2022/12/2933候选式的确定与回溯候选式的确定与回溯(Back

22、tracking)n给定文法给定文法ScAdAab|a?句子句子cad是该文法定义语言的句子是该文法定义语言的句子cAdSbaacAdS当需要用当需要用A A派生派生时，时，无法无法根据输根据输入符号入符号a a唯一的唯一的确定确定A A的候选式的候选式2022/12/2934候选式的确定与回溯候选式的确定与回溯(Backtracking)n给定文法给定文法ScABd Aab|Ba?句子句子cad是该文法定义语言的句子是该文法定义语言的句子bac A BdSc A BdSa当需要用当需要用A A派生派生时，因为时，因为AA使得使得无法无法根据输根据输入符号入符号a a唯一的唯一的确定确定A A

23、的候选式的候选式2022/12/2935候选式的确定与回溯候选式的确定与回溯(Backtracking)n给定文法给定文法ScABd Aba|Ba?句子句子cad是该文法定义语言的句子是该文法定义语言的句子c A BdSa当需要用当需要用A A派生派生时时,虽然有虽然有AA,仍然可以仍然可以根据输根据输入符号入符号a a唯一的唯一的确定确定A A的候选式的候选式2022/12/2936候选式的确定与回溯候选式的确定与回溯(Backtracking)n句子句子cad是该文法定义语言的句子？是该文法定义语言的句子？n对给定文法对给定文法ScAdAab|a，分析需要回溯，分析需要回溯n对给定文法对给

24、定文法ScABd Aab|Ba，分析需要，分析需要回溯回溯n对给定文法对给定文法ScABd Aba|Ba，分析不需，分析不需要回溯要回溯n原因何在？原因何在？2022/12/2937候选式的确定与回溯候选式的确定与回溯(Backtracking)n当要进行某个语法变量的推导时，希望当要进行某个语法变量的推导时，希望能够根据当前符号确定候选式。如果有能够根据当前符号确定候选式。如果有几个候选式（右部）左端第一个符号相几个候选式（右部）左端第一个符号相同，则分析程序无法根据当前输入符号同，则分析程序无法根据当前输入符号选择产生式，只能试探选择产生式，只能试探n希望：寻找一类文法，我们可以方便地希望

25、：寻找一类文法，我们可以方便地根据当前输入符合确定正确的候选式根据当前输入符合确定正确的候选式2022/12/29384.3.1 FIRST 和和 FOLLOW 集集n对于对于 (VTVN)*定义定义:的首符号集的首符号集nFIRST()=a|*a，aVT*n对于对于 AVN定义定义A的后续符号集：的后续符号集：nFOLLOW(A)=a|S*Aa，aVT 2022/12/2939求求FIRST(X)的算法的算法1)对对 xVT，FIRST(x)=x；2)对对 XVN，取，取FIRST(X)的初值：的初值：a|XaP；X PFIRST(X)=a|XaP；XP2022/12/29403)对对 XV

26、N，重复如下过程，直到所有，重复如下过程，直到所有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)2022/12/2941例例 表达式文法的语法符号的表达式文法的语法符号的 FIRST 集集FIRST(F)=(,idFIRST(T)=FIRST(F)=(,id FIRST(E)=FIRST(T)=(,id FIRST(E)=+，FIRST(

27、T)=*,FIRST(+)=+,FIRST(*)=*FIRST()=(FIRST()=)FIRST(id)=idETE ETE ETE ETE E+TEE+TEE+TEE+TE|TFT TFT TFT TFT T*T*T*T*FTFTFTFT|F(E)|idF(E)|idF(E)|idF(E)|id2022/12/2942求求FIRST()的算法的算法n令令=X1Xnn初值初值nFIRST()=FIRST(X1)-;nk=1;n循环循环nwhile FIRST(Xk)&kn donFIRST()=FIRST()(FIRST(Xk+1)-)；nK=k+1;n结束处理结束处理nif k=n&FIR

28、ST(Xn)then FIRST()=FIRST()2022/12/2943求求FOLLOW(A)的算法的算法令令#为句子的结束符，对于所有非终结符为句子的结束符，对于所有非终结符,重复进行重复进行以下计算以下计算n1)将将#加入到加入到 FOLLOW(S)n2)若若 AB，n则则 FOLLOW(B)=FOLLOW(B)(FIRST()n3)如果如果AB或或AB，且，且*，AB，n则则 FOLLOW(B)=FOLLOW(B)FOLLOW(A)2022/12/2944例例 表达式文法的语法变量的表达式文法的语法变量的 FOLLOW 集集FOLLOW(E)=#,)ETEETEETEETE E E

29、E E+TE+TE+TE+TE|TFTTFTTFTTFT T T T T*FTFTFTFT|F(E)|idF(E)|idF(E)|idF(E)|idFIRST(F)=FIRST(F)=FIRST(F)=FIRST(F)=（,id,id,id,idFIRST(T)=FIRST(F)=FIRST(T)=FIRST(F)=FIRST(T)=FIRST(F)=FIRST(T)=FIRST(F)=（,id ,id ,id ,id FIRST(E)=FIRST(T)=FIRST(E)=FIRST(T)=FIRST(E)=FIRST(T)=FIRST(E)=FIRST(T)=（,id ,id ,id ,id

30、 FIRST(EFIRST(EFIRST(EFIRST(E)=+)=+)=+)=+，FIRST(TFIRST(TFIRST(TFIRST(T)=*,)=*,)=*,)=*,FIRST(FIRST()=)=FIRST(FIRST()FOLLOW(E)=FOLLOW(E)=#,)FOLLOW(T)=FIRST (E)FOLLOW(E)FOLLOW(E)=+,),#FOLLOW(T)=FOLLOW(T)=+,),#FOLLOW(F)=FIRST(T)FOLLOW(T)FOLLOW(T)=*,+,),#2022/12/2945小结n主要内容n自顶向下分析方法存在的各种问题nFIRST集合和FOLLOW集合的计算2022/12/2946