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

1、编译原理和技术,大连理工软件学院 胡 彦 ,本讲纲要,自下而上分析概述 自下而上分析方法 LR分析器,自下而上分析概述,重要概念 归约 句柄,归约,归约，是自下而上分析中的重要动作 归约，对应着最右推导的逆过程,a,b,b,c,d,e,A,A,B,S,S aABe A Abc | b B d,文法：,abbcde,aAbcde,aAde,aABe,S,rm,rm,rm,rm,句柄,句柄的非形式定义 句型的句柄，是该句型中与一个产生式右部匹配的字符串,文法： S aABe A Abc | b B d,可能在最右推导的过程中出现的句柄有那些呢？,aABe Abc b d,句柄,句柄的精确定义 右句

2、型的句柄是一个产生式的右部，并且该句柄在用A替换中的句柄之后，得到的是最右推导中的前一个句型 令=，则可以通过产生式A- 归约为句型A,abbcde,aAbcde,rm,aAAcde,rm,aAAcde不是文法的右句型,b是不是句柄？,所以aAbcde中的b不是句柄！,如果b是句柄，那么意味着存在这一步推导,所有能够在最右推导中出现的句型，称为右句型,文法： S aABe A Abc | b B d,句柄,句柄的特性 句柄的右边都是终结符（或者句柄右边没有任何符号）,假设，存在句型B，并且是句柄，可以通过产生式A-进行归约,这意味着什么？,存在下面的推导 A B =rmB,问题何在？,不是最右

3、推导！,结论：句型的右边不可能 出现非终结符,句柄,句柄的特性 句柄的右边都是终结符（或者句柄右边没有任何符号） 在文法有二义的时候，句柄可能不唯一（因为对某个句子，可能存在两个最右推导）,本讲纲要,自下而上分析概述 自下而上分析方法 LR分析器,分析的方法,处理的对象：句子（由终结符组成的串）,id1 * id2 + id3,句子中符号的扫描方向是从左到右,分析的过程,所有的步骤与动作,id1,id2,id3,*,+,$,初始状态：栈里面只有一个$,动作：,移进一个终结符,E E + E | E * E | (E ) | E | id,栈,句子,分析的过程,所有的步骤与动作,id1,id2,

4、id3,*,+,$,目前状态：栈里面已经识别的串是id1,扫视一下表达式文法，看看有没有形成句柄,E E + E | E * E | (E ) | E | id,E id,id是一个句柄,动作：,利用E id进行归约,分析的过程,所有的步骤与动作,E,id2,id3,*,+,$,目前状态：栈里面已经识别的串是E,归约之后，E不是句柄,E E + E | E * E | (E ) | E | id,动作：,移进下一个终结符*,分析的过程,所有的步骤与动作,E,id2,id3,*,+,$,目前状态：栈里面已经识别的串是E*,E*不是句柄,E E + E | E * E | (E ) | E | i

5、d,动作：,移进下一个终结符id2,分析的过程,所有的步骤与动作,E,id2,id3,*,+,$,目前状态：栈里面已经识别的串是E*id2,有没有句柄出现？,E E + E | E * E | (E ) | E | id,动作：,利用产生式E id进行归约,id2是句柄,分析的过程,所有的步骤与动作,E,E,id3,*,+,$,目前状态：栈里面已经识别的串是E*E,有没有句柄出现？,E E + E | E * E | (E ) | E | id,动作：,移进终结符+,E*E是产生式E E *E 的句柄， 但同时我们也可以选择继续移进,当栈顶出现句柄的时候， 可以选择归约动作，也可以 选择移进动

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

7、+E,有没有句柄出现？,E E + E | E * E | (E ) | E | id,动作：,利用产生式E E + E进行归约,有！,分析的过程,所有的步骤与动作,E,E,*,$,归约后状态：栈里面已经识别的串是E*E,有没有句柄出现？,E E + E | E * E | (E ) | E | id,动作：,利用产生式E E * E进行归约,有！,分析的过程,所有的步骤与动作,E,$,归约后状态：栈里面已经识别的串是E,E E + E | E * E | (E ) | E | id,串已经归约到开始符号E，并且 输入的终结符在这个过程中已经被消耗完毕,3.4 自下而上分析,3.4.3 用栈实

8、现移进归约分析 分析器的四种动作： 移进动作 把下一个输入符号压栈。 归约动作 分析器知道整个句柄已经完全出现在栈顶，它确定句柄的左端在栈中的位置，再决定采用哪个非终结符来代替句柄（即确定使用哪个产生式）。 接受动作 分析器宣告分析成功。 报错动作 分析器发现了语法错误，调用错误恢复例程。,分析表的作用是：确定分析的下一步动作是移进还是归约，如果是归约，那么应用使用那个产生式进行归约,3.4 自下而上分析,使用移进归约方式，即使知道了应该进行归约，也还有两个问题必须解决，他们是 确定右句型中将要归约的子串 如何确定选择哪一个产生式,3.4 自下而上分析,3.4.4 移进归约分析的冲突 移进归约

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

10、 expr,用paramter id归约？,用expr id归约？,不容易抉择呢！,由A(I, J)开始的语句 栈输入 id ( id, id ),本讲纲要,自下而上分析概述 自下而上分析方法 LR分析器,LR分析器,LR分析器处理的是一类LR(k)文法 k指的是决定分析动作的时候向前看的符号个数 k=1时可以省略，表示分析的时候只要往前看1个符号 LR分析器采用的方法称为LR分析方法 LR分析方法是自下而上分析的一种，也是最为有效的一种,在深入LR分析方法的探讨之前，我们需要引入一个新的概念,活前缀,活前缀,文法例子,S aABe A Abc | b B d,自下而上分析时，栈中可能出现的串

11、： a ab aA aAb aAbc aAd aAB aABe S,活前缀定义： 对于任一文法GS，若S =*A=， 若 是的前缀，则称是G的一个活前缀,活前缀与句柄的关系,文法例子,S aABe A Abc | b B d,栈中可能出现的串： a ab aA aAb aAbc aAd aAB aABe S, 活前缀已含有句柄的全部符号，表明产生式A的 右部已出现在栈顶。,出现句柄（对应A-b）,出现句柄（对应A-Abc）,出现句柄（对应B-d）,出现句柄（对应S-aABe）,活前缀与句柄的关系,文法例子,S aABe A Abc | b B d,栈中可能出现的串： a ab aA aAb a

12、Abc aAd aAB aABe S, 活前缀已含有句柄的全部符号，表明产生式A的 右部已出现在栈顶。,出现产生式A-Abc右端的一部分， 期望从输入串中看到bc,出现产生式S-aABe的右端一部分， 期望从输入串中看到e, 活前缀只含句柄的一部分符号如1表明A12的右部子串1 已出现在栈顶，当前期待从输入串中看到2推出的符号。,出现产生式A-Abc右端的一部分， 期望从输入串中看到c,活前缀与句柄的关系,文法例子,S aABe A Abc | b B d,栈中可能出现的串： a ab aA aAb aAbc aAd aAB aABe S, 活前缀已含有句柄的全部符号，表明产生式A的 右部已出现在栈顶。,出现符号A推出的符号串,