语法分析自上而下分析幻灯片.ppt

《语法分析自上而下分析幻灯片.ppt》由会员分享，可在线阅读，更多相关《语法分析自上而下分析幻灯片.ppt（113页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、语法分析自上而下分析第1页，共113页，编辑于2022年，星期二课程安排课程安排内内 容容讲授课时讲授课时实验课时实验课时第一章第一章 引引 论论2第二章第二章 高级程序语言及其语法描述高级程序语言及其语法描述2第三章第三章 词法分析词法分析实验一实验一 词法分析器（第词法分析器（第6、7、8、9周）周）108第四章第四章 语法分析语法分析-自上而下分析自上而下分析8第五章第五章 语法分析语法分析-自下而上分析自下而上分析实验二实验二 语法分析器（第语法分析器（第13、14、15、16周）周）88第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译8第七章第七章 语义分析及中间代码产生语

2、义分析及中间代码产生8第八章第八章 优优 化化2合合 计计4816第2页，共113页，编辑于2022年，星期二实验时间：实验时间：实验一词法分析：实验一词法分析：第第6、7、8、9周周实验二语法分析：第实验二语法分析：第13、14、15、16周周实验地点：实验地点：计算机系实验中心（计算机系实验中心（5教教910、911）指导教师：指导教师：杨健、张谦杨健、张谦实验安排实验安排杨健杨健：13488702754张谦张谦：18801041780 邮箱：邮箱： 地点：五教地点：五教8层层802图像处理研究室图像处理研究室 第3页，共113页，编辑于2022年，星期二数字媒体制作实验室数字媒体制作实验

3、室910 计计11-12软件开发实验室软件开发实验室911 计计11-34第第6、7、8、9周，都是周，都是周二周二1,2节节实验一实验一 词法分析器（第词法分析器（第6、7、8、9周）周）第4页，共113页，编辑于2022年，星期二第四章第四章 语法分析语法分析-自上而下分析自上而下分析4.1 语法分析器的功能语法分析器的功能4.2 自上而下分析面临的问题自上而下分析面临的问题4.3 LL(1)分析法分析法4.4 递归下降分析程序构造递归下降分析程序构造4.5 预测分析程序预测分析程序第5页，共113页，编辑于2022年，星期二第四章第四章 语法分析语法分析-自上而下分析自上而下分析了解：了

4、解：语法分析器的功能。语法分析器的功能。熟悉：熟悉：预测分析程序、递归下降分析程序的设计方预测分析程序、递归下降分析程序的设计方法。法。掌握：掌握：LL(1)分析法的条件，消除左递归的算法，分析法的条件，消除左递归的算法，预测分析表的构造。预测分析表的构造。第6页，共113页，编辑于2022年，星期二第四章第四章 语法分析语法分析-自上而下分析自上而下分析作业：作业：4.1，4.2第7页，共113页，编辑于2022年，星期二4.1 考虑下面文法考虑下面文法G1:Sa(T)TT,S S（1）消去）消去G1的左递归。然后对每个非终结符，写出的左递归。然后对每个非终结符，写出不带回溯的递归子程序。不

5、带回溯的递归子程序。（2）经改写后的文法是否是）经改写后的文法是否是LL(1)的？给出它的预测分的？给出它的预测分析表。析表。第四章第四章 语法分析语法分析-自上而下分析自上而下分析第8页，共113页，编辑于2022年，星期二4.2 对下面的文法对下面的文法G：ETE E+E TFT T T FPF F*F P(E)a b（1）计算这个文法的每个非终结符的计算这个文法的每个非终结符的FIRST和和FOLLOW。（2）证明这个文法是证明这个文法是LL(1)的。的。（3）构造它的预测分析表。构造它的预测分析表。（4）构造它的递归下降分析程序。构造它的递归下降分析程序。第9页，共113页，编辑于20

6、22年，星期二第三章第三章 词法分析词法分析实验一实验一 词法分析器词法分析器 每次实验结束都必须写出实验报告，报告内容包括：每次实验结束都必须写出实验报告，报告内容包括：实验题目、实验目的和要求，实验的实现（包括主要设实验题目、实验目的和要求，实验的实现（包括主要设计思想、实现算法、主要技术问题的处理方法，及实验计思想、实现算法、主要技术问题的处理方法，及实验结果），结论分析。结果），结论分析。实验二实验二 语法分析器语法分析器第10页，共113页，编辑于2022年，星期二实验二实验二 语法分析器构造语法分析器构造一、目的和要求一、目的和要求 借助于词法分析程序提供的分析结果，编写一个算符优

