语法分析自上而下分析

语法分析自上而下分析第一页，共一百一十三页，2022年，8月28日课程安排内容讲授课时实验课时第一章引论2第二章高级程序语言及其语法描述2第三章词法分析实验一词法分析器（第6、7、8、9周）108第四章语法分析----自上而下分析8第五章语法分析----自下而上分析实验二语法分析器（第13、14、15、16周）88第六章属性文法和语法制导翻译8第七章语义分析及中间代码产生8第八章优化2合计4816第二页，共一百一十三页，2022年，8月28日实验时间：实验一词法分析：第6、7、8、9周实验二语法分析：第13、14、15、16周实验地点：计算机系实验中心（5教910、911）指导教师：杨健、张谦实验安排杨健：张谦：邮箱：bigjordon@126.com地点：五教8层802图像处理研究室第三页，共一百一十三页，2022年，8月28日数字媒体制作实验室910计11-12

软件开发实验室911计11-34

第6、7、8、9周，都是周二1,2节实验一词法分析器（第6、7、8、9周）第四页，共一百一十三页，2022年，8月28日第四章语法分析-自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序第五页，共一百一十三页，2022年，8月28日第四章语法分析-自上而下分析了解：语法分析器的功能。熟悉：预测分析程序、递归下降分析程序的设计方法。掌握：LL(1)分析法的条件，消除左递归的算法，预测分析表的构造。第六页，共一百一十三页，2022年，8月28日第四章语法分析-自上而下分析作业：

4.1，4.2第七页，共一百一十三页，2022年，8月28日4.1考虑下面文法G1:

S→a∣∧∣(T) T→T,S∣S（1）消去G1的左递归。然后对每个非终结符，写出不带回溯的递归子程序。（2）经改写后的文法是否是LL(1)的？给出它的预测分析表。第四章语法分析-自上而下分析第八页，共一百一十三页，2022年，8月28日4.2对下面的文法G： E→TE E→+E∣ε T→FT T→T∣ε F→PF F→*F∣ε P→(E)∣a∣b∣∧（1）计算这个文法的每个非终结符的FIRST和FOLLOW。（2）证明这个文法是LL(1)的。（3）构造它的预测分析表。（4）构造它的递归下降分析程序。第九页，共一百一十三页，2022年，8月28日第三章词法分析实验一词法分析器

每次实验结束都必须写出实验报告，报告内容包括：实验题目、实验目的和要求，实验的实现（包括主要设计思想、实现算法、主要技术问题的处理方法，及实验结果），结论分析。实验二语法分析器第十页，共一百一十三页，2022年，8月28日实验二

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

值语句带标号的赋值语句→<标号><赋值语句>赋值语句→变量=算术表达式条件语句→

IF<布尔表达式>THEN语句｜IF

<布尔表达式>THEN语句ELSE语句第十一页，共一百一十三页，2022年，8月28日实验二

语法分析器构造转移语句→GOTO标号变量→标识符标识符→字母｜<标识符><数字>字母→A｜B｜…｜Z｜a｜b｜…｜z数字→0｜1｜…｜9算术表达式→项｜算术表达式+项｜算术表达式-项项→因子｜项*因子｜项/因子｜因子↑项因子→变量｜常数｜(表达式)布尔表达式→<算术表达式><关系符><算术表达式>关系符→>｜<｜>=｜<=｜=｜<>标号→常数常数→数字｜<常数><数字>第十二页，共一百一十三页，2022年，8月28日实验二

