编译原理(清华)第六章自底向上优先分析.ppt

《编译原理(清华)第六章自底向上优先分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章自底向上优先分析法学习目标：掌握：构造算符优先关系表，进行算符优先分析，构造优先函数理解：算符优先文法，最左素短语了解：简单优先分析法6.1自底向上分析方法概述6.2自底向上优先分析方法概述6.3算符优先分析法6.1自底向上分析方法概述基本思想从输入符号串开始，利用文法的产生式逐步进行归约，试图归约到文法开始符从语法树角度看，是以输入符号串作为语法树的末端结点符号串，自底向上的构造语法树，使文法开始符正好是该语法树的根。如果最终根结点是开始符，则输入符号串是语言的一个句子，否则不是。自底向上分析过程实际上是一个不

2、断进行直接归约的过程。遇到的问题如何找出进行直接归约的“可归约串”（句柄）基本实现方法－“移进－归约”方法引进一个先进后出的符号栈来存放符号对输入符号串自左向右进行扫描，并把当前输入符号下推入栈中（移进），边移进边分析，一旦栈顶符号串形成某个句型的句柄（为某产生式的右部）时，就用相应的非终结符（产生式的左部）替换它(归约)。重复这一过程，直到输入符号串的末端，此时如果栈中只剩文法开始符号，则输入符号串是文法的句子，否则不是。规范归约：自底向上分析的移进－归约过程是自顶向下最右推导的逆过程，因为最右推导为规范推导，所以自

3、左向右的归约称为规范归约。例文法：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d输入串abbcde#的最右推导的过程为：S=>aAcBe=>aAcde=>aAbcde=>abbcde自底向上分析的过程为：abbcde

4、-aAbcde

5、-aAcde

6、-aAcBe

7、-S例文法：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d判断输入串abbcde#是否为该文法的句子用符号栈对输入符号串自底向上的分析过程为：归约（S→aAcBe）##aAcBe10）接受##S11）移进ee##aAcB9）归约（B→d）

8、e##aAcd8）移进dde##aAc7）归约（A→Ab）cde##aAb5）移进ccde##aA6）移进bbcde##aA4）归约（A→b）bcde##ab3）移进bbbcde##a2）移进aabbcde##1）动作输入符号串符号栈步骤关键问题：如何在分析的过程中确定句柄何时移进？栈顶未形成句柄何时归约？栈顶形成句柄常用自底向上分析法：算符优先分析法（6.3）LR类分析法（第7章）6.2自底向上优先分析法概述优先分析法两类：简单优先分析法基本思想：按一定原则定义文法中所有符号（终结符和非终结符）之间的优先关系，按照这

9、种关系确定归约过程中的句柄并实行归约。是一种规范归约。简单优先分析法准确、规范，但效率低，不实用，不介绍。算符优先分析法基本思想：只定义文法中终结符之间的优先关系（不考虑非终结符），并由这种关系指导分析过程不是规范归约算符优先分析法分析速度快，特别适用于表达式的分析。缺点是不规范，常常要采用适当措施克服其缺点。6.3算符优先分析法算符优先分析法特别适用于表达式的分析从表达式得到的启发：表达式的归约顺序与运算顺序是一样的通常算术表达式的运算次序是先乘除后加减，同优先级时服从左结合E→E+T

10、TT→T×F

11、FF→(E)

12、i

13、符号串E+T+T×F的归约过程为：E+T+T×F

14、-E+T×F

15、-E+T

16、-E运算次序只与运算符（优先级，结合性）有关，与运算对象无关可以根据运算符（终结符）的优先关系指导归约过程，与运算对象（非终结符）无关6.3.1优先关系6.3.2算符优先文法的定义6.3.3算符优先关系表的构造6.3.4算符优先分析算法6.3.5优先函数6.3.6算符优先分析法的局限性6.3.1优先关系优先关系只存在于句型中相邻出现的符号相邻：算符优先分析法只考虑终结符之间的优先关系，不考虑非终结符，所以两个终结符相邻指其中没有其他的终结符（但可

17、以有非终结符）如：E+T×i，＋和×相邻，×和i相邻，但＋和i不相邻终结符间优先关系表示：终结符a和b之间的优先关系表示如下：ab表示a的优先级高于b优先关系定义的依据在当前句柄中的符号优先于与其相邻的不在句柄中的符号被归约，其优先关系大同一句柄中的相邻符号同时被归约，其优先关系相同不可能相邻出现在任何句型中的两个符号，无法比较其归约的先后，故它们之间无优先关系E→E+T

18、TT→T×F

19、FF→(E)

20、iEE+TTF(E)句型(E)+T的句柄是(E),所以‘)’>‘+

21、’‘(’=‘)’注意：<，=，>是三种有序关系，与数学中的<，=，>不同，所以a=b不意味b=a，a>b不意味b

22、TT→T×F

23、FF→(E)

24、iETF(E)E+T在句型(E)+T中得)>+，在(E+T)中得+>)