第4章 语法分析——自上而下分析.ppt_第1页
第4章 语法分析——自上而下分析.ppt_第2页
第4章 语法分析——自上而下分析.ppt_第3页
第4章 语法分析——自上而下分析.ppt_第4页
第4章 语法分析——自上而下分析.ppt_第5页
已阅读5页,还剩35页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第4章 语法分析 自上而下分析,4.1 语法分析器的功能 4.2 自上而下分析面临的问题 4.3 LL(1)分析法 4.4 递归下降分析程序构造 4.5 预测分析程序,第4章 语法分析 自下而上分析,语法分析器的位置,语法分析器,语法分析器的输入 Token序列:词法分析产生的输出,是各个单词都正确的源程序,是一个有限序列 语法分析器的功能 按照语言的语法构成规则, 识别输入的符号串能否构成一个句子。规则是用文法的产生式来定义的。 对给定一个输入串,如何判定它是不是一个句子? 根据文法的产生式规则,从开始符号出发,看能否推导出这个输入串匹配的句子。这就需要建立与输入串匹配的语法分析树。 语法分

2、析器的输出 分析树:如何表示? P89 错误处理信息:定位、继续编译,常用的语法分析方法:根据建立语法分析树的方法不同,语法分析方法有两类:,自上而下分析法:从文法的开始符号出发,向下推导(使用最左推导) ,尽可能使用各种产生式,推导出与输入串匹配的句子。 自下而上分析法:从输入符号串开始,逐步进行归约(最右推导的逆过程),直至归约到文法的开始符号。,自顶向下分析,自上而下分析的主旨是:对任何输入串,试图用一切可能的办法,从文法的开始符号出发,自上而下地为输入串建立一个语法树。 从推导的角度看,从开始符号出发,使用最左推导,试图推导出与输入符号串相同的句子。 从语法树的角度看,从根节点出发,反

3、复使用所有可能的产生式,谋求输入串的匹配,试图向下构造一棵语法树,其末端结点正好与输入符号串相同。 这是一个反复试探的过程。,自顶向下分析面临的问题,问题1:回溯,例1:设有文法 (1) S - xAy (2) A - *|* 现有输入串:x*y 其分析过程如下:,失败,需要退回,重新选取A的侯选式 这时使得分析器的动作不稳定,产生的原因?,问题2:左递归 左递归:是左递归的,如果一个文法中存在某个非终结符号A,使A A。 如果是A A,则称为直接左递归,否则称为间接左递归。,例2:设有文法: E-E+T|T T-T*F|F F-(E)|i 现有输入串i*i+i, 其分析过程是:,失败:由于使

4、用最左推导,对左递归文法进行自顶向下分析时,会导致死循环。,产生的原因?,结论,左递归和回溯问题的产生直接与描述语言的文法有关 因此,要对文法进行确定的自顶向下分析应该改造文法,使其不含左递归和回溯,左递归的消除,1. 直接左递归的消除: 假定产生式为:PP|,将其替换为形式等价的产生式组:,例2:文法 E - E+T|T T-T*F|F F-(E)|i 消去左递归后为:,E - TE E-+TE| T-FT T-*FT| F-(E)|i,一般而言,产生式为:AA1|A2|An|1|2|m 将其替换为:,2. 间接左递归的消除 (1) 代入 (2) 消除直接左递归,回 溯,回溯产生的真正原因是

5、:某非终结符对应多个侯选式,它们右部的第一个终结符相同,从而导致语法分析器选择了错误的侯选式。 如果希望没有回溯,对文法有什么要求?,定义:对G的所有非终结符的每个侯选式定义首终结符集: First() = a| a,aVT 若 ,则 First(),因此,不产生回溯的条件就是: 对非终结符A的任意两个不同的侯选式ai 和aj , 都有: First(ai) First(aj) = 当要求用A进行匹配时,就能根据所面临的输入字符,准确地选取一个A的侯选式。,消除回溯的方法,反复使用“提取公共左因子”的方法来改造文法,使得文法的每个非终结符号的各个候选式的首终结符两两不相交,来避免回溯。 例:,

6、设产生式为:A1|2|n 将其替换为:,例3:有如下两个产生式: if E then S1 else S2; if E then S1; 提取左因子后: if E then S1 B; B else S2 | ;,是否满足:没有左递归,每个侯选式的首终结符集不相交这两个条件,就一定能进行有效的自顶向下分析呢? 例:使用下述文法对 i + i 进行分析:,E TE E +TE| T FT T *FT| F (E)|i,第一步:ifirst(TE) ifirst(FT) ifirst(F),第三步:+first(E) ,LL(1)分析条件:,并不是在任何情况下,A面对输入符号a, a不属于A的任何