语法分析器构造三、说明和提示1.本实验的优先表可以手工先设计好。2.本实验要求中提出的“产生相应的归约信息”意指在语法分析的过程中，一旦产生归约，在程序上产生并最终输出归约产生式序号。3.出错类型的产生可预先对应优先表中出错栏列表说明其出错类型，并分别编序，当分析中产生错误时以字符串输出相应表中错误信息。4.算法采用一个符号栈的数据结构，既用它存放终结符，也用它存放非终结符。第十三页，共一百一十三页，2022年，8月28日第四章语法分析-自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序第十四页，共一百一十三页，2022年，8月28日中间代码单词符号语法单位中间代码目标代码词法分析器语法分析器语义分析与中间代码产生器优化器源程序表格管理出错处理目标代码生成器编译程序总框第十五页，共一百一十三页，2022年，8月28日本章主要介绍语法分析的处理要进行语法分析，必须对语言的语法结构进行描述。采用正规式和有限自动机可以描述和识别语言的单词符号；用上下文无关文法来描述语法规则。第四章语法分析-自上而下分析第十六页，共一百一十三页，2022年，8月28日形式化定义：一个上下文无关文法是一个四元式（VT,VN,S,Ｐ）VT是一个非空有限集，它的每个元素称为终结符号；VN是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=ф；S是一个非终结符号，称为开始符号；S∈VN。Ｐ是一个产生式集合（有限），每个产生式的形式是P→а。其中，P∈VN，а∈(VT∪VN)＊。开始符号S必须至少在某个产生式的左部出现一次。P→а1|а2|…|аn。其中，аi称为是P的一个候选式。→读作“定义”，直竖读为“或”,它是元语言符号。2.3.1上下文无关文法第十七页，共一百一十三页，2022年，8月28日2.3.1上下文无关文法定义：称A直接推出，即A

仅当A是一个产生式，且，(VT

VN)*

。如果1

2

n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n

。对文法G(E)：Ei|E+E|E*E|(E)E(E)(E+E)(i+E)(i+i)第十八页，共一百一十三页，2022年，8月28日

用表示：从1出发，经过0步或若干步，可以推出n。

所以：即或定义：假定G是一个文法，S是开始符号。如果，则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。通常，用

表示：从1出发，经过一步或若干步，可以推出n。第十九页，共一百一十三页，2022年，8月28日例：(i*i+i)是文法G(E)：Ei|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上下文无关文法第二十页，共一百一十三页，2022年，8月28日第四章语法分析-自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序第二十一页，共一百一十三页，2022年，8月28日4.1语法分析器的功能语法分析的任务是分析一个文法的句子结构。语法分析器的功能：按照文法的产生式，识别输入符号串是否为一个句子。策略：自上而下分析法，自下而上分析法。

