第5章自顶向下语法分析方法学习教案

《第5章自顶向下语法分析方法学习教案》由会员分享，可在线阅读，更多相关《第5章自顶向下语法分析方法学习教案（147页珍藏版）》请在装配图网上搜索。

1、会计学1第第5章自顶向下语法分析方法章自顶向下语法分析方法(fngf)第一页，共147页。法分析的过程就是为一个(y )句子建立语法树的过程。第1页/共147页第二页，共147页。第2页/共147页第三页，共147页。n预测分析法第3页/共147页第四页，共147页。nLR第4页/共147页第五页，共147页。第5页/共147页第六页，共147页。第6页/共147页第七页，共147页。Sa A B b Ab Acd e第7页/共147页第八页，共147页。第8页/共147页第九页，共147页。第9页/共147页第十页，共147页。第10页/共147页第十一页，共147页。第11页/共147页第

2、十二页，共147页。第12页/共147页第十三页，共147页。第13页/共147页第十四页，共147页。Sx A y* * * *(S,x) 选择选择(xunz)产生式产生式SxAy 当前当前(dngqin)要替换的非终结符要替换的非终结符当前要匹配的输入符当前要匹配的输入符 (A, * *) 可选择两个产生式可选择两个产生式 AA* * *或或AA* *Sx A y* *回溯：回到出错点，重新回溯：回到出错点，重新选择产生式选择产生式AA* *，成功，成功第14页/共147页第十五页，共147页。第15页/共147页第十六页，共147页。第16页/共147页第十七页，共147页。Sa A S

3、Sa A Sb ASa A Sb第17页/共147页第十八页，共147页。交集不为。nSELECT(AbA)SELECT(A)=b第18页/共147页第十九页，共147页。第19页/共147页第二十页，共147页。EE + TE + TEE + TEE + TE + TE + T第20页/共147页第二十一页，共147页。第21页/共147页第二十二页，共147页。第22页/共147页第二十三页，共147页。第23页/共147页第二十四页，共147页。第24页/共147页第二十五页，共147页。最左推导最左推导过程过程所选产生式所选产生式输入串输入串( (当前要替换的非当前要替换的非终结符终结

4、符, ,输入符输入符) )1Sacbad#(S,a)2aABSaABacbad#(A,c)3acABAcAacbad#(A,b)4acbBBAbBacbad#(B,a)5acbaBBaacbad#(B,d)6acbadBdacbad#推导成功推导成功第25页/共147页第二十六页，共147页。Sa A B c Ab Bad第26页/共147页第二十七页，共147页。第27页/共147页第二十八页，共147页。此(ync)分析过程是唯一确定的。第28页/共147页第二十九页，共147页。第29页/共147页第三十页，共147页。最左推导最左推导过程过程所选产生式所选产生式输入串输入串( (当前要

5、替换的非当前要替换的非终结符终结符, ,输入符输入符) )1Sddca#(S,d)2AaSAaddca#(A,d)3dAaAdAddca#(A,d)4ddAaAdAddca#(A,c)5ddcaAcddca#推导成功推导成功第30页/共147页第三十一页，共147页。SA a d Ad Ac第31页/共147页第三十二页，共147页。第32页/共147页第三十三页，共147页。第33页/共147页第三十四页，共147页。集)。*第34页/共147页第三十五页，共147页。第35页/共147页第三十六页，共147页。第36页/共147页第三十七页，共147页。最左推导最左推导过程过程所选产生式所

6、选产生式输入串输入串( (当前要替换的非当前要替换的非终结符终结符, ,输入符输入符) )1Saca#(S,a)2aABSaABaca#(A,c)3acABAcAaca#(A,a)4acBAaca#(B,a)5acaBaaca#推导成功推导成功第37页/共147页第三十八页，共147页。Sa A Bc Aa第38页/共147页第三十九页，共147页。第39页/共147页第四十页，共147页。第40页/共147页第四十一页，共147页。*第41页/共147页第四十二页，共147页。第42页/共147页第四十三页，共147页。*第43页/共147页第四十四页，共147页。第44页/共147页第四十

