程序设计语言与编译原理_自上而下的语法分析课件.ppt-得力文库

资源描述

《程序设计语言与编译原理_自上而下的语法分析课件.ppt》由会员分享，可在线阅读，更多相关《程序设计语言与编译原理_自上而下的语法分析课件.ppt（89页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、程序设计语言与编译语法分析u对无关文法无关文法G=(VT，VN，S，P)及符号串及符号串，判断，判断是否是文法是否是文法G的一个合法的一个合法句子句子。即即 S S*=w=w？程序设计语言与编译符号串符号串（二元式流）（二元式流）正确句子的语法树正确句子的语法树报告语法错误报告语法错误语法分析程序语法分析程序第七章第七章自上而下的语法分析自上而下的语法分析第一节第一节引言引言一一.语法分析的功能语法分析的功能程序设计语言与编译语法分析:自上而下(自顶而下)自下而上(自底而上)二二.语法分析方法的分类语法分析方法的分类自上而下语法分析法自上而下语法分析法:或从开始符号出发或从开始符号出发,找

2、最左推导找最左推导;或从根开始或从根开始,构造推导树。构造推导树。自下而上语法分析法自下而上语法分析法:从输入串开始从输入串开始,归约归约,直至文法开始符。直至文法开始符。程序设计语言与编译自上而下的语法分析的语法分析u分析分析过程程从文法开始符出从文法开始符出发，能否找到一个，能否找到一个最左最左推推导序列，使得序列，使得S=*w；或者从根或者从根结点点S开始，根据最左推开始，根据最左推导，能，能否构造一棵否构造一棵语法法树，使得，使得该语法法树的叶的叶结点自左至右的点自左至右的连接正好是接正好是。给定文法给定文法G=(VG=(VT T,V VN N,S,S，P)P)以及输入串以及输入串w

3、 w V VT T*,*,程序设计语言与编译自下而上的语法分析的语法分析u分析分析过程程从从出出发，能否找到一个，能否找到一个最左最左规约（最右推（最右推导的逆的逆过程）序列，逐步向上程）序列，逐步向上规约，直至文，直至文法的开始符法的开始符S；或者或者对生成生成的的语法法树，按最左，按最左规约对语法法树进行行剪枝剪枝，能否最后只剩下根，能否最后只剩下根结点点S。给定文法给定文法G=(VG=(VT T,V VN N,S,S，P)P)以及输入串以及输入串w w V VT T*,*,程序设计语言与编译u自上而下的自上而下的语法分析可分法分析可分为不确定不确定和和确定确定的两的两类。u回溯分析法回

4、溯分析法是不确定的分析方法。是不确定的分析方法。u递归下降分析法下降分析法和和预测分析法分析法属于属于确定的分析方法。确定的分析方法。程序设计语言与编译第二节第二节回溯分析法回溯分析法一一.一个实例一个实例SxAyAaba输入串为xay,说明分析过程。x xA Ay ya a b b S Sx xA Ay ya a S S从文法的开始符号S出发，选取S的候选式进行推导，接着按最左推导进行下去；如果推导失败，再换用其他的候选式；若穷尽所有的候选式都失败，则表明w不是G的句子，w存在语法错语。程序设计语言与编译(1)公共左因子的存在 A1|2(2)左递归 AA 或 AA+二二.存在的问题存在的问

5、题回溯回溯直接左递归直接左递归间接左递归间接左递归(3)产生式可能产生回溯的原因有可能产生回溯的原因有程序设计语言与编译(1)公共左因子u公共左因子公共左因子，是指在文法的，是指在文法的产生式集合生式集合中，某个非中，某个非终结符的多个候符的多个候选式具有相式具有相同的前同的前缀。一般，一般，公共左因子的公共左因子的产生式生式为 A12程序设计语言与编译存在公共左因子u采采取取试探探的的方方法法来来分分析析每每一一个个候候选式，分析的式，分析的过程程很可能很可能产生回溯。生回溯。u若所有的候若所有的候选式都没有公共左因子式都没有公共左因子就就可可以以选择惟惟一一匹匹配配的的候候选式式，不不会

