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

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 w V VT T*,程

3、序设计语言与编译自下而上的语法分析的语法分析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

7、 bS S S SA Aa aS Sb b程序设计语言与编译 例：将文法SxAyAaba改造成：SxAyAaBBbxay的推导过程如右图S Sx xA Ay ya a B B 三三.解决回溯：提取公共左因子解决回溯：提取公共左因子程序设计语言与编译 一般方法一般方法提取公共左因子提取公共左因子 产生式：产生式：程序设计语言与编译 四四.消除左递归消除左递归改写为改写为PP|P|P PPP|P|PP PPPP改写为改写为PP|改写为改写为P P|PPP|程序设计语言与编译一般地一般地:AAAA 1 1|A A 2 2|A|A m m|1 1|2 2|n n （i i，j j不以不以A A开头）开

8、头）改写为改写为:AA 1 1P P 2 2P.P.n nPP PP 1 1PP 2 2P.P.m mPP 程序设计语言与编译u一般而言，假定一般而言，假定P相关的全部产生式是相关的全部产生式是PP 1|P 2|P m|1|2|n其中，每个其中，每个 都不等于都不等于，每个，每个 都不以都不以P开头开头 那么，消除那么，消除P的直接左递归性就是把这些规的直接左递归性就是把这些规则改写成：则改写成：P 1P|2P|nP P 1P|2P|mP|左递归变右递归程序设计语言与编译u例例 文法文法G(E):EET|TTT*F|FF(E)|i经消去直接左递归后变成：经消去直接左递归后变成：ETE E+TE

9、|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|程序设计语言与编译 P P PP+例子：例子：A A Bc BcaaB B Ab AbA A Abc Abc aaA A aP aPP P bcP bcP 改为：改为：程序

10、设计语言与编译 算法算法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 的产生式改写为的产生式改写为 A Ai i1 1|2 2|k k 其中其中A Aj j1 1|2 2|k k是是A Aj j的所有产生式的所有产生式;消除消除A Ai i产

11、生式的直接左递归产生式的直接左递归;end end3.3.化简：删除多余产生式，即在从文法开始符号的化简：删除多余产生式，即在从文法开始符号的 任何推导中都不会出现的非终结符的产生式；任何推导中都不会出现的非终结符的产生式；程序设计语言与编译以 SQcc QRbb RSaa为例,按S,Q,R排列,或R,Q,S排列程序设计语言与编译 SQc|cQRb|bRSa|a步骤：步骤：1.1.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

12、 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消除上式的直接左递归得：消除上式的直接左递归得：SSabcS|bcS|cSabcS|bcS|cS S SabcS|abcS|i=3,j=1i=3,j=1，A Ai i=S,A=S,Aj j=R=R，无相应产，无相应产生式，没有操作生式，没有操作3.3.：经过上述算法，：经过上述算法，Q Q和和R R的产生式为多余的产生式，可的产生式为多余的产生式

13、，可删除。最后得：删除。最后得：SSabcS|bcS|cSabcS|bcS|cSSSabcS|abcS|程序设计语言与编译1.按R、Q、S排列,代入后 RSaa QSababb SSabcabc bcc SQccSQccQRbbQRbbRSaaRSaa2.2.消除消除S S中的直接左递归中的直接左递归 文法产生的语言文法产生的语言:(abc|bc|c)(abc):(abc|bc|c)(abc)*SabcSbcScSSabcS 程序设计语言与编译1.按S、Q、R排列,代入后 SQcc QRbb R Qcacaa R RbcabcacaaSQccSQccQRbbQRbbRSaaRSaa2.2.消除

14、消除R R中的直接左递归中的直接左递归 R bcaRcaRaRR bcaRcaRaR R bcaR R bcaR 文法产生的语言文法产生的语言:(bca|ca|a)(bca):(bca|ca|a)(bca)*bc|bc|cbc|bc|c 程序设计语言与编译文法产生的语言文法产生的语言:(bca|ca|a)(bca):(bca|ca|a)(bca)*bc|bc|cbc|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请先提取文

