自底向上优先分析法.PPT

1、1,自底向上优先分析法,掌握：构造算符优先关系表，进行算符优先分析，构造优先函数 理解：算符优先文法，最左素短语 了解：简单优先分析法,2,1 自底向上分析方法概述,基本思想 从输入符号串开始，利用文法的产生式逐步进行归约，试图归约到文法开始符 从语法树角度看，是以输入符号串作为语法树的末端结点符号串，自底向上的构造语法树，使文法开始符正好是该语法树的根。如果最终根结点是开始符，则输入符号串是语言的一个句子，否则不是。 自底向上分析过程实际上是一个不断进行直接归约的过程。,遇到的问题 如何找出进行直接归约的“可归约串”（句柄） 基本实现方法“移进归约”方法 引进一个先进后出的符号栈来存放符号

2、对输入符号串自左向右进行扫描，并把当前输入符号下推入栈中（移进）， 边移进边分析，一旦栈顶符号串形成某个句型的句柄（为某产生式的右部）时，就用相应的非终结符（产生式的左部）替换它(归约)。 重复这一过程，直到输入符号串的末端，此时如果栈中只剩文法开始符号，则输入符号串是文法的句子，否则不是。,4,规范归约： 自底向上分析的移进归约过程是自顶向下最右推导的逆过程，因为最右推导为规范推导，所以自左向右的归约称为规范归约。,例 文法：(1) SaAcBe (2)Ab (3)AAb (4) Bd 输入串 abbcde#的最右推导的过程为： S=aAcBe=aAcde=aAbcde=abbcde 自底向

3、上分析的过程为： abbcde|-aAbcde|-aAcde|-aAcBe|-S,例 文法：(1) SaAcBe (2)Ab (3)AAb (4) Bd 判断输入串 abbcde# 是否为该文法的句子,用符号栈对输入符号串自底向上的分析过程为：,6,关键问题：如何在分析的过程中确定句柄 何时移进？栈顶末形成句柄 何时归约？栈顶形成句柄 常用自底向上分析法： 算符优先分析法 LR类分析法,7,2 自底向上优先分析法概述,优先分析法两类： 简单优先分析法 基本思想：按一定原则定义文法中所有符号（终结符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄并实行归约。 是一种规范归约。 简单优

4、先分析法准确、规范，但效率低，不实用。,8,算符优先分析法 基本思想：只定义文法中终结符之间的优先关系（不考虑非终结符），并由这种关系指导分析过程 不是规范归约 算符优先分析法分析速度快，特别适用于表达式的分析。缺点是不规范，常常要采用适当措施克服其缺点。,9,3 算符优先分析法,算符优先分析法特别适用于表达式的分析 从表达式得到的启发： 表达式的归约顺序与运算顺序是一样的 通常算术表达式的运算次序是先乘除后加减，同优先级时服从左结合,EE+T|T TTF|F F(E)|i,符号串E+T+TF的归约过程为： E+T+TF |- E+TF |- E+T |- E,10,运算次序只与运算符（优先级

5、，结合性）有关，与运算对象无关 可以根据运算符（终结符）的优先关系指导归约过程，与运算对象（非终结符）无关,11,3.1 优先关系,优先关系只存在于句型中相邻出现的符号 相邻：算符优先分析法只考虑终结符之间的优先关系，不考虑非终结符，所以两个终结符相邻指其中没有其他的终结符（但可以有非终结符） 如：E+Ti，和相邻，和i相邻， 但和i不相邻 终结符间优先关系表示： 终结符a和b之间的优先关系表示如下： ab 表示a的优先级高于b,优先关系定义的依据 在当前句柄中的符号优先于与其相邻的不在句柄中的符号被归约，其优先关系大 同一句柄中的相邻符号同时被归约，其优先关系相同,不可能相邻出现在任何句型中

6、的两个符号，无法比较其归约的先后，故它们之间无优先关系,EE+T|T TTF|F F(E)|i,E,E,+,T,T,F,(,E,),句型(E)+T的句柄是(E) , 所以) + ( = ),注意：是三种有序关系，与数学中的不同，所以a=b不意味b=a，ab不意味ba,E,E,+,T,T,F,(,E,),如：(=)，但是)=(不成立，因为)和(不可能相邻出现在任何句型中，它们之间没有优先关系,EE+T|T TTF|F F(E)|i,E,T,F,(,E,),E,+,T,在句型(E)+T中得 ) +，在(E+T)中得 + ),按公认的计算顺序规定优先级和结合性，得到优先关系如下： ,/的优先级高，遵