6、会产生回溯。生回溯。程序设计语言与编译(2)左递归左递归u左左递归的形式的形式为 A=+A 特特别地地 A=A 就是直接左就是直接左递归程序设计语言与编译例子例子:S SaS SaS bS b文法文法G(s)G(s)：符合串符合串baabaa的推导过程。的推导过程。S Sb bS Sa aS Sb b a aS Sa aS SS Sb b程序设计语言与编译产生式产生式S aASS aASS bS bA bASA bASA A 文法文法G(S)G(S)：输入串输入串abab的推导过程。的推导过程。S SA Aa aS SA Ab bS S S SA Aa aS Sb b程序设计语言与编译例：将

7、文法SxAyAaba改造成：SxAyAaBBbxay的推导过程如右图S Sx xA Ay ya a B B 三三.解决回溯：提取公共左因子解决回溯：提取公共左因子程序设计语言与编译一般方法一般方法AAAA1 1 1 1|2 2 2 2|n n n n|提取公共左因子提取公共左因子 AAAA B|B|B|B|BBBB 1|1|1|1|2|2|2|2|n n n n产生式：产生式：程序设计语言与编译四四.消除左递归消除左递归1.1.消除直接消除直接左递归左递归左递归左递归改写为改写为PP|P|P PPP|P|PP PPPP改写为改写为PP|改写为改写为P P|PPP|程序设计语言与编译一般地一

8、般地:AAAA 1 1|A A 2 2|A|A m m|1 1|2 2|n n （i i，j j不以不以A A开头）开头）改写为改写为:AA 1 1P P 2 2P P.n nP P P P 1 1P P 2 2P P.m mP P 程序设计语言与编译u一般而言，假定一般而言，假定P相关的全部相关的全部产生式是生式是PP 1|P 2|P m|1|2|n其中，每个其中，每个都不等于都不等于，每个，每个都不以都不以P开开头那么，消除那么，消除P的直接左的直接左递归性就是把性就是把这些些规则改写成：改写成：P 1P|2P|nP P 1P|2P|mP|左递归变右递归程序设计语言与编译u例例文法

9、文法G(E):EET|TTT*F|FF(E)|i经消去直接左消去直接左递归后后变成：成：ETE E+TE|TFT T*FT|F(E)|i(4.2)PP 1|P 2|P m|1|2|nP 1P|2P|nP P 1P|2P|mP|程序设计语言与编译u例如文法例如文法G(S):SQc|cQRb|bRSa|a (4.3)虽没有直接左没有直接左递归，但，但S、Q、R都是左都是左递归的的SQcRbcSabcu例：设文法例：设文法G(A):A Ac|Aad|bd|e消去直接左递归：消去直接左递归：A bdA|eAA cA|adA|程序设计语言与编译 2.2.间接间接左递归的消除左递归的消除左递归的消除左递归

10、的消除P P PP+例子：例子：A A Bc BcaaB B Ab AbA A Abc Abc aaA A aP aPP P bcP bcP 改为：改为：程序设计语言与编译算法算法1.1.将文法将文法G G的所有非终结符按任一顺序排列，设为的所有非终结符按任一顺序排列，设为A A1 1,A,An n2.2.执行下面算法，消除可能的左递归：执行下面算法，消除可能的左递归：for i:=1 to n dofor i:=1 to n do for j:=1 to i-1 do for j:=1 to i-1 do begin begin 把一个形如把一个形如A Ai iA Aj j 的产生式改写为

12、 R，Q Q Q Q，S S S S排列排列排列排列2.2.2.2.执行算法执行算法执行算法执行算法i=1i=1没有操作没有操作 i=2,j=1 i=2,j=1，A Ai i=Q,A=Q,Aj j=R,=R,有有QRbQRb|b b 把把RSaRSa|a a代入上式得代入上式得:Q QSab|ab|Sab|ab|b b 该式无直接左递归该式无直接左递归i=3,j=2i=3,j=2，A Ai i=S,A=S,Aj j=Q=Q，SQcSQc|c c将上面得到的将上面得到的Q Q的产生式代入的产生式代入得：得：SSSabSabc c|abc|bc|c|abc|bc|c消除上式的直接左递归得：消除上式

