cha自上而下语法分析实用.pptx

《cha自上而下语法分析实用.pptx》由会员分享，可在线阅读，更多相关《cha自上而下语法分析实用.pptx（91页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/231内容回顾内容回顾(续续)最左(最右)推导在推导的任何一步=*(其中和是句型)，都对中的最左(最右)非终结符进行替换句型分析(句子分析)识别一个符号串是否为某文法的句型(句子)的过程也就是某文法的某个推导的构造过程n设文法设文法G G G G为为:E E+T|T E E+T|T E E+T|T E E+T|T T T*F|F T T*F|F T T*F|F T T*F|F F(E)|i F(E)|i F(E)|i F(E)|i n请问符号串i+i*ii+i*i是 否为该文法的句子?E E E EE +TE +TE +TE +TT *FT *FT *FT *FF F F FF

2、F F FT T T Ti i i ii i i ii i i i自自上上 而而下下自自下下而而上上章节目录章节目录第1页/共91页2023/3/2324.14.1语法分析的功能语法分析的功能 p67p67任务分析并判定输入的单词符 号串是否符合该语言的语 法规则(上下文无关文法)实质就是按照文法的产生式，识别输入符号串是否为一 个句子(合法程序，语句，表达式等)词法扫描器语法分析器语义处理单词符号单词符号语法树语法树第2页/共91页2023/3/233语法分析器的设计思想和输出语法分析器的设计思想和输出设计思想判断是否能从文法的开始符号出发推导出这个输入串或者,判断能否建立一棵与输入串匹配的

3、语法分析树输入 单词符号串输出 语法分析树格式化的程序合法的表达式、语句、函数出错处理要求尽快发现错误，准确定位可能时进行恢复处理，继续语法分析第3页/共91页2023/3/234常用语法分析方法常用语法分析方法 p66p66语法分析算法可分为两大类:自上而下分析法从文法的开始符号出发，反复使用各种产生式向 下推导，寻找与输入符号串匹配的推导自下而上分析法从输入串开始，逐步进行归约，直至归约到文法 的开始符号两种方法反映了两种不同的语法树的构造过程自上而下从树根推导到树叶自下而上从树叶归约到树根第4页/共91页2023/3/235上下文无关文法（型文法）上下文无关文法（型文法）编程语言的语法大

4、都可用2型文法来描述没有一种方法能够有效地分析所有上下文 无关文法存在无法处理的2型文法每种方法能够处理一部分上下文无关文法每种方法都有适用范围章节目录章节目录第5页/共91页2023/3/2364.2 自上而下分析面临的问题 p67基本方法对任何输入串,试图从文法的开始符号出发，自上而下地为输入串建立一棵语法树，或者说为输入串寻找一个最左推导。过程本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程如何选择哪个产生式进行推导?第6页/共91页2023/3/237自上而下分析举例自上而下分析举例 p67p67例 文法GS SxAy Aab|a 判断输入串 w=x a y是否为该文法的句

5、子？S Sx xA Ay y试探试探a ab b失败失败回溯回溯a a试探成功试探成功分析结束分析结束S Sx xA Ay y=x xa ay y=问题产生回溯的原因是什么?第7页/共91页2023/3/238自上而下分析面临的问题自上而下分析面临的问题 p68p68公共左因子产生回溯例 文法G:S xAy A ab|a无法确定非终结符A面临输入符 号a时选用哪个关于A的候选式 左递归无限循环例 文法G:S Sa|abaw=abaaaw=abaaaS SS Sa aS Sa au无法确定何时用无法确定何时用SabaSabaSabaSaba产生式产生式 进行推导进行推导n某些文法导致自上而下分析

6、具有不确定性章节目录章节目录第8页/共91页2023/3/2394.3 LL(1)4.3 LL(1)分析法分析法 p68p68为了构造不带回溯的自上而下分析算法n消除文法的左递归n消除回溯、提取左因子nLL(1)分析条件uLL(1)文法章节目录章节目录第9页/共91页2023/3/23104.3.1 4.3.1 左递归的消除左递归的消除 p69p69关于非终结符P P的规则直接左递归定义：若P PP P 、*例如 E E E E+T+TT T（含有E E的左递归）T T T T*F*FF F（含有T T的左递归）F (E)F (E)i i 第10页/共91页2023/3/2311间接左递归的定

