《《编译原理课程教案》第4章(1)自上而下语法分析_图文》由会员分享，可在线阅读，更多相关《《编译原理课程教案》第4章(1)自上而下语法分析_图文（80页珍藏版）》请在金锄头文库上搜索。
1、自上而下语法分析方法第四章（1） 本章要求主要内容：语法分析的任务和设计，自上 而下语法分析方法及其相关概念，Sample 语言语法分析程序的设计 重点掌握：语法分析的任务和接口设计， 自顶顶向下语法分析面临的问题及解决方法 ，掌握First集和Follow集的概念和求解方 法，掌握LL(1)文法的判定方法，能够使用 递归下降分析方法和预测分析方法实现编 写语法分析器，并对一个输入串进行分析 。 高级语言的语法结构适合用上下文无关 文法来描述，上下文无关文法是语法分 析的基础。 语法分析是编译过程的核心，其任务是 在词法分析识别出正确的单词符号串的 基础上，分析并判定程序的语法结构是 否符合语
2、法规则。4.1 语法分析的任务 问题： 在上一章词法分析中讲解了如何判断源程序 中单词的正确性，并输出了正确的单词符号 。那么如何知道这些正确的单词是否能构成 正确的表达式、语句或程序呢？这就是语法 分析的任务。 语法分析的任务 在词法分析识别出正确的单词符号串的基础 上，分析并判定程序的语法结构是否符合语 法规则。语法分析在编译系统中所处的位置 语法分析器的输入 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、，是句子。 常用的语法分析方法： 自顶向下分析法： 从文法的开始符号出发，向下推导(使用最左推 导) ，尽可能使用各种产生式，推导出与输入串 匹配的句子，从而建立语法树。 自底向上分析法： 从输入符号串开始，逐步进行归约(最右推导的 逆过程)，直至归约到文法的开始符号，从而建 立语法树。 具体分类：自顶向下分析 递归下降分析 预测分析(LL) 自底向上分析 算符优先分析 LR分析4.3 自顶向下语法分析及面临的问题 自上而下分析主要是：对任何输入串，试图用 一切可能的办法，从文法的开始符号出发，自 上而下地为输入串建立一个语法树。 从推导的角度看，从开始符号出发，使用最左 推导，试图推导出与输
5、入符号串相同的句子。 从语法树的角度看，从根节点出发，反复使用 所有可能的产生式，谋求输入串的匹配，试图 向下构造一棵语法树，其末端节点正好与输入 符号串相同。 需要反复试探。 例1：设有文法 (1) S xAy (2) A *|*现有输入串：x*y其分析过程如右：SxAy*失败，需要退回，重新选取 A的侯选式，这时使得分析 器的动作不稳定思考：产生回溯的原因？x*y输入符号串 ：问题1：回溯(P67)真正原因是：文法的产生式有问题。左递归：文法中存在某个AVn，有A A。直接左递归：有产生式A A间接左递归： 例2：设有文法G(E)：(1) E E+T | T(2) T T*F | F(3)
6、 F (E) | i 现有输入串i*i+i, 分析过程是：EE+TE+TE+T失败：对左递归文法使用 最左推导，出现死循环。思考：产生左递归的原因？ 问题2：左递归(P68)真正原因是：文法的产生式有问题。 结论1. 左递归和回溯问题的产生直接与描述 语言的文法有关2. 应该改造文法，使其不含左递归和回 溯，才能进行确定的自顶向下分析4.3 问题的解决方法消除左递归消除回溯消除左递归 1. 直接左递归的消除P69： 假定产生式为：PP|，将其替换为形式 等价的产生式组：例2：文法E E+T | TT T*F | FF (E) | i消去左递归后为：T FT T *FT | PP P P E T
7、E E +TE | F (E) | i 一般而言，若产生式形式为： AA1|A2|An|1|2|m 将其替换为：A1 B|2 B |m B B1 B|2 B |n B|练 习 消去文法GS的左递归S (T) | a + S | aT T,S | SS (T) | a + S | aT STT ,ST |答案：例：给定间接左递归文法，请 消除左递归(1) 代入 (2) 消除直接左递归S Qc|c Q Rb|b R Sa|a解：第1步：为R、S、Q排序第2步：代入：将R代入Q, Q代入S，得到新的文 法产生式组：R Sa|a Q Sab|ab|bS Sabc|abc|bc|c第3步：消去S的直接左
8、递归，得到S abcS|bcS|cS S abcS|2. 间接左递归的消除方法P69 方法是:反复 “提取公共左因子”，使得文法的 每个非终结符号的各个候选式的首终结符集两 两不相交，来避免回溯。设产生式为： A1|2|n AAA 1|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 | S (T) | aS S + S | T STT ,ST | S答案:问题: 如果希望
9、没有回溯，对文法 有什么要求？ 回溯产生的真正原因是：某非终结符对 应多个侯选式，它们右部的第一个终结 符相同，从而导致语法分析器选择了错 误的侯选式。 如果希望没有回溯，对文法有什么要求 ？对不含左递归的文法G，对某非终结符的侯选式：First() = a| a,aVT若 ，则 First()* * *侯选式的首终结符集的定义即，由该候选式推导出的所有符号串中的第 一个终结符的集合。4.3 LL(1)文法 例：对右边的文法G，每个候选 式的First集为： SAp Aa | AcA AaAFirst(Ap) = a, c, p First(a ) = a First() = First(cA
10、) = c First(aA) = a解：SAp SBq Aa AcA Bb BdB 练习：求给定文法的每个候选式的First 集First(S1) = First(Ap) a,c First(S2) = First(Bq)=b,d First(A1) = a First(A2) = c First(B1) = b First(B2) = d解：(1) S xAy (2) A *|* 在右边给定的文法中，A 的候选式有两个，其首终 结符集为： First(A1) = * First(A2) = * 相交,就会产生回溯 因此，只要存在某个非终结符的多个候选式的 首终结符集相交，就会在推导的某时刻
11、产生回溯 。从而导致语法分析器选择了错误的侯选式。 因此，不产生回溯的条件就是： 对非终结符A的任意两个不同的侯选式ai 和aj ，都有： First(ai) FirstFirst( (aj) = 当要求用A进行匹配时，就能根据所面临的输入 字符，准确地选取一个A的侯选式。非终结符A的首终结符集的定义即，由该非终结符推导出的所有符号串中 的第一个终结符的集合。对不含左递归的文法G，对某非终结符A：First(A) = a| A a,aVT若A ，则 First(A)* * *SAp SBq Aa AcA Bb BdB 练习：求给定文法的每个候选式的First集和每 个非终结符的First集。
12、解：First(A)=a,c First(B)=b,d First(S)=a,c,b,d求非终结符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。则 当X1X2X3.Xi =(1ik)时，把 First(Xi+1.Xk)的非元素加到 First(A)中； 当X1X2X3.Xk=时，把First()加入First(A)中
13、 5.重复执行上述过程，直到First(A)不再增大*SAp SBq Aa AcA Bb BdB 例：用算法求下述文法的 每个非终结符的First集First(A) = a,c First(B) = b,d First(S) = First(A) First(B)= a,c,b,d 解： E TE E +TE E T FT T *FT T F (E) F i First(F) = ( ，i First(T) = *， First(E) = +， First(T) = First(F) = ( ，i First(E) = First(T) = ( ，i 练 习求下列文法的每个非终结符的First
14、集 是否满足：没有左递归，每个侯选式的 首终结符集不相交这两个条件，就一定 能进行有效的自顶向下分析呢？思考题确定的自上而下的分析v举例1：对于文法G1S：SpASqBAcAdAa 对输入串pccadd，自上而下的推导过程是： S = pA = pcAd = pccAdd = pccadd 对应的分析树：v例2：对于文法G2S：SAp SBq AaAc A Bb Bd B输入串ccap，自上而下的推导过 程是： S = Ap = cAp = ccAp = ccap 例3：使用下述文法对 i + i 进行分析：E TEE +TE| T FTT *FT | F (E)|i第一步：iFirst(TE)iFirst(FT)iFirst(F)ETEFTi第三步：+First(E) 第二步：+first(T)用自动匹配不读输入符号+TEFTiLL(1)分析条件后随符号集的定义 假定S是文法的开始符号，对于AN： Follow(a)=a|SAa，aT 特别，若 SA，则，# FOLLOW(A) 当非终结符A面临a时， a不属于A的任何侯选首 终结符集，但A的某个候选首终结符集中含，只 有当a FOLLOW(
