《ch6-自底向上优先分析方法》由会员分享，可在线阅读，更多相关《ch6-自底向上优先分析方法（72页珍藏版）》请在金锄头文库上搜索。
1、1,第六章 自下而上优先分析法,自下而上分析方法(移进-归约分析）基本思想： 用一个寄存文法符号的先进后出栈，将输入符号按从左到右扫描顺序逐个移入栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可归约串时（对应于某条规则右部）就进行一次归约，即用该规则左部非终结符替换相应规则右部符号串。重复这一过程直到整个输入串分析完毕，最终若栈中剩下句子右界符“#”和文法的开始符号，则所分析的输入符号串是文法的正确句子；否则就不是正确的句子，报告错误。,2,【例】文法GS（见右面部分），对输入串 abbcde# 进行语法分析，检查该符号串是否是该文法的正确句子。,SaAcBeAbAAbBd,abbcd
2、e,aAbcde,aAcde,aAcBe,S,输入串分析过程,3,SaAcBe Ab AAb Bd,分析过程可以看成自底向上构造语法树的过程，每步归约都是构造一颗子树，当输入串结束时，整个语法树构造完成。,自底向上构造语法树,4,可以看出，一个句型中当含有多个子串可以匹配不同产生式的右部时，将有不同的归约过程，究竟应该对谁先归约呢？答案：句柄 。,使用句柄归约,在分析过程中，如何确定句柄呢？,5,6.1 自下而上优先分析法概述,优先分析法有两种：简单优先分析法(规范归约)对文法按一定原则求出所有文法符号的优先关系，以确定归约过程中的句柄。算符优先分析法(不规范归约)规定算符之间的优先关系，即终
3、结符之间的优先关系，在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符号。,6,6.1 自下而上优先分析法概述,简单优先分析法: 准确、规范，但分析效率较低，实际使用价值不大。算符优先分析法： 分析速度快，适用于表达式分析，但归约不规范。,7,6.2 简单优先分析法,简单优先分析法是按照文法符号的优先关系确定句柄。,1.优先关系 (1) X=Y 当且仅当G中存在产生式规则AXY (2) XXB ， 且BY (3) XY 当且仅当G中存在产生式规则ABD ， 且BX和D=Y,关键：确定文法符号间的优先关系。,8,举例说明文法符号的优先关系,9,文法符号间的优先关系采用语法树结构表示：
4、,语法树结构,10,注：矩阵元素为空时表示该文法的任何句型中不会出现该符号对的相邻关系，在分析时若遇到它们相邻，则说明出错，也就肯定输入符号串不是该文法的句子。,优先关系矩阵,11,2.简单优先文法 若一个文法满足： （1）在文法符号集V中，任意两个符号之间最多只有一种关系成立。 （2）在文法中任意两个产生式没有相同的右部，则这样的文法为简单优先文法。,简单优先文法,12,3.简单优先分析法优先分析算法 （1）根据优先文法构造优先关系矩阵。 （2）存储文法产生式，并设符号栈S。 （3）将输入符号串a1a2an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性下一个待输入符号aj时为止。 （
5、4）栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak,即找到ak-11，n-1 满足性质 1。若 n-1A，A 为非终结符。由假设的 的尾符号和 的首符号都不是非终结符，否则与假设矛盾。又若 A 是文法的规则，则有n-1 n = 而 A 是文法的规则，它不含两个相邻非终结符，所以 也不含两个相邻的非终结符，满足性质 1。,算符文法的性质：,21,性质2：若 Ab 或 bA 出现在算符文法的句型 中，其中AVN ,bVT,则 中任何含 b 的短语必包含 A.,证明：用反证法。由算符文法的性质 1 可知。S bA若存在 B b，这时 b 和 A 不同时归约，分属于不同的短语，则必有 SB
6、A，这样在句型 BA 中，存在相邻的非终结符，所以与性质 1 矛盾。故： 中任何含 b 的短语必包含 A，证毕。,*,注意：含 b 的短语必含 A，含 A 的短语不一定含 b。,22,2终结符号间的优先关系设 G 是一个算符文法，对于任何终结符 a、b，算符优先关系 定义如下：,a=b 当且仅当 G 中含有形如Pab或PaQb的规则；ab 或RQb；ab当且仅当 G 中含有形如PRb的产生式，而Ra或RaQ；,23,由语法树来说明优先关系,1)a = b 则存在语法子树(a)，a和b 在同一句柄中同时归约，所以优先级相同。2)a b 则存在语法子树(c)，a和b 不在同一句柄中，a先归约，所以
7、 b 的优先级小于 a。, 为 或非终结符,24,设有一个不含-规则的算符文法 G，如果任何终结符对(a，b)至多只满足下述关系之一： a=b， ab， aa或A-Ba的产生式 DO INSERT(A,a) WHILE STACK 非空 DO BEGIN 把STACK的顶项记为(B,a)托出去 FOR 每个形如A-B产生式 DO INSERT(A,a) ENDEND,Procedure INSERT(A,a); IF NOT FA,a THEN BEGIN FA,a:=TRUE PUSH(A,a) ONTO STACK END,计算FIRSTVT(A)的算法：,FA,a是一个布尔数组其值为真当
8、且仅当aFIRSTVT(A),32,举例说明： 求表达式文法中每个非终结符的FIRSTVT集合。,33,举例说明： 求表达式文法中每个非终结符的FIRSTVT集合。,34,按同样方法，求每个非终结符的LASTVT（A）的集合,35,for ( 每条产生式 Ax1x2xn ) for ( i=1; i xi+1; ,2、构造分析表的算法,36,对于算符优先文法，可以引入一个新的文法开始符号S 。 SS，可以看成是句子的括号。 所以:对 FirstVT(S)中的所有 b，置 ;置 = ;,关于输入结束符号 的解释,37,对 E 求 FIRSTVT（E）和 LASTVT（E）:按构造规则，EET，则
9、+FIRSTVT(E)又 ET，TT*F，则*FIRSTVT(E)又 ET，TF，F(E)，则(FIRSTVT(E)又 ET，TF，Fi，则iFIRSTVT(E)故，FIRSTVT(E)+，*，i。类似地，LASTVT(E)+，*，i。,【例】表达式文法GE：构造该文法的算符优先关系表。,EE + T | TTT * F | FF (E)i,首先构造每个非终结符的 FirstVT 和 LastVT:,38,按步骤构造如下：(1)逐条扫描产生式，因有产生式F(E)，则有（ = ）。(2)寻找终结符在左边，非终结符在右边的符号对有EE+T+T则 + + TT*FT*则 LastVT(F) *F(E)E)则 LastVT(E) )(3) #，# = #.,
