自顶向下语法分析方法.ppt

上传人：小飞机

文档编号：4941587

上传时间：2023-05-24

格式：PPT

页数：88

大小：687.50KB

《自顶向下语法分析方法.ppt》由会员分享，可在线阅读，更多相关《自顶向下语法分析方法.ppt（88页珍藏版）》请在三一办公上搜索。

1、第五章自顶向下语法分析方法,2023/5/24,自顶向下语法分析方法,2,语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)常用的语法分析方法有自顶向下分析和自底向上分析,2023/5/24,自顶向下语法分析方法,3,自顶向下分析法也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子。确定的自顶向下分析方法：对文法有一定的限制，但实现方法简单、直观，便于手工构造或自动生成语法分析器，目前仍是常用的方法之一。不确定的自顶向下分析方法：带回溯的分析方法，是一种穷举的试探方法，效率低，代价高，极少使用

2、,2023/5/24,自顶向下语法分析方法,4,主要内容,5.1 确定的自顶向下的分析思想5.2 LL(1)文法的判别5.3 某些非LL(1)文法到LL(1)文法的等价变换5.4 不确定的自顶向下分析思想5.5 确定的自顶向下分析法,2023/5/24,自顶向下语法分析方法,5,5.1 确定的自顶向下分析思想,确定的自顶向下分析方法，是从文法的开始符号出发，考虑如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符以向下推导，或如何构造一课相应的语法树。,2023/5/24,自顶向下语法分析方法,6,例5.1,文法G1S：S pA|qBA cAd|aB dB|b输入串：W=

3、pccadd,存在推导过程：SpApcAdpccAddpccaddW是文法合法的句子,2023/5/24,自顶向下语法分析方法,7,相应的语法树：,文法G1S：S pA|qBA cAd|aB dB|b输入串：W=pccadd,2023/5/24,自顶向下语法分析方法,8,对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，因此分析过程是唯一的。这个文法有以下特点：(1)每个产生式的右边都由终结符号开始；(2)如果两个产生式有相同的左部，那么它们的右部由不同的终结符号开始。,文法G1S：S pA|qBA cAd|aB dB|b输入串：W=pccadd,2023/5

4、/24,自顶向下语法分析方法,9,例5.2,文法G2S：S Ap|BqA cA|aB dB|b对于输入串：W=ccap,存在推导过程：SApcApccApccapW是文法合法的句子,2023/5/24,自顶向下语法分析方法,10,语法树为：,文法G2S：S Ap|BqA cA|aB dB|b对于输入串：W=ccap,2023/5/24,自顶向下语法分析方法,11,这个文法的特点是：(1)产生式的右部不全是由终结符开始(2)如果两个产生式有相同的左部，它们的右部由不同的终结符或非终结符开始。(3)文法中无空产生式对于相同左部的产生式含有非终结符开始的产生式时，在推导过程中选用哪个产生式不太直观。

6、入符号是属于哪个产生式的首符号集合而决定选择相应产生式进行推导。这样仍能构造确定的自顶向下分析。,2023/5/24,自顶向下语法分析方法,14,例5.3,文法G3S：S aA|dA bAS|对于输入串：W=abd,存在推导过程：SaAabASabSabdW是文法合法的句子,2023/5/24,自顶向下语法分析方法,15,语法树为：,文法G3S：S aA|dA bAS|对于输入串：W=abd,2023/5/24,自顶向下语法分析方法,16,可以看出，当某一非终结符的产生式中含有空产生式时，它的非空产生式中右部的首符号集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的终结符集也不相交，仍

7、可构造确定的自顶向下分析。,2023/5/24,自顶向下语法分析方法,17,设G=(VN,VT,P，S)是上下文无关文法，AVN，S是开始符号FOLLOW（A）=aS A 且a FIRST（），V*，V+若S A,且，则#FOLLOW(A)也可以定义为：FOLLOW（A）=aS Aa且a VT 若有S A,且，则#FOLLOW(A)#为输入串的结束符，或称输入串括号,定义5.2,2023/5/24,自顶向下语法分析方法,18,当文法中含有形如A，A的产生式时，其中AVN,V*。若和不能同时推导出空，假定,，则当FIRST()(FIRST()FOLLOW(A)=时，对于非终结符A的替换仍可唯一地