15、法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 a|c A SbcP|dP A SbcP|dP PdP|PdP|间接左递归间接左递归 S AB|bc S AB|bc B a|c B a|c A ABbcP|bcbcP A ABbcP|bcbcP|dP P dP|P dP|间接左递归间接左递归 S AB|bc S AB|bc B a|c B a|c A bcbcPQ A b

16、cbcPQ|dPQ Q BbcPQ|Q BbcPQ|P dP|P dP|程序设计语言与编译回顾回顾 1.1.语法分析功能语法分析功能2.2.两大类两大类3.3.回溯分析回溯分析1.1.自上而下自上而下(自顶而下自顶而下)2.2.自下而上自下而上(自底而上自底而上)a.a.公共左因子公共左因子b.b.左递归左递归c.c.空产生式空产生式程序设计语言与编译 当文法改造为无公共左因子当文法改造为无公共左因子,无左递归时无左递归时,让让每个非终结符对应一个过程，该过程对相应每个非终结符对应一个过程，该过程对相应的非终结符产生式的右部短语进行语法分析，的非终结符产生式的右部短语进行语法分析，这种分析方法

17、称为这种分析方法称为。这样的。这样的分析程序称为分析程序称为。第三节第三节 递归下降分析法递归下降分析法程序设计语言与编译例:G(E)EE+TT TT*FF F(E)i消除左递归消除左递归:ETE :ETE E+TE E+TE TFT TFT T T*FTFT F(E)i F(E)i 一一.分析方法分析方法程序设计语言与编译过程过程advanceadvance:匹配并把输入串指针后移一位变量变量symsym:输入指针指向的符号Error()Error():出错处理函数 procedure advance(t:token);begin if sym=t then sym=nexttoken el

18、se error（）end;程序设计语言与编译procedure E;begin T;Eend;procedure T;begin F;Tend;ETE ETE E+TEE+TETFT TFT TT*FTFTF(E)iF(E)iprocedure E;if sym=+then begin advance(+);T;E end;procedure T;if sym=*then begin advance(*);F;T end;程序设计语言与编译ETE ETE E+TEE+TETFT TFT TT*FTFTF(E)iF(E)iprocedure F;if sym=i then advance(i)

19、else if sym=(then begin advance();E;if sym=)then advance()else error()end else error();程序设计语言与编译i+ii+i*i#i#的递归下降分析过程的递归下降分析过程ETEETEE+TEE+TETFTTFTTT*FTFTF(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用花

20、括号表示闭包运算*;可以重复任意多次用 表示可任意重复0次至n次 =0=;用表示 ,即表示的出现可有可无(等价于)；n n0 00 00 01 10 0程序设计语言与编译例一：标识符的定义利用扩充例一：标识符的定义利用扩充BNFBNF表示为表示为ET+TTF*FFi|(E)EE+TTTT*FFF(E)i例二：文法例二：文法ILLSILLSSTSTSTSTTLDTLDLab.zLab.zD012.9D012.9 I ILL|DLL|D L La|b|za|b|z D D0|1|90|1|9 程序设计语言与编译 decimal signinteger.digitexponent exponentE

21、signinteger integerdigitdigit sign+-digit 0 1 9例三：实数可定义为例三：实数可定义为 程序设计语言与编译 pxyzpv改写成:p(xyz)v 程序设计语言与编译ET+TTF*FFi|(E)EE+TTTT*FFF(E)i+0 01 12 2T T 0 01 12 2F F*0 01 13 3（）i i2 2E E 程序设计语言与编译procedure E;Begin T;while sym=+do begin advance(+);T end endET+T+0 01 12 2T T ET+TTF*FFi|(E)三三.改进的递归下降分析法改进的递归下

22、降分析法F F 程序设计语言与编译procedure T;begin F;while sym=*do begin advance(*);F end end;TF*F0 01 12 2F F*程序设计语言与编译procedure F;if sym=i then advance(i)else if sym=(then begin advance();E;if sym=)then advance()else error end else error；0 01 13 3（）i i2 2E EFi|(E)程序设计语言与编译i+ii+i*i#i#的递归下降分析过程的递归下降分析过程ET+TET+TTFTF

