第五章自上而下的语法分析

1、n本章内容本章内容：从识别符号出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。从语法树的角度看，自顶向下分析过程是以识别符号为根结点根结点，试图向下构造一棵语法树，使其末端结点符号串正好与输入符号串相同。n基本知识点基本知识点：自上而下语法分析的基本思想和面临的问题，消除左递归的方法，避免回溯对文法的要求，递归子程序法，LL(1)分析法。n重点重点：消除左递归的方法，递归子程序的构造方法，LL(1)文法，LL(1)分析表的构造方法。n难点难点：符号串的FIRST集合的求法，文法非终结符号FOLLOW集合的求法以及LL(1)分析,表的构造。第五章第五章 自顶

2、向下语法分析自顶向下语法分析n文法有03型四种，语法分析方法有两种：自顶向下和自下而上自顶向下和自下而上 自顶向下分析过程: 为输入串从开始符开始构造语法树从文法开始符出发向下推导，推出句子。自顶向下语法分析自顶向下语法分析5.1 确定的自顶向下分析见例5.1S p AS q BA c A dA aW=pccadd输入串:特点:1,产生式右部由终结符开始;2,相同左部的产生式其右部由不同终结符开始特点:1,产生式右部不全由终结符开始;2,相同左部的产生式其右部由不同终结符或非终结符开始;3,文法无空产生式产生式右部串的第一个符号产生式右部串的第一个符号即即frist需要看后跟符号即follow

3、自顶向下分析总是根据当前句型中的符号和当前输入的符号决定下一步应执行的分析动作。如果句型中当前为终结符且与输入符号匹配，则读下一个输入符号；如果当前为非终结符号，则根据输入符号选择该非终结符的一个产生式进行下一步推导，为了分析方便，能够对输入串确定句型所选择的产生式需要定义两个集合：即文法符号串的首符号集First和非终结符的后跟符号集Follow。首符号集的定义首符号集的定义:n设G=（VN、VT、P、S）是上下文无关文法，则该文法的符号串的开始符号集为：nFIRST（ ）=a| * a，aVT，、V*n若 * ，则 FIRST（ ）设设是文法是文法G的任一符号串，定义的任一符号串，定义的首

4、符号集的首符号集first()是由是由推导出来的串中作为第一个符号的推导出来的串中作为第一个符号的所有终结符的集合；如果所有终结符的集合；如果*，则则 first()first()。即:为了求出给定文法关于符号X的首符号集首符号集first(X)first(X)，应用下列规则，直到再没有任何终结符号或能加到该首符号集为止。 求首符号集求首符号集:(1)(1)如果如果X X是终结符，则是终结符，则first(X)=Xfirst(X)=X。(2)(2)如果如果XX是一个产生式，则是一个产生式，则 first(X) first(X)。(3)(3)如果如果X X是非终结符，并且是非终结符，并且XYXY

5、1 1Y Y2 2Y YK K是一个产生是一个产生式，对某一个式，对某一个i i若有若有Y Y1 1Y Y2 2Y Yi i- -1 1* * 且且afirst(Yafirst(Yi i) )，则则afirst(X)afirst(X)；如果如果first(Yfirst(Yj j) )，j=1j=1，2 2，kk，则把则把加入加入first(X)first(X)。例如，例如，first(Yfirst(Y1 1) )中的每个元素都属于中的每个元素都属于first(X)first(X)；如果如果Y Y1 1不能推导出不能推导出，则则first(X)=first(Yfirst(X)=first(Y1

6、1) )； 如果如果Y Y1 1* *，则则把把first(yfirst(y2 2) )加入加入first(X)first(X)。 后跟符号集的定义后跟符号集的定义:n设G=（VN、VT、P、S）是上下文无关文法，AVN ，S是开始符号，则文法符号A的后跟符号集为：nFOLLOW（A）=a|S * A 且 aVT，aFIRST（），VT*，V+ n若S * A，且 * ，则# FOLLOW（A） 设设A为一个非终结符号，定义为一个非终结符号，定义A的后随符号集的后随符号集follow(A)为任为任意句型中紧跟在意句型中紧跟在A之后出现的所有终结符号的集合。之后出现的所有终结符号的集合。即：即：

7、若存在推导S * Aa， 、是任意语法符号串，follow(A)为所有可能的终结符号a的集合。应该注意，在推导过程中，在A和a之间可能出现其它符号串，但推导的结果 * ，这样，仍然有a follow(A)。 对给定的文法对给定的文法，求其非终结符A的集合follow(A)，应用下列规则，直到follow(A)不能再加入任何终结符号为止。(1)若A是开始符号，则输入符号的结束标志#follow(A)。(2)如果存在产生式BA，则把first()除之外的所有符号加入follow(A)。(3)如果存在产生式BA或 BA，且first()包含,即 ，则把 follow(B) 加入 follow(A)。

8、 选择集合SELECT:n给定上下文无关文法的产生式A （ AVN， V* ），n若 * ，则SELECT( A )= FIRST（ ）n若 * ，则SELECT（ A ）= (FIRST（ ）) FOLLOW（A）即即设 A 是文法G的任意产生式，该产生式的选用集定义如下：1)若 ,且不存在推导 +,则产生式A 的选用集select(A )= first()2) 若 ,但存在推导 +, 则产生式A 的选用集select(A )= first() follow(A)3) 若 = ,即产生式为A , 则其选用集select(A )= follow(A) LL（1）文法的定义n一个上下文无关文法是

