《自底向上优先分析方法》由会员分享，可在线阅读，更多相关《自底向上优先分析方法（72页珍藏版）》请在金锄头文库上搜索。
1、1,第六章自下而上优先分析法,所有的自下而上分析方法都是按照移进-归约法的原理.基本思想是用一个寄存文法符号的先进后出栈，将输入符号按从左到右扫描顺序逐个移入栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可归约串时（对应于某条规则右部）就进行一次归约，即用该规则左部非终结符替换相应规则右部符号串.重复这一过程直到整个输入串分析完毕.最终若栈中剩下句子右界符“#”和文法的开始符号，则所分析的输入符号串是文法的正确句子.否则,就不是正确的句子，报告错误.,2,设 G =(VT,VN,S,P), ,(VTVN)*, AP,Aw w归约的过程是，已知w 和产生式 A，用产生式A左部 A 替换w
2、 中的，得到符号串Aw.从输入符号串出发，每次从被归约的句型中找到一个产生式的右部，用其左部替换之，得到新的句型，直至归约到文法的开始符号。,归约,3,【例】文法GS对输入串 abbcde# 进行语法分析，检查该符号串是否是该文法的正确句子。,SaAcBeAbAAbBd,4,SaAcBe Ab AAb Bd,a,b,b,c,d,e,abbcde,aAbcde,aAcde,aAcBe,S,A,A,B,S,5,从例子中可以看出，一个句型中当含有多个子串可以匹配不同产生式的右部时，将有不同的归约过程，究竟应该对谁先归约呢？,6,一个句型的最左直接短语称为该句型的句柄，句柄是规范归约的可归约串。假定是
3、文法 G 的一个句子，称序列n,n-1,n-2,0是的一个规范归约，如果此序列满足：1)n=；0为文法的开始符，即0=S；2)对任何i，0in, i-1是从i经把句柄替换为相应产生式的左部符号而得到的。如果文法G是无二义的，规范归约是最右推导的逆过程，规范归约也称最左归约,最右推导也称规范推导。结论：对规范句型来说，句柄的后面不会出现非终结符。因此，规范归约的实质是在移进过程中，发现栈顶呈现句柄时就用相应的产生式的左部符号进行替换。,规范归约简述,7,对输入串 abbcde 的最右推导过程是： SaAcBeaAcdeaAbcdeabbcde。 用语法树表示如下图所示：,8,用语法树表示规范归约
4、过程如下图所示：它与最右推导的逆过程相对应。,9,非形式地，一个符号串的“句柄”是和一个规则右部匹配的子串，而且把它归约到该规则左部的非终结符,代表了最右推导逆过程的一步。,句柄,找句柄是非常重要的,在很多情况下，匹配某个规则 A 右部的最左输入子串 不是句柄，因为用这个规则归约产生的串不能归约到开始符号。【例】对于串 aAbcdeb 是产生式 Ab 的右部,但 b 不是句柄。如果进行归约，得到 aAAcde，而 aAAcde不能归约到 S.因此我们必须更精确地定义句柄。,10,形式的说，右句型(最右推导可得的句型)的句柄是一个与规则 A和中的一个位置有关的，从这个位置开始往右可找到，用 A
5、代替得到最右推导的前一个右句型，即如果 S Aw w,那么，在 后是 w 的句柄。句柄右侧的 w 是未读入的终结符号。,句柄(续),*rm,rm,11,“移进一归约”分析器使用一个栈和一个存放输入符号串w 的缓冲器。分析器的初始状态为: 栈输入动作#w# 工作过程：自左至右把串 w 的符号一一移进栈里，一旦栈顶形成句柄时，就进行归约。这种归约可能持续多次，直至栈顶不再呈现句柄为止。然后，继续向栈里移进符号，重复这个过程，直至最终形成如下格局： 栈输入#S#(分析成功接受),“移进-归约”分析法的栈实现,12,符号栈输入串动作初态#w#(移进、归约、出错)（中间过程）终态#S#(分析成功接受),
6、符号栈的使用,13,对符号栈的使用有“移进”、“归约”、“接受”、“出错处理”等操作。,“移进”是指在栈顶还没有形成可归约串时，把输入串的一个符号移进符号栈；“归约”是指发现栈顶已形成可归约串，对其进行归约；“接受”是指宣布分析成功，表明输入串是文法合法的句子；“出错处理”是指栈顶符号和要输入的符号在某种关系上出现矛盾，分析过程无法正常进行，通常此时要调用出错处理程序确定错误类型、校正错误，并使分析过程继续进行下去。,14,还有一个非常重要的事实，任何可归约串的出现必在栈顶，不会在栈的内部。对规范归约而言，这个事实是明显的。规范归约是最左归约，这种“最左性”保证可归约串一定在栈顶。也正因为如此
7、，先进后出栈在自下而上分析中是一种非常重要的数据结构。,15,6.1 自下而上优先分析法概述,优先分析法有两种：简单优先分析法(规范归约)文法按一定原则规定文法符号的优先关系算符优先分析法(不规范归约)规定算符之间的优先关系,简单优先分析法:准确、规范，但效率较低，实际使用价值 不大.算符优先分析法：分析速度快，适用于表达式分析，但归约 不规范.,16,6.2 简单优先分析法,简单优先分析法是按照文法符号的优先关系确定句柄.因此，在这种方法中的关键是确定文法符号间的优先关系.,1.优先关系 (1) X=Y 当且仅当G中存在产生式规则AXY (2) XXB ， 且BY (3) XY 当且仅当G中
8、存在产生式规则ABD ， 且BX和D=Y例6.2 见书P. 105,+,+,*,17,2.简单优先文法若一个文法满足：（1）在文法符号集V中，任意两个符号之间最多只有一种关系成立；（2）在文法中任意两个产生式没有相同的右部.则这样的文法为简单优先文法.,18,3.简单优先分析法优先分析算法（1）根据优先文法构造优先关系矩阵；（2）存储文法产生式，并设符号栈S；（3）将输入符号串a1a2an#依次逐个存入符号栈S中，直到 遇到栈顶符号ai的优先性下一个待输入符号aj时为止.（4）栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符 号ak,即找到ak-1 -, 但没有 - 1，n-1 满足性质
9、1。若 n-1A，A 为非终结符。由假设的 的尾符号和 的首符号都不是非终结符，否则与假设矛盾。又若 A 是文法的规则，则有n-1 n = 而 A 是文法的规则，它不含两个相邻非终结符，所以 也不含两个相邻的非终结符，满足性质 1。,*,证明：用归纳法设 是句子，S，即S01.n-1n,26,性质2：若 Ab 或 bA 出现在算符文法的句型 中，其中AVN ,bVT,则 中任何含 b 的短语必包含 A.,证明：用反证法。由算符文法的性质 1 可知。S bA若存在 B b，这时 b 和 A 不同时归约，分属于不同的短语，则必有 SBA，这样在句型 BA 中，存在相邻的非终结符，所以与性质 1 矛
10、盾。故： 中任何含 b 的短语必包含 A，证毕。,*,注意：含 b 的短语必含 A，含 A 的短语不一定含 b。,27,2终结符号间的优先关系的定义设 G 是一个算符文法，对于任何终结符 a、b，算符优先关系 定义如下：,a=b 当且仅当 G 中含有形如Aab或AaBb的规则；ab 或BCb；ab当且仅当 G 中含有形如ABb的产生式，而Ba或BaC；,+,+,+,+,28,由语法树来说明优先关系,1)a = b 则存在语法子树(a)，a和b 在同一句柄中同时归约，所以优先级相同。2)a b 则存在语法子树(c)，a和b 不在同一句柄中，a先归约，所以 b 的优先级小于 a。,其中 为 或非终结符,29,3算符优先文法的定义设有一个不含-规则的算符文法 G，如果任何终结符对(a，b)至多只满足下述关系之一：a=b，ab，ab；则称 G 是一个算符优先文法，也称 OPG 文法。(OPG Operator Precedence Grammar),30,【例】文法GE：EE+E | E*E | (E) | id,所有规则中都没有相邻的非终结符，所以它是算符文法 OG 文法。由于 EE+E 和 EE*E，所以有 + *运算符 + 和 * 之间存在两种不同的优先关系，所以该文法不是算符优先文法 OPG.,