23、*FFF(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)分析法）是一种表分析法）是一种表驱动方法，由下推栈、预测分析表和驱动方法，由下推栈、预测分析表和控制程序组成。它实际上一种下推自控制程序组成。它实际上一种下推自动机的实现模型。动机的实现模型。程序设计语言与编译LL(1)分析法分析法是一种不带回溯的非递归自上而下分析法。LL(1)的含义的含义:第一个L表明自左至右自左至右扫描输入串

24、扫描输入串;第二个L表明最左推导最左推导;1表明向右查看一个符号。类似地,可有LL(k)文法,即向前查看k个符号才能确定选用哪个产生式,不过LL(k)(k1)在实际中极少使用。程序设计语言与编译 LL(1)分析法的基本思想分析法的基本思想:根据输入串的当前输入符确定选用某一个某一个产生式进行推导,当该输入符与推导的第一个符号相同时，再取输入串的下一个符号,继续确定下一个推导应选的产生式,如此下去,直到推出被分析的输入串为止。一个LL(1)分析器由一张一张LL(1)分析分析表表(预测分析表)、一个先进后出分析栈一个先进后出分析栈和一个控制程序控制程序(表驱动程序)组成。程序设计语言与编译a1a2

25、aian#分析表M控制程序输入串：栈顶#x1xj输出分析栈图 LL(1)分析器程序设计语言与编译对图 的LL(1)分析器说明如下：(1)输入串输入串是待分析的符号串,它以“#”作为结束标志。(注:#VT但不是文法符号,是由分析程序自动添加的)(2)分析栈分析栈存放分析过程中的文法符文法符号号。分析开始时栈底先放一个“#”,再压入文法开始符;当分析栈中仅剩“#”且输入串指针指向串尾的“#”时,分析成功。程序设计语言与编译 (3)分析表分析表用一个矩阵M(二维数组)表示,它概括了文法的全部信息。矩阵的矩阵的每一行每一行与文法的一个与文法的一个非终结符非终结符相关联相关联,而而每一列每一列与文法的一

26、个与文法的一个终结符终结符或或“#”关联。关联。分析表元素MA,a中的内容为一条A的产生式,表明当A面临输入符a时应采用的候选式;当元素内容为空时,表明A不应面临输入符a,即输入串含语法错误。程序设计语言与编译(4)控制程序控制程序根据分析栈栈顶符号栈顶符号x和当当 前输入符前输入符a决定分析器的动作:若xa“#”,则分析成功。若xa“#”,即栈顶符号x与当前输入符a匹配,则将x从栈顶弹出,输入串指针后移,继续对下一个字符进行分析。若x为非终结符非终结符A,则查分析表MA,a:i.若MA,a为一产生式,则A自栈顶弹出,MA,a中产生式的右部符号逆序压栈逆序压栈;若MA,a为A,则只将A自栈顶弹

27、出。ii.若MA,a为空,则发现语法错误,调用出错处理程序进行处理。程序设计语言与编译控制程序控制程序描述如下:将“#”和文法开始符依次入栈;把第一个输入符读入a;do 把栈顶符号弹出并放入x中;if(xVT)if(xa)将下一输入符读入a;else error();else if(Mx,a“xy1y2yk”)把y1y2yk按逆序入栈逆序入栈;输出“xy1y2yk”;else error();while(x!=“#”)程序设计语言与编译一一.预测分析过程预测分析过程1.1.预测分析表预测分析表 形式:MA,a矩阵,AVN,a VT#内容:A或出错标志(空白表示)程序设计语言与编译预测分析表预测