7、先语借助于词法分析程序提供的分析结果，编写一个算符优先语法分析程序，程序能进行语法结构分析和错误检查并产生相应的法分析程序，程序能进行语法结构分析和错误检查并产生相应的归约信息。同时给出出错信息和错误类型，从而加深对语法分析归约信息。同时给出出错信息和错误类型，从而加深对语法分析的理解。的理解。二、实验内容二、实验内容 给定文法给定文法G和算符优先分析法，构造其算符优先分析程序。文法和算符优先分析法，构造其算符优先分析程序。文法G：语句语句赋值语句条件语句转移语句带标号的赋赋值语句条件语句转移语句带标号的赋 值语句值语句带标号的赋值语句带标号的赋值语句赋值语句赋值语句变量变量=算术表达式算术表

8、达式条件语句条件语句 IF THEN 语句语句 IF THEN 语句语句 ELSE 语句语句第11页，共113页，编辑于2022年，星期二实验二实验二 语法分析器构造语法分析器构造转移语句转移语句GOTO标号标号变量变量标识符标识符标识符标识符字母字母字母字母ABZabz数字数字019算术表达式算术表达式项算术表达式项算术表达式+项算术表达式项算术表达式-项项项项因子项因子项*因子项因子项/因子因子因子因子项项因子因子变量常数变量常数(表达式表达式)布尔表达式布尔表达式关系符关系符=标号标号常数常数常数常数数字数字第12页，共113页，编辑于2022年，星期二实验二实验二 语法分析器构造语法分

9、析器构造三、说明和提示三、说明和提示1.本实验的优先表可以手工先设计好。本实验的优先表可以手工先设计好。2.本实验要求中提出的本实验要求中提出的“产生相应的归约信息产生相应的归约信息”意指在语法分意指在语法分析的过程中，一旦产生归约，在程序上产生并最终输出归析的过程中，一旦产生归约，在程序上产生并最终输出归约产生式序号。约产生式序号。3.出错类型的产生可预先对应优先表中出错栏列表说明出错类型的产生可预先对应优先表中出错栏列表说明其出错类型，并分别编序，当分析中产生错误时以字符串其出错类型，并分别编序，当分析中产生错误时以字符串输出相应表中错误信息。输出相应表中错误信息。4.算法采用一个符号栈的

10、数据结构，既用它存放终结符，算法采用一个符号栈的数据结构，既用它存放终结符，也用它存放非终结符。也用它存放非终结符。第13页，共113页，编辑于2022年，星期二第四章第四章 语法分析语法分析-自上而下分析自上而下分析4.1 语法分析器的功能语法分析器的功能4.2 自上而下分析面临的问题自上而下分析面临的问题4.3 LL(1)分析法分析法4.4 递归下降分析程序构造递归下降分析程序构造4.5 预测分析程序预测分析程序第14页，共113页，编辑于2022年，星期二中间代码中间代码单词符号单词符号语法单位语法单位中间代码中间代码目标代码目标代码词法分析器词法分析器语法分析器语法分析器语义分析与中间

11、代码产生语义分析与中间代码产生器器优化器优化器源程序源程序表表格格管管理理出出错错处处理理目标代码生成器目标代码生成器编译程序总框编译程序总框第15页，共113页，编辑于2022年，星期二本章主要介绍语法分析的处理本章主要介绍语法分析的处理要进行语法分析，必须对语言的语法结构进要进行语法分析，必须对语言的语法结构进行描述。行描述。采用采用正规式正规式和和有限自动机有限自动机可以描述和识别语言的可以描述和识别语言的单词符号；单词符号；用用上下文无关文法上下文无关文法来描述语法规则。来描述语法规则。第四章第四章 语法分析语法分析-自上而下分析自上而下分析第16页，共113页，编辑于2022年，星期

12、二形式化定义：形式化定义：一个上下文无关文法是一个四元式（一个上下文无关文法是一个四元式（VT,VN,S,）VT是一个非空有限集，它的每个元素称为终结符号；是一个非空有限集，它的每个元素称为终结符号；VN是是一一个个非非空空有有限限集集，它它的的每每个个元元素素称称为为非非终终结结符符号号，VTVN=；S是一个非终结符号，称为开始符号；是一个非终结符号，称为开始符号；SVN。是是一一个个产产生生式式集集合合（有有限限），每每个个产产生生式式的的形形式式是是P。其其中中，PVN，(VTVN)。开开始始符符号号S必必须须至至少少在在某某个个产生式的左部出现一次。产生式的左部出现一次。P1|2|n。