7、五页，共147页。* * *第45页/共147页第四十六页，共147页。唯一正确的选择A的某个产生式去匹配。第46页/共147页第四十七页，共147页。第47页/共147页第四十八页，共147页。第48页/共147页第四十九页，共147页。第49页/共147页第五十页，共147页。第50页/共147页第五十一页，共147页。第51页/共147页第五十二页，共147页。n第二种推导过程推出了ab。第52页/共147页第五十三页，共147页。第53页/共147页第五十四页，共147页。第54页/共147页第五十五页，共147页。第55页/共147页第五十六页，共147页。第56页/共147页第五十

8、七页，共147页。*第57页/共147页第五十八页，共147页。+第58页/共147页第五十九页，共147页。+第59页/共147页第六十页，共147页。第60页/共147页第六十一页，共147页。第61页/共147页第六十二页，共147页。第62页/共147页第六十三页，共147页。第63页/共147页第六十四页，共147页。第64页/共147页第六十五页，共147页。第65页/共147页第六十六页，共147页。*第66页/共147页第六十七页，共147页。*第67页/共147页第六十八页，共147页。的后随符号。+ +第68页/共147页第六十九页，共147页。*第69页/共147页第七十

9、页，共147页。第70页/共147页第七十一页，共147页。n (SAB,且B , CAD) na ，c ，第71页/共147页第七十二页，共147页。第72页/共147页第七十三页，共147页。第73页/共147页第七十四页，共147页。anSELECT(Dc)FIRST(c)c 第74页/共147页第七十五页，共147页。第75页/共147页第七十六页，共147页。*第76页/共147页第七十七页，共147页。第77页/共147页第七十八页，共147页。第78页/共147页第七十九页，共147页。n所以，该文法(wnf)不是LL(1)文法(wnf)。第79页/共147页第八十页，共147页

10、。第80页/共147页第八十一页，共147页。第81页/共147页第八十二页，共147页。+ +第82页/共147页第八十三页，共147页。导(tudo)AA，则称该文法是右递归的。+ + + +第83页/共147页第八十四页，共147页。+ +第84页/共147页第八十五页，共147页。第85页/共147页第八十六页，共147页。+ + +第86页/共147页第八十七页，共147页。第87页/共147页第八十八页，共147页。第88页/共147页第八十九页，共147页。m mn n第89页/共147页第九十页，共147页。第90页/共147页第九十一页，共147页。第91页/共147页第九十

11、二页，共147页。n第92页/共147页第九十三页，共147页。第93页/共147页第九十四页，共147页。第94页/共147页第九十五页，共147页。能导致最终正确地匹配，只得再换另一个候选式去试探，从而引起回溯。第95页/共147页第九十六页，共147页。从而可以消除上面所说的回溯现象。第96页/共147页第九十七页，共147页。第97页/共147页第九十八页，共147页。、共左因子，则可反复提取它们的共同左因子，直到每个新引入的非终结符的产生式再无公共左因子为止。第98页/共147页第九十九页，共147页。第99页/共147页第一百页，共147页。第100页/共147页第一百零一页，共1

12、47页。第101页/共147页第一百零二页，共147页。自顶向下的语法分析。第102页/共147页第一百零三页，共147页。第103页/共147页第一百零四页，共147页。第104页/共147页第一百零五页，共147页。第105页/共147页第一百零六页，共147页。nFIRST(F)=(,inFOLLOW(T)=,)，# nFOLLOW(F)=*,，),#第106页/共147页第一百零七页，共147页。nnSELECT(T)FOLLOW(T)十，），nSELECT(F（E）) （ nSELECT(Fi)i第107页/共147页第一百零八页，共147页。两不相交，因此(ync)，该文法是LL（

