《编译原理课程教案》第4章：自上而下语法分析.ppt

《《编译原理课程教案》第4章：自上而下语法分析.ppt》由会员分享，可在线阅读，更多相关《《编译原理课程教案》第4章：自上而下语法分析.ppt（74页珍藏版）》请在三一办公上搜索。

1、自上而下语法分析方法,第四章（1）,本章要求,主要内容：语法分析的任务和设计，自上而下语法分析方法及其相关概念，Sample语言语法分析程序的设计重点掌握：语法分析的任务和接口设计，自顶向下语法分析面临的问题及解决方法，掌握First集和Follow集的概念和求解方法，掌握LL(1)文法的判定方法，能够使用递归下降分析方法和预测分析方法实现编写语法分析器，并对一个输入串进行分析。,高级语言的语法结构适合用上下文无关文法来描述，上下文无关文法是语法分析的基础。语法分析是编译过程的核心，其任务是在词法分析识别出正确的单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。,4.1 语法分析的

2、任务,问题：在上一章词法分析中讲解了如何判断源程序中单词的正确性，并输出了正确的单词符号。那么如何知道这些正确的单词是否能构成正确的表达式、语句或程序呢？这就是语法分析的任务。语法分析的任务在词法分析识别出正确的单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。,语法分析在编译系统中所处的位置,语法分析器的输入Token序列：词法分析的输出，是各个单词都正确的源程序的变换形式，是一个有限序列语法分析器的输出分析树：表示方法？见教材 P89错误处理信息：定位、继续编译,4.2 语法分析的接口设计,语法分析器的功能按照语言的语法构成规则,识别输入的符号串能否构成一个句子。这些规则是用文

3、法的产生式来定义的。问题对给定的一个输入串，如何判定它是不是一个句子？方法根据文法的产生式规则，从开始符号出发，看能否推导出与这个输入串匹配的句子。这就需要建立与输入串匹配的语法分析树。,G=(E,i,+,*,(,),P,E)P：E E+E E E*E E(E)E i,解：使用最左推导：E E*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i,例：判定输入串(i+i)*i是否是下述文法的句子？,结论：能够从开始符号出发推导出给定的输入串，因此，是句子。,常用的语法分析方法：,自顶向下分析法：从文法的开始符号出发，向下推导(使用最左推导)，尽可能使用各种产生式，推导出与输入串

4、匹配的句子，从而建立语法树。自底向上分析法：从输入符号串开始，逐步进行归约(最右推导的逆过程)，直至归约到文法的开始符号，从而建立语法树。具体分类：,4.3 自顶向下语法分析及面临的问题,自上而下分析主要是：对任何输入串，试图用一切可能的办法，从文法的开始符号出发，自上而下地为输入串建立一个语法树。从推导的角度看，从开始符号出发，使用最左推导，试图推导出与输入符号串相同的句子。从语法树的角度看，从根节点出发，反复使用所有可能的产生式，谋求输入串的匹配，试图向下构造一棵语法树，其末端节点正好与输入符号串相同。需要反复试探。,例1：设有文法(1)S xAy(2)A*|*现有输入串：x*y 其分析过

5、程如右：,失败，需要退回，重新选取A的侯选式，这时使得分析器的动作不稳定,思考：产生回溯的原因？,问题1：回溯(P67),真正原因是：文法的产生式有问题。,左递归：文法中存在某个AVn，有A A。直接左递归：有产生式A A 间接左递归：,例2：设有文法G(E)：(1)E E+T|T(2)T T*F|F(3)F(E)|i现有输入串i*i+i,分析过程是：,失败：对左递归文法使用最左推导，出现死循环。,思考：产生左递归的原因？,问题2：左递归(P68),真正原因是：文法的产生式有问题。,结论,1.左递归和回溯问题的产生直接与描述语言的文法有关2.应该改造文法，使其不含左递归和回溯，才能进行确定的自

