《第四章自上而下语法分析》由会员分享，可在线阅读，更多相关《第四章自上而下语法分析（82页珍藏版）》请在金锄头文库上搜索。
1、第四章 自顶向下语法分析方法v 自顶向下分析的一般过程和问题 v FIRST和FOLLOW集定义和计算 v LL(1) 文法定义v LL(1)分析程序实现4.1 语法分析概述v语法分析是编译过程的核心，其任务是在词 法分析识别出正确的单词符号串的基础上，分 析并判定程序的语法结构是否符合语法规则。v高级语言的语法结构适合用上下文无关文法 来描述，上下文无关文法是语法分析的基础。语法分析在编译系统中所处的位置 语法分析器的输入 Token序列：词法分析的输出，是各个单词都正 确的源程序的变换形式，是一个有限序列 语法分析器的输出 分析树：表示方法？ 见教材 P89 错误处理信息：定位、继续编译语
2、法分析的接口设计v语法分析器的功能按照语言的语法构成规则, 识别输入的符 号串能否构成一个句子。这些规则是用文 法的产生式来定义的。v问题 对给定的一个输入串，如何判定它是不是 一个句子？v方法 根据文法的产生式规则，从开始符号出发 ，看能否推导出与这个输入串匹配的句子 。这就需要建立与输入串匹配的语法分析 树。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例1：判定输入串(i+i)*i是否是下述文法
3、的句子？结论：能够从开始符号出发推导出给定的输入串，因此，是句子。7 7 7 7例2：已知符号串S=cad 文法GZ: ZcAd Aab|a 求证：SL(GZ) 分析过程 是设法建立一棵语法树, 使语法树的末端结点与 给定符号串相匹配. .1. 1.开始开始: :令令Z Z为根结点为根结点Z Z2. 2.用用Z Z的右部的右部, ,符号串去匹配输入串符号串去匹配输入串 Z Zc cA Ad d完成一步推导完成一步推导Z ZcAdcAd 检查检查 c-cc-c匹配匹配 A A是非终结符是非终结符, ,将匹配任务交给将匹配任务交给A A8 8 8 83. 3. 选用选用A A的右部符号串匹配输入串
4、的右部符号串匹配输入串 A A有两个右部有两个右部, ,选第一个选第一个 c cA Ad da ab bZ Z完成进一步推导完成进一步推导A Aabab 检查检查,a-a,a-a匹配匹配,b-d,b-d不匹配不匹配( (失败失败) ) 但是还不能冒然宣布但是还不能冒然宣布S S L(GZ) L(GZ) 4. 4. 回溯回溯 即砍掉即砍掉A A的子树的子树 改选改选A A的第二右部的第二右部 Z Zc cA Ad da aA Aa a 检查检查 a-aa-a匹配匹配 d-dd-d匹配匹配建立语法树建立语法树, ,末端结点为末端结点为cadcad与与输入输入cadcad相匹配相匹配, , 建立了推
5、导序列建立了推导序列 Z ZcAdcAdcadcad cadcad L(G(ZL(G(Z) )S=cad GZ: S=cad GZ: ZcAdZcAd Aab|aAab|a分析工作要部分析工作要部 分地或全部地分地或全部地 退回去重做叫退回去重做叫 回溯回溯 常用的语法分析方法： 自顶向下分析法： 从文法的开始符号出发，向下推导(使用最左推 导) ，尽可能使用各种产生式，推导出与输入串 匹配的句子，从而建立语法树。 自底向上分析法： 从输入符号串开始，逐步进行归约(最右推导的 逆过程)，直至归约到文法的开始符号，从而建 立语法树。 具体分类：自顶向下分 析递归下降分析 预测分析(LL) 自底向
6、上分析 算符优先分析 LR分析4.2 自顶向下语法分析v自上而下分析主要是：对任何输入串，试图用 一切可能的办法，从文法的开始符号出发，自上 而下地为输入串建立一个语法树。v从推导的角度看，从开始符号出发，使用最左 推导，试图推导出与输入符号串相同的句子。v从语法树的角度看，从根节点出发，反复使用 所有可能的产生式，谋求输入串的匹配，试图向 下构造一棵语法树，其末端节点正好与输入符号 串相同。v需要反复试探。句型的推导v 最左（最右）推导：在推导的任何一步 ，其中、是句型，都是对中的最左（右）非 终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型。复习自顶向下分析方法特点1
7、.分析过程是带有预测的，对输入符号串要预测属于什么 语法成分，然后根据该语法成分的文法建立语法树。2.分析过程是一种试探过程，是尽一切办法(选用不同规则) 设法建立语法树的过程，由于是试探过程，故难免有失败， 所以分析过程需进行回溯，因此我们也称这种方法是带 回溯的自顶向下分析方法。 例1：设有文法 (1) S xAy (2) A |=现有输入串：x=y其分析过程如右：SxAy*失败，需要退回，重新选取 A的侯选式，这时使得分析 器的动作不稳定思考：产生回溯的原因？X=y输入符号串 ：问题1：回溯真正原因是：文法的产生式有问题。回溯问题14141414什么是回溯?分析工作要部分地或全部地退回去
8、重做叫回溯造成回溯的条件：文法中，对于某个非终结符号的规则其右部 有多个选择，并根据所面临的输入符号不能准确 的确定所要选择时，就可能出现回溯。回溯带来的问题：严重的效率低，只有在理论上的意义而无实际意义U:= 1 | 2 | 3 左递归：文法中存在某个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, 分析过程是：EE+TE+TE+T失败：对左递归文法使用 最左推导，出现死循环。思考：产生左递归的原因？ 问题2：左递归真正原因是：文法的产生式有问题。 结论
9、1. 左递归和回溯问题的产生直接与描述语 言的文法有关2. 应该改造文法，使其不含左递归和回溯 ，才能进行确定的自顶向下分析4.3 问题的解决方法v消除左递归v消除回溯4.3.1 消除左递归(1) 直接左递归的消除：假定产生式为：PP|，将其替换为形 式等价的产生式组：例2：文法E E+T | TT T*F | FF (E) | i消去左递归后为：T FT T *FT | PP P P E TE E +TE | F (E) | iv证明的关键步骤：P-P | P- | | | | P- ( | | | | )P- P, P- | | | | P- P, P- | P 一般而言，若产生式形式为：
10、 AA1|A2|An|1|2|m 将其替换为：A1 B|2 B |m B B1 B|2 B |n B|练 习v消去文法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的直接左递归，得到S abcS|bcS|cS S abcS|(2) 间接左递归
11、的消除方法v方法是:反复 “提取公共左因子”，使得文法 的每个非终结符号的各个候选式的首终结符集两 两不相交，来避免回溯。设产生式为： A1|2|n AAA 1|2|n替换为：4.3.2消除回溯v例3：有如下两个产生式： if E then S1 else S2; if E then S1; 提取左因子后： if E then S1 B;B else S2 | ;练习v提取下述文法的左因子S (T) | a + S | aT ST T ,ST | S (T) | aS S + S | T STT ,ST | S答案:问题: 如果希望没有回溯，对文法 有什么要求？v回溯产生的真正原因是：某非终结
12、符对应多 个侯选式，它们右部的第一个终结符相同，从 而导致语法分析器选择了错误的侯选式。v如果希望没有回溯，对文法有什么要求？对不含左递归的文法G，对某非终结符的侯选式：First() = a| a,aVT若 ，则 First()* * *4.4.1 侯选式的首终结符集的定义即，由该候选式推导出的所有符号串中的第 一个终结符的集合。4.4 LL(1)文法 例：对右边的文法G，每个候选 式的First集为： SAp Aa | AcA AaAFirst(Ap) = a, c, p First(a ) = a First() = First(cA) = c First(aA) = a解：SAp SB
13、q 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 =|v在右边给定的文法中，A 的候选式有两个，其首终结 符集为： First(A1) = First(A2) = 相交,就会产生回溯 因此，只要存在某个非终结符的多个候选式的 首终结符集相交，就会在推导的某时刻产生回溯 。从而导致语法分析器选择了错误的侯选式。v因此，不产生
14、回溯的条件就是： 对非终结符A的任意两个不同的侯选式ai 和aj ，都有： First(ai) FirstFirst( (aj) = v当要求用A进行匹配时，就能根据所面临的输入 字符，准确地选取一个A的侯选式。32323232例子设有文法GS: S-Aa | Bb A-d | cA B-b | aB对S: FIRST(Aa)=d,c, FIRST(Bb)=a,b, FIRST(Aa) FIRST(Bb)= 对A: FIRST(d)=d, FIRST(CA)=c, FIRST(d) FIRST(Ca)= 对B: FIRST(b)=b, FIRST(aB)=a, FIRST(b) FIRST(aB)= 若给定 w=abb则自顶而下分析对应的推导为:S=Bb=aBb=abb求非终结符A的First集的算法 求某一非终结符A的首终结符集First(A)的算法为：v1.若有产生式Aa,aVT，把a加到First(A)中；v2.若有产生式A, 把加到First(A)中；v3.若有产生式AX，XVN，把First(X)中非元素 加到First(A)中；v4.若有产生式AX1X2X3.Xk,其中X1X2.XkVN。则当X1X2X3.Xi =(1ik)时，把 First
