程序设计语言编译原理(第三版)第4章.ppt
《程序设计语言编译原理(第三版)第4章.ppt》由会员分享,可在线阅读,更多相关《程序设计语言编译原理(第三版)第4章.ppt(53页珍藏版)》请在三一办公上搜索。
1、第四章语法分析自上而下分析,4.1 语法分析器的功能4.2 自上而下分析面临的问题4.3 LL(1)分析法4.4 递归下降分析程序构造4.5 预测分析程序4.6 LL(1)分析中的错误处理(略),4.1 语法分析器的功能,1.任务:在词法分析识别出单词符号串的基础上,分析并判定程序的语法结构是否符合语法规则。,2.语法分析器的地位:,4.1 语法分析器的功能,3.本质:按文法的产生式,识别输入符号串 是否为一个句子。,4.语法分析方法分类:自上而下分析法自下而上分析法,4.2 自上而下面临的问题,一、基本思想:,1.自上而下:从文法的开始符号出发,向下 推导,推出句子,2.主旨:对任何输入串,
2、试图用一切可能的 办法,从开始符号出发,自上而下 地为输入串建立一棵语法树。,4.2 自上而下面临的问题,二、举例:自上而下方法的分析过程本质上是一种试探过程,是反复使用不同产生式谋求匹配输入串的过程。,4.2 自上而下面临的问题,S,x A y,4.2 自上而下面临的问题,实现上述带回溯试探法的简单途径:让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配,就用这个候选去扩展语法树,并返回“真”值;否则,保持原来的语法树和IP值不变,并返回“假”值。,4.2 自上而下面临的问题,三、困难和缺点,1.文法的左递归性问题 使自上而下的分析过程陷入
3、无限循环,2.回溯问题;3.虚假匹配难以消除;,4.当最终报告分析不成功时,难于知道输入串中 出错的确切位置;,5.采用了一种穷尽一切可能的试探法,效率很低,代价极高.,4.3 LL(1)分析法,一、左递归的消除:,1.规则:(直接左递归消除),PP,PP|P|P|,4.3 LL(1)分析法,4.3 LL(1)分析法,.消除间接左递归:,()把文法的所有按任一种顺序排列成 P1,P2,Pn;按此顺序执行:,()FOR i=1 To n Do Begin For j:=1 To i-1 Do 把形如Pi Pj 的规则改写成 Pi1|2|k 其中Pj1|2|k是关于Pj的所有规则;消除关于Pi规则
4、的直接左递归性 End,4.3 LL(1)分析法,解答,()化简由()所得的文法,即去除那些从开始符号 出发永远无法到达的非终结符的产生规则.,解答:令非终结符排序为 R、Q、Si=1,无法执行fori=2,j=1Q Rb|bR Sa|a Q Sab|ab|b,4.3 LL(1)分析法,i=3,j=1无关系i=3,j=2S Qc|cQ Sab|ab|b S Sabc|abc|bc|c,消除S的直接左递归 S abcS|bcS|cS S abcS|,返回,4.3 LL(1)分析法,二、消除回溯,提取公共左因子,4.3 LL(1)分析法,.消除回溯必须保证:对文法的任何非终结符,当要它去匹配输入串
5、时,能够根据它所面临的输入符号准确地指派它的一个候选去执行任务,并且此候选的工作结果应是确信无疑的。,即:若此候选获得成功匹配,那么,这种匹配决不会是虚假的;若此候选无法完成匹配任务,则任何其它候选也肯定无法完成。,例:设所面临的第一个输入符号为,若能根据不同的输入符号指派相应的候选 作为全权代表去执行任务,那就肯定无需回溯。在这里已不再是让某个候选去试探性地执行任务,而是根据所面临的输入符号准确地指派唯一的一个候选。,4.3 LL(1)分析法,.当不得回溯时,对文法有什么要求?非终结符的各个候选的首符集的交集均为空。,4.3 LL(1)分析法,此时,当要求A匹配输入串时,A根据它所面临的第一
6、个输入符号a,准确地指派某一个候选前去执行任务;这个候选就是那个终结首符集含a的.,即:first()是的所有可能推导的开头终结符或可能的。,3.提取公共左因子A.事实上,许多文法均存在这样的非终结符,其所有候选的终结首符集并非两两不相交。例如:语句if条件then语句else语句 if条件then语句,4.3 LL(1)分析法,B.如何把一个文法改造成任何非终结符的所有候选首符集两两不相交呢?,代价:大量引进新的非终结符和_产生式.,4.3 LL(1)分析法,经过反复提取左因子,就能把每个非终结符(包括新引进者)的所有候选首符集变成两两不相交.,三、分析条件,1.当一个文法不含左递归,并且满
7、足每个非终结符的所有候选首符集两两不相交的条件,是不是就一定能进行有效的自上而下分析了呢?,4.3 LL(1)分析法,例:文法EE+T|TTT*F|FF(E)|i,输入串:,4.3 LL(1)分析法,经消去直接左递归后变成ETEE+TE|TFTT*FT|F(E)i,.由上分析是不是就意味着:当非终结符面临输入符号,且不属于的任意候选首符集,但的某个候选首符集包含时,就一定可以使自动匹配?,分析:只有当是在文法的某个句型中允许跟在后的终结符时,才可能允许自动匹配,否则,在这里的出现是一种语法错误。,4.3 LL(1)分析法,4.3 LL(1)分析法,即:follow(A)是所有句型中出现在紧接A
8、之后的终结符或“”。,当面临输入符号,且 first(A),但first(A),只有当afollow(A)时,才可能允许A自动匹配。,3.LL(1)文法,4.3 LL(1)分析法,构造不带回溯的自上而下分析的文法的条件:(1)文法不含左递归;,(2)文法中每一个非终结符A的各个产生式的候选首符集 两两不相交即:若A1|2|n则first(i)first(j)=(),(3)对文法中的每个非终结符,若它存在某个候选首符 集包含,则first(A)follow(A)=,若一个文法G满足以上条件,则称该文法G为LL(1)文法.,4.LL(1)文法的自上而下分析(有效的无回溯的),分析:A1|2|n,4
9、.3 LL(1)分析法,对非终结符A进行匹配,此时面临的输入符号为a:(1)若afirst(i),则指派i去执行匹配任务;,(2)若a不属于任何一个候选首符集,则若first(i),且afollow(A),则让A与自动匹配;否则,a的出现是一种语法错误.,一.实现思想 对应文法中每个非终结符编写一个递归过程,每个过程的功能是识别由该非终结符推出的串,当某非终结符的产生式有多个侯选时能够按LL(1)形式可唯一地确定选择某个侯选进行推导.,4.4 递归下降分析程序构造,二.基本构造方法1.基本构造方法:对文法的每个非终结符号,都根据其产生式 的各个候选式的结构,为其编写一个对应的子程序(或函数),
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 程序设计语言 编译 原理 第三
链接地址:https://www.31ppt.com/p-6596248.html