语法分析-自底向上分析

《语法分析-自底向上分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章语法分析——自底向上分析在自底向上的分析方法中，分析过程从输入符号串开始，通过反复查找当前句型的句柄，并使用规则，将找到的句柄归约成相应的非终结符号，直到归约到开始符号。5.1规范推导、规范句型和规范归约规范推导就是最右推导，而通过规范推导能得到的句型就是规范句型。规范归约也称为最左归约，是规范推导的逆过程，即在分析的每一步，将当前句型的句柄归约成相应的非终结符号。5.1规范推导、规范句型和规范归约从符号串开始，向上归约，如果最终能够规约到文法的开始符号S，则同样可以说明该输入符号串是这个文法的句子。其归约过程如图5.1所

2、示。ScBcAaAbdbScBcAaAbdScBcAadScBcAaS(a)b归约为A(b)Ab归约为A(c)d归约为B(d)aAcBe归约为S(e)图5.1归约过程例5.1有文法G[S]：S::=aAcBeA::=bA::=AbB::=d分析符号串abbcde是否为该文法的句子。解：首先，我们从文法的开始符号进行规范推导，依次使用1、4、3、2规则，就可得到符号串abbcde。规范推导过程如下：S=>aAcBe=>aAcde=>aAbcde=>abbcde5.2自底向上分析方法的一般过程自底向上分析方法，也称为移进归约法，其过

3、程是：设置一个寄存符号的先进后出栈，称为符号栈。在分析进行时，把输入符号逐个按扫描顺序移进栈里，当栈顶符号串形成句柄(即为某条规则的右部)时，就归约，把栈顶构成句柄的那个符号串用相应规则左部的非终结符号来代替。再检查栈顶是否又出现了新的句柄，若有，继续归约；若没有形成新的句柄，则再从输入符号串移进新的符号，如此继续直到整个输入符号串处理完毕。最终如果栈里只有识别符号，则所分析的输入符号串为合法的句子，报告成功；否则，输入串是不合法的符号串，报告错误。步骤符号栈输入符号串动作123456789101112##a#ab#aA#aAb

4、#aA#aAc#aAcd#aAcB#aAcBe#S#Sabbcde#bbcde#bcde#bcde#cde#cde#de#e#e####左界符进栈进栈进栈用A→b归约进栈用A→Ab归约进栈进栈用B→d归约进栈用S→aAcBe归约接受表5.1输入串abbcde的分析过程上述分析可看出，每次归约的句柄都出现在符号栈的栈顶，不会出现在栈的中间，因为算法是自左向右扫描输入符号串，进行的是最左归约。例5.1有文法G[S]：S::=aAcBeA::=bA::=AbB::=d分析符号串abbcde是否为该文法的句子。5.2自底向上分析方法的一

5、般过程存在着句柄识别问题:例如表5.1中的第5步，栈内符号串为aAb，由于文法中同时有规则A::=Ab和A::=b，那么，符号串Ab和b都是某规则的右部，都可以作为句柄归约。如果选择b作为句柄归约成A，那么，最终就达不到归约到开始符号S的目的。事实上，不能因为规则A::=b就断定b是句柄，因为aAAcde并不是一个句型，即不存在推导过程S==*>aAAcde。对句型aAbcde来说，其简单短语是Ab和d，其中Ab是最左简单短语，所以是句柄。从自底向上分析的一般过程可看出，如何寻找或确定一个句型的句柄，是构造一个自左向右扫描、自底

6、向上分析方法必须要解决的一个关键问题。最常用的自底向上的分析方法有算符优先方法和LR分析方法，算符优先方法仅适用于算符文法，而LR分析方法应用比较普遍。5.3LR分析方法在自底向上的分析中，当一串貌似句柄的符号串出现在栈顶时，用什么方法来判定它是否为一个真正的句柄呢？这里我们介绍LR(K)分析技术。LR(K)分析方法的L表示从左到右扫描所给定的输入串，R表示以相反的方向构造该输入串的最右推导(即规范推导)。K表示为了做出分析决定需要向前看的输入符号的个数。LR分析方法对文法适应性强，分析能力强，对源程序中错误的诊断灵敏，但结构比

7、前面介绍的自顶向下的分析方法复杂，向前查看的符号愈多，相应的分析方法愈复杂。LR(0)分析器是LR分析方法中最简单的一种，在确定分析动作时，不需要向前查看任何符号。这种分析器分析能力较弱，实用性差，但它是构造其它更复杂的LR分析器的基础。5.3.1LR分析器逻辑结构LR分析器有一个给定的输入符号串，一个分析栈和一个有穷的控制系统。如图5.2所示。a1a2……an输入符号串分析栈：ASn......#S0有穷的控制系统：分析表(动作、转换)总控程序其中，输入符号串就是等待分析的符号串。分析栈有两部分：一个是符号栈，另一个是状态栈，

8、它们都是先进后出栈。而控制系统包括一个分析表和一个总控程序。对于不同的文法来说，分析表各有不同，但总控程序都是一样的。LR分析器的工作过程就是在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的符号和状态以及当前的输入符号，查阅分析表并按分析表的指示完成相