13、的直接左递归得：SSabcSabcS|bcS|bcS|cS|cS S SabcSabcS|i=3,j=1i=3,j=1，A Ai i=S,A=S,Aj j=R=R，无相应产生，无相应产生式，没有操作式，没有操作3.3.化简化简化简化简：经过上述算法，：经过上述算法，Q Q和和R R的产生式为多余的产生式，可的产生式为多余的产生式，可删除。最后得：删除。最后得：SSabcSabcS|bcS|bcS|cS|cSS SabcSabcS|程序设计语言与编译1.按R、Q、S排列,代入后 RSaa QSababb SSabcabc bcc SQccSQccQRbbQRbbRSaaRSaa2.2.消除消除S

14、 S中的直接左递归中的直接左递归文法产生的语言文法产生的语言:(abc|bc|c)(abc)*:(abc|bc|c)(abc)*SabcSbcScSSabcS 程序设计语言与编译1.按S、Q、R排列,代入后SQccQRbbRQcacaaRRbcabcacaaSQccSQccQRbbQRbbRSaaRSaa2.2.消除消除R R中的直接左递归中的直接左递归 R bcaRR bcaRcaRcaRaRaR R R bcaR bcaR 文法产生的语言文法产生的语言:(bca|ca|a)(bca)*bc|bc|c:(bca|ca|a)(bca)*bc|bc|c 程序设计语言与编译文法产生的语言文法产生

15、的语言:(bca|ca|a)(bca)*bc|bc|c:(bca|ca|a)(bca)*bc|bc|c文法产生的语言文法产生的语言:(abc|bc|c)(abc)*:(abc|bc|c)(abc)*程序设计语言与编译对于文法G=（a,b,c,d,S,A,S,P）;其中P为:S Aa|Ac|bc A Ad|Sbc|d请先提取文法G的公共左因子，再消除左递归。练习练习程序设计语言与编译提取公共左因子 S AB|bc B a|c A Ad|Sbc|d S Aa|Ac|bcS Aa|Ac|bcA Ad|Sbc|dA Ad|Sbc|d直接左递归直接左递归 S AB|bc S AB|bc B a|c B

17、共左因子公共左因子b.b.左递归左递归c.c.空产生式空产生式程序设计语言与编译当当文文法法改改造造为为无无公公共共左左因因子子,无无左左递递归归时时,让让每每个个非非终终结结符符对对应应一一个个过过程程，该该过过程程对对相相应应的的非非终终结结符符产产生生式式的的右右部部短短语语进进行行语语法法分分析析，这这种种分分析析方方法法称称为为递递归归下下降降分分析析法法。这这样样的的分析程序称为分析程序称为递归下降分析器递归下降分析器。第三节第三节递归下降分析法递归下降分析法程序设计语言与编译例:G(E)EE+TT TT*FF F(E)i消除左递归消除左递归:ETE:ETE E E+TE+TE

18、 TFT TFT T T*FT*FT F(E)i F(E)i 一一.分析方法分析方法程序设计语言与编译过程过程advanceadvance:匹配并把输入串指针后移一位变量变量symsym:输入指针指向的符号Error()Error():出错处理函数 procedure advance(t:token);begin if sym=t then sym=nexttoken else error（）end;程序设计语言与编译procedure E;begin T;Eend;procedure T;begin F;Tend;ETEETE E E+TE+TETFTTFT T T*FT*FTF(E)iF(

19、E)iprocedure E;if sym=+then begin advance(+);T;E end;procedure T;if sym=*then begin advance(*);F;T end;程序设计语言与编译ETEETE E E+TE+TETFTTFT T T*FT*FTF(E)iF(E)iprocedureF;ifsym=ithenadvance(i)elseifsym=(thenbeginadvance();E;ifsym=)thenadvance()elseerror()endelseerror();程序设计语言与编译i+i*i#i+i*i#的递归下降分析过程的递归下降分

