语法分析自上而下分析精品文稿.ppt

语法分析自上而下分析第1页，本讲稿共113页课程安排课程安排内内 容容讲授课时讲授课时实验课时实验课时第一章第一章 引引 论论2第二章第二章 高级程序语言及其语法描述高级程序语言及其语法描述2第三章第三章 词法分析词法分析实验一实验一 词法分析器（第词法分析器（第6、7、8、9周）周）108第四章第四章 语法分析语法分析-自上而下分析自上而下分析8第五章第五章 语法分析语法分析-自下而上分析自下而上分析实验二实验二 语法分析器（第语法分析器（第13、14、15、16周）周）88第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译8第七章第七章 语义分析及中间代码产生语义分析及中间代码产生8第八章第八章 优优 化化2合合 计计4816第2页，本讲稿共113页实验时间：实验时间：实验一词法分析：实验一词法分析：第第6、7、8、9周周实验二语法分析：第实验二语法分析：第13、14、15、16周周实验地点：实验地点：计算机系实验中心（计算机系实验中心（5教教910、911）指导教师：指导教师：杨健、张谦杨健、张谦实验安排实验安排杨健杨健：13488702754张谦张谦：18801041780 邮箱：邮箱： 地点：五教地点：五教8层层802图像处理研究室图像处理研究室 第3页，本讲稿共113页数字媒体制作实验室数字媒体制作实验室910 计计11-12软件开发实验室软件开发实验室911 计计11-34第第6、7、8、9周，都是周，都是周二周二1,2节节实验一实验一 词法分析器（第词法分析器（第6、7、8、9周）周）第4页，本讲稿共113页第四章第四章 语法分析语法分析-自上而下分析自上而下分析4.1 语法分析器的功能语法分析器的功能4.2 自上而下分析面临的问题自上而下分析面临的问题4.3 LL(1)分析法分析法4.4 递归下降分析程序构造递归下降分析程序构造4.5 预测分析程序预测分析程序第5页，本讲稿共113页第四章第四章 语法分析语法分析-自上而下分析自上而下分析了解：了解：语法分析器的功能。语法分析器的功能。熟悉：熟悉：预测分析程序、递归下降分析程序的设计方预测分析程序、递归下降分析程序的设计方法。法。掌握：掌握：LL(1)分析法的条件，消除左递归的算法，预分析法的条件，消除左递归的算法，预测分析表的构造。测分析表的构造。第6页，本讲稿共113页第四章第四章 语法分析语法分析-自上而下分析自上而下分析作业：作业：4.1，4.2第7页，本讲稿共113页4.1 考虑下面文法考虑下面文法G1:Sa(T)TT,S S（1）消去）消去G1的左递归。然后对每个非终结符，写出的左递归。然后对每个非终结符，写出不带回溯的递归子程序。不带回溯的递归子程序。（2）经改写后的文法是否是）经改写后的文法是否是LL(1)的？给出它的预测的？给出它的预测分析表。分析表。第四章第四章 语法分析语法分析-自上而下分析自上而下分析第8页，本讲稿共113页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页第三章第三章 词法分析词法分析实验一实验一 词法分析器词法分析器 每次实验结束都必须写出实验报告，报告内容每次实验结束都必须写出实验报告，报告内容包括：实验题目、实验目的和要求，实验的实现包括：实验题目、实验目的和要求，实验的实现（包括主要设计思想、实现算法、主要技术问题的（包括主要设计思想、实现算法、主要技术问题的处理方法，及实验结果），结论分析。处理方法，及实验结果），结论分析。实验二实验二 语法分析器语法分析器第10页，本讲稿共113页实验二实验二 语法分析器构造语法分析器构造一、目的和要求一、目的和要求 借助于词法分析程序提供的分析结果，编写一个算符优先借助于词法分析程序提供的分析结果，编写一个算符优先语法分析程序，程序能进行语法结构分析和错误检查并产生相语法分析程序，程序能进行语法结构分析和错误检查并产生相应的归约信息。同时给出出错信息和错误类型，从而加深对语应的归约信息。同时给出出错信息和错误类型，从而加深对语法分析的理解。法分析的理解。二、实验内容二、实验内容 给定文法给定文法G和算符优先分析法，构造其算符优先分析程序。和算符优先分析法，构造其算符优先分析程序。文法文法G：语句语句赋值语句条件语句转移语句带标号的赋赋值语句条件语句转移语句带标号的赋 值语句值语句带标号的赋值语句带标号的赋值语句赋值语句赋值语句变量变量=算术表达式算术表达式条件语句条件语句 IF THEN 语句语句 IF THEN 语句语句 ELSE 语句语句第11页，本讲稿共113页实验二实验二 语法分析器构造语法分析器构造转移语句转移语句GOTO标号标号变量变量标识符标识符标识符标识符字母字母字母字母ABZabz数字数字019算术表达式算术表达式项算术表达式项算术表达式+项算术表达式项算术表达式-项项项项因子项因子项*因子项因子项/因子因子因子因子项项因子因子变量常数变量常数(表达式表达式)布尔表达式布尔表达式关系符关系符=标号标号常数常数常数常数数字数字第12页，本讲稿共113页实验二实验二 语法分析器构造语法分析器构造三、说明和提示三、说明和提示1.本实验的优先表可以手工先设计好。本实验的优先表可以手工先设计好。2.本实验要求中提出的本实验要求中提出的“产生相应的归约信息产生相应的归约信息”意指在语法分意指在语法分析的过程中，一旦产生归约，在程序上产生并最终输出归约产析的过程中，一旦产生归约，在程序上产生并最终输出归约产生式序号。生式序号。3.出错类型的产生可预先对应优先表中出错栏列表说明出错类型的产生可预先对应优先表中出错栏列表说明其出错类型，并分别编序，当分析中产生错误时以字符串其出错类型，并分别编序，当分析中产生错误时以字符串输出相应表中错误信息。输出相应表中错误信息。4.算法采用一个符号栈的数据结构，既用它存放终结符，也用它算法采用一个符号栈的数据结构，既用它存放终结符，也用它存放非终结符。存放非终结符。第13页，本讲稿共113页第四章第四章 语法分析语法分析-自上而下分析自上而下分析4.1 语法分析器的功能语法分析器的功能4.2 自上而下分析面临的问题自上而下分析面临的问题4.3 LL(1)分析法分析法4.4 递归下降分析程序构造递归下降分析程序构造4.5 预测分析程序预测分析程序第14页，本讲稿共113页中间代码中间代码单词符号单词符号语法单位语法单位中间代码中间代码目标代码目标代码词法分析器词法分析器语法分析器语法分析器语义分析与中间代码产语义分析与中间代码产生器生器优化器优化器源程序源程序表表格格管管理理出出错错处处理理目标代码生成器目标代码生成器编译程序总框编译程序总框第15页，本讲稿共113页本章主要介绍语法分析的处理本章主要介绍语法分析的处理要进行语法分析，必须对语言的语法结要进行语法分析，必须对语言的语法结构进行描述。构进行描述。采用采用正规式正规式和和有限自动机有限自动机可以描述和识别语可以描述和识别语言的单词符号；言的单词符号；用用上下文无关文法上下文无关文法来描述语法规则。来描述语法规则。第四章第四章 语法分析语法分析-自上而下分析自上而下分析第16页，本讲稿共113页形式化定义：形式化定义：一个上下文无关文法是一个四元式（一个上下文无关文法是一个四元式（VT,VN,S,）VT是一个非空有限集，它的每个元素称为终结符号；是一个非空有限集，它的每个元素称为终结符号；VN是是一一个个非非空空有有限限集集，它它的的每每个个元元素素称称为为非非终终结结符符号号，VTVN=；S是一个非终结符号，称为开始符号；是一个非终结符号，称为开始符号；SVN。是是一一个个产产生生式式集集合合（有有限限），每每个个产产生生式式的的形形式式是是P。其其中中，PVN，(VTVN)。开开始始符符号号S必必须须至至少少在在某某个个产生式的左部出现一次。产生式的左部出现一次。P1|2|n。其其中中，i称称为为是是P的的一一个个候候选选式式。读读作作“定义定义”，直竖读为，直竖读为“或或”,它是元语言符号。它是元语言符号。2.3.1 上下文无关文法上下文无关文法第17页，本讲稿共113页2.3.1 上下文无关文法上下文无关文法定义：称定义：称 A 直接推出直接推出 ，即，即 A 仅当仅当A 是一个产生式，是一个产生式，且且，(VT VN)*。如果如果 1 2 n，则我们称这个序列是从，则我们称这个序列是从 1到到 n的一的一个个推导推导。若存在一个从。若存在一个从 1到到 n的推导，则称的推导，则称 1可以可以推导推导出出 n。对文法对文法G(E)：E i|E+E|E*E|(E)E (E)(E+E)(i+E)(i+i)第18页，本讲稿共113页 用用 表示：从表示：从 1出发，经过出发，经过0步步或若干步，可以推出或若干步，可以推出 n。所以所以：即即 或或定义：假定定义：假定G是一个文法，是一个文法，S 是开始符号。是开始符号。如果如果 ，则，则 称是一个称是一个句型句型。仅含终。仅含终结符号的句型是一个结符号的句型是一个句子句子。文法。文法G所产生的句所产生的句子的全体是一个子的全体是一个语言语言，将它记为，将它记为 L(G)。通常，用通常，用 表示：从表示：从 1出发，经出发，经过一步或若干步，可以推出过一步或若干步，可以推出 n。第19页，本讲稿共113页例：例：(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页第四章第四章 语法分析语法分析-自上而下分析自上而下分析4.1 语法分析器的功能语法分析器的功能4.2 自上而下分析面临的问题自上而下分析面临的问题4.3 LL(1)分析法分析法4.4 递归下降分析程序构造递归下降分析程序构造4.5 预测分析程序预测分析程序第21页，本讲稿共113页4.1 语法分析器的功能语法分析器的功能语法分析的语法分析的任务任务是分析一个文法的句子结构。是分析一个文法的句子结构。语法分析器的语法分析器的功能功能：按照文法的产生式，识别输：按照文法的产生式，识别输入符号串是否为一个句子。入符号串是否为一个句子。策略策略：自上而下分析法，自下而上分析法。：自上而下分析法，自下而上分析法。两种方法反映了两种语法树的构造过程。两种方法反映了两种语法树的构造过程。第22页，本讲稿共113页源程序源程序单词符号单词符号取下一单取下一单词符号词符号.语法分语法分析树析树词法分词法分析器析器语法分语法分析器析器符号表符号表编译程序编译程序后续部分后续部分图图4.1 语法分析器在编译程序中的地位语法分析器在编译程序中的地位4.1 语法分析器的功能语法分析器的功能第23页，本讲稿共113页语法分析的方法语法分析的方法-自上而下分析法自上而下分析法(Top-down)基本思想基本思想：它从文法的开始符号出发，反复使用各种：它从文法的开始符号出发，反复使用各种产生式，寻找产生式，寻找“匹配匹配”的的推导推导。从树根到叶子来建立语从树根到叶子来建立语法树。法树。递归下降分析法递归下降分析法：对每个非终结符号构造一个相应的：对每个非终结符号构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。间的信息反馈和联合作用实现对输入串的识别。预测分析程序预测分析程序优点：直观、简单和宜于手工实现。优点：直观、简单和宜于手工实现。第24页，本讲稿共113页 语法分析的方法语法分析的方法-自下而上分析法自下而上分析法(Bottom-up)基本思想基本思想：从输入串开始，逐步进行：从输入串开始，逐步进行“归约归约”，直到文，直到文法的开始符号。即从树末端开始，构造语法树。法的开始符号。即从树末端开始，构造语法树。从树叶从树叶到树根来建立到树根来建立语法树。语法树。所谓归约，是指根据文法的产生所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。式规则，把产生式的右部替换成左部符号。算符优先分析法算符优先分析法：按照算符的优先关系和结合性质进：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。行语法分析。适合分析表达式。LR分析法分析法：规范归约：规范归约第25页，本讲稿共113页 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页，本讲稿共113页第四章第四章 语法分析语法分析-自上而下分析自上而下分析4.1 语法分析器的功能语法分析器的功能4.2 自上而下分析面临的问题自上而下分析面临的问题4.3 LL(1)分析法分析法4.4 递归下降分析程序构造递归下降分析程序构造4.5 预测分析程序预测分析程序第27页，本讲稿共113页4.2 自上而下分析面临的问题自上而下分析面临的问题自上而下就是从文法的开始符号出发，自上而下就是从文法的开始符号出发，向下向下推导推导，推出句子。，推出句子。自上而下分析的主旨：对任何输入串，自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符试图用一切可能的办法，从文法开始符号号(根结点根结点)出发，自上而下地为输入串出发，自上而下地为输入串建立一棵建立一棵语法树语法树。或者说，为输入串寻。或者说，为输入串寻找一个最左推导。找一个最左推导。第28页，本讲稿共113页例例 文法文法G(E):E iE E+EE E*EE (E)对句子对句子(i+i)最左推导最左推导E(E)(E+E)(i+E)(i+i)4.2 自上而下分析面临的问题自上而下分析面临的问题第29页，本讲稿共113页例例 假定有文法假定有文法G(S):(1)SxAy (2)A*|*分析输入串分析输入串x*y序号序号 指示器指示器IP指向指向 语法树语法树 最左推导最左推导 说明说明 x*yS根结根结S,当前符当前符xx*yx得匹配得匹配,移动移动IP Sx A ySx A y用用SxAy展开展开S欲用欲用xAy匹配输匹配输入串入串SxAy x*y第30页，本讲稿共113页序号序号 IP指向指向 语法树语法树 最左推导最左推导 说明说明 Sx*yx A y试用试用A*展展开开ASxAyx*y*x*y*得匹配得匹配,移动移动IP,但但y得不到得不到匹配匹配Sx A y*用用A*展开展开失败失败,回溯回溯,回到回到第第步步Sx A ySxAyx*y第31页，本讲稿共113页 序号序号 IP指向指向 语法树语法树 最左推导最左推导 说明说明 x*ySx A y试用试用A*展开展开ASxAyx*y*x*y*得匹配得匹配,移动移动IPSx A y*A完成匹配完成匹配,y得得匹配匹配,移动移动IP,输输入串匹配成功入串匹配成功,结束结束Sx A ySxAyx*yx*y*第32页，本讲稿共113页存在回溯的原因存在回溯的原因文法中非终结符文法中非终结符A的产生式右部称为的产生式右部称为A的候选式，如果有多个候选式左端第一的候选式，如果有多个候选式左端第一个符号相同，则语法分析程序无法根据个符号相同，则语法分析程序无法根据当前输入符号选择产生式，只能试探。当前输入符号选择产生式，只能试探。例例 假定有文法假定有文法G(S):(1)SxAy (2)A*|*分析输入串分析输入串x*y第33页，本讲稿共113页自上而下分析方法的步骤自上而下分析方法的步骤：（：（带回溯的试探过程）带回溯的试探过程）遇遇非终结符非终结符,就试图用某个候选式就试图用某个候选式展开展开,期望此候选能匹期望此候选能匹配输入串配输入串,若不能匹配若不能匹配,则要则要回溯回溯。遇遇终结符终结符，就进行就进行匹配匹配，然后移动输入串指针，然后移动输入串指针IP指向指向下一个符号。下一个符号。回溯回溯是一项复杂而费时的工作，须废弃已做的许多工作，恢复到是一项复杂而费时的工作，须废弃已做的许多工作，恢复到前面的某一情况，效率很低。前面的某一情况，效率很低。4.2 自上而下分析面临的问题自上而下分析面临的问题第34页，本讲稿共113页当某个非终结符有多个产生式候选时，可能带来如当某个非终结符有多个产生式候选时，可能带来如下问题下问题:1.分析过程中，当一个非终结符用某一个候分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。选匹配成功时，这种匹配可能是暂时的。出错时出错时，不得不，不得不“回溯回溯”。2.文法左递归问题。一个文法是含有文法左递归问题。一个文法是含有左递归左递归的，如果存在非终结符的，如果存在非终结符P含有左递归的文法将使自上而下的分析陷入含有左递归的文法将使自上而下的分析陷入无限循环。无限循环。4.2 自上而下分析面临的问题自上而下分析面临的问题第35页，本讲稿共113页第四章第四章 语法分析语法分析-自上而下分析自上而下分析4.1 语法分析器的功能语法分析器的功能4.2 自上而下分析面临的问题自上而下分析面临的问题4.3 LL(1)分析法分析法4.4 递归下降分析程序构造递归下降分析程序构造4.5 预测分析程序预测分析程序第36页，本讲稿共113页4.3 LL(1)分析法分析法构造不带回溯的自上而下分析算法构造不带回溯的自上而下分析算法要消除文法的左递归性要消除文法的左递归性克服回溯克服回溯第37页，本讲稿共113页4.3 LL(1)分析法分析法4.3.1 左递归的消除左递归的消除 4.3.2 消除回溯、提左因子消除回溯、提左因子 4.3.3 LL(1)分析条件分析条件第38页，本讲稿共113页4.3.1 左递归的消除左递归的消除直接消除见诸于产生式中的左递归：假直接消除见诸于产生式中的左递归：假定关于非终结符定关于非终结符P的产生式为的产生式为 PP|其中其中 不以不以P开头，开头，不等于不等于。可以把可以把P的产生式等价地改写为如下的的产生式等价地改写为如下的非直接左递归形式：非直接左递归形式：P P P P|左递归变左递归变右递归右递归第39页，本讲稿共113页例例 文法文法G(E):EET|TTT*F|FF(E)|i经消去直接左递归后变成：经消去直接左递归后变成：ETE E+TE|TFT T*FT|F(E)|i第40页，本讲稿共113页一般而言，假定一般而言，假定P的产生式是的产生式是PP 1|P 2|P m|1|2|n其中，每个其中，每个 都不等于都不等于，每个，每个 都不以都不以P开头。开头。那么，消除那么，消除P的直接左递归性就是将产生式改写成：的直接左递归性就是将产生式改写成：P 1P|2P|nP P 1P|2P|mP|左递归变左递归变右递归右递归4.3.1 左递归的消除左递归的消除第41页，本讲稿共113页例如文法例如文法G(S):SQc|cQRb|bRSa|a 虽没有直接左递归，但虽没有直接左递归，但S、Q、R都是左递归的都是左递归的SQcRbcSabc一个文法消除左递归的条件：一个文法消除左递归的条件：不含以不含以 为右部的产生式为右部的产生式不含回路。不含回路。4.3.1 左递归的消除左递归的消除第42页，本讲稿共113页消除左递归的算法消除左递归的算法:（1）把文法）把文法G的所有非终结符按任一种顺序排列成的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；按此顺序执行；（2）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页例例 考虑文法考虑文法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的规则已是多余的，化简的规则已是多余的，化简为：为：SabcS|bcS|cS S abcS|文法文法(4.4)第44页，本讲稿共113页注意，由于对非终结符排序的不同，最后所得的文法在形式上可能注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。不一样。但不难证明，它们都是等价的。例如，若对文法非终结符排序选为例如，若对文法非终结符排序选为S、Q、R，那么，最后所，那么，最后所得的无左递归文法是：得的无左递归文法是：SQc|cQRb|b 文法文法(4.5)RbcaR|caR|aR R bcaR|文法文法(4.4)和和(4.5)的等价性是显然的。的等价性是显然的。消除左递归前后，消除左递归前后，文法的开始符号不变文法的开始符号不变。4.3.1 左递归的消除左递归的消除第45页，本讲稿共113页例例 考虑文法考虑文法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|最后所得的无左递归文法是：最后所得的无左递归文法是：SQc|c QRb|b 文法文法(4.5)RbcaR|caR|aR R bcaR|第46页，本讲稿共113页4.3 LL(1)分析法分析法4.3.1 左递归的消除左递归的消除 4.3.2 消除回溯、提左因子消除回溯、提左因子 4.3.3 LL(1)分析条件分析条件第47页，本讲稿共113页回溯问题回溯问题什么是回溯什么是回溯?分析工作要部分地或全部地退回去重做叫回溯。分析工作要部分地或全部地退回去重做叫回溯。造成回溯的条件：造成回溯的条件：文法中，对于某个非终结符号的产生式右部文法中，对于某个非终结符号的产生式右部有多个选择，并根据所面临的输入符号不能准确有多个选择，并根据所面临的输入符号不能准确地确定所要的选择时，就可能出现回溯。地确定所要的选择时，就可能出现回溯。回溯带来的问题：回溯带来的问题：严重的低效率，只有在理论上的意义而无实际意义。严重的低效率，只有在理论上的意义而无实际意义。例例 假定有文法假定有文法G(S):(1)SxAy (2)A*|*分析输入串分析输入串x*y第48页，本讲稿共113页4.3.2 消除回溯、提左因子消除回溯、提左因子为了消除回溯就必须保证：对文法的任为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。选的工作结果应是确信无疑的。A 1|2|nSa.IPA.第49页，本讲稿共113页令令G是一个不含左递归的文法，对是一个不含左递归的文法，对G的所有非终结符的所有非终结符的每个候选的每个候选 定义它的定义它的终结首符集终结首符集FIRST()为：为：特别是，若特别是，若 ，则规定，则规定FIRST()。若非终结符若非终结符A的所有候选终结的所有候选终结首符集两两不相交，即首符集两两不相交，即A的任何两个不同候选的任何两个不同候选 i和和 jFIRST(i)FIRST(j)当要求当要求A匹配输入串时，匹配输入串时，A就能根据它所面临的第一个输入就能根据它所面临的第一个输入符号符号a，准确地指派某一个候选前去执行任务。这个候选，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含就是那个终结首符集含a的的。FIRST()是是 的所有可能推导的开头的所有可能推导的开头终结符或终结符或可能的可能的。第50页，本讲稿共113页提取公共左因子提取公共左因子:假定关于假定关于A的产生式是的产生式是 A 1|2|n|1|2|m(其中，每个其中，每个 不以不以 开头开头)那么，可以把产生式改写成那么，可以把产生式改写成A A|1|2|mA 1|2|n经过反复提取左因子，就能够把每个非终结符经过反复提取左因子，就能够把每个非终结符(包包括新引进者括新引进者)的所有候选首符集变成为两两不相交。的所有候选首符集变成为两两不相交。第51页，本讲稿共113页52文法文法 S iBtSeS|iBtS|a B b 提取公共左因子改写文法。提取公共左因子改写文法。提取公共左因子，提取公共左因子，将文法改写为将文法改写为 S iBtSS|a S eS|B b4.3.2 消除回溯、提左因子消除回溯、提左因子第52页，本讲稿共113页一个文法不含左递归，且所有候选式首一个文法不含左递归，且所有候选式首符集两两不相交，但带符集两两不相交，但带产生式，在自上产生式，在自上而下分析又带来新问题：这就引出而下分析又带来新问题：这就引出自动自动匹配匹配问题。问题。当非终结符当非终结符A面临输入符号面临输入符号a，且，且a不属于不属于A的的任意候选首符集，但任意候选首符集，但A的某个候选首符集包的某个候选首符集包含含 时，就一定可以使时，就一定可以使A自动匹配。这是一自动匹配。这是一种错误。种错误。4.3.2 消除回溯、提左因子消除回溯、提左因子第53页，本讲稿共113页4.3 LL(1)分析法分析法4.3.1 左递归的消除左递归的消除 4.3.2 消除回溯、提左因子消除回溯、提左因子 4.3.3 LL(1)分析条件分析条件文法是文法是LL(1)的的 第一个第一个L 从左到右扫描输入串从左到右扫描输入串 第二个第二个L 生成的是最左推导生成的是最左推导 1 向前看一个输入符号（向前看一个输入符号（lookahead)第54页，本讲稿共113页 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页i +i IPEG(E):ETE E+TE|TFT T*FT|F(E)|i第56页，本讲稿共113页i +i IPETE G(E):ETE E+TE|TFT T*FT|F(E)|i第57页，本讲稿共113页i +i IPETE FT G(E):ETE E+TE|TFT T*FT|F(E)|i第58页，本讲稿共113页i +i IPETE FT iG(E):ETE E+TE|TFT T*FT|F(E)|i第59页，本讲稿共113页i +i IPETE FT iG(E):ETE E+TE|TFT T*FT|F(E)|i第60页，本讲稿共113页i +i IPETE FT i G(E):ETE E+TE|TFT T*FT|F(E)|i第61页，本讲稿共113页i +i IPETE FT i+TE G(E):ETE E+TE|TFT T*FT|F(E)|i第62页，本讲稿共113页i +i IPETE FT i+TE G(E):ETE E+TE|TFT T*FT|F(E)|i第63页，本讲稿共113页i +i IPETE FT i+TE FT G(E):ETE E+TE|TFT T*FT|F(E)|i第64页，本讲稿共113页i +i IPETE FT i+TE FT iG(E):ETE E+TE|TFT T*FT|F(E)|i第65页，本讲稿共113页i +i IPETE FT i+TE FT iG(E):ETE E+TE|TFT T*FT|F(E)|i第66页，本讲稿共113页i +i IPETE FT i+TE FT i G(E):ETE E+TE|TFT T*FT|F(E)|i第67页，本讲稿共113页i +i IPETE FTi+TE FT i G(E):ETE E+TE|TFT T*FT|F(E)|iS T+第68页，本讲稿共113页假定假定S是文法是文法G的开始符号，对于的开始符号，对于G的任的任何非终结符何非终结符A，我们定义，我们定义 若若 ,则规定则规定 FOLLOW(A)4.3.3 LL(1)分析条件分析条件即即FOLLOW(A)是是所所有有句句型型中中紧紧跟跟在在A之之后后的的终终结结符符或或#。第69页，本讲稿共113页构造不带回溯的自上而下分析的文法条件构造不带回溯的自上而下分析的文法条件1.文法不含左递归。文法不含左递归。2.对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的的各个产生式的候选首符集两两不相交。即，若候选首符集两两不相交。即，若A 1|2|n 则则 FIRST(i)FIRST(j)(i j)3.对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个，若它存在某个候选首符集包含候选首符集包含，当当FIRST(j)时，时，则则FOLLOW(A)FIRST(i)=如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为为LL(1)文法文法。第70页，本讲稿共113页对于一个满足上述条件的文法，可以对对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下其输入串进行有效的无回溯的自上而下分析。假设要用非终结符分析。假设要用非终结符A进行匹配，面进行匹配，面临的输入符号为临的输入符号为a，A的所有产生式为的所有产生式为A 1|2|n1.若若a FIRST(i)，则指派，则指派 i执行匹配任务；执行匹配任务；2.若若a不属于任何一个候选首符集，则：不属于任何一个候选首符集，则：(1)若若 属于某个属于某个FIRST(i)且且 a FOLLOW(A)，则让则让A与与 自动匹配。自动匹配。(2)否则，否则，a的出现是一种语法错误。的出现是一种语法错误。第71页，本讲稿共113页第四章第四章 语法分析语法分析-自上而下分析自上而下分析4.1 语法分析器的功能语法分析器的功能4.2 自上而下分析面临的问题自上而下分析面临的问题4.3 LL(1)分析法分析法4.4 递归下降分析程序构造递归下降分析程序构造4.5 预测分析程序预测分析程序第72页，本讲稿共113页4.4 递归下降分析程序构造递归下降分析程序构造构造不带回溯的自上而下分析程序构造不带回溯的自上而下分析程序要消除文法的左递归性要消除文法的左递归性克服回溯克服回溯第73页，本讲稿共113页当一个文法满足当一个文法满足LL(1)条件时，我们就可以为它构造一个不带回条件时，我们就可以为它构造一个不带回溯的自上而下分析程序，溯的自上而下分析程序，这个分析程序是由一组递归过程这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符。这样的一组成的，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。个分析程序称为递归下降分析器。4.4 递归下降分析程序构造递归下降分析程序构造如果用某种高级语言写出所有递归过程，那就可以用这个如果用某种高级语言写出所有递归过程，那就可以用这个语言的编译系统来产生整个的语法分析程序。语言的编译系统来产生整个的语法分析程序。几个全局过程和变量：几个全局过程和变量：ADVANCE，读入读入IP 指向的输入符号到指向的输入符号到SYM中中，把输，把输入串指示器入串指示器IP指向下一个输入符号指向下一个输入符号。SYM，IP当前所指的输入符号。当前所指的输入符号。ERROR，出错处理程序。，出错处理程序。第74页，本讲稿共113页例例:文法文法G(E):ETE E+TE|TFT T*FT|F(E)|i非终结符号的分析子程序的功能非终结符号的分析子程序的功能是：用产生式是：用产生式 右部符号串来匹配输入串。右部符号串来匹配输入串。每个非终结符都有对应的递归过程，在分析过每个非终结符都有对应的递归过程，在分析过程中，当需要从某个非终结符出发进行展开程中，当需要从某个非终结符出发进行展开(推推导导)时，就调用这个非终结符对应的子程序。时，就调用这个非终结符对应的子程序。第75页，本讲稿共113页假定在开始工作前，输入串指示器假定在开始工作前，输入串指示器IP指向第一个输入符指向第一个输入符号。当每个子程序工作完毕之后，号。当每个子程序工作完毕之后，IP总是指向下一个未总是指向下一个未处理的符号。处理的符号。E+TE|E 只有两个候选，第一个候选的开头终结符为只有两个候选，第一个候选的开头终结符为+，第二个第二个候选为候选为。当当E 面临输入符号面临输入符号+时，就令时，就令第一个候选进入工作，当面临第一个候选进入工作，当面临任何其它输入符号任何其它输入符号时，时，E 就自动认为获得了匹配（这时，更就自动认为获得了匹配（这时，更精确的做法是判断该精确的做法是判断该输入符号是否属于输入符号是否属于FOLLOW(E)）。4.4 递归下降分析程序构造递归下降分析程序构造第76页，本讲稿共113页/将将看成与任一符号匹配看成与任一符号匹配例例:文法文法G(E):ETE E+TE|TFT T*FT|F(E)|i对应的递归下降子程序为对应的递归下降子程序为:PROCEDURE E；BEGIN T；E END；PROCEDURE E；IF SYM=+THEN BEGINADVANCE；T；E END；第77页，本讲稿共113页PROCEDURE T；BEGIN F；T END；PROCEDURE T；IF SYM=*THENBEGIN ADVANCE；F；T END；例例:文法文法G(E):ETE E+TE|TFT T*FT|F(E)|i对应的递归下降子程序为对应的递归下降子程序为:第78页，本讲稿共113页例例:文法文法G(E):ETE E+TE|TFT T*FT|F(E)|i对应的递归下降子程序为对应的递归下降子程序为:PROCEDURE F；IF SYM=i THEN ADVANCE ELSE IF SYM=(THEN BEGIN ADVANCE;E；IF SYM=)THEN ADVANCE ELSE ERROR END ELSE ERROR;第79页，本讲稿共113页第四章第四章 语法分析语法分析-自上而下分析自上而下分析4.1 语法分析器的功能语法分析器的功能4.2 自上而下分析面临的问题自上而下分析面临的问题4.3 LL(1)分析法分析法4.4 递归下降分析程序构造递归下降分析程序构造4.5 预测分析程序预测分析程序第80页，本讲稿共113页4.5 预测分析程序预测分析程序 4.5.1 预测分析程序工作过程预测分析程序工作过程 4.5.2 预测分析表的构造预测分析表的构造 本节要重点掌握