7、循左结合，得, /, /, / +,-的优先级低，遵循左结合，得+, +-, -, + (, )规定括号的优先级大于括号外的运算符，小于括号内的运算符，如E + ( E + T )，有 + # 运算对象 i 的优先级最高 优先关系表如右图所示：,说明：表中为空的元素表示：在该文法的任何句型中都不会出现这两个终结符相邻，所以他们无优先关系，如不会有这样的表达式 ) i ,15,算符优先分析法 1 文法要满足一定的条件，即为算符优先文法 2 根据文法按一定规则计算算符之间的优先关系 3 按优先关系进行算符优先分析,16,3.2 算符优先文法的定义,1 算符文法 定义： 设有上下文无关文法 G ，如

8、果G中产生式的右部没有两个非终结符相连，则称G为算符文法（Operater Grammar），也称OG文法 例如： 表达式文法 EE+E|EE|(E)|i 是算符文法 性质： (1) 在算符文法中任何句型都不包含两个相连的非终结符。,17,证明：用反证法。因为由算符文法的性质1知可有：S = =bA若存在B = b，这时b和A不同时归约，则必有S = BA,这样在句型BA中存在相邻的非终结符B和A，所以与性质1矛盾，证毕。注意：含b的短语必含A，含A的短语不一定含b。,(2) 如果Ab或bA出现在算符文法的句型r中，其中A VN，b VT，则r中任何含b的短语必含有A（含A的短语不一定含有b）

9、,句型E+T+TF 短语有：E+T TF E+T+TF,2 算符优先关系的定义 设G是一个不含产生式的算符文法，a和b是任意两个终结符，A,B,C是非终结符，算符优先关系定义如下： a = b 当且仅当G中有形如 Aab 或 AaBb 的产生式。,说明：为或B，a，b在用一句柄中同时归约所以优先级相同,a,b,A,例如：有产生式F(E) 所以( = ),a + b 或 B=+ Cb,说明：为或C，a，b不在同一句柄中，b先归约，所以a的优先级低于b,a,B,A,P,b,文法EE+T|T TTF|F F(E)|i 由EE+T T=+ TF 得+,a b 当且仅当G中有形如 ABb 的产生式， 且

10、 B=+ a 或 B=+ aC,说明： 为或C ，a，b不在同一句柄中，a先归约，所以a的优先级大于b,b,B,A,P,a,文法EE+T|T TTF|F F(E)|i 由EE+T E=+ TF 得+,3 算符优先文法 定义： 设有一不含产生式的算符文法G，如果对任意两个终结符对a,b之间至多只有一种优先关系成立，则称G是一个算符优先文法(Operater Precedence Grammar)，即OPG文法。 说明： 两个终结符之间的优先关系是有序的，算符优先文法允许ab，ba同时存在，而不允许有ab，a ) ，) +同时存在，不允许 + ) 和 + ) 同时存在,22,例 表达式文法 EE+

11、E|EE|(E)|i 由EE+E且E=+ EE得+ E+E得 +和的优先关系不唯一，所以不是算符优先文法,包含优先级和结合性的表达式文法是算符优先文法 EE+T|T TTF|F F(E)|i,23,3.3 算符优先关系表的构造,最左终结符集FIRSTVT FIRSTVT(B)=b|B=+ b 或 B=+ Cb 其中bVT, B,CVN 直观上说FIRSTVT(B)是由B推导出的最左终结符(允许左边有一非终结符)的集合。 与FIRST() = a VT | * a. 对照 文法符号串的开始符号集是由推导出的开头的终结符（包括）组成,24,例文法：EE+T|T TTF|F F(E)|i,FIRST

