第11讲-语法分析-VI.ppt

1、上下文无关文法,自上而下,自下而上,LL(1)文法,2个函数,递归下降预测分析,非递归的预测分析,最左推导,最右推导,！,温故而知新,2,最左推导与自上而下分析,自上而下分析 对应着应用最左推导构建语法树的过程,E TE E + TE | T FT T * FT | F (E) | id,输入：id*id,E,E lm TE lm FT E lm id T E lm id * F T E lm id * id T E lm id * id E lm id*id,3,自上而下分析，可以使用最右推导吗？,E TE E + TE | T FT T * FT | F (E) | id,输入：id*id

2、,E,E rm TE rm Trm F T rm F * F T rm F * F rm F * id rm id*id,从左至右读取输入字符串，却要进行最右推导。这样利用左边的字符来决定右边的非终结符的展开方式，非常困难。因此，最右推导不适合使用自上而下的方式构造分析树。,最左推导与自上而下分析,4,自下而上分析,从给定的句子开始，希望把句子归结为开始符号 后面会看到 最右推导，使用于自下而上分析 自下而上分析，对应最右推导的逆过程 引入归约的概念 归约，是推导的逆过程,E,id+id*id,5,本讲纲要,自下而上分析概述 自下而上分析方法 LR分析器,6,自下而上分析概述,重要概念 归约

3、句柄,7,3.4 自下而上分析,3.4.1 归约 例S aABe A Abc | b B d,8,abbcde,3.4 自下而上分析,3.4.1 归约 例S aABe A Abc | b B d abbcde,9,aAbcde rm abbcde,3.4 自下而上分析,3.4.1 归约 例S aABe A Abc | b B d abbcde aAbcde,10,aAde rm aAbcde rm abbcde,3.4 自下而上分析,3.4.1 归约 例S aABe A Abc | b B d abbcde aAbcde aAde,11,aABe rm aAde rm aAbcde rm ab

4、bcde,3.4 自下而上分析,3.4.1 归约 例S aABe A Abc | b B d abbcde aAbcde aAde aABe,12,S rm aABe rm aAde rm aAbcde rm abbcde,3.4 自下而上分析,3.4.1 归约 例S aABe A Abc | b B d abbcde aAbcde aAde aABe S,13,归约，是自下而上分析中的重要动作 归约，对应着最右推导的逆过程,归约,14,3.4.2 句柄: 和某产生式右部匹配的子串 S aABe A Abc | b B d S rm aABe rm aAde rm aAbcde rm abbc

5、de,1. 句柄是句型的一个字串,2. 把句柄归约成非终结符代表了某一步最右推导的逆过程,3.4 自下而上分析,15,3.4.2 句柄 句柄性质： S rm aABe rm aAde rm aAbcde rm abbcde 句柄的右边仅含终结符。 如果文法二义，那么句柄可能不唯一。,例 E E + E | E * E | (E ) | id E rm E * E E rm E + E rm E * E + Erm E + id3 rm E * E + id3rm E * E + id3 rm E * id2 + id3 rm E * id2 + id3 rm id1 * id2 + id3 r

6、m id1 * id2 + id3 在句型E * E + id3中，句柄不唯一。,3.4 自下而上分析,16,句柄,句柄的非形式定义 句型的句柄，是该句型中与一个产生式右部匹配的字符串,文法： S aABe A Abc | b B d,可能在最右推导的过程中出现的句柄有那些呢？,aABe Abc b d,17,句柄,句柄的精确定义 右句型 的句柄是一个产生式的右部 ，并且该句柄 在用A替换中的句柄之后，得到的是最右推导中的前一个句型 令 = ，则可以通过产生式A- 归约为句型 A,abbcde,aAbcde,rm,aAAcde,rm,aAAcde不是文法的右句型,b是不是句柄？,所以aAbcd

7、e中的b不是句柄！,如果b是句柄，那么意味着存在这一步推导,所有能够在最右推导中出现的句型，称为右句型,文法： S aABe A Abc | b B d,18,句柄,句柄的特性 句柄的右边都是终结符（或者句柄右边没有任何符号）,假设，存在句型B，并且是句柄，可以通过产生式A-进行归约,这意味着什么？,存在下面的推导 A B =rmB,问题何在？,不是最右推导！,结论：句型的右边不可能 出现非终结符,19,例：设文法G(S)：(1) S aAcBe (2) A b (3) A Ab (4) B d 试对abbcde进行“移进归约”分析。,20,本讲纲要,自下而上分析概述 自下而上分析方法 LR分

8、析器,21,3.4.3 用栈实现移进归约分析 分析器的四种动作： 移进动作 把下一个输入符号压栈。 归约动作 分析器知道整个句柄已经完全出现在栈顶，它确定句柄的左端在栈中的位置，再决定采用哪个非终结符来代替句柄（即确定使用哪个产生式）。 接受动作 分析器宣告分析成功。 报错动作 分析器发现了语法错误，调用错误恢复例程。,分析表的作用是：确定分析的下一步动作是移进还是归约，如果是归约，那么应用使用哪个产生式进行归约,3.4 自下而上分析,22,3.4 自下而上分析,3.4.3 用栈实现移进归约分析 通过移进归约分析器在分析输入串id1 * id2 + id3时动作序列来了解移进归约分析的工作方式