7、义间接左递归的定义 p68p68间接左递归定义：若P P=+P P *例如 间接左递归 S S Aa Aa A A S Sb|bb|b S S=Aa=Aa=S Sba ba 即S S=+=+S Sb b用S S的产生式右部替换A A右部的S S得：A A A Aab|bab|b 变成A A的产生式含有直接左递归第11页/共91页2023/3/2312消除直接左递归的方法消除直接左递归的方法 p69p69改写为等价的右递归 形如：P P 非，不以P开始改写为：PP（P为新增加的非终结符）PP改写前产生式可产生短语 P=P=改写后产生式可产生短语 P=P=P=等价等价第12页/共91页2023/3

8、/2313举例：表达式文法直接左递归的消除举例：表达式文法直接左递归的消除E E E E+T+TT TT T T T*F*FF FF (E)F (E)i inE E T T E E EE +T +T EEnT T F F T T T T *F *F TTnF F (E)(E)i i第13页/共91页2023/3/2314消除多个直接左递归消除多个直接左递归 p69p69 若有多个左递归的产生式如：若有多个左递归的产生式如：PPPPPPPP1 1 1 1|PPPP2 2 2 2|PPPPm m m m|1 1 1 1|2 2 2 2|n n n nn消除左递归后变为：PP1 1P P|2 2 P

9、 P|n nP P P P 1 1P P|2 2 P P|m mP P|n消除左递归要求文法：1.1.无回路（A=A=*A A）2.2.无空产生式（A A ）第14页/共91页2023/3/2315消除直接左递归课堂练习例如有文法：KKKKa a|K|Kb b|K|Kc c|d d|e eBEGINBEGINn消除左递归后变为：K K d dK K|e eK K K K a aK K|b bK K|c cK K|第15页/共91页2023/3/2316间接左递归消除举例 p70 S QcS Qcc c Q Q Rb Rbb b R R Sa Saa aS=Qc=Rbc=Sabc S=Qc=Rb

10、c=Sabc 是间接左递归消除方法1 1：将非终结符排序：R Q SR Q S将R R的右部代入Q Q，S S：Q Q SaSab ba ab bb b S Qc S Qcc c（不变）n将Q Q的右部代入S S：S S SabSabc cababc cb bc cc cn消除S S的直接左递归：S abcSS abcSbcSbcS|cS|cS S SabcSabcS|Q Sab Q Sabab|bab|b R Sa R Saa an整理化简：删除Q Q，R R（无用）n消除左递归后得：S abcSS abcSbcSbcS|cS|cS S SabcSabcS|第16页/共91页2023/3/2

11、317间接左递归消除举例（续）p70 S S Qc Qcc c Q Q Rb Rbb b R Sa R Saa a消除方法2 2：将非终结符排序：S Q RS Q R将S S的右部代入Q Q，R R：Q RbQ Rbb b（不变）R R QcQca ac ca|aa|an将将Q Q Q Q的右部代入的右部代入R R R R：R R R R RbRbRbRbcacacacab b b bca|ca|aca|ca|aca|ca|aca|ca|an消除消除R R R R的直接左递归：的直接左递归：R bcaRR bcaRR bcaRR bcaR caRcaRcaRcaR|aR|aR|aR|aR R

12、R R R bcaRbcaRbcaRbcaR|n整理化简：整理化简：S S S S，Q Q Q Q（有用）（有用）n消除左递归后得：消除左递归后得：S QcS QcS QcS Qcc c c c Q Rb Q Rb Q Rb Q Rbb b b b R bcaR R bcaR R bcaR R bcaR caRcaRcaRcaR|aR|aR|aR|aR R R R R bcaRbcaRbcaRbcaR|第17页/共91页2023/3/2318消除左递归算法 p701.1.以某种顺序将文法的非终结符排列 P P1 1，P P2 2，,P,Pn n 2.FOR i:=1 TO n DO2.FOR