12、VT(F)=(，i FIRSTVT(T)=，(，i FIRSTVT(E)=+，(，i,FIRST(F)=(，i FIRST(T)=(，i FIRST(E)=(，i,25,构造FIRSTVT(A)的算法 令每个非终结符的FIRSTVT集为空 依次扫描文法中的每条产生式，根据规则(a)(b)，求各非终结符的FIRSTVT集 (a)若产生式Aa，或ABa， 则aFIRSTVT(A)； (b)若有产生式AB,且aFIRSTVT(B)， 则aFIRSTVT(A) 重复2)，直到每个FIRSTVT集合都不发生变化为止,例 文法：EE+T|T TTF|F F(E)|i求各非终结符的FIRSTVT集,第三次,

13、F,T,E,第二次,(，i,+,第一次,第四次迭代的时候，E、T、F 的FIRSTVT集都不再发生变换，算法终止, (，i, (，i,(a)若产生式Aa，或ABa，则aFIRSTVT(A)； (b)若有产生式AB,且aFIRSTVT(B)，则aFIRSTVT(A),27,最右终结符集LASTVT LASTVT(B)=a|B=a 或 B=aC 其中aVT, B,CVN 直观上说LASTVT(B)是由B推导出的最右终结符(允许右边有一非终结符)的集合。,例文法： EE+T|T TTF|F F(E)|i,LASTVT(F)=)，i LASTVT(T)=，)，i LASTVT(E)=+，)，i,28,

14、构造LASTVT(A)的算法与构造FIRSTVT(A)算法相似 根据下面两条规则 若产生式Aa，或AaB，则aLASTVT(A) 若有产生式AB，且aLASTVT(B)，则aLASTVT(A),例 文法：EE+T|T TTF|F F(E)|i求各非终结符的LASTVT集,第三次,F,T,E,第二次,)，i,+,第一次,第四次迭代的时候，E、T、F 的LASTVT集都不再发生变换，算法终止, )，i, )，i,a)若产生式Aa，或AaB，则aLASTVT(A) b)若有产生式AB，且aLASTVT(B)，则aLASTVT(A),优先关系的确定 =关系： 查看产生式右部，有形如Aab或AaBb 的

15、产生式，则a=b 例E(E)，则有(=) 关系： 若有形如ABb 的产生式，对每个 a LASTVT(B)，都有ab 例EE+T，LASTVT(E)=+ , , i , ) ， 则有+，+，i+，)+,构造算符优先关系表算法 逐条扫描文法中的每条产生式，按以下四种情况处理： 对产生式右部终结符相邻的符号对，即产生式右部有形如Aab的符号对(a,b)，则ab 对产生式右部两终结符之间为一个非终结符的符号对，即产生式右部有形如AaBb的符号对(a,b)，则ab 对产生式右部终结符在前非终结符在后的相邻符号对，即产生式右部有形如AaB的符号对(a,B)，则aa,例 文法 EE+T|T TTF|F F

16、(E)|i,FIRSTVT（E）= +，i，( FIRSTVT（T）= ，i，( FIRSTVT（F）= i，( ,LASTVT（E）=+ , , ) , i LASTVT（T）= , ) , i LASTVT（F）= ) , i ,依次考察每个产生式的右部： 由E+和LASTVT(E)=+,),i 得到：+，+，)+，i+,#,+,(,+,i,),(,#,i,),由+T和FIRSTVT(T)=,(,i 得到：+，+(，+i,由(E和FIRSTVT(E)=+,(,i得到：(+，(，(，(i,=,#,+,(,+,i,),=,(,#,i,),例 文法 EE+T|T TTF|F F(E)|i,由T和

17、LASTVT(T)=,),i 得到：，)，i,由F和FIRSTVT(F)=(,i得到：(，i,由(E)得到：(=),由E)和LASTVT(E)=+,),i得到：+)，)，)，i),关于#的优先关系，可认为有产生式 E #E#而获得 #=#；,由E#，得LASTVT(E)#, 即：+#，#，)#，i#,由#E，得#FIRSTVT(E)，即： #+，#，#i，#(,34,根据算符优先关系表可以判断文法是否为算符优先文法,文法 EE+T|T TTF|F F(E)|I 的算符优先关系表为：,优先关系表中无多重定义 此文法是算符优先文法,35,3.4 算符优先分析算法,说明： 算符优先分析法的归约过程与

18、规范归约不同,文法 EE+T|T TTF|F F(E)|i,输入串i+i的语法树：,i+i的规范归约： i+i |- F+i |- T+i |-E+i |-E+F |- E+T |- E i+i的算符优先分析： i+i |-F+i |-F+F |-E,当单个非终结符是句柄时，算符优先法无法确定该非终结符为句柄,36,算符优先法每次归约最左素短语而不是句柄 最左素短语的定义和确定方法是算符优先分析算法的关键。,37,1. 最左素短语的定义 定义： 设有文法GS，其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其它素短语。 最左边的素短语称为最左素短语。,例 文法：EE+T|T T