两种方法反映了两种语法树的构造过程。第二十二页，共一百一十三页，2022年，8月28日源程序单词符号取下一单词符号...语法分析树词法分析器语法分析器符号表编译程序后续部分图4.1语法分析器在编译程序中的地位4.1语法分析器的功能第二十三页，共一百一十三页，2022年，8月28日语法分析的方法-自上而下分析法(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找“匹配”的推导。从树根到叶子来建立语法树。递归下降分析法：对每个非终结符号构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序优点：直观、简单和宜于手工实现。第二十四页，共一百一十三页，2022年，8月28日语法分析的方法-自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。从树叶到树根来建立语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约第二十五页，共一百一十三页，2022年，8月28日

G(E)：Ei|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第二十六页，共一百一十三页，2022年，8月28日第四章语法分析-自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序第二十七页，共一百一十三页，2022年，8月28日4.2自上而下分析面临的问题自上而下就是从文法的开始符号出发，向下推导，推出句子。自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。第二十八页，共一百一十三页，2022年，8月28日例文法G(E):

EiEE+EEE*EE(E)对句子(i+i)最左推导E(E)(E+E)(i+E)(i+i)4.2自上而下分析面临的问题第二十九页，共一百一十三页，2022年，8月28日例假定有文法G(S):(1)S→xAy(2)A→**|* 分析输入串x*y序号指示器IP指向语法树最左推导说明

x*yS根结S,当前符x①x*y③x得匹配,移动IPSx

A

ySxAy用S→xAy展开S欲用xAy匹配输入串SxAy

②x*y第三十页，共一百一十三页，2022年，8月28日序号IP指向语法树最左推导说明Sx*yx

A

y试用A→**展开ASxAyx**y④**x*y⑤*得匹配,移动IP,但y得不到匹配Sx

A

y*

*用A→**展开失败,回溯,回到第③步⑥Sx

A

ySxAyx*y第三十一页，共一百一十三页，2022年，8月28日

序号IP指向语法树最左推导说明x*ySx

A

y试用A→*展开ASxAyx*y⑦*

x*y⑧*得匹配,移动IPSx

A

y*

A完成匹配,y得匹配,移动IP,输入串匹配成功,结束⑨Sx

A

ySxAyx*yx*y*

第三十二页，共一百一十三页，2022年，8月28日存在回溯的原因文法中非终结符A的产生式右部称为A的候选式，如果有多个候选式左端第一个符号相同，则语法分析程序无法根据当前输入符号选择产生式，只能试探。例假定有文法G(S):(1)S→xAy(2)A→**|* 分析输入串x*y第三十三页，共一百一十三页，2022年，8月28日自上而下分析方法的步骤：（带回溯的试探过程）⑴

遇非终结符,

就试图用某个候选式展开,期望此候选能匹配输入串,若不能匹配,则要回溯。⑵遇终结符，就进行匹配，然后移动输入串指针IP指向下一个符号。回溯是一项复杂而费时的工作，须废弃已做的许多工作，恢复到前面的某一情况，效率很低。4.2自上而下分析面临的问题第三十四页，共一百一十三页，2022年，8月28日当某个非终结符有多个产生式候选时，可能带来如下问题:1.分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。2.文法左递归问题。一个文法是含有左递归的，如果存在非终结符P含有左递归的文法将使自上而下的分析陷入无限循环。4.2自上而下分析面临的问题第三十五页，共一百一十三页，2022年，8月28日第四章语法分析-自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序第三十六页，共一百一十三页，2022年，8月28日4.3LL(1)分析法构造不带回溯的自上而下分析算法要消除文法的左递归性克服回溯第三十七页，共一百一十三页，2022年，8月28日4.3LL(1)分析法4.3.1左递归的消除4.3.2消除回溯、提左因子4.3.3LL(1)分析条件第三十八页，共一百一十三页，2022年，8月28日4.3.1左递归的消除直接消除见诸于产生式中的左递归：假定关于非终结符P的产生式为

P→P|其中不以P开头，不等于。可以把P的产生式等价地改写为如下的非直接左递归形式：

P→P

P→P|左递归变右递归第三十九页，共一百一十三页，2022年，8月28日例文法G(E):E→E＋T|TT→T*F|FF→(E)|i经消去直接左递归后变成：E→TEE→+TE|

T→FTT→*FT|F→(E)|i

第四十页，共一百一十三页，2022年，8月28日一般而言，假定P的产生式是 P→P1|P2|…|Pm

|1|2|…|n其中，每个都不等于，每个都不以P开头。那么，消除P的直接左递归性就是将产生式改写成：P→1P|2P|…|nP P→1P|2P|…|mP|左递归变右递归4.3.1左递归的消除第四十一页，共一百一十三页，2022年，8月28日例如文法G(S):S→Qc|cQ→Rb|bR→Sa|a 虽没有直接左递归，但S、Q、R都是左递归的SQcRbcSabc一个文法消除左递归的条件：不含以为右部的产生式不含回路。4.3.1左递归的消除第四十二页，共一百一十三页，2022年，8月28日消除左递归的算法:（1）把文法G的所有非终结符按任一种顺序排列成P1，P2，…，Pn；按此顺序执行；（2）FORi:=1TOnDOBEGIN

FORj:=1TOi-1DO把形如Pi→Pj的产生式改写成Pi→1|2|…|k;(其中Pj→1|2|…|k是Pj的产生式)消除Pi产生式的直接左递归性

END（3）化简由（2）所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生式。为非终结符编号，再采用代入法将间接左递归变为直接左递归，消除直接左递归。第四十三页，共一百一十三页，2022年，8月28日例考虑文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非终结符的排序为R、Q、S。

对于R，不存在直接左递归。

把R代入到Q的有关候选后，把Q的产生式变为Q→Sab|ab|b

现在的Q不含直接左递归，把它代入到S的有关候选后，S变成S→Sabc|abc|bc|c

消除S的直接左递归后：

S→abcS|bcS|cS

S→abcS|

Q→Sab|ab|b

R→Sa|aQ和R的规则已是多余的，化简为： S→abcS|bcS|cS S→abcS|

文法(4.4)第四十四页，共一百一十三页，2022年，8月28日注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。例如，若对文法非终结符排序选为S、Q、R，那么，最后所得的无左递归文法是： S→Qc|c Q→Rb|b

文法(4.5) R→bcaR|caR|aR

R→bcaR|

文法(4.4)和(4.5)的等价性是显然的。消除左递归前后，文法的开始符号不变。4.3.1左递归的消除第四十五页，共一百一十三页，2022年，8月28日例考虑文法G(S)S→Qc|cQ→Rb|bR→Sa|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→bcaR|

最后所得的无左递归文法是：

S→Qc|c

Q→Rb|b

文法(4.5)

R→bcaR|caR|aR

R→bcaR|

第四十六页，共一百一十三页，2022年，8月28日4.3LL(1)分析法4.3.1左递归的消除4.3.2消除回溯、提左因子4.3.3LL(1)分析条件第四十七页，共一百一十三页，2022年，8月28日回溯问题什么是回溯?分析工作要部分地或全部地退回去重做叫回溯。造成回溯的条件：

文法中，对于某个非终结符号的产生式右部有多个选择，并根据所面临的输入符号不能准确地确定所要的选择时，就可能出现回溯。回溯带来的问题：严重的低效率，只有在理论上的意义而无实际意义。例假定有文法G(S):(1)S→xAy(2)A→**|* 分析输入串x*y第四十八页，共一百一十三页，2022年，8月28日4.3.2消除回溯、提左因子为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。A→1|2|…|nSa….IPA......第四十九页，共一百一十三页，2022年，8月28日令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为：

特别是，若，则规定FIRST()。若非终结符A的所有候选终结首符集两两不相交，即A的任何两个不同候选i和jFIRST(i)∩FIRST(j)＝当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的。FIRST()是的所有可能推导的开头终结符或可能的ε。第五十页，共一百一十三页，2022年，8月28日提取公共左因子:

假定关于A的产生式是A→1|2|…|n|1|2|…|m (其中，每个

不以开头)那么，可以把产生式改写成A→A|1|2|…|mA→1|2|…|n经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。第五十一页，共一百一十三页，2022年，8月28日52文法

SiBtSeS|iBtS|aBb

提取公共左因子改写文法。提取公共左因子，将文法改写为

SiBtSS|aS

eS|εB

b4.3.2消除回溯、提左因子第五十二页，共一百一十三页，2022年，8月28日一个文法不含左递归，且所有候选式首符集两两不相交，但带ε产生式，在自上而下分析又带来新问题：这就引出自动匹配问题。当非终结符A面临输入符号a，且a不属于A的任意候选首符集，但A的某个候选首符集包含时，就一定可以使A自动匹配。这是一种错误。4.3.2消除回溯、提左因子第五十三页，共一百一十三页，2022年，8月28日4.3LL(1)分析法4.3.1左递归的消除4.3.2消除回溯、提左因子4.3.3LL(1)分析条件文法是LL(1)的第一个L从左到右扫描输入串第二个L生成的是最左推导

1向前看一个输入符号（lookahead)第五十四页，共一百一十三页，2022年，8月28日E→TEE→+TE|T→FTT→*FT|F→(E)|ii+i4.3.3LL(1)分析条件例文法G(E):E→E＋T|TT→T*F|FF→(E)|i经消去直接左递归后变成：E→TEE→+TE|