13、i:=1 TO n DO BEGIN BEGIN FOR j:=1 TO i-1 DO FOR j:=1 TO i-1 DO 把形如P Pi iPPj j的规则改写成 P Pi i1 1|2 2|k k,其中 P Pj j1 1|2 2|k k是关于P Pj j的所有规则;消除P Pi i的直接左递归 ENDEND3.3.化简由2 2所得的文法，即去除那些从开始符号 出发永远无法到达的非终结符的产生式n当非终结符的排列顺序不 同时，变换后的文法形式 可能不同，但是它们都和 原文法是等价的 节目录节目录第18页/共91页2023/3/23194.3.2 4.3.2 消除回溯、提左因子消除回溯、提

14、左因子 p71p71消除回溯目的对文法的任何非终结符，当它去匹配输入串 时，能够根据输入符号，准确地选择合适的候选式去匹配若需要非终结符A A去匹配输入串，A A的候选式 为AA1 1|2 2|n n ，A A所面临的第一个输入符号为a a时，A A能准确地选择i i去执行匹配任务，则无需回溯第19页/共91页2023/3/2320提取公共左因子方法提取公共左因子方法 p71p71对于所有形如 AA1 12 2.n n的规则 其中，为左因子，不以开头改写为AAAA 其中AA为新增加的非终结符 AA1 12 2.n n例如 S xAyS xAy A A a ab|b|a an提左因子后变换为 S

15、 xAy S xAy S xAy S xAy A A A A a a a aA A A A A A A A b|b|b|b|节目录节目录第20页/共91页2023/3/23214.3.3 LL(1)分析条件 p71FIRSTFIRST集合的定义与计算FOLLOWFOLLOW集合的定义与计算LL(1)LL(1)文法的定义LL(1)LL(1)分析节目录节目录第21页/共91页2023/3/2322FIRST()集合的定义 p71设G=(G=(T T，N N，S S，P P）*FIRST(FIRST()=)=a a|=*a a，a aT T 若=*，则FIRST(FIRST()FIRST(FIRST

16、()是的所有可能推导的首遇终结符号或，是选择产生式的依据a a E T E E T E E+T EE+T ET F T T F T T*F TT*F T F (E)F (E)i inFIRST(FIRST(E)(E)=)=(（E E）=0 0（E E）nFIRSTFIRST（TETE）=（，i i TETE=FT=FTE E=（E E）T TE ETETE=FT=FTE E=i iT TE E第22页/共91页2023/3/2323FIRST()FIRST()的计算法的计算法FIRST()=FIRST()=a a=*a a ，aaT T 若=*，则 FIRST()FIRST()计算文法符号X

17、X的FIRSTFIRST（X X）计算文法符号串=X=X1 1X X2 2XXn n的FIRST()FIRST()第23页/共91页2023/3/2324FIRST(X)FIRST(X)的计算法的计算法 p78p78重复以下计算，直到FIRSTFIRST（X X）不再增大为止:1)1)若 XXT T，则 FIRST(X)=FIRST(X)=X X 。例 FIRSTFIRST（+）=+FIRST=+FIRST（i i）=i=i2)2)若 XXN N，若有XXa a，则将 a a 加入FIRST(X)FIRST(X)；例 E+TE +FIRSTE+TE +FIRST（EE）FF（E E）|i|i

18、（，iFIRSTiFIRST（F F）若有X X，则将加入FIRST(X)FIRST(X)。例 E FIRSTE FIRST（EE）第24页/共91页2023/3/2325u若有若有X X X X Y Y Y Y1 1 1 1Y Y Y Yi-1i-1i-1i-1Y Y Y Yi i i iY Y Y Yk k k k ，并对于某个并对于某个i i i i，有有1ji-11ji-11ji-11ji-1，FIRSTFIRSTFIRSTFIRST（Y Y Y Yj j j j），），即即Y Y Y Y1 1 1 1，Y Y Y Yi-1i-1i-1i-1=*，则将所有则将所有FIRST(YFIRS

19、T(YFIRST(YFIRST(Yj j j j)-FIRST(Y)-FIRST(Y)-FIRST(Y)-FIRST(Yi i i i)-)-)-)-加入加入FIRST(X)FIRST(X)FIRST(X)FIRST(X)中；中；-n3)3)若有 X X Y Y，且 Y Y N N ，则 FIRST(Y)-FIRST(Y)-加入FIRST(X);FIRST(X);例 FF(E)|E)|i i FIRST(F)=FIRST(F)=（，i i TTF FT FIRST(T)T FIRST(T)=FIRST(=FIRST(F F)-)-=（，i i u若所有若所有Y Y Y Y1 1 1 1,Y,Y

