《编译原理实践及应用》第4章自上而下语法分析-PPT.ppt

《《编译原理实践及应用》第4章自上而下语法分析-PPT.ppt》由会员分享，可在线阅读，更多相关《《编译原理实践及应用》第4章自上而下语法分析-PPT.ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、规则是用文法的产生式来定义的。问题 对给定的一个输入串，如何判定它是不是一个句子？方法 根据文法的产生式规则，从开始符号出发，看能否推导出与这个输入串匹配的句子。这就需要建立与输入串匹配的语法分析树。7G=(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是否是下述文法的句子？结论：能够从开始符号出发推导出给定的输入串，因此，是句子。8大家有疑问的，可以询问和交流可以互相讨论下，但要小声点可以互相讨论下，但要小声点9 常用的语法分析方法：自顶向下

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

5、相同。需要反复试探。11 例1：设有文法(1)S xAy(2)A*|*现有输入串：x*y 其分析过程如右：Sx A y*失败，需要退回，重新选取A的侯选式，这时使得分析器的动作不稳定思考：产生回溯的原因？x*y输入符号串：问题1：回溯(P67)真正原因是：文法的产生式有问题。12左递归：文法中存在某个A Vn，有A A。直接左递归：有产生式A A 间接左递归：例2：设有文法G(E)：(1)E E+T|T(2)T T*F|F(3)F(E)|i现有输入串i*i+i,分析过程是：EE+TE+TE+T失败：对左递归文法使用最左推导，出现死循环。思考：产生左递归的原因？问题2：左递归(P68)真正原因是

6、：文法的产生式有问题。13 结论1.左递归和回溯问题的产生直接与描述语言的文法有关2.应该改造文法，使其不含左递归和回溯，才能进行确定的自顶向下分析144.3 问题的解决方法 消除左递归 消除回溯15 消除左递归1.直接左递归的消除P69：假定产生式为：PP|，将其替换为形式等价的产生式组：例2：文法 E E+T|T T T*F|F F(E)|i消去左递归后为：T FTT*FT|PP P P E TEE+TE|F(E)|i16 一般而言，若产生式形式为：AA1|A2|An|1|2|m 将其替换为：A 1 B|2 B|m BB 1 B|2 B|n B|17练 习 消去文法GS的左递归S(T)|a

7、+S|aT T,S|SS(T)|a+S|aT STT,ST|答案：18例：给定间接左递归文法，请消除左递归(1)代入(2)消除直接左递归S Qc|cQ Rb|bR Sa|a解：第1步：为R、S、Q排序 第2步：代入：将R代入Q,Q代入S，得到新的文 法产生式组：R Sa|a Q Sab|ab|b S Sabc|abc|bc|c 第3步：消去S的直接左递归，得到S abcS|bcS|cSS abcS|2.间接左递归的消除方法P6919 方法是:反复“提取公共左因子”，使得文法的每个非终结符号的各个候选式的首终结符集两两不相交，来避免回溯。设产生式为：A1|2|n A AA 1|2|n替换为：消除

8、回溯20 例3：有如下两个产生式：if E then S1 else S2;if E then S1;提取左因子后：if E then S1 B;B else S2|;21练习 提取下述文法的左因子S(T)|a+S|aT ST T,ST|S(T)|aS S+S|T STT,ST|S答案:22问题:如果希望没有回溯，对文法有什么要求？回溯产生的真正原因是：某非终结符对应多个侯选式，它们右部的第一个终结符相同，从而导致语法分析器选择了错误的侯选式。如果希望没有回溯，对文法有什么要求？23对不含左递归的文法G，对某非终结符的侯选式：First()=a|a,aVT 若，则 First()*侯选式的首终

9、结符集的定义即，由该候选式推导出的所有符号串中的第一个终结符的集合。4.3 LL(1)文法24 例：对右边的文法G，每个候选式的First集为：S ApA a|A cAA aAFirst(Ap)=a,c,pFirst(a)=aFirst()=First(cA)=cFirst(aA)=a解：25 S ApS BqA aA cAB bB dB 练习：求给定文法的每个候选式的First集First(S1)=First(Ap)a,c First(S2)=First(Bq)=b,d First(A1)=aFirst(A2)=cFirst(B1)=bFirst(B2)=d解：26(1)S xAy(2)A*

10、|*在右边给定的文法中，A的候选式有两个，其首终结符集为：First(A1)=*First(A2)=*相交,就会产生回溯 因此，只要存在某个非终结符的多个候选式的首终结符集相交，就会在推导的某时刻产生回溯。从而导致语法分析器选择了错误的侯选式。27 因此，不产生回溯的条件就是：对非终结符A的任意两个不同的侯选式ai 和aj，都有：First(ai)FirstFirst(aj)=当要求用A进行匹配时，就能根据所面临的输入字符，准确地选取一个A的侯选式。28非终结符A的首终结符集的定义即，由该非终结符推导出的所有符号串中的第一个终结符的集合。对不含左递归的文法G，对某非终结符A：First(A)=

11、a|A a,aVT 若A，则 First(A)*29 S ApS BqA aA cAB bB dB 练习：求给定文法的每个候选式的First集和每个非终结符的First集。解：First(A)=a,cFirst(B)=b,dFirst(S)=a,c,b,d30求非终结符A的First集的算法 求某一非终结符A的首终结符集First(A)的算法为：1.若有产生式Aa,aVT，把a加到First(A)中；2.若有产生式A,把加到First(A)中；3.若有产生式AX，XVN，把First(X)中非元素加到First(A)中；4.若有产生式AX1X2X3.Xk,其中X1X2.XkVN。则当X1X2X

12、3.Xi=(1ik)时，把First(Xi+1.Xk)的非元素加到 First(A)中；当X1X2X3.Xk=时，把First()加入First(A)中 5.重复执行上述过程，直到First(A)不再增大*31 S ApS BqA aA cAB bB dB 例：用算法求下述文法的每个非终结符的First集First(A)=a,cFirst(B)=b,dFirst(S)=First(A)First(B)=a,c,b,d 解：32 E TEE+TEE T FTT*FTT F(E)F i First(F)=(，i First(T)=*，First(E)=+，First(T)=First(F)=(，i First(E)=First(T)=(，i 练 习求下列文法的每个非终结符的First集 33是否满足：没有左递归，每个侯选式的首终结符集不相交这两个条件，就一定能进行有效的自顶向下分析呢？思考题34确定的自上而下的分析v举例1：对于文法G1S：SpA SqB AcAd Aa对输入串pccadd，自上而下的推导过程是：S=pA=pcAd=pccAdd=pccadd对应的分析树：35