28、分析表EETTFi+*()#ETEETEE+TETFTTFTT*FTFiF(E)EETTTETEETEE+TEE+TETFTTFTTT*FTFTF(E)iF(E)i 程序设计语言与编译2.2.分析方法分析方法初始时,#和开始符入栈,输入指针指向第一个符号,然后根据下推栈栈顶符x和当前输入符a进行工作:x=a=#,x=a=#,成功成功 x=ax=a#,#,匹配匹配 x x V VN N,查表查表并把产生式右部符号按逆序推进栈 程序设计语言与编译例：文法例：文法G G2 2E ETETEEE+TE|+TE|T TFTFTTT*FT|FT|F F(E)|i(E)|i如何对输入串如何对输入串i+ii+

29、i*i i按照预测分析法进行语法分析按照预测分析法进行语法分析?程序设计语言与编译下推栈下推栈输入串输入串查分析表查分析表i+ii+i*i#i#E#E#ET#ET#ETF#ETF#ET#ET#ETi#ETi#E#E#ET#ET#ET+#ET+i+ii+i*i#i#+i+i*i#i#i+ii+i*i#i#i+ii+i*i#i#+i+i*i#i#+i+i*i#i#i i*i#i#ETEETETFTTFTTFTTFTFiFiTTE+TEE+TE 匹配匹配匹配匹配程序设计语言与编译#ETF#ETF i i*i#i#ETi#ETi#ET#ET#ETF#ETF*#ETi#ETi#ETF#ETF#ET#ET

30、#E#E *i#i#i#i#*i#i#i#i#TT*FTFT结束结束FiFiTT i i*i#i#FiFiEE 匹配匹配匹配匹配匹配匹配程序设计语言与编译例例 7 一个文法的LL(1)分析表如下所示,试给出输入串aadl的分析过程。输入串aadl的分析过程如下:程序设计语言与编译符号栈当前输入符输入串说 明#Aaadl#弹出栈顶符,将AaA右部反序压栈#Aaaadl#匹配,弹出栈顶符a,读出下一输入符a#Aa dl#弹出栈顶符,将AABl右部反序压栈#lBAa dl#弹出栈顶符,将AaA右部反序压栈#lBAaa dl#匹配,弹出栈顶符a,读出下一输入符d#lBAd l#由A仅弹出栈顶符号A#l

31、Bd l#弹出栈顶符,将BdB右部反序压栈#lBdd l#匹配,弹出栈顶符d,读出下一输入符l#lBl#由B仅弹出栈顶符号B#ll#匹配,弹出栈顶符l,读出下一输入符#匹配,分析成功程序设计语言与编译内容回顾内容回顾预测分析预测分析 1.1.下推堆栈下推堆栈2.2.总控程序总控程序3.3.预测分析表预测分析表总控程序总控程序 x=a=#,x=a=#,成功成功 x=ax=a#,#,匹配匹配 x x V VN N,查表查表程序设计语言与编译基本思想是基本思想是:当文法中某一当文法中某一非终结符非终结符呈现在呈现在栈顶时栈顶时,根据当前的输入符号根据当前的输入符号,分分析表应指示析表应指示要用该非终

32、结符里要用该非终结符里的哪一条规则取匹配输入串的哪一条规则取匹配输入串(即即进行下一步最左推导进行下一步最左推导)根据这个思想根据这个思想,我们不难把构我们不难把构造分析表算法构造出来造分析表算法构造出来!分析表MA，a的构造程序设计语言与编译分析表MA，a的构造q构造构造FIRST()和和FOLLOW(A)q构造分析表构造分析表MA，a程序设计语言与编译二二.FIRST.FIRST集和集和FOLLOWFOLLOW集集1.FIRST1.FIRST集集定义定义:假定是文法任一符号串,对(VTVN)*,有 FIRST（）a|a.,aVT.若,则FIRST(）*即FIRST()是的所有所有可能推出的

33、首首 终结符终结符或可能的组成的集合。*程序设计语言与编译 对每个文法符号对每个文法符号X X V VT T V VN N，连续使用入下规，连续使用入下规则，直到每个则，直到每个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)的所有非 元素都加入FI