6、顶向下分析,4.3 问题的解决方法,消除左递归消除回溯,消除左递归,1.直接左递归的消除P69：假定产生式为：PP|，将其替换为形式等价的产生式组：,例2：文法 E E+T|T T T*F|F F(E)|i消去左递归后为：,T FTT*FT|,E TEE+TE|,F(E)|i,一般而言，若产生式形式为：AA1|A2|An|1|2|m 将其替换为：,练 习,消去文法GS的左递归,S(T)|a+S|aT T,S|S,例：给定间接左递归文法，请消除左递归,(1)代入(2)消除直接左递归,S Qc|cQ Rb|bR Sa|a,解：第1步：为R、S、Q排序 第2步：代入：将R代入Q,Q代入S，得到新的文

7、 法产生式组：R Sa|a Q Sab|ab|b S Sabc|abc|bc|c 第3步：消去S的直接左递归，得到,S abcS|bcS|cSS abcS|,2.间接左递归的消除方法P69,方法是:反复“提取公共左因子”，使得文法的每个非终结符号的各个候选式的首终结符集两两不相交，来避免回溯。,设产生式为：A1|2|n,消除回溯,例3：有如下两个产生式：if E then S1 else S2;if E then S1;,提取左因子后：if E then S1 B;B else S2|;,练习,提取下述文法的左因子,S(T)|a+S|aT ST T,ST|,问题:如果希望没有回溯，对文法有什么

8、要求？,回溯产生的真正原因是：某非终结符对应多个侯选式，它们右部的第一个终结符相同，从而导致语法分析器选择了错误的侯选式。如果希望没有回溯，对文法有什么要求？,侯选式的首终结符集的定义,即，由该候选式推导出的所有符号串中的第一个终结符的集合。,4.3 LL(1)文法,SApSBqAaAcABbBdB,练习：求给定文法的每个候选式的First集,(1)S xAy(2)A*|*,在右边给定的文法中，A的候选式有两个，其首终结符集为：First(A1)=*First(A2)=*相交,就会产生回溯,因此，只要存在某个非终结符的多个候选式的首终结符集相交，就会在推导的某时刻产生回溯。从而导致语法分析器选

9、择了错误的侯选式。,因此，不产生回溯的条件就是：对非终结符A的任意两个不同的侯选式ai 和aj，都有：First(ai)First(aj)=当要求用A进行匹配时，就能根据所面临的输入字符，准确地选取一个A的侯选式。,非终结符A的首终结符集的定义,即，由该非终结符推导出的所有符号串中的第一个终结符的集合。,SApSBqAaAcABbBdB,练习：求给定文法的每个候选式的First集和每个非终结符的First集。,求非终结符A的First集的算法,求某一非终结符A的首终结符集First(A)的算法为：1.若有产生式Aa,aVT，把a加到First(A)中；2.若有产生式A,把加到First(A)中