T→FTT→*FT|F→(E)|i

第五十五页，共一百一十三页，2022年，8月28日i+iIPEG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第五十六页，共一百一十三页，2022年，8月28日i+iIPETEG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第五十七页，共一百一十三页，2022年，8月28日i+iIPETEFTG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第五十八页，共一百一十三页，2022年，8月28日i+iIPETEFTiG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第五十九页，共一百一十三页，2022年，8月28日i+iIPETEFTiG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第六十页，共一百一十三页，2022年，8月28日i+iIPETEFTiG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第六十一页，共一百一十三页，2022年，8月28日i+iIPETEFTi+TEG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第六十二页，共一百一十三页，2022年，8月28日i+iIPETEFTi+TEG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第六十三页，共一百一十三页，2022年，8月28日i+iIPETEFTi+TEFTG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第六十四页，共一百一十三页，2022年，8月28日i+iIPETEFTi+TEFTiG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第六十五页，共一百一十三页，2022年，8月28日i+iIPETEFTi+TEFTiG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第六十六页，共一百一十三页，2022年，8月28日i+iIPETEFTi+TEFTiG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i第六十七页，共一百一十三页，2022年，8月28日i+iIPETEFT’i+TEFTiG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|iS…T+…第六十八页，共一百一十三页，2022年，8月28日假定S是文法G的开始符号，对于G的任何非终结符A，我们定义