13、其其中中，i称称为为是是P的的一一个个候候选选式式。读读作作“定定义义”，直竖读为，直竖读为“或或”,它是元语言符号。它是元语言符号。2.3.1 上下文无关文法上下文无关文法第17页，共113页，编辑于2022年，星期二2.3.1 上下文无关文法上下文无关文法定义：称定义：称 A 直接推出直接推出 ，即，即 A 仅当仅当A 是一个产生式，是一个产生式，且且，(VT VN)*。如果如果 1 2 n，则我们称这个序列是从，则我们称这个序列是从 1到到 n的一个的一个推导推导。若存在一个从。若存在一个从 1到到 n的推导，则称的推导，则称 1可以可以推导推导出出 n。对文法对文法G(E)：E i|E

14、+E|E*E|(E)E (E)(E+E)(i+E)(i+i)第18页，共113页，编辑于2022年，星期二 用用 表示：从表示：从 1出发，经过出发，经过0步步或若干步，可以推出或若干步，可以推出 n。所以所以：即即 或或定义：假定定义：假定G是一个文法，是一个文法，S 是开始符号。如是开始符号。如果果 ，则，则 称是一个称是一个句型句型。仅含终结。仅含终结符号的句型是一个符号的句型是一个句子句子。文法。文法G所产生的句子所产生的句子的全体是一个的全体是一个语言语言，将它记为，将它记为 L(G)。通常，用通常，用 表示：从表示：从 1出发，经过出发，经过一步或若干步，可以推出一步或若干步，可以