20、析过程ETEETEE E+TE+TETFTTFTT T*FT*FTF(E)iF(E)iE ET TT Ti ii ii ii ii i+*#F FM(i)M(i)F FM(i)M(i)F FM(i)M(i)E EM(+)M(+)T TM(M()E EM(M()#T TM(M()#T TM(*)M(*)M(M()程序设计语言与编译二二.扩充的扩充的BNFBNF用花括号表示闭包运算*;可以重复任意多次用表示可任意重复0次至n次 =0=;用表示 ,即表示的出现可有可无(等价于)；1.1.表示形式表示形式n n0 00 00 01 10 0程序设计语言与编译例一：标识符的定义利用扩充例一：标识符的

21、定义利用扩充BNFBNF表示为表示为ET+TTF*FFi|(E)EE+TTTT*FFF(E)i例二：文法例二：文法ILLSILLSSTSTSTSTTLDTLDLab.zLab.zD012.9D012.9 I ILL|DLL|D L La|b|a|b|z|z D D0|1|0|1|9|9 程序设计语言与编译decimalsigninteger.digitexponentexponentEsignintegerintegerdigitdigitsign+-digit019例三：实数可定义为例三：实数可定义为程序设计语言与编译 pxyzpv改写成:p(xyz)v2.2.左递归的消除左递归的消除程

22、序设计语言与编译3.3.文法的转换图表示文法的转换图表示ET+TTF*FFi|(E)EE+TTTT*FFF(E)i+0 01 12 2T T 关于关于关于关于E E E E的转换图的转换图的转换图的转换图0 01 12 2F F*关于关于关于关于T T T T的转换图的转换图的转换图的转换图0 01 13 3（）i i2 2E E关于关于关于关于F F F F的转换图的转换图的转换图的转换图程序设计语言与编译procedure E;Begin T;while sym=+do begin advance(+);T end endET+T+0 01 12 2T T 关于关于关于关于E E E E

23、的转换图的转换图的转换图的转换图ET+TTF*FFi|(E)三三.改进的递归下降分析法改进的递归下降分析法F F 程序设计语言与编译procedure T;begin F;while sym=*do begin advance(*);F end end;TF*F0 01 12 2F F*关于关于关于关于T T T T的转换图的转换图的转换图的转换图程序设计语言与编译procedure F;if sym=i then advance(i)else if sym=(then begin advance();E;if sym=)then advance()else error end else e

24、rror；0 01 13 3（）i i2 2E E关于关于关于关于F F F F的转换图的转换图的转换图的转换图Fi|(E)程序设计语言与编译i+i*i#i+i*i#的递归下降分析过程的递归下降分析过程ET+TET+TTF*FTF*FF(E)iF(E)iE ET TT TF FF FF Fi ii ii i+i i#i i*M(i)M(i)M(*)M(*)M(i)M(i)M(+)M(+)M(i)M(i)程序设计语言与编译第四节第四节预测分析法预测分析法预预测测分分析析（LL(1)LL(1)分分析析法法）是是一一种种表表驱驱动动方方法法，由由下下推推栈栈、预预测测分分析析表表和和控控制制程

25、程序序组组成成。它它实实际际上上一一种种下下推推自自动机的实现模型。动机的实现模型。程序设计语言与编译LL(1)分析法分析法是一种不带回溯的非递归自上而下分析法。LL(1)的的含含义义:第一个L表明自自左左至至右右扫扫描描输输入入串串;第二个L表明最最左左推推导导;1表明向右查看一个符号。类似地,可有LL(k)文法,即向前查看k个符号才能确定选用哪个产生式,不过LL(k)(k1)在实际中极少使用。程序设计语言与编译LL(1)分分析析法法的的基基本本思思想想:根据输入串的当前输入符确定选用某某一一个个产生式进行推导,当该输入符与推导的第一个符号相同时，再取输入串的下一个符号,继续确定下一个推导应