若

,则规定＃FOLLOW(A)4.3.3LL(1)分析条件即FOLLOW(A)是所有句型中紧跟在A之后的终结符或#。第六十九页，共一百一十三页，2022年，8月28日构造不带回溯的自上而下分析的文法条件1.文法不含左递归。2.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A→1|2|…|n则FIRST(i)∩FIRST(j)＝ (ij)3.对文法中的每个非终结符A，若它存在某个候选首符集包含，当ε∈FIRST(αj)时，则FOLLOW(A)∩FIRST(αi)=Φ如果一个文法G满足以上条件，则称该文法G为LL(1)文法。 第七十页，共一百一十三页，2022年，8月28日对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为A→1|2|…|n1.若aFIRST(i)，则指派i执行匹配任务；2.若a不属于任何一个候选首符集，则：(1)若属于某个FIRST(i)且aFOLLOW(A)，则让A与自动匹配。(2)否则，a的出现是一种语法错误。第七十一页，共一百一十三页，2022年，8月28日第四章语法分析-自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序第七十二页，共一百一十三页，2022年，8月28日4.4递归下降分析程序构造构造不带回溯的自上而下分析程序要消除文法的左递归性克服回溯第七十三页，共一百一十三页，2022年，8月28日当一个文法满足LL(1)条件时，我们就可以为它构造一个不带回溯的自上而下分析程序，这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。4.4递归下降分析程序构造如果用某种高级语言写出所有递归过程，那就可以用这个语言的编译系统来产生整个的语法分析程序。几个全局过程和变量：ADVANCE，读入IP指向的输入符号到SYM中，把输入串指示器IP指向下一个输入符号。SYM，IP当前所指的输入符号。ERROR，出错处理程序。第七十四页，共一百一十三页，2022年，8月28日例:文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i 非终结符号的分析子程序的功能是：用产生式右部符号串来匹配输入串。每个非终结符都有对应的递归过程，在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。第七十五页，共一百一十三页，2022年，8月28日假定在开始工作前，输入串指示器IP指向第一个输入符号。当每个子程序工作完毕之后，IP总是指向下一个未处理的符号。E→+TE|E

只有两个候选，第一个候选的开头终结符为+，第二个候选为。当E

面临输入符号+时，就令第一个候选进入工作，当面临任何其它输入符号时，E就自动认为获得了匹配（这时，更精确的做法是判断该输入符号是否属于FOLLOW(E)）。4.4递归下降分析程序构造第七十六页，共一百一十三页，2022年，8月28日//将ε看成与任一符号匹配例:文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i对应的递归下降子程序为:

PROCEDUREE；BEGIN T；EEND；

PROCEDUREE；IFSYM=‘+’THEN BEGIN ADVANCE；T；E

END；第七十七页，共一百一十三页，2022年，8月28日PROCEDURET；BEGIN F；TEND；PROCEDURET；IFSYM=‘*’THENBEGINADVANCE；F；TEND；例:文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i对应的递归下降子程序为:

第七十八页，共一百一十三页，2022年，8月28日例:文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i对应的递归下降子程序为:

PROCEDUREF；IFSYM=‘i’THEN

ADVANCEELSE

IFSYM=‘(’THEN

BEGIN

ADVANCE;

E；

IFSYM=‘)’THEN