15、推出 n。第19页，共113页，编辑于2022年，星期二例：例：(i*i+i)是文法是文法G(E)：E i|E+E|E*E|(E)的一个句子。的一个句子。证明：证明：E (E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E，(E)，(E+E)，(E*E+E)，(i*i+i)是句型。是句型。2.3.1 上下文无关文法上下文无关文法第20页，共113页，编辑于2022年，星期二第四章第四章 语法分析语法分析-自上而下分析自上而下分析4.1 语法分析器的功能语法分析器的功能4.2 自上而下分析面临的问题自上而下分析面临的问题4.3 LL(1)分析法分析法4.4 递归下降分析程序

16、构造递归下降分析程序构造4.5 预测分析程序预测分析程序第21页，共113页，编辑于2022年，星期二4.1 语法分析器的功能语法分析器的功能语法分析的语法分析的任务任务是分析一个文法的句子结构。是分析一个文法的句子结构。语法分析器的语法分析器的功能功能：按照文法的产生式，识别输：按照文法的产生式，识别输入符号串是否为一个句子。入符号串是否为一个句子。策略策略：自上而下分析法，自下而上分析法。：自上而下分析法，自下而上分析法。两种方法反映了两种语法树的构造过程。两种方法反映了两种语法树的构造过程。第22页，共113页，编辑于2022年，星期二源程序源程序单词符号单词符号取下一单取下一单词符号词

17、符号.语法分语法分析树析树词法分词法分析器析器语法分语法分析器析器符号表符号表编译程序编译程序后续部分后续部分图图4.1 语法分析器在编译程序中的地位语法分析器在编译程序中的地位4.1 语法分析器的功能语法分析器的功能第23页，共113页，编辑于2022年，星期二语法分析的方法语法分析的方法-自上而下分析法自上而下分析法(Top-down)基本思想基本思想：它从文法的开始符号出发，反复使用各种：它从文法的开始符号出发，反复使用各种产生式，寻找产生式，寻找“匹配匹配”的的推导推导。从树根到叶子来建立语从树根到叶子来建立语法树。法树。递归下降分析法递归下降分析法：对每个非终结符号构造一个相应的：对

18、每个非终结符号构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。间的信息反馈和联合作用实现对输入串的识别。预测分析程序预测分析程序优点：直观、简单和宜于手工实现。优点：直观、简单和宜于手工实现。第24页，共113页，编辑于2022年，星期二 语法分析的方法语法分析的方法-自下而上分析法自下而上分析法(Bottom-up)基本思想基本思想：从输入串开始，逐步进行：从输入串开始，逐步进行“归约归约”，直到，直到文法的开始符号。即从树末端开始，构造语法树。文法的开始符号。即从树末端开始，构造语法树。

19、从从树叶到树根来建立树叶到树根来建立语法树。语法树。所谓归约，是指根据文法所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。的产生式规则，把产生式的右部替换成左部符号。算符优先分析法算符优先分析法：按照算符的优先关系和结合性：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。质进行语法分析。适合分析表达式。LR分析法分析法：规范归约：规范归约第25页，共113页，编辑于2022年，星期二 G(E)：E i|E+E|E-E|E*E|E/E|(E)给出给出i*i+i的语法树。的语法树。i*i+i E*i+i E*E+i E+i E+E Ei+*EiiEEEE第26页，共11

20、3页，编辑于2022年，星期二第四章第四章 语法分析语法分析-自上而下分析自上而下分析4.1 语法分析器的功能语法分析器的功能4.2 自上而下分析面临的问题自上而下分析面临的问题4.3 LL(1)分析法分析法4.4 递归下降分析程序构造递归下降分析程序构造4.5 预测分析程序预测分析程序第27页，共113页，编辑于2022年，星期二4.2 自上而下分析面临的问题自上而下分析面临的问题自上而下就是从文法的开始符号出发，向自上而下就是从文法的开始符号出发，向下下推导推导，推出句子。，推出句子。自上而下分析的主旨：对任何输入串，试自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号

21、图用一切可能的办法，从文法开始符号(根根结点结点)出发，自上而下地为输入串建立一棵出发，自上而下地为输入串建立一棵语法树语法树。或者说，为输入串寻找一个最左推。或者说，为输入串寻找一个最左推导。导。第28页，共113页，编辑于2022年，星期二例例 文法文法G(E):E iE E+EE E*EE (E)对句子对句子(i+i)最左推导最左推导E(E)(E+E)(i+E)(i+i)4.2 自上而下分析面临的问题自上而下分析面临的问题第29页，共113页，编辑于2022年，星期二例例 假定有文法假定有文法G(S):(1)SxAy (2)A*|*分析输入串分析输入串x*y序号序号 指示器指示器IP指向

22、指向 语法树语法树 最左推导最左推导 说明说明 x*yS根结根结S,当前符当前符xx*yx得匹配得匹配,移动移动IP Sx A ySx A y用用SxAy展开展开S欲用欲用xAy匹配输匹配输入串入串SxAy x*y第30页，共113页，编辑于2022年，星期二序号序号 IP指向指向 语法树语法树 最左推导最左推导 说明说明 Sx*yx A y试用试用A*展展开开ASxAyx*y*x*y*得匹配得匹配,移动移动IP,但但y得不到得不到匹配匹配Sx A y*用用A*展开展开失败失败,回溯回溯,回到回到第第步步Sx A ySxAyx*y第31页，共113页，编辑于2022年，星期二 序号序号 IP指

23、向指向 语法树语法树 最左推导最左推导 说明说明 x*ySx A y试用试用A*展开展开ASxAyx*y*x*y*得匹配得匹配,移动移动IPSx A y*A完成匹配完成匹配,y得得匹配匹配,移动移动IP,输输入串匹配成功入串匹配成功,结束结束Sx A ySxAyx*yx*y*第32页，共113页，编辑于2022年，星期二存在回溯的原因存在回溯的原因文法中非终结符文法中非终结符A的产生式右部称为的产生式右部称为A的候的候选式，如果有多个候选式左端第一个符号相选式，如果有多个候选式左端第一个符号相同，则语法分析程序无法根据当前输入符号同，则语法分析程序无法根据当前输入符号选择产生式，只能试探。选择

24、产生式，只能试探。例例 假定有文法假定有文法G(S):(1)SxAy (2)A*|*分析输入串分析输入串x*y第33页，共113页，编辑于2022年，星期二自上而下分析方法的步骤自上而下分析方法的步骤：（：（带回溯的试探过程）带回溯的试探过程）遇遇非终结符非终结符,就试图用某个候选式就试图用某个候选式展开展开,期望此候选能匹配期望此候选能匹配输入串输入串,若不能匹配若不能匹配,则要则要回溯回溯。遇遇终结符终结符，就进行，就进行匹配匹配，然后移动输入串指针然后移动输入串指针IP指向指向下一个符号。下一个符号。回溯回溯是一项复杂而费时的工作，须废弃已做的许多工作，是一项复杂而费时的工作，须废弃已做

25、的许多工作，恢复到前面的某一情况，效率很低。恢复到前面的某一情况，效率很低。4.2 自上而下分析面临的问题自上而下分析面临的问题第34页，共113页，编辑于2022年，星期二当某个非终结符有多个产生式候选时，可能带来如当某个非终结符有多个产生式候选时，可能带来如下问题下问题:1.分析过程中，当一个非终结符用某一个候选匹分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。配成功时，这种匹配可能是暂时的。出错时出错时，不得不不得不“回溯回溯”。2.文法左递归问题。一个文法是含有文法左递归问题。一个文法是含有左递归左递归的，的，如果存在非终结符如果存在非终结符P含有左递归的文法将

26、使自上而下的分析陷入无限循含有左递归的文法将使自上而下的分析陷入无限循环。环。4.2 自上而下分析面临的问题自上而下分析面临的问题第35页，共113页，编辑于2022年，星期二第四章第四章 语法分析语法分析-自上而下分析自上而下分析4.1 语法分析器的功能语法分析器的功能4.2 自上而下分析面临的问题自上而下分析面临的问题4.3 LL(1)分析法分析法4.4 递归下降分析程序构造递归下降分析程序构造4.5 预测分析程序预测分析程序第36页，共113页，编辑于2022年，星期二4.3 LL(1)分析法分析法构造不带回溯的自上而下分析算法构造不带回溯的自上而下分析算法要消除文法的左递归性要消除文法

27、的左递归性克服回溯克服回溯第37页，共113页，编辑于2022年，星期二4.3 LL(1)分析法分析法4.3.1 左递归的消除左递归的消除 4.3.2 消除回溯、提左因子消除回溯、提左因子 4.3.3 LL(1)分析条件分析条件第38页，共113页，编辑于2022年，星期二4.3.1 左递归的消除左递归的消除直接消除见诸于产生式中的左递归：假定直接消除见诸于产生式中的左递归：假定关于非终结符关于非终结符P的产生式为的产生式为 PP|其中其中 不以不以P开头，开头，不等于不等于。可以把可以把P的产生式等价地改写为如下的非直接的产生式等价地改写为如下的非直接左递归形式：左递归形式：P P P P|

28、左递归变左递归变右递归右递归第39页，共113页，编辑于2022年，星期二例例 文法文法G(E):EET|TTT*F|FF(E)|i经消去直接左递归后变成：经消去直接左递归后变成：ETE E+TE|TFT T*FT|F(E)|i第40页，共113页，编辑于2022年，星期二一般而言，假定一般而言，假定P的产生式是的产生式是PP 1|P 2|P m|1|2|n其中，每个其中，每个 都不等于都不等于，每个，每个 都不以都不以P开头。开头。那么，消除那么，消除P的直接左递归性就是将产生式改写成：的直接左递归性就是将产生式改写成：P 1P|2P|nP P 1P|2P|mP|左递归变左递归变右递归右递归

29、4.3.1 左递归的消除左递归的消除第41页，共113页，编辑于2022年，星期二例如文法例如文法G(S):SQc|cQRb|bRSa|a 虽没有直接左递归，但虽没有直接左递归，但S、Q、R都是左递归的都是左递归的SQcRbcSabc一个文法消除左递归的条件：一个文法消除左递归的条件：不含以不含以 为右部的产生式为右部的产生式不含回路。不含回路。4.3.1 左递归的消除左递归的消除第42页，共113页，编辑于2022年，星期二消除左递归的算法消除左递归的算法:（1）把文法）把文法G的所有非终结符按任一种顺序排列成的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；按此顺序执行；（2

30、）FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如把形如PiPj 的的产生式产生式改写成改写成 Pi 1|2|k ;(其中其中Pj 1|2|k是是Pj的的产生式产生式)消除消除Pi产生式产生式的直接左递归性的直接左递归性 END（3）化简由（）化简由（2）所得的文法。去除那些从开始符号出发）所得的文法。去除那些从开始符号出发永远无法到达的非终结符的永远无法到达的非终结符的产生式产生式。为非终结符编号，再采用代入法将间接左递归变为为非终结符编号，再采用代入法将间接左递归变为直接左递归，消除直接左递归。直接左递归，消除直接左递归。第43页，共113页，编辑

31、于2022年，星期二例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|a令它的非终结符的排序为令它的非终结符的排序为R、Q、S。对于对于R，不存在直接左递归。，不存在直接左递归。把把R代入到代入到Q的有关候选后，把的有关候选后，把Q的产生式变为的产生式变为 QSab|ab|b 现在的现在的Q不含直接左递归，把它代入到不含直接左递归，把它代入到S的有关候选后，的有关候选后，S变变成成SSabc|abc|bc|c 消除消除S的直接左递归后：的直接左递归后：SabcS|bcS|cS S abcS|QSab|ab|b RSa|aQ和和R的规则已是多余的，化简的规则已是多余的，化简为：为：Sab

32、cS|bcS|cS S abcS|文法文法(4.4)第44页，共113页，编辑于2022年，星期二注意，由于对非终结符排序的不同，最后所得的文法在形式注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。上可能不一样。但不难证明，它们都是等价的。例如，若对文法非终结符排序选为例如，若对文法非终结符排序选为S、Q、R，那么，最后，那么，最后所得的无左递归文法是：所得的无左递归文法是：SQc|cQRb|b 文法文法(4.5)RbcaR|caR|aR R bcaR|文法文法(4.4)和和(4.5)的等价性是显然的。的等价性是显然的。消除左递归前后，消除左递归前

33、后，文法的开始符号不变文法的开始符号不变。4.3.1 左递归的消除左递归的消除第45页，共113页，编辑于2022年，星期二例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|a令它的非终结符的排序为令它的非终结符的排序为S、Q、R。对于对于S 和和Q都不存在直接左递归。都不存在直接左递归。把把S代入到代入到R的有关候选后，把的有关候选后，把R的产生式变为的产生式变为 R Qca|ca|a 把把Q代入到代入到R的有关候选后，的有关候选后，R变成变成R Rbca|bca|ca|a 消除消除R 的直接左递归后：的直接左递归后：R bcaR|caR|aR R bca R|最后所得的无左递归文法

34、是：最后所得的无左递归文法是：SQc|c QRb|b 文法文法(4.5)RbcaR|caR|aR R bcaR|第46页，共113页，编辑于2022年，星期二4.3 LL(1)分析法分析法4.3.1 左递归的消除左递归的消除 4.3.2 消除回溯、提左因子消除回溯、提左因子 4.3.3 LL(1)分析条件分析条件第47页，共113页，编辑于2022年，星期二回溯问题回溯问题什么是回溯什么是回溯?分析工作要部分地或全部地退回去重做叫回溯。分析工作要部分地或全部地退回去重做叫回溯。造成回溯的条件：造成回溯的条件：文法中，对于某个非终结符号的产生式右部文法中，对于某个非终结符号的产生式右部有多个选择

35、，并根据所面临的输入符号不能准确有多个选择，并根据所面临的输入符号不能准确地确定所要的选择时，就可能出现回溯。地确定所要的选择时，就可能出现回溯。回溯带来的问题：回溯带来的问题：严重的低效率，只有在理论上的意义而无实际意义。严重的低效率，只有在理论上的意义而无实际意义。例例 假定有文法假定有文法G(S):(1)SxAy (2)A*|*分析输入串分析输入串x*y第48页，共113页，编辑于2022年，星期二4.3.2 消除回溯、提左因子消除回溯、提左因子为了消除回溯就必须保证：对文法的任何为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够非终结符，当要它去匹配输入串时，能够

36、根据它所面临的输入符号准确地指派它的根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作一个候选去执行任务，并且此候选的工作结果应是确信无疑的。结果应是确信无疑的。A 1|2|nSa.IPA.第49页，共113页，编辑于2022年，星期二令令G是一个不含左递归的文法，对是一个不含左递归的文法，对G的所有非终结符的每的所有非终结符的每个候选个候选 定义它的定义它的终结首符集终结首符集FIRST()为：为：特别是，若特别是，若 ，则规定，则规定FIRST()。若非终结符若非终结符A的所有候选的所有候选终结首符集两两不相交，即终结首符集两两不相交，即A的任的任何两个不同候选何两个

37、不同候选 i和和 jFIRST(i)FIRST(j)当要求当要求A匹配输入串时，匹配输入串时，A就能根据它所面临的第一个输入符就能根据它所面临的第一个输入符号号a，准确地指派某一个候选前去执行任务。这个候选就是，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含那个终结首符集含a的的。FIRST()是是 的所有可能推导的开头的所有可能推导的开头终结符或终结符或可能的可能的。第50页，共113页，编辑于2022年，星期二提取公共左因子提取公共左因子:假定关于假定关于A的产生式是的产生式是 A 1|2|n|1|2|m(其中，每个其中，每个 不以不以 开头开头)那么，可以把产生式改写成那

38、么，可以把产生式改写成A A|1|2|mA 1|2|n经过反复提取左因子，就能够把每个非终结符经过反复提取左因子，就能够把每个非终结符(包括新引进者包括新引进者)的所有候选首符集变成为两两不的所有候选首符集变成为两两不相交。相交。第51页，共113页，编辑于2022年，星期二52文法文法 S iBtSeS|iBtS|a B b 提取公共左因子改写文法。提取公共左因子改写文法。提取公共左因子，提取公共左因子，将文法改写为将文法改写为 S iBtSS|a S eS|B b4.3.2 消除回溯、提左因子消除回溯、提左因子第52页，共113页，编辑于2022年，星期二一个文法不含左递归，且所有候选式首

39、符一个文法不含左递归，且所有候选式首符集两两不相交，但带集两两不相交，但带产生式，在自上而下产生式，在自上而下分析又带来新问题：这就引出分析又带来新问题：这就引出自动匹配自动匹配问题。问题。当非终结符当非终结符A面临输入符号面临输入符号a，且，且a不属于不属于A的任意候选首符集，但的任意候选首符集，但A的某个候选首符的某个候选首符集包含集包含 时，就一定可以使时，就一定可以使A自动匹配。这自动匹配。这是一种错误。是一种错误。4.3.2 消除回溯、提左因子消除回溯、提左因子第53页，共113页，编辑于2022年，星期二4.3 LL(1)分析法分析法4.3.1 左递归的消除左递归的消除 4.3.2

40、 消除回溯、提左因子消除回溯、提左因子 4.3.3 LL(1)分析条件分析条件文法是文法是LL(1)的的 第一个第一个L 从左到右扫描输入串从左到右扫描输入串 第二个第二个L 生成的是最左推导生成的是最左推导 1 向前看一个输入符号（向前看一个输入符号（lookahead)第54页，共113页，编辑于2022年，星期二 ETE E+TE|TFT T*FT|F(E)|i i+i4.3.3 LL(1)分析条件分析条件例例 文法文法G(E):EET|TTT*F|FF(E)|i经消去直接左递归后变成：经消去直接左递归后变成：ETE E+TE|TFT T*FT|F(E)|i第55页，共113页，编辑于2