7、侯选式,但A中含产生式时都可以使用自动匹配。,定义(后随符号集):假定S是文法的开始符号,对于AN: FOLLOW(A)=a|SAa,aT 特别,若 SA,则,# FOLLOW(A) 因此,当非终结符A面临a时, 且a不属于A的任何侯选首终结符集,但A的某个候选首终结符集中含,只有当a FOLLOW(A)时才能自动进行匹配。,*,*,LL(1) 文法:(对文法进行不带回溯的确定的自顶向下分析的条件),据此判别是否为LL(1)文法。 (1) 文法不含左递归 (2) 对文法中的任一个非终结符A的各个产生式的侯选首终结符集两两不相交,即:若 A1|2|n ,则 First(ai) First(aj)

8、 = ( i j ) (3) 对文法中的每个非终结符A,若它存在某个首选符集含有 ,则 First(A) Follow(A) = ,LL(1)文法的分析过程,(P73)假设要用非终结符A进行匹配,面临输入符号a,A的所有侯选式为: A1|2|n 分析过程为: 若a First(Ai),则使用i去执行匹配任务。 若a不属于任何一个产生式的首选符集, (1)若不属于任何一个 First(Ai),则出错。 (2)若属于某个First(Ai),同时a Follow(A), 则让A 与自动匹配;否则,a的出现是一种语法错误。,两个集合的构造,1、FIRST 2、FOLLOW,1、FIRST集的求法,(1

9、)文法符号的终结首符集:FIRST(X) XVT FIRST(X) =X XVN, 需观察X为左部的产生式规则,FIRST集的求法,Aa.,A1| 2|.| n FIRST(A),A,AX1X2.XK,a. X2.XK,FIRST(X1),FIRST(X2),.,X2.XK, . ,FIRST集的求法,例:求下面每个非终结符号的FIRST集合: E TE E +TE |T FTT *FT |F (E) | i,FIRST(E) = FIRST(E )=FIRST(T) =FIRST(T )=FIRST(F) =,(,i ,+, ,*, ,(, i ,(, i ,1、FIRST集的求法,(1)文

10、法符号的终结首符集:FIRST(X) XVT FIRST(X) =X XVN, 需观察X为左部的产生式规则,(2)候选式的终结首符集:FIRST() =X1X2Xn,2、FOLLOW集的求法,BA,FOLLOW(A),BA,若A是开始符号,#,FOLLOW集的求法,例:求下面每个非终结符号的FOLLOW集: E TE E +TE |T FTT *FT |F (E) | i,FIRST(E) = (, i FIRST(E )= +, FIRST(T) = (, i FIRST(T )= *, FIRST(F) = (, i ,FOLLOW(E) = FOLLOW ( E )=FOLLOW (T)

11、 =FOLLOW (T )=FOLLOW (F) =, #, ) , #, ) , +,#, ) , +,#, ) , *,+,#, ) ,练习:求下题的FIRST和FOLLOW集合。 Sa | (T) TST T ,ST | ,4.4 递归下降分析程序的构造,void E() T; E ,4.5 预测分析程序,一、预测分析表构造 二、预测分析程序,4.5 预测分析程序,一、预测分析表的构造 1、FIRST集合构造 2、FOLLOW集合构造 3、预测分析表的构造,3、预测分析表的构造,A1|2|n LL(1)分析过程为: (1)若a FIRST(i),则使用i去执行匹配任务。 (2)若a不属于

12、任何一个产生式的首选符集,则: 若属于某个FIRST(i),同时a FOLLOW(A), 则让A 与自动匹配; 否则,a的出现是一种语法错误。,构造分析表的方法: (1)对每个A,执行第2步和第3步; (2)对每个终结符a FIRST(),把A加至MA,a中; (3)若FIRST(),则对任何b FOLLOW(),把A加至MA,b中; (4)把所有无定义的位置上标上“出错标志”。,例: E TEE +TE |T FTT *FT |F (E) |i,ETE,ETE,E+TE,E ,E ,T FT,T FT,T ,T ,T ,Fi,F(E),T*FT,3、预测分析表的构造,二、预测分析程序,4.5 预测分析程序,初始:,某个中间结果,a. xVN,查看预测分析表: Xx1.xn,下一步产生的结果,b. xVT,X=a

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论