26、选的产生式,如此下去,直到推出被分析的输入串为止。一个LL(1)分析器由一一张张LL(1)分分析析表表(预测分析表)、一一个个先先进进后后出出分分析析栈栈和一个控制程序控制程序(表驱动程序)组成。程序设计语言与编译a1a2aian#分析表M控制程序输入串：栈顶#x1xj输出分析栈图LL(1)分析器程序设计语言与编译对图的LL(1)分析器说明如下：(1)输输入入串串是待分析的符号串,它以“#”作为结束标志。(注:#VT但不是文法符号,是由分析程序自动添加的)(2)分分析析栈栈存放分析过程中的文文法法符符号号。分析开始时栈底先放一个“#”,再压入文法开始符;当分析栈中仅剩“#”且输入串指针指向串尾

27、的“#”时,分析成功。程序设计语言与编译(3)分分析析表表用一个矩阵M(二维数组)表示,它概括了文法的全部信息。矩矩阵阵的的每每一一行行与与文文法法的的一一个个非非终终结结符符相相关关联联,而而每每一一列列与与文文法法的的一一个个终终结结符符或或“#”关关联联。分析表元素MA,a中的内容为一条A的产生式,表明当A面临输入符a时应采用的候选式;当元素内容为空时,表明A不应面临输入符a,即输入串含语法错误。程序设计语言与编译(4)控制程序控制程序根据分析栈栈顶符号栈顶符号x和当当前输入符前输入符a决定分析器的动作:若xa“#”,则分析成功。若xa“#”,即栈顶符号x与当前输入符a匹配,则将x从栈

28、顶弹出,输入串指针后移,继续对下一个字符进行分析。若x为非终结符非终结符A,则查分析表MA,a:i.若MA,a为一产生式,则A自栈顶弹出,MA,a中产生式的右部符号逆序压栈逆序压栈;若MA,a为A,则只将A自栈顶弹出。ii.若MA,a为空,则发现语法错误,调用出错处理程序进行处理。程序设计语言与编译控制程序控制程序描述如下:将“#”和文法开始符依次入栈;把第一个输入符读入a;do把栈顶符号弹出并放入x中;if(xVT)if(xa)将下一输入符读入a;elseerror();elseif(Mx,a“xy1y2yk”)把y1y2yk按逆序入栈逆序入栈;输出“xy1y2yk”;elseerror()

