第4章语法分析自上而下分析

1、第4章语法分析自上而下分析第4章 语法分析 自上而下分析第4章语法分析自上而下分析4.1 语法分析器的功能4.2 自上而下分析面临的问题4.3 LL(1)分析法4.4 递归下降分析程序构造4.5 预测分析程序第4章 语法分析 自下而上分析第4章语法分析自上而下分析n语法分析器的位置语法分析器词法分析器符号表编译程序的后续部分token取下一个单词语法树第4章语法分析自上而下分析语法分析器n语法分析器的输入qToken序列：词法分析产生的输出，是各个单词都正确的源程序，是一个有限序列n语法分析器的功能q按照语言的语法构成规则, 识别输入的符号串输入的符号串能否构成一个句子。规则是用文法的产生式来

2、定义的。q对给定一个输入串，如何判定它是不是一个句子？q根据文法的产生式规则，从开始符号出发，看能否推导出这个输入串匹配的句子。这就需要建立与输入串匹配的语法分析树。n语法分析器的输出q分析树：如何表示？ P89q错误处理信息：定位、继续编译第4章语法分析自上而下分析 常用的语法分析方法：常用的语法分析方法：根据建立语法分析树的方法不同，语法分析方法有两类： 自顶向下分析递归下降分析预测分析(LL)自底向上分析 算符优先分析 LR分析( LR(0)LR(0)、SLR(1)SLR(1)、LR(1)LR(1)、LALR)LALR)自上而下分析法自上而下分析法：从文法的开始符号出发，向下推导从文法的

3、开始符号出发，向下推导(使用最左推使用最左推导导) ，尽可能使用各种产生式，推导出与输入串，尽可能使用各种产生式，推导出与输入串匹配的句子。匹配的句子。自下而上分析法自下而上分析法：从输入符号串开始，逐步进行归约从输入符号串开始，逐步进行归约(最右推导的最右推导的逆过程逆过程)，直至归约到文法的开始符号。，直至归约到文法的开始符号。第4章语法分析自上而下分析自顶向下分析n自上而下分析的主旨是：对任何输入串，试图用一切可能的办法，从文法的开始符号出发，自上而下地为输入串建立一个语法树。n从推导的角度看，从开始符号出发，使用最左推导，试图推导出与输入符号串相同的句子。n从语法树的角度看，从根节点出

4、发，反复使用所有可能的产生式，谋求输入串的匹配，试图向下构造一棵语法树，其末端结点正好与输入符号串相同。n这是一个反复试探的过程。第4章语法分析自上而下分析自顶向下分析面临的问题自顶向下分析面临的问题 n问题1：回溯例1：设有文法(1) S - xAy (2) A - *|* 现有输入串：x*y 其分析过程如下：SxAy*失败，需要退回，重新选取失败，需要退回，重新选取A A的侯选式的侯选式这时使得分析器的动作不稳定这时使得分析器的动作不稳定产生的原因？x*y输入符号串：第4章语法分析自上而下分析n问题2：左递归n左递归：是左递归的，如果一个文法中存在某个非终结符号A，使A A。n如果是A A

5、，则称为直接左递归，否则称为间接左递归。例2：设有文法：E-E+T|TT-T*F|FF-(E)|i(1) 现有输入串i*i+i, 其分析过程是：EE+TE+TE+T失败：由于使用最左推导，对左递归文法进失败：由于使用最左推导，对左递归文法进行自顶向下分析时，会导致死循环。行自顶向下分析时，会导致死循环。产生的原因？第4章语法分析自上而下分析结论n左递归和回溯问题的产生直接与描述语言的文法有关n因此，要对文法进行确定的自顶向下分析应该改造文法，使其不含左递归和回溯第4章语法分析自上而下分析左递归的消除n1. 1. 直接左递归的消除：直接左递归的消除：q假定产生式为：假定产生式为：PP|PP|，将

6、其替换为形式等价，将其替换为形式等价的产生式组：的产生式组：例2：文法 E - E+T|T T-T*F|F F-(E)|i消去左递归后为： E - TE E-+TE| T-FT T-*FT| F-(E)|i PP P P 第4章语法分析自上而下分析q一般而言，产生式为：一般而言，产生式为：AAA1 1|A|A2 2|A|An n| |1 1| |2 2|m m 将其替换为：将其替换为：A1 B|2 B |m BB1 B|2 B |n B| 2. 2. 间接左递归的消除间接左递归的消除 (1) (1) 代入代入 (2) (2) 消除直接左递归消除直接左递归第4章语法分析自上而下分析回 溯n回溯产

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

8、造文法，使得文法的每个非终结符号的各个候选式的首终结符两两不相交，来避免回溯。n例： 设产生式为设产生式为：A1 1|2 2|n n 将其替换为：将其替换为：AAA1|2|n第4章语法分析自上而下分析n例3：有如下两个产生式： if E then S1 else S2; if E then S1;提取左因子后： if E then S1 B; B else S2 | ;第4章语法分析自上而下分析n是否满足：没有左递归，每个侯选式的首终结符集不相交这两个条件，就一定能进行有效的自顶向下分析呢？n例：使用下述文法对 i + i 进行分析： E TE E +TE| T FT T *FT| F (E)

9、|i第一步：ifirst(TE) ifirst(FT) ifirst(F)ETEFTi第三步：+first(E)第二步：+first(T) 用用自动匹配自动匹配 不读输入符号不读输入符号+TEFTiLL(1)分析条件：第4章语法分析自上而下分析n并不是在任何情况下，A面对输入符号a， a不属于A的任何侯选式，但A中含产生式时都可以使用自动匹配。n定义(后随符号集)：假定S是文法的开始符号，对于 AN N： FOLLOW(A)=a|SFOLLOW(A)=a|SAaAa，aaT T 特别，若 S SAA，则，则，# # FOLLOW(A)FOLLOW(A)n因此，当非终结符A面临a时， 且a不属于

