东北大学秦皇岛分校编译原理课件 第六章.ppt

《东北大学秦皇岛分校编译原理课件 第六章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章自底向上优先分析法自底向上分析法的基本思想及主要方法自底向上分析法也称移进-归约法。自底向上分析法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上归约，试图归约到文法的识别符号。从语法树的角度来看：自底向上分析的过程是以输入符号串作为末端结点符号串，向着根结点的方向往上构造语法树，使识别符号正好是该语法树的根结点。自底向上分析法的关键在于：如何在每一步归约当中，找到当前句型的句柄，并判断句柄是否唯一。主要的分析方法有：简单优先分析法、算符优先分析法、LR类分析法。自底向上分析法中面临的问题及解决方法采用自底向上分析法分

2、析的每一步中，会遇到两个基本问题：（1）如何找出进行直接归约的简单短语？（2）找出的简单短语应直接归约到哪一个非终结符号？解决方法：由于分析过程是从左往右扫描源程序，所以遇到的第一个简单短语正好是句柄，因此，第一个问题变为：如何找到句柄。对于如何找到句柄，找到句柄后应归约到哪一个非终结符号这两个问题，不同的自底向上分析法有不同的解决方法。简单短语：只经过一次推导得到的短语叫简单短语；句柄：句型的最左简单短语。自底向上分析法的基本实现方法自底向上分析的基本实现方法是：移进-归约法。引入“#”作为栈底标志符号。在整个分析过程中，共有4类动

3、作：（1）移入：读入下一个输入符号并把它下推进栈。（2）归约：当栈顶的（部分）符号串形成一个句柄时，对此句柄进行归约，把形成句柄的符号串替换为相应的非终结符号。（3）接受：当识别程序发现栈顶除了栈底标志符号#外仅有识别符号，而输入也以达到右端标志符号#时，便识别出输入符号串是一个句子，执行接受动作并结束本次识别。（4）报错：发现输入符号串不是句子而无法继续识别。自底向上优先分析法的基本思想常见的自底向上的分析算法：（1）优先分析法（2）LR类分析法优先分析法分为：（1）简单优先分析法：采用规范归约，考虑所有文法符号（包括终结符号、非终

4、结符号）之间的优先关系。（2）算符优先分析法：不是规范归约，只考虑算符（即终结符号）之间的优先关系。自底向上优先分析法的基本思想：利用文法符号中相邻符号之间的优先关系找出句柄。简单优先分析法及简单优先文法简单优先分析法按照文法符号（终结符号和非终结符号）的优先关系确定句柄。如何确定任意两个文法符号之间的优先关系？如何构造优先关系表补充内容FIRST关系：UFIRSTS存在规则U→S……（注：S可以是终结符号，也可以是非终结符号。）FIRST关系的传递闭包：FIRST+=FIRST∪FIRST2∪FIRST3∪……LAST关系：ULA

5、STS存在规则U→……S（注：S可以是终结符号，也可以是非终结符号。）LAST关系的传递闭包：LAST+=LAST∪LAST2∪LAST3∪……例：求文法G的FIRST关系和LAST关系G[A]：A→Af

6、BB→Ddc

7、DeC→eD→Bf∵A→AfA→BB→DdcB→DeC→eD→Bf∴AFIRSTAAFIRSTBBFIRSTDBFIRSTDCFIRSTeDFIRSTBFIRST={（A，A），（A，B），（B，D），（C，e），（D，B）}∴ALASTfALASTBBLASTcBLASTeCLASTeDLASTfLAST={（A，

8、f），（A，B），（B，c），（B，e），（C，e），（D，f）}FIRST={（A，A），（A，B），（B，D），（C，e），（D，B）}FIRST2={（A，A），（A，B），（A，D），（B，B），（D，D）}FIRST3={（A，A），（A，B），（A，D），（B，D），（D，B）}FIRST4=FIRST2∴FIRST+=FIRST∪FIRST2∪FIRST3={(A，A)，(A，B)，(A，D)，(B，D)，(C，e)，(D，B)，(D，D)}LAST={(A，f)，(A，B)，(B，c)，(B，e)，(C，e)，(D，f

9、)}LAST+={={(A，f)，(A，B)，(A，c)，(A，e)，(B，c)，(B，e)，(C，e)，(D，f)}优先关系的形式定义：（1）相等关系X=Y：当且仅当G中存在规则A→…XY…（2）小于关系XY…）（3）大于关系X>Y：当且仅当G中存在规则A→…BD…，且BLAST+X（即B=>…X）和DFIRST*Y（即D=>Y…）。在此限定S为终结符号。简单优先文法满足条件：（1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。（2）在文法中任意两个产

10、生式没有相同的右部。由简单优先文法的定义可知，简单优先文法是无二义性的。++*构造优先关系构造相等关系“=”很简单，只需要顺次考察文法的各规则即可。如：例6.2（1）。构造大于和小于关系，可以使用如下两个公式：其中，（F