9、。,23,分析的方法,处理的对象：句子（由终结符组成的串）,id1 * id2 + id3,句子中符号的扫描方向是从左到右,24,分析的过程,所有的步骤与动作,id1,id2,id3,*,+,$,初始状态：栈里面只有一个$,动作：,移进一个终结符,E E + E | E * E | (E ) | E | id,栈,句子,25,分析的过程,所有的步骤与动作,id1,id2,id3,*,+,$,目前状态：栈里面已经识别的串是id1,扫视一下表达式文法，看看有没有形成句柄,E E + E | E * E | (E ) | E | id,E id,id是一个句柄,动作：,利用E id进行归约,26,分

10、析的过程,所有的步骤与动作,E,id2,id3,*,+,$,目前状态：栈里面已经识别的串是E,归约之后，E不是句柄,E E + E | E * E | (E ) | E | id,动作：,移进下一个终结符*,27,分析的过程,所有的步骤与动作,E,id2,id3,*,+,$,目前状态：栈里面已经识别的串是E*,E*不是句柄,E E + E | E * E | (E ) | E | id,动作：,移进下一个终结符id2,28,分析的过程,所有的步骤与动作,E,id2,id3,*,+,$,目前状态：栈里面已经识别的串是E*id2,有没有句柄出现？,E E + E | E * E | (E ) |

11、E | id,动作：,利用产生式E id进行归约,id2是句柄,29,分析的过程,所有的步骤与动作,E,E,id3,*,+,$,目前状态：栈里面已经识别的串是E*E,有没有句柄出现？,E E + E | E * E | (E ) | E | id,动作：,移进终结符+,E*E是产生式E E *E 的句柄， 但同时我们也可以选择继续移进,当栈顶出现句柄的时候， 可以选择归约动作，也可以 选择移进动作,怎么选择？暂且留着疑问， 等后面将具体的分析技术时 再讨论一下,30,分析的过程,所有的步骤与动作,E,E,id3,*,+,$,目前状态：栈里面已经识别的串是E*E+,有没有句柄出现？,E E +

12、E | E * E | (E ) | E | id,动作：,移进终结符id3,没有！,31,分析的过程,所有的步骤与动作,E,E,id3,*,+,$,目前状态：栈里面已经识别的串是E*E+id3,有没有句柄出现？,E E + E | E * E | (E ) | E | id,动作：,利用产生式E id进行归约,有！,32,分析的过程,所有的步骤与动作,E,E,E,*,+,$,目前状态：栈里面已经识别的串是E*E+E,有没有句柄出现？,E E + E | E * E | (E ) | E | id,动作：,利用产生式E E + E进行归约,有！,33,分析的过程,所有的步骤与动作,E,E,*,

13、$,归约后状态：栈里面已经识别的串是E*E,有没有句柄出现？,E E + E | E * E | (E ) | E | id,动作：,利用产生式E E * E进行归约,有！,34,分析的过程,所有的步骤与动作,E,$,归约后状态：栈里面已经识别的串是E,E E + E | E * E | (E ) | E | id,串已经归约到开始符号E，并且 输入的终结符在这个过程中已经被消耗完毕,35,3.4 自下而上分析,使用移进归约方式，即使知道了应该进行归约，也还有两个问题必须解决，他们是 确定右句型中将要归约的子串 如何确定选择哪一个产生式,36,3.4.4 移进归约分析的冲突 移进归约冲突,归约

14、乎？,移进乎？,如果移进归约分析器处于格局 栈 输入 if expr then stmtelse $,例 stmt if expr then stmt | if expr then stmt else stmt | other,两难啊！,3.4 自下而上分析,37,归约归约冲突 stmt id (parameter_list) | expr := expr parameter_list parameter_list, parameter | parameter parameter id expr id (expr_list) | id expr_list expr_list, expr | e

15、xpr,用paramter id归约？,用expr id归约？,不容易抉择呢！,由A(I, J)开始的语句 栈输入 id ( id, id ),3.4 自下而上分析,38,本讲纲要,自下而上分析概述 自下而上分析方法 LR分析器,39,LR分析器,LR分析器处理的是一类LR(k)文法 k指的是决定分析动作的时候向前看的符号个数 k=1时可以省略，表示分析的时候只要往前看1个符号 LR分析器采用的方法称为LR分析方法 LR分析方法是自下而上分析的一种，也是最为有效的一种,40,本节介绍LR(k)分析技术 特点 适用于一大类上下文无关文法 效率高 主要介绍构造LR分析表的三种技术 简单的LR方法（简称SLR） 规范的LR方法 向前看的LR方法（简称LALR）,3.5 LR分析器,41,3.5.1 LR分析算法,3.5 LR分析器,42,例 E E + T | T T T * F | F F (E ) | id,