资源预览内容
第1页 / 共82页
第2页 / 共82页
第3页 / 共82页
第4页 / 共82页
第5页 / 共82页
第6页 / 共82页
第7页 / 共82页
第8页 / 共82页
第9页 / 共82页
第10页 / 共82页
亲,该文档总共82页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第四章 自顶向下语法分析方法v 自顶向下分析的一般过程和问题 v FIRST和FOLLOW集定义和计算 v LL(1) 文法定义v LL(1)分析程序实现4.1 语法分析概述v语法分析是编译过程的核心,其任务是在词 法分析识别出正确的单词符号串的基础上,分 析并判定程序的语法结构是否符合语法规则。v高级语言的语法结构适合用上下文无关文法 来描述,上下文无关文法是语法分析的基础。语法分析在编译系统中所处的位置 语法分析器的输入 Token序列:词法分析的输出,是各个单词都正 确的源程序的变换形式,是一个有限序列 语法分析器的输出 分析树:表示方法? 见教材 P89 错误处理信息:定位、继续编译语法分析的接口设计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是否是下述文法的句子?结论:能够从开始符号出发推导出给定的输入串,因此,是句子。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的右部符号串匹配输入串的右部符号串匹配输入串 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相匹配相匹配, , 建立了推导序列建立了推导序列 Z ZcAdcAdcadcad cadcad L(G(ZL(G(Z) )S=cad GZ: S=cad GZ: ZcAdZcAd Aab|aAab|a分析工作要部分析工作要部 分地或全部地分地或全部地 退回去重做叫退回去重做叫 回溯回溯 常用的语法分析方法: 自顶向下分析法: 从文法的开始符号出发,向下推导(使用最左推 导) ,尽可能使用各种产生式,推导出与输入串 匹配的句子,从而建立语法树。 自底向上分析法: 从输入符号串开始,逐步进行归约(最右推导的 逆过程),直至归约到文法的开始符号,从而建 立语法树。 具体分类:自顶向下分 析递归下降分析 预测分析(LL) 自底向上分析 算符优先分析 LR分析4.2 自顶向下语法分析v自上而下分析主要是:对任何输入串,试图用 一切可能的办法,从文法的开始符号出发,自上 而下地为输入串建立一个语法树。v从推导的角度看,从开始符号出发,使用最左 推导,试图推导出与输入符号串相同的句子。v从语法树的角度看,从根节点出发,反复使用 所有可能的产生式,谋求输入串的匹配,试图向 下构造一棵语法树,其末端节点正好与输入符号 串相同。v需要反复试探。句型的推导v 最左(最右)推导:在推导的任何一步 ,其中、是句型,都是对中的最左(右)非 终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型。复习自顶向下分析方法特点1.分析过程是带有预测的,对输入符号串要预测属于什么 语法成分,然后根据该语法成分的文法建立语法树。2.分析过程是一种试探过程,是尽一切办法(选用不同规则) 设法建立语法树的过程,由于是试探过程,故难免有失败, 所以分析过程需进行回溯,因此我们也称这种方法是带 回溯的自顶向下分析方法。 例1:设有文法 (1) S xAy (2) A |=现有输入串:x=y其分析过程如右:SxAy*失败,需要退回,重新选取 A的侯选式,这时使得分析 器的动作不稳定思考:产生回溯的原因?X=y输入符号串 :问题1:回溯真正原因是:文法的产生式有问题。回溯问题14141414什么是回溯?分析工作要部分地或全部地退回去重做叫回溯造成回溯的条件:文法中,对于某个非终结符号的规则其右部 有多个选择,并根据所面临的输入符号不能准确 的确定所要选择时,就可能出现回溯。回溯带来的问题:严重的效率低,只有在理论上的意义而无实际意义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:左递归真正原因是:文法的产生式有问题。 结论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 一般而言,若产生式形式为: 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) 间接左递归的消除方法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回溯产生的真正原因是:某非终结符对应多 个侯选式,它们右部的第一个终结符相同,从 而导致语法分析器选择了错误的侯选式。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 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 =|v在右边给定的文法中,A 的候选式有两个,其首终结 符集为: First(A1) = First(A2) = 相交,就会产生回溯 因此,只要存在某个非终结符的多个候选式的 首终结符集相交,就会在推导的某时刻产生回溯 。从而导致语法分析器选择了错误的侯选式。v因此,不产生回溯的条件就是: 对非终结符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
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号