29、;while(x!=“#”)程序设计语言与编译一一.预测分析过程预测分析过程1.1.预测分析表预测分析表形式:MA,a矩阵,AVN,a VT#内容:A或出错标志(空白表示)程序设计语言与编译预测分析表预测分析表EETTFi+*()#ETEETEE+TETFTTFTT*FTFiF(E)EETTTETEETEE E+TE+TETFTTFTT T*FT*FTF(E)iF(E)i 程序设计语言与编译2.2.分析方法分析方法初始时,#和开始符入栈,输入指针指向第一个符号,然后根据下推栈栈顶符x和当前输入符a进行工作:x=a=#,x=a=#,成功成功 x=ax=a#,#,匹配匹配 x x V VN N,

30、查表查表并把产生式右部符号按逆序推进栈程序设计语言与编译例：文法例：文法G G2 2E ETETEE E+TE+TE|T TFTFTT T*FT*FT|F F(E)|i(E)|i如何对输入串如何对输入串i+i*ii+i*i按照预测分析法进行语法分析按照预测分析法进行语法分析?程序设计语言与编译下推栈下推栈输入串输入串查分析表查分析表i+i*i#i+i*i#E#E#E#ET T#E#ET TF F#E#ET T#E#ET Ti i#E#E#E#ET T#E#ET+T+i+i*i#i+i*i#+i*i#+i*i#i+i*i#i+i*i#i+i*i#i+i*i#+i*i#+i*i#+i*i#+i*

31、i#i*i#i*i#ETEETETFTTFTTFTTFTFiFiT TE E+TE+TE 匹配匹配匹配匹配程序设计语言与编译#E#ET TF F i*i#i*i#E#ET Ti i#E#ET T#E#ET TF*F*#E#ET Ti i#E#ET TF F#E#ET T#E#E *i#*i#i#i#*i#*i#i#i#T T*FT*FT结束结束FiFiT T i*i#i*i#FiFiE E 匹配匹配匹配匹配匹配匹配程序设计语言与编译例例 7一个文法的LL(1)分析表如下所示,试给出输入串aadl的分析过程。输入串aadl的分析过程如下:程序设计语言与编译符号栈当前输入符输入串说明#Aaadl#

32、弹出栈顶符,将AaA右部反序压栈#Aaaadl#匹配,弹出栈顶符a,读出下一输入符a#Aadl#弹出栈顶符,将AABl右部反序压栈#lBAadl#弹出栈顶符,将AaA右部反序压栈#lBAaadl#匹配,弹出栈顶符a,读出下一输入符d#lBAdl#由A仅弹出栈顶符号A#lBdl#弹出栈顶符,将BdB右部反序压栈#lBddl#匹配,弹出栈顶符d,读出下一输入符l#lBl#由B仅弹出栈顶符号B#ll#匹配,弹出栈顶符l,读出下一输入符#匹配,分析成功程序设计语言与编译内容回顾内容回顾预测分析预测分析 1.1.下推堆栈下推堆栈2.2.总控程序总控程序3.3.预测分析表预测分析表总控程序总控程序 x=a

33、=#,x=a=#,成功成功 x=ax=a#,#,匹配匹配 x x V VN N,查表查表程序设计语言与编译63636363基本思想是基本思想是:当文法中某一当文法中某一非终结符非终结符呈现在呈现在栈顶时栈顶时,根据当前的输入符号根据当前的输入符号,分分析表应指示析表应指示要用该非终结符里要用该非终结符里的哪一条规则取匹配输入串的哪一条规则取匹配输入串(即即进行下一步最左推导进行下一步最左推导)根据这个思想根据这个思想,我们不难把构我们不难把构造分析表算法构造出来造分析表算法构造出来!终结符号终结符号终结符号终结符号非非非非终终终终结结结结符符符符号号号号分析表MA，a的构造程序设计语言与编译分

34、析表MA，a的构造q构造构造FIRST()和和FOLLOW(A)q构造分析表构造分析表MA，a程序设计语言与编译二二.FIRST.FIRST集和集和FOLLOWFOLLOW集集1.FIRST1.FIRST集集定定义义:假定是文法任一符号串,对(VTVN)*,有 FIRST（）a|a.,aVT.若,则FIRST(）*即FIRST()是的所有所有可能推出的首首终结符终结符或可能的组成的集合。*程序设计语言与编译 FIRSTFIRSTFIRSTFIRST集的构造方法集的构造方法集的构造方法集的构造方法对每个文法符号对每个文法符号X X V VT T V VN N，连续使用入下，

35、连续使用入下规则，直到每个规则，直到每个FIRST(X)FIRST(X)不再增大不再增大XVT,则FIRST(X)=X;XVN,分三种情形:1.Xa 2.XY 3.XY1Y2Yk程序设计语言与编译1.若有Xa,把a加入FIRST(X);若有X,把加入FIRST(X);2.若有XY,YVN,把FIRST(Y)的所有非所有非元素元素都加入FIRST(X);3.若有XY1Y2Yk,而Y1Yi1都有,则把FIRST(Yj)(j=1,2,i)的所有非元素都加入FIRST(X);特别地,若Y1Yk均有产生式,则把也加入到FIRST(X)。程序设计语言与编译首先把FIRST(X X1 1)-加入FIRST

36、()；若对任何1ji-1,FIRST(X Xi i),则把FIRST(X Xi i)加入FIRST()中；如果所有FIRST(X Xi i)均包含，则把加入FIRST()中=X X1 1X X2 2X Xn nXiV,i=1,2,3,.n程序设计语言与编译例:G(E)ETE E+TE TFT T*FT F(E)iE EE ET TT TF FFIRSTFIRST(i(i(i(i(i(i+*FIRST(E)=+,;FIRST(T)=*,;FIRST(F)(,i;由由TF知知,把把FIRST(F)的所有非的所有非元素加入元素加入FIRST(T),故故FIRST(T)=(,i;由由ET知知,把把FI

37、RST(T)的所有非的所有非元素加入元素加入FIRST(E),故故FIRST(E)=(,i程序设计语言与编译FIRST(Y1)=y1,FIRST(Y2)=y2,FIRST(A)=aFIRST(X)=y1,y2,a例子：例子：X X Y Y1 1Y Y2 2A A Y Y1 1 y y1 1 Y Y2 2 y y2 2 A A a a 程序设计语言与编译定义定义:对AVN,有 FOLLOW(A)=aS.Aa.,aVT 若S .A,则规定#FOLLOW(A),其中S为开始符号.*2.Follow2.Follow集集FOLLOW(A)是所有所有句型中出现在紧随A之后的终结符终结符或#。程序设计语

38、言与编译#FOLLOW(S)AB:将FIRST()-加入FOLLOW(B)AB:将FOLLOW(A)加入FOLLOW(B)AB且:将FOLLOW(A)加入FOLLOW(B)*求法求法求法求法注注意意:求求FOLLOW(B)FOLLOW(B)实实际际上上是是考考察察B B在产生式右端的每一次出现在产生式右端的每一次出现程序设计语言与编译FOLLOW(X)=#FOLLOW(Y1)=y2,aFOLLOW(Y2)=aFOLLOW(A)=#例子：例子：X X Y Y1 1Y Y2 2A A Y Y1 1 y y1 1 Y Y2 2 y y2 2 A A a a 程序设计语言与编译例:G(E)ETE E

39、+TE TFT T*FT F(E)iE EE ET TT TF FFIRSTFIRST(i(i(i(i(i(i+*程序设计语言与编译试构造文法GE的FOLLOW集。解:1)FOLLOW(E)=#;2)由由ETE知,FIRST(E)属于FOLLOW(T),即FOLLOW(T)+;由E+TE|,FIRST(E)属于由由TFT知,FIRST(T)属于FOLLOW(F),即FOLLOW(F)*;由T*FT|知,FIRST(T)属于由由F(E)|i知,FIRST()属于FOLLOW(E),即FOLLOW(E),#;程序设计语言与编译3)由由ETE知,FOLLOW(E)属于FOLLOW(E),即FOLLO

40、W(E),#;由由ETE且E知,FOLLOW(E)属于FOLLOW(T),即FOLLOW(T)+,),#;由E+TE知,FOLLOW(E)属于FOLLOW(E)由E+TE且E知,FOLLOW(E)属于FOLLOW(T)程序设计语言与编译由由TFT知,FOLLOW(T)属于FOLLOW(T)，即FOLLOW(T)+,),#;由由TFT且T知,FOLLOW(T)属于FOLLOW(F),即FOLLOW(F)*,+,),#；由T*FT知,FOLLOW(T)属于FOLLOW(T)由T*FT且T知,FOLLOW(T)属于FOLLOW(F)考虑F(E)|i程序设计语言与编译例:G(E)ETE E+TE TF

41、T T*FT F(E)iE EE ET TT TF FFIRSTFIRSTFOLLOWFOLLOW(i(i(i(i(i(i+*)#)#)#)#+)#+)#+)#+)#*+)#*+)#程序设计语言与编译练习:S-AB S-AB A-Ab|A-Ab|B-a|B-a|试求出试求出S S、A A、B B的的FIRST FIRST 和和 FOLLOWFOLLOW集。集。S SA AB BFIRSTFIRSTFOLLOWFOLLOWa b a b a a b b#b#b#程序设计语言与编译练习:G=G=（a,b,c,a,b,c,（,）,S,A,B,S,P,S,A,B,S,P）,P,P为为 S-bAb S-

42、bAb A-(B|a|A-(B|a|B-Aa)|Ac)B-Aa)|Ac)程序设计语言与编译设上下文无关文法G的产生式形如A1|2|n,当G满足下述条件时则称为LL(1)文法:FIRST(i)FIRST(j)=,ij,i,j=1,2,.,n若i,则FIRST(j)FOLLOW(A)=,ji，j=1,2,.,n 于是,在自顶向下分析时,可根据当前输入符号a选择aFIRST(i)的Ai。*三三.LL(1).LL(1)文法文法程序设计语言与编译在自上而下分析时，若当前输入字符为a,分析栈待匹配的非终结符为A，A1|2|n，则当:aFIRST(i)，或若i,aFOLLOW(A)则Ai便是惟一与a匹配

43、的产生式，即LL（1）文法中的两个条件保证了自上而下匹配的唯一性。LL(1)LL(1)LL(1)LL(1)文法与自上而下分析法的关系文法与自上而下分析法的关系文法与自上而下分析法的关系文法与自上而下分析法的关系程序设计语言与编译对aFIRST(),将A记入MA,a中;若FIRST(),对bFOLLOW(A),将A记入MA,b中;凡未被定义的MA,a项中标以出错标志。四四.预测分析表的构造预测分析表的构造1.1.构造算法构造算法对每个产生式对每个产生式AA 程序设计语言与编译例:G(E)ETE E+TE TFT T*FT F(E)iE EE ET TT TF FFIRSTFIRSTFOLLOWF

44、OLLOW(i(i(i(i(i(i+*)#)#)#)#+)#+)#+)#+)#*+)#*+)#构造过程：构造过程：构造过程：构造过程：1 1）求）求）求）求FIRSTFIRST：2 2）求）求）求）求FOLLOWFOLLOW3 3）构造分析表）构造分析表）构造分析表）构造分析表程序设计语言与编译EETTi i+*()#E EEET TTTF FETEETEETEETEE+TEE+TEEETFTTFTTFTTFTTTT*FTT*FTTTFiFiF(E)F(E)注意注意:用上述算法可以构造出任意给定文法的分析表用上述算法可以构造出任意给定文法的分析表,但不是所有但不是所有文法都能构造出上述那种形

45、状的分析表即文法都能构造出上述那种形状的分析表即MA,a=一条的规则或一条的规则或 Error。对于能用上述算法构造分析表的文法我们称为。对于能用上述算法构造分析表的文法我们称为LL(1)文法文法 3 3）构造）构造）构造）构造分析表分析表分析表分析表FIRST(F)=(,i FIRST(F)=(,i FIRST(T)=*,FIRST(T)=*,FIRST(T)=(,i FIRST(T)=(,i FIRST(E)=+,FIRST(E)=+,FIRST(E)=(,i FIRST(E)=(,i ETE ETE E+TE|E+TE|TFT TFT T*FT|T*FT|F(E)|iF(E)|iFOLL

46、OW(E)=#,)FOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#FOLLOW(F)=*,+,),#程序设计语言与编译MA,a中只记产生式右部;对=x1x2.xn,在M,a中记xn xn-1.x1;当xn xn-1.x1的x1VT时,x1必为a,x1无须入栈,只移动输入指针。2.2.预测分析表的改进预测分析表的改进程序设计语言与编译非非非非LL(1)LL(1)LL(1)LL(1)文法文法文法文法并并非非所所有

48、OLLOW(S)=e,#)=e,#FOLLOW(C)=tFOLLOW(C)=t求预测分析表求预测分析表a ab be ei it t#S SS Sa aS SiCtSSiCtSSS SS Se eS SS S S SC CC Cb b预测分析表预测分析表预测分析表预测分析表程序设计语言与编译内容回顾内容回顾预测分析表预测分析表 1.First1.First集合集合2.Follow2.Follow集合集合算算FirstFirst集集算算FollowFollow集集LL(1)LL(1)文法文法FIRST(FIRST(i i)FIRST(FIRST(j j)=,)=,i i j,i,j=1,2,.,nj,i,j=1,2,.,n若若 i i,则则 FIRST(FIRST(j j)FOLLOW(A)=,FOLLOW(A)=,j j i i，j=1,2,.,nj=1,2,.,n程序设计语言与编译作业作业作业作业必做题：必做题：7.27.2，7.37.3，7.57.5

展开阅读全文