19、TF|F F(E)|i 的一个句型为 T+TF+i,短语为：T，TF，i，T+TF， T+TF+i 素短语为：TF，i 最左素短语为：TF,规范归约每次归约当前句型中的句柄，上面句型的句柄是T 算符优先分析每次归约当前句型的最左素短语，TF，去掉了单非终结符的归约，因为若只有一个非终结符时，无法与句型中该非终结符的左部和右部的串比较优先关系，也就无法确定该非终结符为句柄。,39,2. 最左素短语的确定 最左素短语的形式为： NiaiNi+1ai+1.NjajNj+1 其中Nk(iK j+1)为非终结符或空 Ni和Nj+1在短语中，这是因为算符文法的性质： 性质1：在算符文法中任何句型都不包含两

20、个相邻的非终结符 性质2：如果Ab（或bA）出现在句型r中，其中A VN，b VT，则r中任何含b的短语必含有A,40,最左素短语NiaiNi+1ai+1.NjajNj+1 满足： ai-1 aj+1 根据上述关系，可以构造出算符优先分析算法： 先利用关系找到最左素短语的尾，再利用关系找到最左素短语的头，从而确定最左素短语。,4. 算符优先分析算法 此算法用到一个符号栈S，算法大意为： 将输入符号串a1a2at依次逐个存入符号栈S中，直至符号栈顶终结符aj与当前输入符aj+1的关系为ajaj+1为止； 最左素短语尾已在符号栈S的栈顶，由栈顶向下找最左素短语的头符号，即找到第一个关系ai-1ai

21、。 已找到最左素短语NiaiNi+1ai+1.NjajNj+1 ，用相应的产生式进行归约 重复上述过程，当处理到输入符号串尾时，若栈中只剩：N（N为任何一个非终结符），则分析成功，否则分析失败,例 文法 EE+T|T TTF|F F(E)|i 算符优先关系表如右图： 输入串i+i#的归约过程如下：,动作,剩余输入串,当前符号,优先关系,栈,步骤,43,算法说明： 算法中每次都取终结符进行比较，当栈顶符号不是终结符时，便取其下面符号（这时一定是终结符） 归约时检查是否有与最左素短语对应的产生式，查看产生式的右部： 符号个数与该素短语的符号个数相等 非终结符位置对应，不管其符号名是什么 终结符名字

22、和位置都对应相等； 若有满足以上条件的产生式才归约，否则出错,对输入串i+i#的规范归约过程,10,9,8,7,6,5,4,3,2,1,归约用产生式,句柄,剩余输入串,栈,步骤,EE+T|TTTF|FF(E)|i,E,E,+,T,T,F,i,F,i,E,F,+,F,i,i,采用规范归约 识别i+i的过程,采用算符优先分析 识别i+i的过程,规范归约与算符优先分析 1. 规范归约将输入符号串归约为文法的开始符 算符优先分析将输入符号串归约为任意一个非终结符 2. 规范归约每次归约句柄 算符优先分析每次归约最左素短语，去掉了单非终结符的归约,3. 规范归约选取右部与句柄一致的产生式进行归约 算符优

23、先分析归约时选择产生式时不管非终结符的名字,46,3.5 优先函数,在实际应用中用优先函数来代替优先矩阵表示优先关系 优先函数的定义 对给定的优先关系表，定义两个函数 f，g，它们应满足： 当a=b 则令 f(a)=g(b) 当ab 则令 f(a)g(b) 我们称 f，g 为优先函数，其取值可用整数表示 。,47,优先函数的优缺点,优先关系表 (n+1)2 个单元,优先函数表 2(n+1) 个单元,优点：节省大量内存 缺点：原先无优先关系的对，如：(i,i) 变成有关系： f(i)=6 g(i)=7 ，不能准确指出错误位置,48,对优先函数的说明： 有的优先关系表不存在优先函数 优先函数不唯一

24、。例如优先函数每个元素的值都增加同一个常数，优先关系不变,49,用关系图法构造优先函数 画图：对每个终结符a(包括#)画出fa，ga结点， 若ab或a=b则从fa到gb画一条弧， 若ab或a=b则从gb到fa画一条弧。 列表：给每个结点赋一个数作为其函数值，此数等于从该结点出发所能到达的结点(含自身结点)的个数。 检验：检查优先函数是否满足优先关系条件，若不满足则不存在优先函数。,例 有优先关系表如下：,6,优先函数结果为：,检验：优先函数与优先关系表的优先关系一致,从fi出发所能到达的结点有： fi ，g#，f#，g，f+，g+,51,3.6 算符优先分析法的局限性,适用范围窄，很多实用语言的文法不是算符优先文法 有时错误的句子得到了正确的归约，原因： 去掉了单非终结符的归约 归约时，选择产生式不