41、022年，星期二i +i IPEG(E):ETE E+TE|TFT T*FT|F(E)|i第56页，共113页，编辑于2022年，星期二i +i IPETE G(E):ETE E+TE|TFT T*FT|F(E)|i第57页，共113页，编辑于2022年，星期二i +i IPETE FT G(E):ETE E+TE|TFT T*FT|F(E)|i第58页，共113页，编辑于2022年，星期二i +i IPETE FT iG(E):ETE E+TE|TFT T*FT|F(E)|i第59页，共113页，编辑于2022年，星期二i +i IPETE FT iG(E):ETE E+TE|TFT T*F

42、T|F(E)|i第60页，共113页，编辑于2022年，星期二i +i IPETE FT i G(E):ETE E+TE|TFT T*FT|F(E)|i第61页，共113页，编辑于2022年，星期二i +i IPETE FT i+TE G(E):ETE E+TE|TFT T*FT|F(E)|i第62页，共113页，编辑于2022年，星期二i +i IPETE FT i+TE G(E):ETE E+TE|TFT T*FT|F(E)|i第63页，共113页，编辑于2022年，星期二i +i IPETE FT i+TE FT G(E):ETE E+TE|TFT T*FT|F(E)|i第64页，共11

43、3页，编辑于2022年，星期二i +i IPETE FT i+TE FT iG(E):ETE E+TE|TFT T*FT|F(E)|i第65页，共113页，编辑于2022年，星期二i +i IPETE FT i+TE FT iG(E):ETE E+TE|TFT T*FT|F(E)|i第66页，共113页，编辑于2022年，星期二i +i IPETE FT i+TE FT i G(E):ETE E+TE|TFT T*FT|F(E)|i第67页，共113页，编辑于2022年，星期二i +i IPETE FTi+TE FT i G(E):ETE E+TE|TFT T*FT|F(E)|iS T+第68