34、RST(X);特别地,若Y1Yk均有产生式,则把也加入到FIRST(X)。程序设计语言与编译 首先把FIRST(X X1 1)-加入FIRST()；若对任何1ji-1,FIRST(X Xi i),则把FIRST(X Xi i)加入FIRST()中；如果所有FIRST(X Xi i)均包含，则把加入FIRST()中=X X1 1X X2 2XXn nXiV,i=1,2,3,.n程序设计语言与编译例:G(E)ETE E+TE TFT T*FT F(E)iE EEET TTTF FFIRSTFIRST(i(i(i(i(i(i+*FIRST(E)=+,;FIRST(T)=*,;FIRST(F)(,i;

35、由由TF知知,把把FIRST(F)的所有非的所有非元素加入元素加入FIRST(T),故故FIRST(T)=(,i;由由ET知知,把把FIRST(T)的所有非的所有非元素加入元素加入FIRST(E),故故FIRST(E)=(,i程序设计语言与编译FIRST(Y1)=y1,FIRST(Y2)=y2,FIRST(A)=a FIRST(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),

36、其中S为开始符号.*2.Follow2.Follow集集FOLLOW(A)是所有所有句型中出现在紧随A之后的终结符终结符 或#。程序设计语言与编译#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

37、2A A Y Y1 1 y y1 1 Y Y2 2 y y2 2 A A a a 程序设计语言与编译例:G(E)ETE E+TE TFT T*FT F(E)iE EEET TTTF 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()属于 FOLLO

38、W(E),即FOLLOW(E),#;程序设计语言与编译3)由由ETE知,FOLLOW(E)属于FOLLOW(E),即FOLLOW(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

39、(T)由T*FT且T知,FOLLOW(T)属于FOLLOW(F)考虑F(E)|i 程序设计语言与编译例:G(E)ETE E+TE TFT T*FT F(E)iE EEET TTTF 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#程序设计

40、语言与编译练习:G=G=（a,b,c,a,b,c,（,）,S,A,B,S,P,S,A,B,S,P）,P,P为为 S-bAb S-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)文法文法 程序设计语言与编译在自上而下分析时，若当前输入字

41、符为a,分析栈待匹配的非终结符为A，A1|2|n，则当:aFIRST(i)，或 若i,aFOLLOW(A)则Ai便是惟一与a匹配的产生式，即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 EEET TTTF FFIRSTFIRSTFOLLOWFOLLOW(i(i(

42、i(i(i(i+*)#)#)#)#+)#+)#+)#+)#*+)#+)#程序设计语言与编译注意注意:用上述算法可以构造出任意给定文法的分析表用上述算法可以构造出任意给定文法的分析表,但不是所有但不是所有 文法都能构造出上述那种形状的分析表即文法都能构造出上述那种形状的分析表即MA,a=一条的规则或一条的规则或 Error。对于能用上述算法构造分析表的文法我们称为。对于能用上述算法构造分析表的文法我们称为LL(1)文法文法程序设计语言与编译MA,a中只记产生式右部;对=x1x2.xn,在M,a中记xn xn-1.x1;当xn xn-1.x1的x1VT时,x1必为a,x1无须入栈,只移动输入指针。

43、2.2.预测分析表的改进预测分析表的改进 程序设计语言与编译 并非所有文法并非所有文法G G都可以改写成都可以改写成LL(1)LL(1)文法，即使提取左公文法，即使提取左公因子和消除左递归后，也不是因子和消除左递归后，也不是LL(1)LL(1)文法文法.例：文法例：文法G G4 4S SiCtS|iCtSeS|aiCtS|iCtSeS|aC Cb b提取左因子提取左因子S SiCtSS|aiCtSS|aSSeS|eS|C Cb b求求FIRSTFIRST和和FOLLOWFOLLOWFIRST(S)=i,aFIRST(S)=i,aFIRST(S)=e,FIRST(S)=e,FIRST(C)=bF

44、IRST(C)=bFOLLOW(S)=FOLLOW(S)=e,#FOLLOW(S)=FOLLOW(S)=e,#FOLLOW(C)=tFOLLOW(C)=t求预测分析表求预测分析表a ab be ei it t#S SS Sa aS SiCtSSiCtSSS SS SeSeSS SS 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