20、,Y,Yk k k k=*，则将，则将加入到加入到 FIRST(X)FIRST(X)FIRST(X)FIRST(X)。第25页/共91页2023/3/2326计算XYXY1 1YYi-1i-1Y Yi iYYk k FIRST(X)FIRST(X)集举例若有文法G G为：X YX Y1 1 Y Y2 2 Y Y3 3 Y Y4 4 Y Y5 5 Y1 a Y1 a Y2 b Y2 b Y3 c Y3 c Y4 d Y4 d Y5 e Y5 ef fFIRSTFIRSTFIRSTFIRST集集Y Y Y Y1 1 1 1Y Y Y Y2 2 2 2Y Y Y Y3 3 3 3Y Y Y Y4 4

21、 4 4Y Y Y Y5 5 5 5X X X Xa a a a，b b b b，c c c c，d d d d，e e e e，f f f fa,a,a,a,b,b,b,b,c,c,c,c,d,d,d,d,e,fe,fe,fe,f因为因为Y Y Y Y5 5 5 5=*，所以所以FIRSTFIRSTFIRSTFIRST（X X X X）=*=*因为因为Y Y Y Y5 5 5 5=*，所以所以FIRSTFIRSTFIRSTFIRST（X X X X）第26页/共91页2023/3/2327计算表达式文法计算表达式文法FIRST(X)FIRST(X)集举例集举例文法G G为：E T EE T