44、页，共113页，编辑于2022年，星期二假定假定S是文法是文法G的开始符号，对于的开始符号，对于G的任何的任何非终结符非终结符A，我们定义，我们定义 若若 ,则规定则规定 FOLLOW(A)4.3.3 LL(1)分析条件分析条件即即FOLLOW(A)是是所所有有句句型型中中紧紧跟跟在在A之之后后的的终终结结符符或或#。第69页，共113页，编辑于2022年，星期二构造不带回溯的自上而下分析的文法条件构造不带回溯的自上而下分析的文法条件1.文法不含左递归。文法不含左递归。2.对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的候的各个产生式的候选首符集两两不相交。即，若选首符集两两不

45、相交。即，若A 1|2|n 则则 FIRST(i)FIRST(j)(i j)3.对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个候选，若它存在某个候选首符集包含首符集包含，当当FIRST(j)时，时，则则FOLLOW(A)FIRST(i)=如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为为LL(1)文法文法。第70页，共113页，编辑于2022年，星期二对于一个满足上述条件的文法，可以对其输入对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要串进行有效的无回溯的自上而下分析。假设要用非终结符用非终结符A进行匹配，面临的输入

46、符号为进行匹配，面临的输入符号为a，A的所有产生式为的所有产生式为A 1|2|n1.若若a FIRST(i)，则指派，则指派 i执行匹配任务；执行匹配任务；2.若若a不属于任何一个候选首符集，则：不属于任何一个候选首符集，则：(1)若若 属于某个属于某个FIRST(i)且且 a FOLLOW(A)，则让则让A与与 自动匹配。自动匹配。(2)否则，否则，a的出现是一种语法错误。的出现是一种语法错误。第71页，共113页，编辑于2022年，星期二第四章第四章 语法分析语法分析-自上而下分析自上而下分析4.1 语法分析器的功能语法分析器的功能4.2 自上而下分析面临的问题自上而下分析面临的问题4.3