8、确定候选。即：输入符号 FIRST()：选用产生式A输入符号 FIRST()FOLLOW(A)：选用产生式A,2023/5/24,自顶向下语法分析方法,19,定义5.3,给定上下文无关文法的产生式A，AVN,V*。若，则SELECT(A)=FIRST()若，则SELECT(A)=(FIRST()-)FOLLOW(A),2023/5/24,自顶向下语法分析方法,20,定义5.4,一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式A，A，满足。SELECT(A)SELECT(A)=其中，不能同时。LL(1)文法能够采用确定的自顶向下分析技术,2023/5/24,自

9、顶向下语法分析方法,21,LL(1)文法的含义,第1个L表明自顶向下分析是从左向右扫描输入串第2个L表明分析过程中将用最左推导1表明只需要向右看一个符号便可决定如何推导，即选用哪个产生式,2023/5/24,自顶向下语法分析方法,22,例5.3,文法G3S：S aA|d A bAS|SELECT(S aA)=a SELECT(S d)=d SELECT(A bAS)=b SELECT(A)=a,d,#而SELECT(S aA)SELECT(S d)=ad=SELECT(A bAS)SELECT(A)=ba,d,#=该文法是LL(1)文法，可用确定的自顶向下分析,2023/5/24,自顶向下语法

10、分析方法,23,例5.4,文法G4S：S aAS|b A bA|SELECT(S aAS)=a SELECT(S b)=b SELECT(A bA)=b SELECT(A)=a,b 而SELECT(S aAS)SELECT(Sb)=ab=SELECT(A bA)SELECT(A)=ba,b该文法不是LL(1)文法,2023/5/24,自顶向下语法分析方法,24,5.2 LL(1)文法的判别,当我们选用自顶向下分析技术时，首先必须判别所给文法是否是LL(1)文法，因而对任给文法需计算FIRST，FOLLOW，SELECT集合，进而判别文法是否为LL(1)文法,2023/5/24,自顶向下语法分析

12、first(x)的方法如下：,2023/5/24,自顶向下语法分析方法,28,若xVT，则first(x)x若xVN，且有xa，aVT，则afirst(x)若xVN，x，则first(x)若xVN，y1，y2，yi都VN，若有产生式xy1y2yn，当y1，y2，yi-1都时(1in)，则first(y1)，first(y2)，first(yi1)，first(yi)都包含在first(x)中。e)当上式中所有yi(1in)，则first(x)(first(y1)-)(first(y2)-)(first(yn)-),*,*,2023/5/24,自顶向下语法分析方法,29,first(S)=(f

13、irst(A)-)(first(B)-)b=a,b,first(A)=b=b,first(B)=a=a,first(C)=(first(A)-)first(D)first(b)=a,b,cfirst(D)=a c=a,c,按上面的规则可得上例文法中每个非终结符号的first集合如下：,S AB|bCA|bB|aDC AD|bD aS|c,2023/5/24,自顶向下语法分析方法,30,一个文法符号串的first集合计算方法：,如果文法符号串V*,=X1X2Xn,1、当X1，则first()=first(X1)2、当对任何j（1ji-1，2 i n），first(Xj)first(Xi)，则fi

14、rst()=(first(X1)-)(first(X2)-)(first(Xi-1)-)first(Xi)3、当first(Xj)都含有时(1 j n)，则first()=first(X1)first(X2)first(Xj),*,2023/5/24,自顶向下语法分析方法,31,根据上面规则，每个产生式的右部符号串开始符号集合为：,first(A)first(B)=a,b,b a(first(A)-)first(D)=a,b,cbac,first(AB)=first(bC)=first()=first(aD)=first(AD)=first(b)=first(aS)=first(c)=,文法G

15、S：SAB|bCA|bB|aDC AD|bD aS|c,2023/5/24,自顶向下语法分析方法,32,方法二：由关系图法求文法符号的first集合,1、每个文法符号对应图中的一个结点，终结符结点用符号本身标记，非终结符结点用first(A)标记。2、若文法中有AX，则从对应A的结点到对应X结点连一条箭弧。3、凡是从first(A)结点有路径可到达的终结符结点所标记的终结符都为first(A)的成员。4、根据判别步骤1)确定是否为某非终结符first的成员，若是则将加入该非终结符的first集中。,*,2023/5/24,自顶向下语法分析方法,33,first(S),first(B),firs