22、EE+T EE+T ET F T T F T T*F TT*F T F(E)F(E)i in先找以先找以终结符开头终结符开头的产生式的产生式FIRST(F)=(,i FIRST(F)=(,i FIRST(F)=(,i FIRST(F)=(,i FIRST(E)=+FIRST(E)=+FIRST(E)=+FIRST(E)=+，FIRST(T)=*,FIRST(T)=*,FIRST(T)=*,FIRST(T)=*,n再找右部以再找右部以非终结符开头非终结符开头的产生式的产生式FIRST(T)=FIRST(F)FIRST(T)=FIRST(F)FIRST(T)=FIRST(F)FIRST(T)=FI

23、RST(F)FIRST(E)=FIRST(T)FIRST(E)=FIRST(T)FIRST(E)=FIRST(T)FIRST(E)=FIRST(T)=(,i =(,i =(,i =(,i 第27页/共91页2023/3/2328计算FIRST(X)FIRST(X)集合课堂练习=a=a=a=a，c c c c，d d d d，q q q q 文法G为：S ApS ApBqBqA aA acA cA B dBB dB BEGINBEGINn先找以先找以终结符开头终结符开头的产生式的产生式FIRST(A)=a,c FIRST(A)=a,c FIRST(B)=d,FIRST(B)=d,n再找右部以再找

24、右部以非终结符开头非终结符开头的产生式的产生式FIRST(S)=FIRST(A)-FIRST(S)=FIRST(A)-FIRST(B)-FIRST(B)-因为B=B=FIRST(S),FIRST(S),FIRST(S),FIRST(S),因为因为S=S=S=S=*FIRST(q)FIRST(q)第28页/共91页2023/3/2329FIRST()FIRST()的计算法的计算法设=X=X1 1 X X2 2 X Xi-1 i-1 X Xi i X Xn n，按以下方法构造集合则FIRST(FIRST()=FIRST)=FIRST（X X1 1 )；n若任何1ji-11ji-1,2in2in,F

25、IRST(FIRST(X Xj j)则X Xi i前所有FIRST(FIRST(X Xj j )-)-和FIRST(FIRST(X Xi i )加入到 FIRST()FIRST()中；n若所有的1jn1jn，FIRST(FIRST(X Xj j)则把也加入FIRST()FIRST()中；n若=，则 FIRST()=FIRST()=n若 FIRST(X FIRST(X1 1)即X1=X1=第29页/共91页2023/3/2330计算表达式文法候选式FIRST()集举例候选式的FIRSTFIRST集FIRST(FIRST(TETE)=FIRST()=FIRST(T T)=)=(,i i FIRST

26、(FIRST(+TE+TE)=)=+FIRST(FIRST(FTFT)=FIRST()=FIRST(F F)=)=(,i i FIRST(FIRST(*FT*FT)=)=*FIRST(FIRST(E)(E)=)=(FIRST(FIRST(i i)=)=i i FIRST(FIRST()=)=文法文法GG为：为：EEEETETETETE E E E E+TE+TE+TE+TE|T T T TFTFTFTFT T T T T*FT*FT*FT*FT|FFFF(E)(E)(E)(E)|i i i i非终结符的非终结符的FIRSTFIRSTFIRSTFIRST集集FIRST(E)=(,iFIRST(E

27、)=(,iFIRST(E)=(,iFIRST(E)=(,iFIRST(E)=+,FIRST(E)=+,FIRST(E)=+,FIRST(E)=+,FIRST(T)=(,iFIRST(T)=(,iFIRST(T)=(,iFIRST(T)=(,iFIRST(T)=*,FIRST(T)=*,FIRST(T)=*,FIRST(T)=*,FIRST(F)=(,iFIRST(F)=(,iFIRST(F)=(,iFIRST(F)=(,i第30页/共91页2023/3/2331计算计算FIRST()FIRST()集合课堂练习集合课堂练习文法G G为：S S ApApBqBqA A a acAcAB B dBd

28、B非终结符的非终结符的FIRSTFIRSTFIRSTFIRST集集FIRST(S)=a,c,d,q FIRST(S)=a,c,d,q FIRST(A)=a,cFIRST(A)=a,cFIRST(B)=d,FIRST(B)=d,BEGINBEGIN候选式的FIRSTFIRST集FIRST(FIRST(ApAp)=FIRST()=FIRST(A A)=a,)=a,ccFIRST(FIRST(BqBq)=FIRST()=FIRST(B B)-)-FIRST(FIRST(q q)=d,q =d,qFIRST(FIRST(a a)=a)=aFIRST(FIRST(cAcA)=c)=cFIRST(FIRS

29、T(dBdB)=d)=dFIRST(FIRST()=)=小节目录小节目录第31页/共91页2023/3/2332FOLLOW(A)集合的定义 p73 A AN N FOLLOW(FOLLOW(A A)=)=a aS S=*A Aa a，a aT T 若S S=*A A，则#FOLLOWFOLLOW（A A）#输入串的结束符 也可看作是句子的括号#S#S#FOLLOW(FOLLOW(A A)表示了句型中可能紧跟在A A后面的终结符号S SA Aa aE T E E T E E+T EE+T E T F T T F T T*F TT*F T F (E)F (E)i in ）FOLLOWFOLLOW

30、（E E）S S =TE=TE=FT=FTE E =（E E）T TE E n +FOLLOW FOLLOW（T T）S S=TE=TE=T T+TETE n#FOLLOW FOLLOW（E E）S S=0 0 E E 第32页/共91页2023/3/2333FOLLOW(A)FOLLOW(A)的计算法的计算法 p79p79FOLLOW(FOLLOW(A A)=)=a aS=S=*AaAa，aaT T 若S=S=*A A，则#FOLLOWFOLLOW（A A）重复以下计算，直到每个FOLLOW(A)FOLLOW(A)不再增大为止：1)1)将#加入到 FOLLOW(FOLLOW(S S)中 例#

31、FOLLOW(E)#FOLLOW(E)2)2)若AAB B,则将FIRST()-FIRST()-加入FOLLOW(B)FOLLOW(B)例 ETEETE FIRST(E FIRST(E)-)-加入FOLLOW(T)FOLLOW(T)TFT TFT FIRST(T FIRST(T)-)-加入FOLLOW(F)FOLLOW(F)第33页/共91页2023/3/2334FOLLOW(A)FOLLOW(A)的计算法（续）的计算法（续）3)3)若 A A B B ，或 A A B B，且 =*，即 FIRST()FIRST()，ABAB 则将FOLLOW(A)FOLLOW(A)所有元素加入FOLLOW(

32、B)FOLLOW(B)例例 E E E E T T T T E E E E FOLLOW(E)FOLLOW(E)FOLLOW(E)FOLLOW(E)加入加入FOLLOW(EFOLLOW(EFOLLOW(EFOLLOW(E)E E E E T T T T E E E E EEEEFOLLOW(E)FOLLOW(E)FOLLOW(E)FOLLOW(E)加入加入FOLLOW(T)FOLLOW(T)FOLLOW(T)FOLLOW(T)T T T T F F F F T T T T FOLLOW(T)FOLLOW(T)FOLLOW(T)FOLLOW(T)加入加入FOLLOW(TFOLLOW(TFOLLO

33、W(TFOLLOW(T)T T T T F F F F T T T T FOLLOW(T)FOLLOW(T)FOLLOW(T)FOLLOW(T)加入加入FOLLOW(F)FOLLOW(F)FOLLOW(F)FOLLOW(F)TTTT第34页/共91页2023/3/2335计算表达式文法的计算表达式文法的FOLLOWFOLLOW集举例集举例n#FOLLOW#FOLLOW#FOLLOW#FOLLOW（开始符号）（开始符号）n对每个非终结符查看其在产生式右边的出现对每个非终结符查看其在产生式右边的出现GG：ETEETEETEETE E+TE E+TE E+TE E+TE|TFT|TFT|TFT|TF

34、T T*FT T*FT T*FT T*FT|F(E)|iF(E)|iF(E)|iF(E)|i#FOLLOW(E)#FOLLOW(E)#FOLLOW(E)#FOLLOW(E)相同不需处理相同不需处理=FIRST(E=FIRST(E)-)-FOLLOW(T)FOLLOW(T)FOLLOW(E)FOLLOW(E)=+,),#=+,),#FOLLOW(F)FOLLOW(F)=FIRST(T=FIRST(T)-)-FOLLOW(T)FOLLOW(T)=*,+,),#=*,+,),#FOLLOW(E)FOLLOW(E)=),#=),#FOLLOW(E)FOLLOW(E)=FOLLOW(E)=FOLLOW(

35、E)=),#=),#FOLLOW(T)FOLLOW(T)=FOLLOW(T)=FOLLOW(T)=+,),#=+,),#第35页/共91页2023/3/2336计算计算FOLLOW(A)FOLLOW(A)集合课堂练习集合课堂练习文法G为：S ApS ApBqBqA aA acAcAB dBB dB非终结符的非终结符的FIRSTFIRSTFIRSTFIRST集集FIRST(S)=a,c,d,q FIRST(S)=a,c,d,q FIRST(A)=a,cFIRST(A)=a,cFIRST(B)=d,FIRST(B)=d,BEGINBEGIN 非终结符非终结符FOLLOWFOLLOWFOLLOWFO

36、LLOW集集FOLLOW(S)=#FOLLOW(S)=#FOLLOW(S)=#FOLLOW(S)=#FOLLOW(A)=FIRST(p)-FOLLOW(A)=FIRST(p)-FOLLOW(A)=FIRST(p)-FOLLOW(A)=FIRST(p)-=p =p =p =pFOLLOW(B)=FIRST(q)-FOLLOW(B)=FIRST(q)-FOLLOW(B)=FIRST(q)-FOLLOW(B)=FIRST(q)-=q =q =q =q小节目录小节目录第36页/共91页2023/3/2337i+i#i+i#的推导过程的推导过程 p72p72设有文法设有文法G G G GETEETEET

37、EETE E E E E+TE+TE+TE+TE|TFTTFTTFTTFT T T T T*FT*FT*FT*FT|F(E)|F(E)|F(E)|F(E)|i i i iP79 P79 P79 P79 iFIRST(iFIRST(iFIRST(iFIRST(i i i i)+FIRST(+TE+FIRST(+TE+FIRST(+TE+FIRST(+TE)+FOLLOW(T+FOLLOW(T+FOLLOW(T+FOLLOW(T)#FOLLOW(E#FOLLOW(E#FOLLOW(E#FOLLOW(E)#FOLLOW(T#FOLLOW(T#FOLLOW(T#FOLLOW(T)i ii i生成语法分

38、析树第37页/共91页2023/3/2338推导过程的分析推导过程的分析输入输出输入：符号串(有序的)输出：结构化的符号串(树结构)产生式的选择根据当前符号（单词）语法分析树的表示按照使用序列排列的产生式序列第38页/共91页2023/3/2339消除回溯的条件消除回溯的条件 p71p71非终结符A A的所有候选首符集两两不相交，即A A的任何两个不同候选和，满足：FIRST(FIRST()FIRST()FIRST()=)=当要求 A A 匹配输入串时，A A就能根据它所面 临的第一个输入符号 a a，准确地指派某一个 候选去执行任务，这个候选就是那个终结首 符集含 a a 的第39页/共91

39、页2023/3/2340非终结符非终结符A A的自动匹配的自动匹配 p73p73当非终结符 A A 面临输入符号a a，但a a不属于A A的任何候选首符集，如果A A有候选式AA(A(A的某个候选首符集包含)，可以让A A自动得到匹配，即A A匹配于空字，但输入符号不读进要想让A A自动匹配成功，需要考察FOLLOW(A)FOLLOW(A)第40页/共91页2023/3/2341无回溯的自上而下分析的文法的条件p73文法不含左递归对于文法的每个非终结符 A A 的任何两 个不同的产生式 A|A|1)FIRST()FIRST()=1)FIRST()FIRST()=2)=2)=*和=*不能同时成

40、立3)3)如果=*，则 FISRT()FOLLOW(A)=FISRT()FOLLOW(A)=满足以上条件的文法称为LL(1)LL(1)文法第41页/共91页2023/3/2342表达式文法是表达式文法是 LL(1)LL(1)文法文法满足条件（3 3）：E FIRST(+TE)=+FOLLOW(E)=),#E FIRST(+TE)=+FOLLOW(E)=),#T FIRST(*FT)=*FOLLOW(T)=+,),#T FIRST(*FT)=*FOLLOW(T)=+,),#文法G G是LLLL（1 1）文法n满足条件（满足条件（1 1 1 1）：已消除左递归）：已消除左递归n满足条件（满足条件（

41、2 2 2 2）：）：FIRST(+TEFIRST(+TEFIRST(+TEFIRST(+TE)=+FIRST()=)=+FIRST()=)=+FIRST()=)=+FIRST()=FIRST(*FTFIRST(*FTFIRST(*FTFIRST(*FT)=*FIRST()=)=*FIRST()=)=*FIRST()=)=*FIRST()=FIRST(E)=(FIRST(i)=i FIRST(E)=(FIRST(i)=i FIRST(E)=(FIRST(i)=i FIRST(E)=(FIRST(i)=i n文法文法G G G G：E TE E TE E TE E TE E+TEE+TEE+TE

42、E+TE|T FT T FT T FT T FT T*FTT*FTT*FTT*FT|F(E)F(E)F(E)F(E)i i i i小节目录小节目录第42页/共91页2023/3/2343LL(1)LL(1)分析分析 p73p73含义第一个 L 表示从左向右扫描输入符号串第二个 L 表示生成最左推导1 表示读入一个符号可确定下一步推导LL(1)文法能够对输入串进行有效的 无回溯的自上而下分析第43页/共91页2023/3/2344LL(1)LL(1)分析分析 p73p73对于文法G G，当面临的输入符号为a a，要用 非终结符A A进行匹配时，假设A A的所有产生 式为 AA1 1|2 2|n

43、n1)1)若aFIRST(aFIRST(i i)，则指派i i去执行任务2)2)若a a不属于任何候选首符集，则：若属于某个FIRST(FIRST(i i)且 aFOLLOW(A)aFOLLOW(A)，则让A A与自动匹配 否则，a a的出现是一种语法错误小节目录小节目录第44页/共91页2023/3/2345 4.4 4.4 递归下降分析程序构造递归下降分析程序构造 p74p74不带回溯的自上而下分析程序分析程序一组递归过程每个非终结符一个子过程LLLL（1 1）文法构造分析程序从开始符号所对应的过程开始运行子过程的功能：子过程的功能：对相应非终结符对相应非终结符产生式右部进行语法分析产生式

44、右部进行语法分析第45页/共91页2023/3/2346例例 表达式文法的递归下降分析器表达式文法的递归下降分析器n消除左递归后的表达式文法G G为：E TE E TE E+TEE+TE|T FT T FT T*FTT*FT|F(E)|iF(E)|in可以证明 G G是一个LLLL（1 1）文法E()E()E E()T()T()T T()F()F()5 5个非终结符构造5 5个子过程第46页/共91页2023/3/2347递归下降分析器构造说明递归下降分析器构造说明 p74p74C C语言 E E（）T T;EE;E E E E T T T TE E（1 1）E E（）：完成对 E E T E

45、T E的右部分析PASCALPASCALPASCALPASCAL语言语言procedure E;procedure E;beginbegin T;T;EE;end;end;右部有非右部有非终结符时，终结符时，调用该非调用该非终结符对终结符对应的子过应的子过程来完成程来完成第47页/共91页2023/3/2348递归下降分析器构造说明递归下降分析器构造说明E()E()if(c=if(c=+)p+;p+;T T;EE;E E E E T T T TE E（2 2）E E（）：完成对 E E +T E+T E|的右部分析procedure E;procedure E;if sym=if sym=+t

46、hen then begin begin advance;advance;T T;EE;end end；+其它其它 非非+字符字符 自动匹配自动匹配advanceadvanceadvanceadvance：把输入指针：把输入指针ipipipip下移一位下移一位symsymsymsym：当前所面临的输入符号：当前所面临的输入符号第48页/共91页2023/3/2349表达式文法的递归下降分析器表达式文法的递归下降分析器 举例举例C C语言练习T()T()F F;TT;(3)T():T (3)T():T F TF Tprocedure T;procedure T;beginbegin F F;T

47、T;end;end;T T T T F F F FT T第49页/共91页2023/3/2350表达式文法的递归下降分析器表达式文法的递归下降分析器 举例举例(4)T(4)T():T():T*F*F T T|C C语言练习T T()()if(c=if(c=*)p+;p+;F F;T T;procedure Tprocedure T;if sym=if sym=*then then begin begin advance;advance;F F;T T;end end；T T T T F F F F*其它其它 非非*字符字符 自动匹配自动匹配T T第50页/共91页2023/3/2351表达式文

48、法的递归下降分析器表达式文法的递归下降分析器 举例举例(5)F():F(5)F():F(E)|i(E)|i E E E EF F F F()i i i i其它其它 非非(,i(,i(,i(,i字符出现语法错误字符出现语法错误procedure F;procedure F;begin begin if sym=if sym=(then then begin advance;begin advance;E E;if sym=if sym=)then advance then advance else error else error 括号不匹配 end end else if sym=else i

49、f sym=i i then advance then advance else else errorerror FF面临非（，i i输入符号，语法错误 end end第51页/共91页2023/3/2352的子程序C C语言练习F()F()if(c=if(c=()p+;p+;E E;if(c=if(c=)p+;)p+;else error;else error;/*/*括号不匹配括号不匹配*/else else if(c=if(c=i i)p+;)p+;else else errorerror;/*F/*F/*F/*F面临非面临非(,i(,i(,i(,i输入符号，输入符号，语法错误语法错误*

50、/E E E EF F F F()i i i i其它其它 非非(,i(,i(,i(,i字符出现语法错误字符出现语法错误第52页/共91页2023/3/2353i+i的递归下降分析过程 i ii i生成语法分析树i+i#i+i#匹配成功返回，指针下移自动匹配，返回自动匹配，返回自动匹配，返回匹配成功继续，指针下移匹配成功返回，指针下移分析成功结束第53页/共91页2023/3/2354递归下降分析程序优缺点分析递归下降分析程序优缺点分析优点：1）直观、简单、可读性好2）便于扩充缺点：1)递归算法的实现效率低2)处理能力相对有限3)通用性差，难以自动生成第54页/共91页2023/3/2355 递