13、1）文法，可以进行确定的自顶向下语法分析。第108页/共147页第一百零九页，共147页。第109页/共147页第一百一十页，共147页。n第110页/共147页第一百一十一页，共147页。第111页/共147页第一百一十二页，共147页。n第112页/共147页第一百一十三页，共147页。n else error( );n第113页/共147页第一百一十四页，共147页。第114页/共147页第一百一十五页，共147页。第115页/共147页第一百一十六页，共147页。第116页/共147页第一百一十七页，共147页。第117页/共147页第一百一十八页，共147页。n else error

14、( );n第118页/共147页第一百一十九页，共147页。第119页/共147页第一百二十页，共147页。第120页/共147页第一百二十一页，共147页。第121页/共147页第一百二十二页，共147页。a a1 1 a a2 2 a ai i a an n # #输入输入(shr)串串总控程序总控程序预测分析表预测分析表（LL(1)LL(1)分析表）分析表）栈顶符号栈顶符号# #x x1 1x xn n 分析栈分析栈第122页/共147页第一百二十三页，共147页。第123页/共147页第一百二十四页，共147页。第124页/共147页第一百二十五页，共147页。第125页/共147页第

15、一百二十六页，共147页。nn一个文法G的预测分析表M不含多重定义入口，当且仅当该文法是LL（l）文法。第126页/共147页第一百二十七页，共147页。第127页/共147页第一百二十八页，共147页。i+* *()#EETEETEEE+TEEETTFTTFTTTT* *FTTTFFiF(E)第128页/共147页第一百二十九页，共147页。第129页/共147页第一百三十页，共147页。#S栈顶指针栈顶指针 a1 a2 an #输入串指针输入串指针 第130页/共147页第一百三十一页，共147页。#X1 X2Xm-1 Xm 栈顶指针栈顶指针 a1 ai ai+1 an# 输入串指针输入串

16、指针 此时，可根据栈顶的文法此时，可根据栈顶的文法(wnf)(wnf)符号符号XmXm的不同情况，分别处理：的不同情况，分别处理： 第131页/共147页第一百三十二页，共147页。a1 ai ai+1 an# 输入串指针输入串指针 #X1 X2Xm-1 栈顶指针栈顶指针 第132页/共147页第一百三十三页，共147页。情情形形a1 ai ai+1 an# 输入串指针输入串指针 #X1 X2Xm-1 CBA 栈顶指针栈顶指针 第133页/共147页第一百三十四页，共147页。a1 ai ai+1 an# 输入串指针输入串指针 # 栈顶指针栈顶指针 第134页/共147页第一百三十五页，共14

17、7页。第135页/共147页第一百三十六页，共147页。第136页/共147页第一百三十七页，共147页。#E ( E, +)查表E +TE +i# 7 #ET+ ( +,+)匹配i# # ET ( T,i)查表T FT i# 9 #ETF ( F,i)查表F i i# 10 #ETi ( i,i )匹配# 11 #ET ( T, #)查表T # 12 #E ( E, #)查表E #13 # ( #, #) 成功接收# 第137页/共147页第一百三十八页，共147页。第138页/共147页第一百三十九页，共147页。第139页/共147页第一百四十页，共147页。=FOLLOW（X）n =e

18、nd第140页/共147页第一百四十一页，共147页。第141页/共147页第一百四十二页，共147页。beginds;end#PPbegind；XendXXd；X XsYYY；sY Y 第142页/共147页第一百四十三页，共147页。第143页/共147页第一百四十四页，共147页。XsY s ；s end6 #end Y s ( s, s )匹配；s end7 #end Y ( Y,；)查表Y；sY ；s end8 # end Y s ； ( ；, ；)匹配s end9 #end Y s ( s, s )匹配end10 #end Y ( Y, end )查表Y end#end ( end, end )匹配12 # ( #, #) 成功接收第144页/共147页第一百四十五页，共147页。第145页/共147页第一百四十六页，共147页。第146页/共147页第一百四十七页，共147页。