编译原理：第五章 语法分析5

1、 简单优先分析法是一种从左到右扫描、最左归约分析法；它属于自底向上分析方法。 该方法利用文法符号之间的优先关系来确定待归约的句柄 ，即可确定当前句型的句柄。5.5 简单优先分析法 利用一个分析表，登记选择句柄产生式的知识； 利用一个分析栈，记录分析过程；【分析算法】依次读取单词，并进行如下操作： 当栈顶出现句柄时，规约之，否则移进。 5.5.1. 简单优先分析法基本概念 简单优先分析法的基本要点有三：1. 什么是简单优先分析法？ 2. 简单优先分析过程示例 符号串： = abbeae #SaAeBSbbaG(S): SaAeB|b ASb|e BaAAe 句柄产生式 操 作 剩余串 w 分析栈

2、 移进,NEXT a e # e# a 移进,NEXT e # a# a A 移进,NEXT # e# a A e 归约 A - e # aAe a 归约 B - aA # aAe a A - Sb S - b 归约 e a e # b# a 移进,NEXT b b e a e # a# 归约 a e # e # a S 移进,NEXT e a e # b# a 移进,NEXT b e a e # b# A A a a b e e句柄(接上页) 利用分析栈记录行分析过程：【注】何时栈顶出现句柄？怎样求当前句柄产生式 ？设 待分析的符号串: abbeae# S b# aAe # B句柄 S -

3、aAeB 归约# # S OK同时归约者为相等关系，记作 ；3. 文法符号之间的优先关系归约过程中如何确认句柄？ 是否是句柄，还要看其所在符号串中的位置。语法树从语法树上，找出优先关系（指相临符号之间）如下： S b，a A，A e，e B 如：左后归约者为小于关系，记作； 如：ab,ae, e； 如：bb,be 当把优先关系纳入待分析的符号串时，有如下关系： # a b e a # # a e a # # a A e a # # a A e # # # 结论：一个句型的句柄，位于第一次（自左至右）出现在之间的符号串！ 从文法中获取优先关系! 设si ，sj是两个文法符号; 如：a A，A e

4、，e B，S b； si sj ，当且仅当有Usi sj ； 优先关系的定义 G(S): SaAeB|b ASb|e BaA si +如：ae，aS，aa，ab，esj ，当且仅当有 UVsj ，且 V si； = +如：bb，Bb，Ab，eb。 (3)头符号集合和尾符号集合 设 AVN， si ，sj是两个文法符号;则: FIRSTVT(A)=si| A si, = +LASTVT(A) = sj|A sj。 = +【例5.12】G(S): SaAeB|b，ASb|e，BaA S A B a b e S A B a e S A BFIRSTVT a , b S,e,a,b aLASTVT B

5、,b,A,e b , e A , b , e 头符号集合尾符号集合优先矩阵表项=空表示两个符号不可能相临。 +简单优先分析器的基本组成：优先分析法要求文法应是简单优先文法。优先矩阵分析表 优先分析控制器 分析中只查看当前符号就可确认句柄；5.5.2 简单优先分析器设计1.简单优先文法及其判定 文法产生式没有相同的右部； 如A ，B ， 满足下述特点的文法称为简单优先文法。例5.12 文法，就是简单优先文法，请看：文法符号之间至多有一种优先关系！ 【算法】 si sj ， 当且仅当有Usi sj ； si sj ， 当且仅当有UVsj，且siLASTVT(V)。 2. 简单优先分析矩阵分析表构造

6、设 W,VVN,si，sj是两个文法符号; 简单优先分析表是优先分析法的知识表,是文法的一种机内表示形式：终结符 +非终结符+# a Z #优先关系符号终结符+非终结符+#3. 简单优先控制程序设计开始PUSH(#)NEXT(w)查优先分析表R(Xk,w)=? 空?nerr(#S#) 结束PUSH WPOP(sj)，POP(sj-1)，POP(si)；PUSH(A)。从sj（栈顶符）开始，往栈内查找，找到第一个使si-1?yn只考虑算符（终结符）之间的优先关系 （1）算符文法 设有一文法G，如果G中没有形如AQR的产生式，其中Q和R为非终结符，则称该文法为算符文法（OG文法）。 5.5.3 算

7、符优先分析(2)头符号集合和尾符号集合 设 aVT，P,RVN， 则: FIRSTVT(P)=a| P a 或 P Ra, = +LASTVT(P) =a| P a 或 P aR。 = + = + = +设a,bVT，P,Q,RVN， a b ， 当且仅当有 Pab 或 PaQb ； (3) 算符优先关系定义 a + ab ， 当且仅当有 PRb ，且R a 或 R aQ； = +(4)算符优先文法 如果算符文法G中的任何一对终结符a和b之间，仅满足上述一种关系，则G就是一个算符优先文法（OPG）。 = + = +习题：【习题5.13】已知下述文法：G(E): E - T | E + T | E - T