ADVANCE ELSEERROR

END ELSEERROR;第七十九页，共一百一十三页，2022年，8月28日第四章语法分析-自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序第八十页，共一百一十三页，2022年，8月28日4.5预测分析程序4.5.1预测分析程序工作过程4.5.2预测分析表的构造本节要重点掌握:1.对给定文法构造符号串的FIRST集合和非终结符的FOLLOW集合。

2.构造预测分析表的方法。第八十一页，共一百一十三页，2022年，8月28日4.5.1预测分析程序工作过程预测分析程序或LL(1)分析法：总控程序分析表M[A，a]矩阵，AVN，aVT是终结符或‘＃’，分析栈STACK用于存放文法符号第八十二页，共一百一十三页，2022年，8月28日总控程序分析表X#输入串分析栈STACKa1a2...ai…#预测分析器模型#Sa1a2...ai…#分析开始时：输出第八十三页，共一百一十三页，2022年，8月28日总控程序根据现行栈顶符号X和当前输入符号a，执行下列三种动作之一:（1）若X＝a＝‘＃’，则宣布分析成功，停止分析过程。（2）若X＝a‘＃’，则把X从STACK栈顶逐出，让a指向下一个输入符号。匹配成功4.5.1预测分析程序工作过程第八十四页，共一百一十三页，2022年，8月28日4.5.1预测分析程序工作过程（3）若X是一个非终结符，则查看分析表M。若M[X，a]中存放着关于X的一个产生式，首先将X弹出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为，则意味不推任何东西进栈)。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作（目前暂不管）。若M[X，a]中存放着“出错标志”，则调用出错诊察程序ERROR。推导第八十五页，共一百一十三页，2022年，8月28日例对于文法G(E)E→TEE→+TE|T→FT

T→*FT|F→(E)|i 输入串为i1*i2+i3，利用分析表进行预测分析：分析表矩阵元素M[A,a]指出非终结符A，面临输入符号a时，应选用的候选式（或产生式）。若A不该面临a，则放一出错标志。注：矩阵元素空白表示ERROR第八十六页，共一百一十三页，2022年，8月28日步骤

符号栈

输入串

所用产生式0 #E i1*i2+i3#1 #ET i1*i2+i3# E→TE2 #ETF i1*i2+i3# T→FT3 #ETi i1*i2+i3# F→i推导第八十七页，共一百一十三页，2022年，8月28日步骤

符号栈

输入串

所用产生式4 #ET *i2+i3#5 #ETF* *i2+i3# T→*FT6 #ETFi2+i3#7 #ETi i2+i3#F→i推导推导第八十八页，共一百一十三页，2022年，8月28日步骤

符号栈

输入串

所用产生式8 #ET +i3#9 #E +i3# T→10 #ET+ +i3# E→+TE11 #ET i3#推导推导第八十九页，共一百一十三页，2022年，8月28日步骤

符号栈

输入串

所用产生式12 #ETF i3# T→FT13 #ETi i3# F→i14 #ET #15 #E # T→16 # # E→推导第九十页，共一百一十三页，2022年，8月28日输出的产生式序列对应最左推导的过程，同时对应相应的分析树。最左推导过程：

ETE'FT'E'iT'E'i*FT'E'

