第五章 自底向上优先分析方法
教学要求： 1.掌握算符优先关系表的构造，算符优先分析算法；
2．理解自底向上分析思想，简单优先文法及简单优先分析法，算符优先文法的定义；
目录：5.1 自底向上优先分析法概述
5.2 简单优先分析法 5.3 算符优先分析算法 自下而上语法分析的基本思想：从输入串开始，朝着文法的开始符号进行最左归约，直到到达文法的开始符号为止。主 要是进行移进或归约操作，采用最左归约。也称移进-归约分析法。 工作方式：“移进－归约”方式 即：自左至右把输入 串的符号一个一个移进栈，在移进过程中不断查看栈顶符号串，一旦形成某个句型的句柄时，就将此句柄用相应的产生式左部替换（归约），称为一步归约. 重复上面的过程直到栈顶只剩下文法的开始符号，输入串读完为止，这样就认为识别了一个句子。
自左至右的移进－归约过程是自顶向下最右推导的逆过程，所以也称规范归约。
分析程序模型 a+b……# 语法分析程序 + * # 语发表
注意: 1）初态时栈内仅有栈底符“＃”，读头指针在最左单词符号上。 2）语法分析程序执行的动作： a）移进 读入一个单词并压入栈内，读头后移； b）归约 检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该 符号串，同时输出产生式编号； c）识别成功 移进－归约的结局是栈内只剩下栈底符号和文法开始符号，读头 也指向语句的结束符； d）识别失败
※例如：
步骤 栈 输入串 输出带 动作
有文法如下 （1）S ?aAcBe
0 ＃ 移进 （2 ）A ?b
移 （3 ）A ?Ab 1 ＃a 移进进 （4 ）B ?d 2 ＃ab 归约归 问:语句abbcde 是不是该文法的
3 ＃aA 2 移进约 合法语句？
4 ＃aAb 归约的
分 5 ＃aA 2,3 移进 （1）S ?aAcBe（2）A ?b
析 6 ＃aAc 移进 （3）A ?Ab （4）B ?d
过 7 ＃aAcdS 归约程 自底向上构造的语法树为每次归约构造
8 9
一棵子树，最后当输入串结束时，正好
构造出整个语法树。
10 11 A B A a b b c ＃aAcB ＃2,3,4
移进归约接受
＃S
2,3,4,1
成功
? ?
自底向上分析算法的关键问题是在分析过程
中如何确定句柄.
常用的自下而上分析方法:优先分析和LR分析 5.1 自底向上优先分析法概述
5.1 自底向上优先分析法概述
分类: 1、简单优先分析:对一个文法按一定原则求出所有符号即终结符号和非终结符号之间的优先关系,按照这种关系确定归约过程中的句柄. 特点:准确、规范，但分析效率底，使用价值不大.
2、算符优先分析：只规定算符（终结符号）之间的优先关系，不考虑非终结符号之间的优先关系，只要找到句柄就归约，不考虑归约到那个非终结符号。 特点：不是规范归约，分析速度快，特别适合于表达式的分析.
5.2 简单优先分析法
基本思想: 1、对句型中相邻的文法符号规定优先关系，以寻找句型中的句柄。
2、规定句柄内各相邻符号之间具有相同的优先级。
3、规定句柄两端符号优先级要比位于句柄之外而又和句柄相邻的符
号的优先级高，以先归约句柄。
4、对于文法中所有符号，只要它们可能在某个句型中相邻，就要为
它们规定相应的优先关系，若某两个符号永远不可能相邻，则它们之间就无关系。
一、优先关系：相等、小和大
与数学中的=,<,>不同！
A)XY:当且仅当G中含有形如P?…XY…的产生式,
B)XY:当且仅当G中含有形如P?…XQ…的产生式，其中Q为非终结符，且Q ?Y...
C)XY:当且G中含有形如P?…QR…的产生式，其中Q为非终结符，且Q => …X，R=>Y…
D)对任何X，若文法开始符号S => X…,则# X,若S => …X，则X #，#=#。 ※例如： G[S]： 关系有： 关系有： 关系有：
S?->#S# b=A,A=b, b<(, bb, a>b, B>b
S->bAb (=B,A=a, a=) (<(, (
b A ( B a ) # <· =· ·> ·> ·> =· <· <· <· =· <· =· <· ·> ·> ·> =· ·> =· 二、简单优先文法的定义
一个文法G，若它不含?产生式，也不含任何右部相同的不同产生式，
并且它的任何符号对(X,Y)，或者没有关系，或者存在下述三种关系：·> 、 <·、 =·之一，则称该文法是一个简单优先文法。
三、简单优先分析法
数据结构：构造文法的优先关系矩阵
保存文法的产生式 设置栈S。
算法步骤：将输入符号串a1a2…an#依次逐个存入符号栈S中，直到遇到栈
顶符号ai的优先性 下一个待输入符号aj为止。
栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头ak, 即
找到ak-1 ak为止。
由句柄ak….ai在文法的产生式中查找右部为ak….ai的产生式，
若找到，则用相应的左部替换句柄，若找不到则为出错，这时输入串不是该文法的句子。
重复以上三步，直到归约完输入符号串，栈中只剩下文法的开始
符号为止。
5.3 算符优先分析方法
一、基本思想
1、自下而上归约
2、规定算符(更一般地说，指终结符)的优先级及结合规则，以使得分析过程唯一
3、比较相邻两个算符而决定动作
§注：1)这里的关键是对所有算符定义某种优先关系
2)算符优先分析法是仿效四则运算的计算过程而构造的一种语法分析方法 4、实例
表达式文法： E ?E+E|E-E|E*E|E/E|(E)|i
对这个二义文法可能会有好几个规范推导和归约，真正运算时也有几
种不同结果，但若按算符优先顺序和结合规则的规定进行归约，句子的归约过程就是唯一的，运算结果也唯一。
※例如： i+i-i*(i+i)归约过程如下：
i+i-i*(i+i) 设算量级别最高，最先归约； E +i-i*(i+i)
E+E-i*(i+i) ＋，－同级，先归约左边“＋” E-i*(i+i)
E-E*(i+i) －，*不同级，先归约右边“*” E-E*(E+i) 先括号内，后括号外 E-E*(E+E) 归约括号内 E-E*(E) 归约括号对 E-E*E 先归约“*” E-E 后归约“-”
E 结束（接受）
二、直观算符优先分析法 1、确定运算符的优先级 ·
关键是对一个给定文法G，人为地规定其运算符的优先顺序，优先关系的表示与简单优先文法类似：对于任何两个可能相继出现的终结符a,b，则a、b之间的关系为： 1) a<·b a的优先级低于b 2) a=·b a的优先级等于b 3) a·>b a的优先级高于b
4) 若ab在任何情况下都不可能相继出现，则a,b无关系。
注：1)算符优先分析法的关键是比较两个相继出现的终结符的优先级而决定应采取的动作。
2)要完成运算符间优先级的比较，可以先定义各种可能相继出现的运算符的优先级，并表示为矩阵的形式，使得能够在分析中通过查询矩阵元素而得到算符之间的优先关系。 左 右 + * （ ） I # + ·> <· <· ·> <· ·> * ·> ·> <· ·> <· ·> （ <· <· <· =· <· ） ·> ·> ·> ·> I ·> ·> ·> ·> # <· <· <· <· =· §注：1）在此表中，＋包括－，*包括/，“＃”是一个特殊符号，用于语句的开 始 符号和结束符号。
2）这张表满足通常数学上的习惯约定： a、运算量i的优先级高于算符； b、语句开始和结束符号“＃”与终结符a相继出现时，应该有# <·a和a·>#,
以此来保证语句内先归约。
3）(=·)表示括号是成对归约的。
4）优先关系和代数中的大于小于关系不同， a <·b并不意味着b·> a，终
结符所处的左右位置很重要。
三、算符文法的定义 1、定义及性质
给定上下文无关文法G，若G中所有产生式右部都不包含两个相继的
非终结符，则G为算符文法Operater Grammar(OG)。
§ 注：算符文法保证了两个运算符之间只有一个操作数。 算符文法性质
★性质1 在算符文法中任何句型都不包含两个相邻的非终结符 。
证明：用归纳法。 设γ是句型，即S γ S=ω0 ω1 ... ωn-1 ωn=γ 推导长度为n，归纳起点n=1时，
S=ω0 ω1=γ，即S γ，必存在产生式S→γ，而由算符文
法的定义，文法的产生式中无相邻的非终结符，显然满足性质1。 假设n＞1, ωn-1满足性质1。 若ωn-1=αAδ，A为非终结符。
由假设α的尾符号和δ的首符号都不可能是非终结符，否则与假设矛盾。 又若A→β是文法的产生式，则有ωn-1 ωn=αβδ=γ
而A→β是文法的原产生式，不含两个相邻的非终结符，所以αβγ也
不含两个相邻的非终结符。满足性质1。证毕。
★ 性质2 如果Ab或(bA)出现在算符文法的句型γ中，其中A∈VN ，b∈VT，则γ中任何含b的短语必含有A。 证明：用反证法。
因为由算符文法的性质1知可有： S * γ=αbAβ 若存在B → αb，这时b和A不同时归约，则必有S BAβ,这样在
句型BAβ中存在相邻的非终结符B和A，所以与性质1矛盾，证毕。 注意：含b的短语必含A，含A的短语不一定含b。
2、算符优先文法定义
设G是一个不包含空串产生式的算符文法，并设a,b ?VT; P,Q,R ?VN,定义关系： 1)a =·b 当且仅当G中含有形如P ? …ab…产生式，或者P ? …aQb…产生式； 2)a<·b 当且仅当G中含有形如P ? …aR…的产生式，其中R?b…, 或R?Qb…; 3)a·> b 当且仅当G中有形如P ?…Rb…产生式，其中R ?…a，或R ?…aQ. 若G中任何终结符序偶（a,b）至多满足上述关系之一，则称G为算符优
先文法Operater Precedence Grammar（OPG）。
用语法树来理解更直观 A A A …a B … …… B b …….. …a ? b… P P a=·b ? b … … a ? E 表达式文法： E ?E+E|E*E| (E)|Ia<·b 是算符文法和算符优先文法吗? a·>E + b E
E * E
编译原理 第5章课件