16、t(C),first(A),first(D),b,a,c,文法为：S AB|bCA|bB|aDC AD|bD aS|c,(1)规则1：终结符结点用符号本身标记，本文法中有a,b,c。,(2)规则1：非终结符结点用first(A)标记。本文法中有S,A,B,C,D。,(3)规则2：AX，则A到X画一条箭弧。,S AB看成，XA,=B因此从S到A画一条弧。,S AB看成 A，XB,=A,因此从S到B画一条弧。,S bC看成，Xb,=C因此从S到b画一条弧。,同理：从A到b，从B到a，从C到A、D、b，从D到a、c画一条弧。,2023/5/24,自顶向下语法分析方法,34,(4)规则3：first(

17、A)结点有路径可到达的终结符结点所标记的终结符都为first(A)的成员。,所以，first(S)a,bfirst(A)bfirst(B)afirst(C)a,b,cfirst(D)a,c,(5)规则4：若是某非终结符first的成员，则将加入该非终结符的first集中。,所以，first(S)a,b,first(A)b,first(B)a,first(C)a,b,cfirst(D)a,c,2023/5/24,自顶向下语法分析方法,35,follow集的定义：FOLLOW（A）=aS Aa且a VT 若有S A,且，则#FOLLOW(A),（3）计算Follow 集：方法一：根据Follow定

18、义计算：,2023/5/24,自顶向下语法分析方法,36,构造集合FOLLOW的算法,若S为开始符号,则把“#”加入FOLLOW(S)中,(2)若A B(),则把FIRST()-加入FOLLOW(B),设S,A,BVn,算法：连续使用以下规则，直至FOLLOW集合不再扩大,2023/5/24,自顶向下语法分析方法,37,Follow(S)=#Follow(A)=a，#，cFollow(B)=#Follow(C)=#Follow(D)=#,文法为：S AB|bCA|bB|aDC AD|bD aS|c,2023/5/24,自顶向下语法分析方法,38,方法二：由关系图法求非终结符号的follow集,

19、1、每个文法符号和“#”对应图中的一个结点，终结符结点和“#”用符号本身标记，非终结符结点(AVN)用Follow(A)或First(A)标记。2、从开始符号S的Follow(S)结点到“#”号的结点连一条箭弧。3、若文法中有ABX，且，则从Follw(B)结点到FIRST(X)结点连一条弧，当XVT时，则与X相连。,*,2023/5/24,自顶向下语法分析方法,39,4、若文法中有AB，且，则从Follw(B)结点到 Follow(A)结点连一条箭弧。5、对每一first(A)结点，如果有产生式AX，且，则从First(A)结点到 First(X)结点连一条箭弧。6、凡是从Follow(A)

20、结点有路径可以到达的终结符或“#”号的结点，其所标记的终结符或“#”即为Follow(A)的成员。,*,*,2023/5/24,自顶向下语法分析方法,40,文法为：S AB|bCA|bB|aDC AD|bD aS|c,Follow(S)=#Follow(A)=a，#，cFollow(B)=#Follow(C)=#Follow(D)=#,2023/5/24,自顶向下语法分析方法,41,(4)计算Select集：选择集合的定义给定上下文无关文法的产生式A，AVN，V*，若，则Select（A）=First()，若，则Select(A)=（First()-）Follow(A),*,*,2023/5/

21、24,自顶向下语法分析方法,42,(4)计算Select集：每个产生式的Select集合计算为:Select(SAB)=(first(AB)-)Follow(S)=b,a,#Select(S bC)=first(bC)=bSelect(A)=(first()-)Follow(A)=c,a,#Select(Ab)=first(b)=b Select(B)=(first()-)Follow(B)=#Select(BaD)=first(aD)=aSelect(CAD)=first(AD)=b,a,c,因为AB,S AB|bCA|bB|aDC AD|bD aS|c,2023/5/24,自顶向下语法分析

22、方法,43,Select(Cb)=first(b)=b Select(DaS)=first(aS)=a Select(Dc)=first(c)=c所以select的交集为：,Select(SAB)Select(SbC)=b Select(A)Select(Ab)=Select(B)Select(BaD)=Select(CAD)Select(Cb)=b Select(DaS)Select(Dc)=因此该文法不是LL(1)文法。,2023/5/24,自顶向下语法分析方法,44,5.3 某些非LL(1)文法到LL(1)文法的等价变换,判定任何一个给定文法是不是LL(1)文法，一般需要通过判定方法进行