47、 LL(1)分析法分析法4.4 递归下降分析程序构造递归下降分析程序构造4.5 预测分析程序预测分析程序第72页，共113页，编辑于2022年，星期二4.4 递归下降分析程序构造递归下降分析程序构造构造不带回溯的自上而下分析程序构造不带回溯的自上而下分析程序要消除文法的左递归性要消除文法的左递归性克服回溯克服回溯第73页，共113页，编辑于2022年，星期二当一个文法满足当一个文法满足LL(1)条件时，我们就可以为它构造一个不条件时，我们就可以为它构造一个不带回溯的自上而下分析程序，带回溯的自上而下分析程序，这个分析程序是由一组递归过程这个分析程序是由一组递归过程组成的，每个过程对应文法的一个

48、非终结符。这样的一个分析组成的，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。程序称为递归下降分析器。4.4 递归下降分析程序构造递归下降分析程序构造如果用某种高级语言写出所有递归过程，那就可以用这个语言的如果用某种高级语言写出所有递归过程，那就可以用这个语言的编译系统来产生整个的语法分析程序。编译系统来产生整个的语法分析程序。几个全局过程和变量：几个全局过程和变量：ADVANCE，读入读入IP 指向的输入符号到指向的输入符号到SYM中中，把输，把输入串指示器入串指示器IP指向下一个输入符号指向下一个输入符号。SYM，IP当前所指的输入符号。当前所指的输入符号。ERRO