10、；3.若有产生式AX，XVN，把First(X)中非元素加到First(A)中；4.若有产生式AX1X2X3.Xk,其中X1X2.XkVN。则当X1X2X3.Xi=(1ik)时，把First(Xi+1.Xk)的非元素加到 First(A)中；当X1X2X3.Xk=时，把First()加入First(A)中5.重复执行上述过程，直到First(A)不再增大,*,*,SApSBqAaAcABbBdB,例：用算法求下述文法的每个非终结符的First集,E TEE+TEE T FTT*FTT F(E)F i,First(F)=(，i First(T)=*，First(E)=+，First(T)=Fir

11、st(F)=(，i First(E)=First(T)=(，i,练 习,求下列文法的每个非终结符的First集,是否满足：没有左递归，每个侯选式的首终结符集不相交这两个条件，就一定能进行有效的自顶向下分析呢？,思考题,确定的自上而下的分析举例1：对于文法G1S：SpA SqB AcAd Aa对输入串pccadd，自上而下的推导过程是：S=pA=pcAd=pccAdd=pccadd对应的分析树：,例2：对于文法G2S：,SAp SBqAa AcA Bb BdB,输入串ccap，自上而下的推导过程是：S=Ap=cAp=ccAp=ccap,例3：使用下述文法对 i+i 进行分析：,E TE E+TE

12、|T FT T*FT|F(E)|i,第一步：iFirst(TE)iFirst(FT)iFirst(F),第三步：+First(E),第二步：+first(T)用自动匹配 不读输入符号,LL(1)分析条件,后随符号集的定义,假定S是文法的开始符号，对于AN：Follow(a)=a|SAa，aT 特别，若 SA，则，#FOLLOW(A)当非终结符A面临a时，a不属于A的任何侯选首终结符集，但A的某个候选首终结符集中含，只有当a FOLLOW(A)时才能自动进行匹配。,*,*,对右边给定的文法，求A的后随符号集follow(A),SApAa|AcAAaA,follow(A)=p,求非终结符A的Fol

13、low集的算法,1.如果A是开始符号，Follow(A)2.若有产生式BAa,aVT，则把a加入到Follow(A)中；3.若有产生式BAX，XVN，则把First(X)中非元素加入Follow(A)中；4.若BA 或 BA，=，则把Follow(B)加入到Follow(A)中；5.连续使用上述规则，直到Follow(A)不再增大。,*,例:求下题的Follow集,SApSBqAaAcABbBdB,解：Follow(S)=#Follow(A)=p Follow(B)=q,规则1,规则2,规则2,练 习,1.E TE2.E+TE3.E 4.T FT5.T*FT6.T 7.F(E)8.F i,fo

14、llow(E)=#，)follow(E)=follow(E)=#，)follow(T)=(first(E)-)follow(E)=#,),+follow(T)=follow(T)=#，)，+follow(F)=(first(T)-)follow(T)=*,#,),+,E是开始符号，应用规则1，根据产生式7，应用规则2,根据产生式1，应用规则4,根据产生式2，应用规则3，根据产生式2，3，应用规则4,根据产生式4，应用规则4,根据产生式4，应用规则3根据产生式4，6，应用规则4,求下题的Follow集,(对文法进行不带回溯的确定的自顶向下分析的条件)，据此判别是否为LL(1)文法。(1)文法不含

15、左递归(2)对文法中的任一个非终结符A的各个候选式的首终结符集两两不相交，即：若A1|2|n，则 First(ai)First(aj)=(i j)(3)对文法中的每个非终结符A,若它的某个首终结符集含有，则 First(A)Follow(A)=,LL(1)文法的定义,LL(1)文法的判别,根据 LL(1)的三个条件来判断.判别步骤:1.首先检查是否含有左递归2.若无，计算First集,判别是否满足条件2(即是否有回溯)3.若存在某个A=,求A的 Follow集，并判别条件(3)是否满足(是否可以使用-产生式进行匹配),*,例：判断下述文法是否是LL(1)文法：S aASS bA bAA,解：(

16、1)该文法不含左递归(2)First(SaAS)=a First(Sb)=b First(AbA)=b First(A)=S和A的侯选式的first集都不相交，满足条件2(3)由于 First(A)Follow(A)=First(S)=a,b Follow(A)First(A bA)不满足条件3，则不是LL(1)文法,练 习,判断给定的文法是否为LL(1)文法，若不是，进行改造,解答：First(Aab)=a;First(Aa)=a;不满足条件2，故不是LL(1)文法,改造方法：(消除回溯提取公因子)SxAy;Aa(b|)=SxAy;AaA;A b|,S xAyA ab|a,例3：使用下述文法

17、对 i+i 进行分析：,E TE E+TE|T FT T*FT|F(E)|i,第一步：iFirst(TE)iFirst(FT)iFirst(F),第三步：+First(E),第二步：+first(T)First(T)，+Follow(T)自动匹配,不读输入符号,LL(1)分析过程,follow(E)=#，)follow(E)=follow(E)=#，)follow(T)=follow(E)(first(E)-)=#,),+follow(T)=follow(T)=#，)，+follow(F)=(first(T)-)follow(T)=*,#,),+,LL(1)文法的分析过程,假设要用非终结符A进

18、行匹配，面临输入符号a，A的所有侯选式为：A1|2|n分析过程为：(总结)若a First(Ai),使用i去匹配。若a不属于任何一个产生式的首终结符集，(1)若不属于任何一个 First(Ai)，则出错。(2)若属于某个First(Ai),同时a Follow(A),则让A 与自动匹配；否则，a的出现是一种语法错误。,4.4 递归下降分析方法,是进行语法分析的一种方法要求文法是LL(1)文法实现思想：识别程序由一组过程组成。每个过程对应于文法的一个非终结符号。每一个过程的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的过程来完成。,基本架构(1),对于每个

19、非终结符号的产生式Uu1|u2|un处理的方法如下：U()ch=当前符号;if(ch是u1符号串的第一个符号)处理u1 else if(ch是u2符号串的第一个符号)处理u2elseerror(),由于无回溯的文法保证选择是唯一的。当存在时，可以用error()替代为return;这样可以较晚发现错误。约定：进入这个过程时，已读入U的第一个符号。离开这个过程时，下一个符号已经被读到当前符号。,基本架构(2),对于U的每个右部ui=x1x2xn的处理架构如下：处理x1的程序；处理x2的程序；处理xn的程序；如果右部为空，则不处理。,基本架构(3),对于右部中的每个符号xi如果xi为终结符号：If

20、(x=当前输入符号串中的符号)NextCh()；return;else出错处理如果xi为非终结符号，直接调用相应的过程：xi(),P74 过程对应于前述的文法：,E TEE+TE|T FTT*FT|F(E)|i,在给定的语法定义中选择与IF语句有关的产生式。:=if then else:=:=|=|=:=:=:=:=|:=0|1|2|3|9,如：对应于产生式:=if then 的过程的算法描述为：,ifs()gettoken();If(token!=“if”)error;getnexttoken();bool_expr();getnexttoken();If(token!=“then”)err

21、or;getnexttoken();exe_sentence();,相应于产生式：:=的过程：,bool_expr()gettoken();handle_varible();Getnexttoken();If(token not in!(|=|=)error;Getnexttoken();handle_varible();,请写出for语句的递归下降的分析程序：,:=for:=to do:=|:=*|/|:=:=|:=:=:=.,递归分析程序的优点,实现思想简单明了。程序结构和语法规则直接对应。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。需要书写程序的语言支持递归调用。如果

22、递归调用机制是高效的，那么分析程序也是高效的。,4.5 预测分析程序,递归下降分析法：采用递归过程。因此实现分析程序所使用的高级语言必须支持递归过程才行。预测分析法是自顶向下分析的另一种方法。使用下推自动机的方式实现。使用一个二维分析表和栈联合进行控制来实现分析。,预测分析器模型,分析表M:是一个从VN(VT#)到产生式的映射。在分析时遇到A和a时，应该选择MA,a中存放的产生式。如果MA,a为空，表示出现语法错误。分析表格式:,第1列为非终结符,第1行为终结符+#,每个元素为产生式或空,E TEE+TE|T FTT*FT|F(E)|i,总控程序:,将#压入堆栈中，将开始符号S压入堆栈中读取第

23、一个输入符号到a；循环执行下述操作：栈顶符号弹出放入X中；如果X为终结符号：如果X=a!=#，表明成功匹配a符号;读取下一个符号到a，否则出错；如果X=#如果X=a，分析结束，接受句子。如果 X!=a，出错处理。如果X为非终结符号,则查分析表M:如果MX,a为空，出错处理。如果MX,a=X1 X2Xn,则:将右部Xn X2 X1反序压入堆栈中。,预测分析过程,下面用预测分析方法对输入串i+i*i#进行分析，给出栈的变化过程如下：,构造预测分析表,预测分析过程的总控程序是固定的。对于某个文法，分析表是分析过程的核心。表中MA,a=AX1X2Xn 表示对应于X1X2Xn字的首终结符可以是a。就是说

24、X1X2Xn=aw。可以通过这个方式来确定分析表中的值。(即：求首终结符),*,预测分析表的构造算法,对文法的每个文法符号X构造First(X)对于每一产生式 A,对于每个终结符aFirst(),将A填入 MA,a；如果First()，则构造Follow(A)，对任何元素 bFollow(A)，将A填入MA,b；将所有无定义的 MA,a 标上错误标志。,如果文法是LL(1)文法，其预测分析表中没有多重定义的元素，可以进行确定的分析。,例：求对应于下述文法的预测分析表：,1.首先求first集,E TEE+TE|T FTT*FT|F(E)|i,First(E)=(，i First(E)=+，Fi

25、rst(T)=(，i First(T)=*，First(F)=(，i,2.由于First(E),First(T),求E和T的Follow集,Follow(E)=#，)Follow(T)=#，)，+,3.根据集合的值填表，得到,综合练习,设文法G(S)：S(L)|aS|aLL，S|S(1)消除左递归和回溯；(2)计算每个非终结符的First和Follow集；(3)构造预测分析表。,预测分析表,First(S)(,a Follow(S)#,，,)First(S)(,a,Follow(S)#,，,)First(L)(,a Follow(L)First(L)，,Follow(L),S(L)|aSS S

26、|LSLL,SL|,4.6自上而下语法分析程序的设计,实现的语法成分包括：(1)带类型的简单变量的说明语句；(2)算术表达式和布尔表达式；(3)简单赋值语句；(4)各种控制语句：如if语句、while语句、repeat语句、for语句,源程序举例：,program example;const i5；vara,b,c:integer;x:char;beginif(a+c*3b)and(b3)then c:=3;x:=2+(3*a)-b*c*8;for x:=1+2 to 3 do b:=100;while ab do c:=5;repeat a:=10;until ab;end.,总控程序的框架

27、,void paser()/*语法分析总控程序*/token=getnexttoken();if(token 不是“program”)error()；/*程序中缺少program*/token=getnexttoken();if(token 不是标识符)error()；/*program后应跟程序名*/token=getnexttoken();if(token 不为;或()error();/*程序也可不带(input,output)*/token=getnexttoken();if(token 是 const)handle_const(token);/*调用常量说明处理*/if(token 是

28、 var)handle_var(token)；/*调用变量说明处理*/token=getnexttoken();if(token 不是 begin)error();/*begin标识可执行程序开始*/token=getnexttoken();ST_SORT(token);/*分类调用处理各个可执行语句*/token=getnexttoken();if(token 不是 end.)error()；/*end.标识整个程序结束*/,语句分类函数ST_SORT(token),功能：根据传递的单词判断应该调用哪个语句的处理函数。,ST_SORT(token)if(token 是 if）ifs()；if

29、(token 是 for）fors()；if(token 是 while）whiles()；if(token 是 repeat）repeat()；if(token 是 标识符）assigns()else error();,可执行语句语法分析的实现举例,if E then S1 else S2;,ifs()/*当读取的首字符是if时，才调用该函数*/token=getnexttoken();/*读下一个单词，是E的一部分*/BEXP();/*调用布尔表达式的语法分析程序*/token=getnexttoken();/*读下一个单词*/if(token!=then)error;token=getnexttoken();ST_SORT();/*用ST_SORT()分类处理then后的不同语句*/token=getnexttoken();if(token=else)/*if then-else结构时处理else部分*/token=getnexttoken();ST_SORT();/*处理else后的可执行语句*/else if(token!=;)error;/*无else的if-then结构，后必有；*/,