23、判别。若文法中含有直接或间接左递归，含有左公共因子，该文法肯定不是LL(1)文法，要进行变换。,2023/5/24,自顶向下语法分析方法,45,1、提取左公共因子,若文法中含有形如A|的产生式，这导致了对相同左部的产生式其右部的First集相交,也就是Select(A)Select(A)，不满足LL(1)文法的充分必要条件。则须进行提取左公共因子的等价变换:A(|)写成一般形式：AA A,2023/5/24,自顶向下语法分析方法,46,例1：若文法G1的产生式为：SaSbSaSS提取左公因子后得：SaS(b|)S进一步变换：SaSA Ab A S,2023/5/24,自顶向下语法分析方法,47

24、,例2：若文法G2的产生式：Aad ABc BaA BbB,解：A ad A aAc A bBc B aA B bB,Aa(d|Ac),2023/5/24,自顶向下语法分析方法,48,例1经提取左公共因子后文法仍不是LL(1)文法，例2提取左公共因子后文法是LL(1)文法。经过文法提取左公共因子后的文法不一定是LL(1)文法。,A aA A bBcA dA AcB aAB bB,最后变换为：,2023/5/24,自顶向下语法分析方法,49,经过文法提取左公共因子后的文法，若有多余的产生式，则必须进行化简。,例3：若有文法G3的产生式：SaSd S Ac A aS A b,2023/5/24,自

27、共因子后，只解决了相同左部产生式右部的FIRST集不相交问题。当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL(1)文法。否则还需用LL(1)文法的判别方式进行判断才能确定是否为LL(1)文法。,2023/5/24,自顶向下语法分析方法,54,2、消除左递归,一个文法含有下列形式的产生式时，a)AA AVN,V*b)AB B A A,BVN,，V*称为左递归文法。其中a)是直接左递归，b)是间接左递归如果一个文法是左递归时，则不能采用自顶向下分析法。,2023/5/24,自顶向下语法分析方法,55,左递归举例,例1：文法S Sa S b,所产生的语言是：L ban|n0,输入串

28、：baaa#,例2：文法为：AaB ABb BAc Bd,是间接左递归,输入串：adbcbcbc#,是直接左递归,2023/5/24,自顶向下语法分析方法,56,消除左递归的变换方法：,(1)消除直接左递归：方法：改为右递归。如 SSa 改写为：Sb S Sb Sa S|,2023/5/24,自顶向下语法分析方法,57,消除左递归的一般情况,一般情况下，假定关于A的全部产生式是：AA1|A2|Am|1|2|n其中i(1i m)不等于,j(1 j n)不以A开头，消除直接左递归之后改写为：A1A|2A|nAA1 A|2 A|m A|,2023/5/24,自顶向下语法分析方法,58,(2)消除间接

29、左递归：方法：间接左递归直接左递归右递归,例3：文法G6为:AaBABbBAcBd,AaB ABb BaBc BBbc Bd,BaBc|d BBbc,B(aBc|d)B BbcB|,2023/5/24,自顶向下语法分析方法,59,AaBABbB(aBc|d)BBbc B|,2023/5/24,自顶向下语法分析方法,60,（3）消除文法中一切左递归的算法。对文法中一切左递归的消除要求文法中不含回路，即无AA的推导。满足该文法的充分条件是：文法中不包含形如AA的有害规则和A的产生式。,2023/5/24,自顶向下语法分析方法,61,算法步骤,（1）以某种顺序将文法非终结符排列A1,A2 An（2）

30、从A1开始消除左部为A1的产生式的直接左递归，然后把左部为A1的所有规则的右部逐个替换左部为A2右部以A1开始的产生式中的A1，并消除左部为A2的产生式中的直接左递归。继而以同样方式把A1,A2的右部代入左部为A3右部以A1或A2开始的产生式中，消除左部为A3的产生式之直接左递归，直到把左部为A1,A2,An-1的右部替换左部为An的产生式中，从An中消除直接左递归。,2023/5/24,自顶向下语法分析方法,62,算法归结,（1）以某种顺序将文法非终结符排列A1,A2 An（2）for i:=1 to n dobegin for j:=1 to i-1 do 若Aj的全部产生式为：Aj 1|

31、2|k替代形如Ai Ajr的产生式变为：Ai 1r|2r|krend消除Ai规则的一切直接左递归;end;（3）去掉无用产生式,2023/5/24,自顶向下语法分析方法,63,例如：有文法的产生式为：(1)S Qc|c(2)Q Rb|b(3)R Sa|a该文法的每个非终结符为间接左递归。若非终结符排序为S、Q、R。左部为S的产生式(1)无直接左递归，(2)中右部不含S，所以把(1)右部代入(3)得：(4)R Qca|ca|a 再将(2)的右部代入(4)得：(5)R Rbca|bca|ca|a对(5)消除直接左递归得：,2023/5/24,自顶向下语法分析方法,64,(5)R Rbca|bca|