10、A的任何侯选首终结符集，但A的某个候选首终结符集中含，只有当a FOLLOW(A)FOLLOW(A)时才能自动进行匹配。* * *第4章语法分析自上而下分析nLL(1) 文法：(对文法进行不带回溯的确定的自顶向下分析的条件)，据此判别是否为LL(1)文法。q(1) 文法不含左递归q(2) 对文法中的任一个非终结符A的各个产生式的侯选首终结符集两两不相交，即：若A1|2|n ，则 First(ai)aj) = q(3) 对文法中的每个非终结符A,若它存在某个首选符集含有 ，则 First(A)A) = 第4章语法分析自上而下分析LL(1)文法的分析过程n(P73)假设要用非终结符A进行匹配，面临

11、输入符号a，A的所有侯选式为： A1|2|nn分析过程为分析过程为：q若a First(Ai),则使用i去执行匹配任务。q若a不属于任何一个产生式的首选符集，n(1)若不属于任何一个 First(Ai)，则出错。n(2)若属于某个First(Ai),同时a Follow(A), 则让A 与自动匹配；否则，a的出现是一种语法错误。第4章语法分析自上而下分析两个集合的构造1、FIRST2、FOLLOW第4章语法分析自上而下分析1、FIRST集的求法集的求法 (1)文法符号的终结首符集：FIRST（X） XVT FIRST（X) =X XVN, 需观察X为左部的产生式规则定义：定义：FIRST()=

12、a| a.=a| a.特别是，若特别是，若 ，则规定，则规定 FIRST ()*第4章语法分析自上而下分析FIRST集的求法集的求法 Aa. A1| 2|.| n FIRST(A)AAX1X2.XKA X1X2.XK*a. X2.XKFIRST(X1)FIRST(X2).X2.XK . 第4章语法分析自上而下分析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 第4

13、章语法分析自上而下分析1 1、FIRSTFIRST集的求法集的求法 (1)文法符号的终结首符集：FIRST（X） XVT FIRST（X) =X XVN, 需观察X为左部的产生式规则(2)候选式的终结首符集：FIRST（） =X1X2Xn第4章语法分析自上而下分析2 2、FOLLOWFOLLOW集的求法集的求法 BAFOLLOW(A)BA*若A是开始符号#FIRST()FIRST()FOLLOW(B)FOLLOW(B)FOLLOW(B)FOLLOW(B)第4章语法分析自上而下分析FOLLOWFOLLOW集的求法集的求法 例：求下面每个非终结符号的FOLLOW集： E TE E +TE |T F

14、TT *FT |F (E) | i FIRST(E) = (, i FIRST(E) = (, i FIRST(E FIRST(E )= +, )= +, FIRST(T) = (, i FIRST(T) = (, i FIRST(T FIRST(T )= )= * *, , FIRST(F) = (, i FIRST(F) = (, i FOLLOW(E) = FOLLOW ( E )=FOLLOW (T) =FOLLOW (T )=FOLLOW (F) = #, ) #, ) +,#, ) +,#, ) *,+,#, ) 第4章语法分析自上而下分析练习：求下题的FIRST和FOLLOW集合

15、。 Sa | (T) TST T ,ST | STT FIRST a , ( a , ( , , FOLLOW # , , ) ) ) 第4章语法分析自上而下分析4.4 递归下降分析程序的构造void E() T; E第4章语法分析自上而下分析4.5 预测分析程序一、预测分析表构造二、预测分析程序第4章语法分析自上而下分析4.5 预测分析程序一、预测分析表的构造 1、FIRST集合构造 2、FOLLOW集合构造 3、预测分析表的构造第4章语法分析自上而下分析3、预测分析表的构造、预测分析表的构造 A1|2|nLL（1）分析过程为）分析过程为：(1)若a FIRST(i),则使用i去执行匹配任务

16、。(2)若a不属于任何一个产生式的首选符集，则：n若属于某个FIRST(i),同时a FOLLOW(A), 则让A 与自动匹配；n否则，a的出现是一种语法错误。构造分析表的方法：构造分析表的方法：（1）对每个A，执行第2步和第3步；（2）对每个终结符a FIRST(），把A加至MA,a中；（3）若FIRST()，则对任何b FOLLOW()，把A加至MA,b中；（4）把所有无定义的位置上标上“出错标志”。第4章语法分析自上而下分析例：E TEE +TE |T FTT *FT |F (E) |i i+*()#EETTFETEETEE+TEE E T FTT FTT T T FiF(E)T*FT3

17、、预测分析表的构造、预测分析表的构造 第4章语法分析自上而下分析二、预测分析程序4.5 预测分析程序第4章语法分析自上而下分析初始：a1a2.an#S#分析栈输入串某个中间结果a.#X.#分析栈输入串a. xVN查看预测分析表: Xx1.xn分析栈a.#. .#输入串x1xn下一步产生的结果第4章语法分析自上而下分析a.#X.#分析栈输入串b. xVT.#.#分析栈输入串X=aX!=aX=a =# 下一步产生的结果某个中间结果 出错！ 分析结束 第4章语法分析自上而下分析2、预测分析过程实例、预测分析过程实例n下面用预测分析方法对输入串i+i*i# 进行分析，给出栈的变化过程如下：步骤分析栈剩余输入串所用产生式2 #ET i+i*i#ETETFT 1#E i+i*i#第4章语法分析自上而下分析3#ETFi+i*i#4#ETii+