i*iT'E'i*iE'i*i+TE'i*i+FT'E'i*i+iT'E'i*i+iE'i*i+i第九十一页，共一百一十三页，2022年，8月28日4.5预测分析程序4.5.1预测分析程序工作过程4.5.2预测分析表的构造第九十二页，共一百一十三页，2022年，8月28日4.5.2预测分析表的构造构造FIRST()和FOLLOW(A)构造分析表M[A，a]第九十三页，共一百一十三页，2022年，8月28日构造FIRST()对每一文法符号XVT∪VN构造FIRST(X)。连续使用下面的规则，直至每个FIRST集合不再增大为止：（1）若XVT，则FIRST(X)＝{X}。（2）若XVN，且有产生式X→a…，则把a加入到FIRST(X)中；若X→也是一条产生式，则把也加到FIRST(X)中。（3）若X→Y…是一个产生式且YVN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中；若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有，则把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j＝1,2,…,k，则把加到FIRST(X)中。第九十四页，共一百一十三页，2022年，8月28日对文法G的任何符号串=X1X2…Xn构造集合FIRST()。（1）置FIRST()＝FIRST(X1)\{}；（2）若对任何1ji-1，FIRST(Xj)，则把FIRST(Xi)\{}加至FIRST()中；特别是，若所有的FIRST(Xj)均含有，1jn，则把也加至FIRST()中。显然，若＝则FIRST()＝{}。构造FIRST()第九十五页，共一百一十三页，2022年，8月28日构造FOLLOW(A)对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止：（1）对于文法开始符号S，置＃于FOLLOW(S)中；（2）若A→B是一个产生式，则把FIRST()\{}加至FOLLOW(B)中；（3）若A→B是一个产生式，或AB是一个产生式而(即FIRST())，则把FOLLOW(A)

加至FOLLOW(B)中。第九十六页，共一百一十三页，2022年，8月28日例对于文法G(E)E→TEE→+TE|T→FT

T→*FT|F→(E)|i 构造每个非终结符的FIRST和FOLLOW集合：

FIRST(E)={(,i}FIRST(E)={+,}FIRST(T)={(,i}FIRST(T)={*,}FIRST(F)={(,i}

FOLLOW(E)={),#}FOLLOW(E)={),#}FOLLOW(T)={+,),#}FOLLOW(T)={+,),#}FOLLOW(F)={*,+,),#}第九十七页，共一百一十三页，2022年，8月28日在对文法G的每个非终结符A及其任意候选都构造出FIRST()和FOLLOW(A)之后，现在可以用它们来构造G的分析表M[A，a]。（1）对文法G的每个产生式A→执行第2步和第3步；（2）

对每个终结符aFIRST()，把A→加至M[A，a]中；（3）

若FIRST()，则对任何bFOLLOW(A)，把A→加至M[A，b]中。（4）把所有无定义的M[A，a]标上“出错标志”。第九十八页，共一百一十三页，2022年，8月28日第九十九页，共一百一十三页，2022年，8月28日对产生式ETE由于FIRST(TE)=FIRST(T)={(,i}故应把ETE放入M[E,(]和M[E,i]中。对于产生式E+TE由于FIRST(+TE)={+}所以，应把E+TE放入M[E,+]中。对于产生式E由于FOLLOW(E)={),#}故应把E放入M[E,)]和M[E,#]中。第一百页，共一百一十三页，2022年，8月28日如果G是左递归或二义的，那么，M至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表M。可以证明，一个文法G的预测分析表M不含多重定义入口，当且仅当该文法为LL(1)的。4.5.2预测分析表的构造LL(1)的含义：第一个L表示从左至右扫描输入符号串第二个L表示生成输入串的一个最左推导1表示在决定分析器的每步动作时，向前看一个符号。第一百零一页，共一百一十三页，2022年，8月28日（2）若β=>ε,则FIRST(α)∩FOLLOW(A)=*LL(1)文法定义：一个文法G，其分析表M不含多重定义入口(即分析表中无二条以上产生式)，则称它是一个LL(1)文法。定理：文法G是LL(1)文法的充分必要条件是：对于G的每一个非终结符A的产生式A|,下列条件成立：（1）FIRST(α)∩FIRST(β)=第一百零二页，共一百一十三页，2022年，8月28日试证明文法G是LL(1)文法。证明：

E

→+TE|FIRST(+TE)=｛+｝

FOLLOW(E)=｛)，#｝

T→*FT|FIRST(*FT)=｛*｝

FOLLOW(T)=｛+,)，#｝

F→(E)|iFIRST((E))=｛(｝

FIRST(i)=｛i｝所以G(E)是LL(1)文法。第一百零三页，共一百一十三页，2022年，8月28日G(S): SiCtS|iCtSeS|a Cb提取左因子之后，改写成：G(S): SiCtSS|a SeS| Cb最近匹配原则FIRST(S)={i,a}FIRST(S)={e,}