9、LL（1）文法的充要条件是：n对每个非终结符A的两个不同产生式， A A ，满足SELECT（A） SELECT（A ）= ，其中、不能同时 * 即关于任一非终结符的不同产生式其选用集互不相交，则称G为LL(1)文法。 判断某一文法是否是LL(1)文法的步骤1、求出文法中所有能推出的非终结符号；2、计算文法中每一个产生式右部符号串的FIRST集；3、计算文法中每一个非终结符号的FOLLOW集；4、根据定义计算文法中每一个产生式的SELECT集；5、计算文法中具有相同左部产生式的SELECT集的交集，根据LL（1）文法定义确定该文法是否为LL（1）文法。补充例：5.2 LL(1) 文法的判别n提

10、取左公共因子文法中，如果同一非终极符的不同可选右部包含相同的前缀，则在最左推导过程中，对同一输入符号不能唯一地确定应该使用的产生式，于是只能尝试，造成回溯5.3 非LL(1)文法的等价变换 结论n产生式中含有左递归的文法不是LL（1）文法n相同左部的产生式中含有左公共因子的文法不是LL（1）文法左公共因子一般地如有产生式：A 12 n 当输入符号为从推导出来的非空串时，则不能立即决定使用产生式 A 1 ，还是2 ，在此情况下，为了避免回溯，把产生式改写为： A A A 1 2 n 其中称为左公因子。于是，对当前非终极符A若输入为中推导出来的串，则唯一地使用产生式A A。 对文法中一切左递归的消

11、除要求文法中不含回路即无A+ A的推导。满足这个要求的充分条件是:文法中不包含形如文法中不包含形如A A 的有害规则的有害规则和和 A 的空产生式的空产生式. 左递归直接左递归的形式为：A A1 A2 Am12 n 消除左递归后可改写为：A1 A 2 A n AA1 A 2A m A回溯：回溯是指否定前面的工作而退回到某环节重新做起。左递归n消除直接左递归消除间接左递归消除文法中所有左递归 消除左递归 如何消除一个文法的一切左递归呢？如果一个文法不含回路(形如A=+A的推导)，且产生式的右部也不含的候选式，那么，下述算法将消除文法的左递归： (1) 将文法GS的所有非终结符按一给定的顺序排列：

12、A1、A2、An ； (2) 执行下述循环语句将间接左递归改为直接左递归： for (i=1;i=n;i+) for (j=1;j1)在实际中极少使用。对给定的输入串按照LL(1)文法进行分析，其分析器模型模型如下: 输入缓冲区 输入缓冲区：存放要分析的词汇串分析栈：存放当前句型中尚待分析的文法符号分析表M：是个矩阵。每行对应文法的一个非终极符A A，每列对应终极符号a a，矩阵MAMA，aa表示当前栈顶为A A、输入符号为a a时应选用的产生式LL（1）分析算法分析算法 LL（1）分析表分析表MMXYZ a + b # 分析栈分析栈 输出输出#n预测分析程序n先进后出栈n预测分析表预测分析器

13、组成预测分析器组成（1）如果 X = a = #，算法结束并报告分析成功。接受输入串（2）如果 X = a #，则从栈中弹出X，并使缓冲区指针前进到下一个输入符号。（3）如果X是一个非终极符，则查分析表，若MA，a为X的产生式，用该产生式右部的逆替换栈顶符号，否则出错。 LL（1）分析算法执行如下：分析算法执行如下： LL(1)分析算法输入：串w, 文法G的分析表M输出：如果w L（G）则产生w的最左推导，否则输出错误信息。方法：初态时，分析栈为 #S ，栈顶S是文法的开始符号；缓冲区为 w #。分析器按下列操作进行语法分析：1） Push #,S；指针 ip 指向串 w # 的第一个符号；2

14、） repeat3） 令X为栈顶符号，a为ip所指的符号；4） if X 为终结符或# then5） if X = a = # then 接收 w6） else if X = a # then 弹出 X，并使ip前进7） else error8） else /* X为非终结符 */9） if MX,a = X Y1Y2 Yk then begin10） 弹出X；11） push Yk，Y2，Y1 /* Y1在栈顶 */12） end 13） else error14） until X = # ；/ * 栈为空 */ 预测分析程序框图预测分析程序框图表表5.3 表达式文法的预测分析表表达式文法的

15、预测分析表E E+T |TTT*F|F Fi |(E)例如有文法为例如有文法为: 1.判断文法是否为判断文法是否为LL(1)的的?2.构造预测分析表构造预测分析表 i+*()#ETE TE E +TE TFT FT T *FT Fi (E) 表表5.4 表达式文法的预测分析表表达式文法的预测分析表步骤步骤分析栈分析栈剩余输入串剩余输入串所用产生式所用产生式1234567891011121314151617# E# ET# ETF# ETi# ET# E# ET+# ET# ETF# ETi# ET# ETF # ETF# ETi# E T# E#i + i * i#i + i * i#i + i * i #i + i * i#+ i * i #+ i * i #+ i *