33、语法分析方法,66,下面讲三个例子说明回溯：,1、由于相同左部的产生式的右部First集交集不为空而引起回溯。,例：文法SxAy Aab|a求输入串为xay语法树。,2023/5/24,自顶向下语法分析方法,67,例：文法SxAy Aab|a求输入串为xay语法树。,first(ab)与first(a)的交集不为空,SxAy,若选择Aab，就于xay不匹配,回溯，用Aa就匹配,2023/5/24,自顶向下语法分析方法,68,2、由于相同左部非终结符的右部能，且该非终结符Follow集中含有其右部First集的元素而引起回溯。,例：S aAS|bA bAS|求对输入串ab#的推导树。,*,202

34、3/5/24,自顶向下语法分析方法,69,例：S aAS|bA bAS|求对输入串ab#的推导树。,AFollow(A)=a,bfirst(bAs)=b,2023/5/24,自顶向下语法分析方法,70,3、由于文法含有左递归而引起回溯,例：SSa Sb 若推导baa#,2023/5/24,自顶向下语法分析方法,71,例：SSa Sb 若推导baa#,消除左递归后，再试一遍,2023/5/24,自顶向下语法分析方法,72,由以上例子可以看出：带回溯的自顶向下分析是一个试探过程，当分析不成功时则推翻分析，退回到适当位置再重新试探其余可能的推导。因此，需要记录所选过的产生式，直到把所有可能的推导序列

35、都试完仍不成功，才能确认输入串不是该文法的句子。（为证明输入串不合法，需要穷举或遍历所有的推导）编译程序真正实现时往往边分析边插入语义动作，因而带回溯分析代价很高，效率很低，在实用编译程序中几乎不用。,2023/5/24,自顶向下语法分析方法,73,5.5 确定的自顶向下分析方法,1、递归子程序法：要求文法满足LL(1)文法。是比较简单直观易于构造的一种语法分析方法。PL/0编译程序的语法分析部分就是采用的递归子程序法。基本思想是：对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串。,2023/5/24,自顶向下语法分析方法,74,例：递归子程序实现表达式的语法分

37、n times,slash do begin getsym;factor;endend;,2023/5/24,自顶向下语法分析方法,77,因子=ident|number|（表达式）Procedure factor;begin if sym=ident then getsym elseif sym=number then getsym elseif sym=(then begin getsym;expr;if sym=)then getsym else error end else error end;,2023/5/24,自顶向下语法分析方法,78,2、预测分析方法：自顶向下分析的另一种方法预

38、测分析器的组成：,预测分析程序先进后出栈预测分析表与文法有关,2023/5/24,自顶向下语法分析方法,79,预测分析表可用一个矩阵表示。矩阵元素MA,a中的A表示非终结符，a表示终结符或句子结束符#，矩阵元素MA,a中的内容是一条关于A的产生式，表明当用非终结符A向下推导时，面临输入符a时，所采用的候选产生式，当元素内容无产生式时，表明用A为左部向下推导时遇到了不该出现的符号，因此元素内容为转向出错处理。,2023/5/24,自顶向下语法分析方法,80,(2)分析过程：,#：句子括号S：文法的开始符号X：存放当前栈顶符号的工作单元a：存放当前输入符号a的工作单元,2023/5/24,自顶向下

41、：Select(ETE)=(，i Select(E+TE)=+Select(E)=，#Select(T FT)=(，i Select(T*FT)=*Select(T)=+，#Select(F i)=iSelect(F(E)=(,由上可知有相同左部产生式的Select集合的交集为空，所以文法是LL(1),2023/5/24,自顶向下语法分析方法,86,构造预测分析表：方法：对每个终结符或#用a表示。若aSelect(Aa)，则Aa放入MA,a中。,2023/5/24,自顶向下语法分析方法,87,分析输入串#i+i#的步骤,栈内容栈顶符号当前输入余留串 MX,b 1#E E i+i#E TE2#ET T i+i#T FT3#ETF F i+i#F i4#ETi i i+i#5#ET T+i#T 6#E E+i#E+TE7#ET+i#8#ET T i#T FT 9#ETF F i#F i10#ETi i i#11#ET T#T 12#E E#E 13#,2023/5/24,自顶向下语法分析方法,88,课后作业,1:(3)2:(1),(2),(3),