49、R，出错处理程序。，出错处理程序。第74页，共113页，编辑于2022年，星期二例例:文法文法G(E):ETE E+TE|TFT T*FT|F(E)|i非终结符号的分析子程序的功能非终结符号的分析子程序的功能是：用产生式是：用产生式 右部符号串来匹配输入串。右部符号串来匹配输入串。每个非终结符都有对应的递归过程，在分析过程每个非终结符都有对应的递归过程，在分析过程中，当需要从某个非终结符出发进行展开中，当需要从某个非终结符出发进行展开(推导推导)时，时，就调用这个非终结符对应的子程序。就调用这个非终结符对应的子程序。第75页，共113页，编辑于2022年，星期二假定在开始工作前，输入串指示器假

50、定在开始工作前，输入串指示器IP指向第一个输入符指向第一个输入符号。当每个子程序工作完毕之后，号。当每个子程序工作完毕之后，IP总是指向下一个未处总是指向下一个未处理的符号。理的符号。E+TE|E 只有两个候选，第一个候选的开头终结符为只有两个候选，第一个候选的开头终结符为+，第二个候选第二个候选为为。当当E 面临输入符号面临输入符号+时，就令时，就令第一个候选进入工作，当面临第一个候选进入工作，当面临任何其它输入符号任何其它输入符号时，时，E 就自动认为获得了匹配（这时，更就自动认为获得了匹配（这时，更精确的做法是判断该精确的做法是判断该输入符号是否属于输入符号是否属于FOLLOW(E)）。