编译原理 第六章 算符优先分析法.doc

第6章　自底向上优先分析
第六章 算符优先分析法

课前索引

【课前思考】
　　◇ 什么是自下而上语法分析的策略？
　　◇ 什么是移进-归约分析？
　　◇ 移进-归约过程和自顶向下最右推导有何关系？
　　◇ 自下而上语法分析成功的标志是什么？
　　◇ 什么是可归约串？
　　◇ 移进-归约过程的关键问题是什么？
　　◇ 如何确定可归约串？
　　◇ 如何决定什么时候移进，什么时候归约？
　　◇ 什么是算符文法？什么是算符优先文法？
　　◇ 算符优先分析是如何识别可归约串的？
　　◇ 算符优先分析法的优缺点和局限性有哪些？
【学习目标】
　　算符优先分析法是自下而上（自底向上）语法分析的一种，尤其适应于表达式的语法分析，由于它的算法简单直观易于理解，因此，也是学习其它自下而上语法分析的基础。通过本章学习学员应掌握：
　　◇ 对给定的文法能够判断该文法是否是算符文法
　　◇ 对给定的算符文法能够判断该文法是否是算符优先文法
　　◇ 对给定的算符文法能构造算符优先关系表，并能利用算符优先关系表判断该文法是否是算符优先文法。
　　◇ 能应用算符优先分析算法对给定的输入串进行移进-归约分析，在分析的每一步能确定当前应移进还是归约，并能判断所给的输入串是否是该文法的句子。
　　◇ 了解算符优先分析法的优缺点和实际应用中的局限性。
【学习指南】
　　算符优先分析法是自下而上语法分析的一种，它的算法简单、直观、易于理解，所以通常作为学习其它自下而上语法分析的基础。为学好本章内容，学员应复习有关语法分析的知识，如：什么是语言、文法、句子、句型、短语、简单短语、句柄、最右推导、规范归约基本概念。
【难 重 点】
　　◇ 通过本章学习后，学员应该能知道算符文法的形式。
　　◇ 对一个给定的算符文法能构造算符优先关系分析表，并能判别所给文法是否为 算符优先文法。
　　◇ 分清规范句型的句柄和最左素短语的区别，进而分清算符优先归约和规范归约的区别。
　　◇ 算符优先分析的可归约串是句型的最左素短语，在分析过程中如何寻找可归约串是算符优先分析的关键问题。对一个给定的输入串能应用算符优先关系分析表给出分析（归约）步骤，并最终判断所给输入串是否为该文法的句子。
　　◇ 深入理解算符优先分析法的优缺点和实际应用中的局限性。
【知 识 点】

短语、直接短语、句柄的定义：
　　文法G[S]，
　　S αAδ且A β则称β是句型α β δ相对于非终结符A的短语。
　　若有Aβ则称β是句型α β δ相对于A或规则A → β的直接短语。
　　一个句型的最左直接短语称为该句型的句柄。
　　算符优先分析法是一种自底向上分析方法，也称移进-归约分析法，粗略地说它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，(该句柄对应某产生式的右部)，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。本章将在介绍自底向上分析思想基础上，着重介绍算符优先分析法。
　　栈顶符号串是指该符号串包含栈顶符号在内，并由栈中某个符号为该符号串的头，栈顶符号为该符号串的尾，也可以只有一个栈顶符号。

6.1 自底向上分析概述

自底向上分析法，也称移进-归约分析法，或自下而上分析。现举例说明。

例6.1

　　设文法G[S]为：
　　(1) S→aAcBe
　　(2) A→b
　　(3) A→Ab
　　(4) B→d
　　对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。
　　由于自底向上分析的移进-归约过程是自顶向下最右推导的逆过程，而最右推导为规范推导，自左向右的归约过程也称规范归约。
　　容易看出对输入串abbcde的最右推导是：
　　SaAcBeaAcdeaAbcdeabbcde
　　由此我们可以构造它的逆过程即归约过程。
　　先设一个先进后出的符号栈，并把句子左括号"#"号放入栈底，其分析过程如表6.1。

表6.1 用移进-归约对输入串abbcde#的分析过程
f6-1-1.swf
图6.1 自底向上构造语法树的过程

推倒的逆过程为：SaAcBeaAcdeaAbcdeabbcde
对上述分析过程也可看成自底向上构造语法树的过程，每步归约都是构造一棵子树，最后当输入串结束时刚好构造出整个语法树，图6.1(a)(b)(c)(d)给出构造过程，可与表中相应分析步骤对照。
　　在上述移进-归约或自底向上构造语法树的过程中，我们怎么知道何时移进，何时归约，不能只简单地看成栈顶出现某一产生式的右部就可用相应产生式归约，例如在表6.1分析到第5)步时栈中的符号串是#aAb，栈顶符号串b和Ab分别是产生式(2)，(3)的右部，这时到底用(2)归约还是用(3)归约是自底向上分析要解决的关键问题。
　　由于移进-归约是规范推导(最右推导)的逆过程，即规范归约(最左归约)。当一个文法无二义性时，那么它对一个句子的规范推导是唯一的，规范归约也必然是唯一的。因而每次归约时一定要按当前句型的句柄，也就是说，任何时候栈中的符号串和剩余的输入串组成一个句型，当句柄出现在栈顶符号串中时，则可用句柄归约，这样一直归约到输入串只剩结束符，文法符号栈中只剩开始符号。这时才能认为输入符号串是文法的句子。否则为出错。
　　由此可见自底向上分析的关键问题是在分析过程中如何确定句柄，也就是说如何知道何时在栈顶符号串中已形成某句型的句柄，那么就可以确定何时可以进行归约。
　　自底向上的分析算法很多，我们仅在本章和第7章介绍目前常用的算符优先分析和LR类分析法。
　　小练习：用PL/0的READ(A)语句为例构造自底向上的语法分析树,以体会自底向上的归约过程。下面为参考答案。
图6.3 自底向上的语法分析

6.2 算符优先分析法

算符优先分析的基本思想是只规定算符(广义为终结符)之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符名，算符优先分析的可归约串不一定是规范句型的句柄，所以算符优先归约不是规范归约。算符优先分析的可归约串是当前符号栈中的符号和剩余的输入符号构成句型的最左素短语。
例如:若有文法G为：
　　(1) E→E+E
　　(2) E→E*E
　　(3) E→i
　　对输入串i1+i2*i3的归约过程可表示为表6.3。
表6.3 对输入串i1+i2*i3的归约过程
f6-2-2.swf
在分析到第6步时，栈顶的符号串为E+E，若只从移进-归约的角度讲，栈顶已出现了产生式(1)的右部，可以进行归约，但从通常四则运算的习惯来看应先乘后加，所以应移进，这就提出了算符优先的问题。
　　本节所给例子是二义性文法，对二义性文法不能构造确定的分析过程，但是在本例中，人为地规定了算符之间的优先关系，仍然可构造出确定的分析过程。
6.2.1 直观算符优先分析法
　　通常在算术表达式求值过程中，运算次序是先乘除后加减，这说明了乘除运算的优先级高于加减运算的优先级，乘除为同一优先级但运算符在前边的先做，这称为左结合，同样加减运算也是如此，这也说明了运算的次序只与运算符有关，而与运算对象无关，因而直观算符优先分析法的关键是对一个给定文法G，人为地规定其算符的优先顺序，即给出优先级别和同一个级别中的结合性质，算符间的优先关系表示规定如下：
　　ab表示a的优先性低于b。
　　ab表示a的优先性等于b，即与b相同。
　　ab表示a的优先性高于b。
　　但必须注意，这三个关系和数学中的＜，＝，＞是不同的。当有关系ab时，却不一定有关系ba，当有关系ab时，却不一定有ba，例如：通常表达式中运算符的优先关系有+-，但没有-+，有'('')'，但没有')''('。
　　下面给出一个表达式的文法为：
　　E→E+E|E－E|E*E|E/E|E↑E|(E)|i
本文法是二义性的，由于人为地规定了算符之间的优先级别和同一个级别中的结合性质，所以可能构造出确定的分析过程。
　　我们可以对此表达式的文法按公认的计算顺序规定优先级和结合性如下：
　　① ↑优先级最高。遵循右结合，相当↑↑。
　　例如：2↑3↑2=2↑9=512。（而若为左结合则2↑3↑2=8↑2=64） 也就是同类运算符在归约时为从右向左归约。即 i1↑i2↑i3式先归约i2↑i3。
　　② *,/ 优先级其次。服从左结合，相当 ** 、*/ 、// 、/* 。
　　③ +，- 优先级最低。服从左结合，相当 ++、+- 、-+ 、-- 。
　　④ 对'('，')'规定括号的优先性大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号。对于句子括号'#'号规定与它相邻的任何运算符的优先性都比它大。此外，对运算对象的终结符i其优先级最高。
　　综上所述，我们可对表达式运算符的优先关系构造如表6.4。

表 6.4 算符优先关系表

+
-
*
/
↑
(
)
i
#

+
-
*
/
↑
(
)
i
#

.
.

.
.

.

很显然所给表达式文法是二义性的，但我们人为直观地给出运算符之间的优先关系，由优先关系表6.4可知这种优先关系是唯一的，有了这个优先关系表我们对前面表达式的输入串i1+i2*i3归约过程就能唯一确定了，也就是说在表6.3分析到第6）步时，栈中出现了#E+E，可归约为E，但当前输入符为'*'，由于规定 +*，所以应移进。
　　本节简单介绍直观算符优先分析法，仅仅是为了易于理解算符优先分析法的概念，下一节将介绍对任意给定的一个文法如何按形式算法的规则计算算符之间的优先关系。
6.2.2 算符优先文法的定义
　　我们首先给出算符文法和算符优先文法的定义。
定义6.1 设有一文法G，如果G中没有形如A→…BC…的 产生式，其中B和C为非终结符，则称G为算符文法(Operater Grammar)也称OG文法。
　　例如：表达式文法E→E+E|E*E|(E)|i
　　其中任何一个产生式中都不包含两个非终结符相邻的情况，因此该文法是算符文法。
小练习：学员可证明算符文法有如下两个性质。
　　性质1 在算符文法中任何句型都不包含两个相邻的非终结符 。
　　性质2 如果Ab或(bA)出现在算符文法的句型γ中，其中A∈VN ，b∈VT，则γ中任何含b的短语必含有A。
　　参考答案：
　　证明：性质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
　　用反证法。
　　因为由算符文法的性质1知可有：
　　Sγ=αbAβ
　　若存在Bαb，这时b和A不同时归约，则必有SBAβ,这样在句型BAβ中存在相邻的非终结符B和A，所以与性质1矛盾，证毕。注意：含b的短语必含A，含A的短语不一定含b。
定义6.2 设G是一个不含ε产生式的算符文法，a和b是任意两个终结符，A、B、C是非终结符，算符优先关系、、定义如下 ：
　　① ab 当且仅当G中含有形如A→…ab…或A→…aBb…的产生式
　　② ab 当且仅当G中含有形如A→…aB …的产生式，且Bb… 或BCb…
　　③ ab当且仅当G中含有形如A→…Bb …的产生式，且B…a 或B…aC
以上三种关系也可由下列语法树来说明：
　　① a b 则存在语法子树如图6.3(a)
　　其中δ为ε或为B，这样a, b在同一句柄中同时归约所以优先级相同。
　　② a b 则存在语法子树如图6.3(b)
　　其中δ为ε或为C。a,b不在同一句柄中，b先归约，所以a的优先级低于b。
　　③ a b 则存在语法子树如图6.3(c) 。
图6.3 由语法树结构决定优先性

其中δ为ε或为C，a、b不在同一句柄中，a先归约，所以a的优先性大于b。
　　下面我们给出算符优先文法的定义。
　　由定义6.2可有如下推论：
　　a) 若有产生式A→a…或A→B a…、
　　则a∈FIRSTVT(A)，其中A、B为非终结符，a为终结符。
　　b) 若a∈FIRSTVT(B)且有产生式A→B…则有a∈FIRSTVT(A)。
定义 6.3 设有一不含ε产生式的算符文法G，如果对任意两个终结符对a，b之间至多只有 、 和 三种关系中的一种成立，则称G是一个算符优先文法。(Operator Precedence Grammar)即OPG文法。
　　结论：算符优先文法是无二义性的。
由定义6.2和6.3很容易证明前面我们给的表达式文法。
　　E→E+E|E*E|(E)|i 不是算符优先文法。
　　因为对算符 +、* 来说，由 E→E+E 和 E E*E 可有 +* ，这由语法子树图6.4(a)也可看出。又可由E→E*E 和 E E+E 得 +*，由语法子树表示为图6.4(b)。
图 6.4 二义性文法的语法树

这样+、* 的优先关系不唯一，所以该表达式的文法仅是算符文法而不是算符优先文法。这里必须再次强调，两个终结符之间的优先关系是有序的，允许有 ab，ba同时存在 ，而不允许有 ab，ab，ab 三种情况中之两种同时存在。
6.2.3 算符优先关系表的构造
　　可由定义直接构造
　　由定义6.2我们可计算出给定的算符文法中任何两个终结符对(a,b)之间的优先关系，其算法如下：
　　首先定义如下两个集合：
　　FIRSTVT(B)={b|B b… 或 B Cb…}
　　LASTVT(B)={a|B…a 或 B …aC}
　　三种优先关系的计算为：
　　a) 关系:
　　可直接查看产生式的右部，对如下形式的产生式
　　A→…ab… , A→…aBb…
　　有a b 成 立。
　　b) 关系:
　　求出每个非终结符B的FIRSTVT(B)，在如下形式的产生式
　　A→…aB… 中，对每一 b∈FIRSTVT(B),有ab成立。
　　c) 关系:
　　计算每个非终结符B的LASTVT(B)，在如下形式的产生式
　　A→…Bb… 中，对每一a∈LASTVT(B)，有ab成立。
现在可用上述算法计算下列表达式文法的算符优先关系。
　　若有表达式文法为：
　　(0) E′→#E#
　　(1) E→E+T
　　(2) E→T
　　(3) T→T*F
　　(4) T→F
　　(5) F→P↑F|P
　　(6) P→(E)
　　(7) P→i
　　E′→#E#为对原文法的扩充，'#'表示句子括号，所描述的语言和扩充前完全相同。为了分析过程的确切，把'#'号也作为终结符对待。
　　计算表达式文法的优先关系为：
　　a) 关系
　　由产生式(0) E′→#E# 和(6) P→(E)
　　可得'#''#'，'（''）'成立。
为了求和关系 ，需先由定义6.2计算每个非终结符的FIRSTVT集合和LASTVT集合，结果为：
　　FIRSTVT(E′)={#}
　　FIRSTVT(E)={+，*，↑，(，i}
　　FIRSTVT(T)={*，↑，(，i}
　　FIRSTVT(F)={↑,(，i}
　　FIRSTVT(P)={(，i}
　　LASTVT(E′)={#}
　　LASTVT(E)={+，*，↑，)，i}
　　LASTVT(T)={*，↑，)，i}
　　LASTVT(F)={↑，)，i}
　　LASTVT(P)={)，i}
　　在计算每个非终结符的FIRSTVT集合和LASTVT集合时，可先考虑文法中含有E→T，T→F ，F→P形式的产生式，由定义6.2的推论可知P的FIRSTVT集合和LASTVT集合也属于F的FIRSTVT集合和LASTVT集合，同样F的也属于T的，T的也属于E的。集合中的其它元素可根据定义由产生式直接计算。
　　然后逐条扫描产生式寻找终结符在前非终结符在后的相邻符号对和非终结符在前终结符在后的相邻符号对，即产生式右部有形如
　　A→…aB… 和 A→…Bb… 的产生式。
b) 关系：对所给表达式文法中终结符在前非终结符在后的相邻符号对有：
　　#E 则有：# FIRSTVT( E)
　　+T 则有：+ FIRSTVT(T)
　　*F 则有：* FIRSTVT(F)
　　↑F 则有：↑ FIRSTVT(F)
　　(E 则有：( FIRSTVT(E)
　　c) ·＞关系：对表达式文法中非终结符在前终结符在后的相邻符号对有：
　　E# 则有：LASTVT(E) #
　　E+ 则有：LASTVT(E) +
　　T* 则有：LASTVT(T) *
　　P↑ 则有：LASTVT(P) ↑
　　E) 则有：LASTVT(E) )
　　从而可以构造优先关系矩阵为表6.5。
表6.5 表达式文法算符优先关系表

+
*
↑
i
(
)
#

+
*
↑
i
(
)
#

.

.

.

.

.

.

6.2.4 算符优先分析算法
　　上一节介绍了如何对已给定的文法按其产生式构造算符优先关系表，有了算符优先关系表并满足算符优先文法时，我们就可以对任意给定的符号串进行归约分析，进而判定输入串是否为该文法的句子。然而用算符优先分析法的归约过程与规范归约是不同的。
(1) 算符优先分析句型的性质
　　根据算符优先文法的定义 6.3 可知算符优先分析句型有如下性质：
　　如果aNb(或ab)出现在句型r中，则a和b之间有且只有一种优先关系,即：
　　若a b则在r中必含有b而不含a的短语存在。
　　若a b则在r中必含有a而不含b的短语存在。
　　若a b则在r中含有a的短语必含有b，反之亦然。
读者可根据定义6.3证明此性质。由此性质可见算符优先文法在归约过程中只考虑终结符之间的优先关系确定可归约串（句柄），而与非终结符无关，只需知道把当前句柄归约为某一非终结符，不必知道该非终结符的名字是什么，这样也就去掉了单非终结符的归约，因为若只有一个非终结符时无法与句型中该非终结符的左部及右部的串比较优先关系。也就无法确定该非终结符为句柄。
由（1）给出算符文法的性质，可以知道算符文法的任何一个句型应为如下形式：
　　#N1a1N2a2 ... Nnan Nn+1#
　　其中Ni(1≤i≤n+1)为非终结符或空，ai(1≤i≤n)为终结符。
　　若有Niai ... NjajNj+1为句柄，则Ni和Nj+1在句柄中，这是由于算符文法的任何句型中均无两个相邻的非终结符，且终结符和非终结符相邻时含终结符的句柄必含相邻的非终结符(见6.2.2中的性质2)。
　　该句柄中终结符之间的关系为：
　　ai-1 ai
　　ai ai+1…… aj-1 aj
　　aj aj+1
由于算符优先分析过程归约时，只能把和之间的符号串作为可归约串进行归约。
　　例如：若有一输入串i+i#，用表达式文法的算符优先关系表6.5，进行算符优先归约时步骤如表6.8。
　　由表6.8可以看出算符优先分析不是规范归约，在第3)步和第6)步栈顶的F都不能当做句柄归约为T，因为在第3)步句型#F+i#中，只有#+，所以 F 构不成句柄，在第6)步句型#F+F#中，也只有#+和+#，因而栈顶的F仍不能构成句柄。而对输入串i+i#当用规范归约时其过程如表6.7。
　　至于为什么在规范归约的过程中F能构成句柄的原因将在第7章的LR类分析法中介绍。
　　为了解决在算符优先分析过程中如何寻找到可归约串的问题，现引进最左素短语的概念。
f6-2-3.swf
(2) 最左素短语
　　定义6.5 设有文法G[S],其句型的素短语是一个短语,它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素短语。
　　例如,若表达式文法G[E]为：
　　E→E+T|T
　　T→T*F|F
　　F→P↑F|P
　　P→(E)|i
图 6.8 句型T+T*F+i的语法树

若有句型#T+T*F+i#，它的语法树如图6.8。其短语有：
　　T+T*F+i 相对于非终结符E的短语
　　T+T*F 相对于非终结符E的短语
　　T 相对于非终结符E的短语
　　T*F 相对于非终结符T的短语
　　i 相对于非终结符P,F,T的短语
　　由定义6.5知i和T*F为素短语，T*F为最左素短语。也为算符优先分析的可归约串。由6.2.4(1)可知一个算符优先文法的最左素短语满足如下条件：
　　ai-1 ai ai+1 ... aj aj+1
　　上述句型#T+T*F+i#写成算符分析过程的形式为：
　　#N1a1N2a2N3a3a4#其中a1 = +, a2 = *, a3 = +, a4 = i
　　a1 a2 (因+ *)
　　a2 a3 (因* +)
　　由此 N2a2N3 即T*F为可归约串，也就是前面分析的最左素短语。
　　在实际分析过程中不必考虑非终结符名是T还是F或是E，而只要知道是非终结符即可，具体在表达式文法中的T还是F或是E都为运算对象。
　　上述句型#T+T*F+i#的归约过程由于去掉了单非终结符E→T，T→F的归约，所以得不到真正的语法树，而只是构造出语法树的框架如图6.9。
图 6.9 算符优先分析时语法树的框架

特别要注意在算符优先分析过程中，因去掉了单非终结符之间的归约，非终结符的名字没有任何意义。所以在归约过程中所有的非终结符都用同一个名字。
(3) 算符优先分析归约过程的算法
　　自底向上的算符优先分析法，也为自左向右归约，我们已经知道它不是规范归约。规范归约的关键问题是如何寻找当前句型的句柄，而算符优先分析归约的关键是如何找最左素短语。最左素短语 NiaiNi+1ai+1 … ajNj+1 应满足：
　　ai-1 ai
　　ai ai+1 … aj
　　aj aj+1
　　在文法的产生式中存在右部符号串的符号个数与该素短语的符号个数相等，非终结符号对应 Nk,(k=i，…，j+1)不管其符号名是什么。终结符对应ai，…，aj，其符号名要与ai，…，aj的实际名相一致，相应位置也一致，才有可能形成素短语。由此，我们在分析过程中可以设置一个符号栈S，用以寄存归约或待形成最左素短语的符号串，用一个工作单元a存放当前读入的终结符号，归约成功的标志是当读到句子结束符#时，S栈中只剩#N，即只剩句子最左括号'#'和一非终结符N。下面给出分析过程的示意图如图6.10。
　　在归约时要检查是否有对应产生式的右部与S[j+1]…S[k]相符，若有才可归约，否则出错。在这个分析过程中把'#'也放在终结符集中。
S[j+1]…S[k]为S栈中符号串，S[k]为栈顶符号。所谓检查是否有对应产生式的右部与S[j+1]…S[k]相符，是指符号个数是否相等，对应的终结符名是否相同。不管非终结符名字。
　　规范归约时句柄为某一产生式的右部，归约结果为从符号栈中去掉与句柄相同的产生式右部符号串，并把左部非终结符放入栈中，代替归约前的句柄。
图 6.10 算符优先分析归约过程框图

6.2.5 算符优先分析法的局限性
　　由于算符优先分析法去掉了单非终结符之间的归约，尽管在分析过程中，当决定是否为句柄时采取一些检查措施，但仍难完全避免把错误的句子得到正确的归约。
例如，下述文法是一个算符优先文法，其产生式为：
　　S→S;D|D
　　D→D(T)|H
　　H→a|(S)
　　T→T+S|S
　　其中VN＝{S，D，T，H}，VT＝{；,(,),a,+}，S为开始符号。
　　对应的算符优先关系矩阵为表6.14。
表 6.14 算符优先关系矩阵表

;
(
)
a
+
#

;
(
)
a
+
#

.

.
.

.

.

.

请读者以表6.14 算符优先关系矩阵表，用算符优先分析法对输入串(a+a)#
　　进行分析，不难发现它可以完全正确地进行归约，然而(a+a)#却不是该文法能推导出的句子。
　　此外，通常一个适用语言的文法也很难满足算符优先文法的条件，因而致使算符优先分析法仅适用于表达式的语法分析。

本章小结

【本章小结】
　　语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)，目前语法分析常用的方法有自顶向下（自上而下）分析（见第5章）和自底向上（自下而上）分析两大类。而自底向上分析又可分为算符优先分析和LR分析（见第7章），它们的分析都是移进-归约过程，是自顶向下最右推导的逆过程，但LR分析是规范归约 ，算符优先分析不是规范归约。它们的区别在于识别可归约串的原则不同。LR分析是按规范句型的句柄为可归约串，算符优先分析是以句型的最左素短语为可归约串，这样算符优先分析去掉了单非终结符的归约（即一个非终结符到另一个非终结符的归约），因此，算符优先分析法比LR分析（规范归约）法的归约速度快。在LR分析一章的语法分析器自动生成工具Yacc中，对算数表达式的归约往往会用到算符优先关系的概念。
　　算符优先分析的缺点是对文法有一定的限制，在实际应用中往往只用于算数表达式的归约。由于算符优先分析不是规范归约，所以可能把不是文法的句子错误的归约成功。
　　算符优先分析是移进-归约过程，移进就是将一个终结符推进栈 ，归约就是将0个或多个符号（某个产生式的右部）从栈中弹出，将相应产生式左部的非终结符压入栈中。对一个输入符号串，不断地进行移进-归约过程，若能归约到文法的开始符号则为归约成功。在归约工作的每一步，都是从当前栈顶符号串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为"可归约串"。因此， 如何识别"可归约串"是算符优先分析的关键问题。
本章学习的重点：
　　对一个给定的算符文法能构造算符优先关系分析表，并能判别所给文法是否为算符优先文法。对一个给定的输入串能应用算符优先关系分析表给出分析（归约）步骤，并最终判断所给输入串是否为该文法的句子。分清规范句型的句柄和最左素短语的区别，进而分清算符优先归约和规范归约的区别。

课后习题
第6章　习题

第1题
　　已知文法G[S]为：
　　S→a|∧|(T)
　　T→T,S|S
　　(1) 计算G[S]的FIRSTVT和LASTVT。
　　(2) 构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。
　　(3) 给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。

第2题
　　对题1的G[S]
　　(1) 给出(a,(a,a))和(a,a)的最右推导，和规范归约过程。
(2) 将(1)和题1中的(3)进行比较给出算符优先归约和规范归约的区别。

问答题答案
问答第1题
　　文法：
　　S→a|∧|(T)
　　T→T,S|S
　　展开为：
　　S→a
　　S→∧
　　S→(T)
　　T→T,S
　　T→S
(1) FIRSTVT -- LASTVT表
非终结符
FIRSTVT集
LASTVT集
S
{ a ∧ ( }..
{ a ∧ ) }..
T
{ a ∧ ( , }
{ a ∧ ) , }
(2) 算符优先关系表（OPERATER PRIORITY RELATION TABLE）

a
∧
(
)
,
#
a
∧
(
)
,
#
.
.

.

.
.

.

.
.

.

表中无多重人口所以是算符优先（OPG）文法。
（3）对输入串（a,a）#的算符优先分析过程为
栈（STACK）
当前输入字符（CHAR）
剩余输入串（INPUT_STRING）
动作（ACTION）
#
#(
#(a
#(N
#(N,
#(N,a
#(N,N
#(N
#(N)
#N
(
a
,
,
a
)
)
)
#
#
a,a)#...
,a)#...
a)#...
a)#...
)#...
#...
#...
#...

Move in
Move in
Reduce: S→a
Move in
Move in
Reduce: S→a
Reduce: T→T,S
Move in
Reduce: S→(T)
Success!
对输入串（a,(a,a)）# 的算符优先分析过程为：
栈（STACK）
当前字符（CHAR）
剩余输入串
（INPUT_STRING）
动作（ACTION）
#
#(
#(a
#(N
#(N,
#(N,(
#(N,(a
#(N,(N
#(N,(N
#(N,(N,a
#(N,(N,N
#(N,(N
#(N,(N)
#(N,N
#(N
#(N)
#N
(
a
,
,
(
a
,
,
a
)
)
)
)
)
)
#
#
a,(a,a))#...
,(a,a))#...
(a,a))#...
(a,a))#...
a,a))#...
,a))#...
a))#...
a))#...
))#...
)#...
)#...
)#...
#...
#...
#...

Move in
Move in
Reduce: S→a
Move in
Move in
Move in
Reduce: S→a
Move in
Move in
Reduce: S→a
Reduce: T→T,S
Move in
Reduce: S→(T)
Reduce: T→T,S
Move in
Reduce: S→(T)
Success!

问答第2题
　　文法：
　　S→a|∧|(T)
　　T→T,S|S
　　对(a,a）和（a,(a,a)）的最右推导：
　　(a,a）的最右推导过程为：
　　S(T)
　 　(T,S)
　 　(T,a)
　 　(S,a)
　 　(a,a)
　　（a,(a,a)）的最右推导过程为:
　　S(T)
　 　(T,S)
　 　(T,(T))
　 　(T,(T,S))
　　 (T,(T,a))
　　 (T,(S,a))
　 　(T,(a,a))
　 　(S,(a,a))
　 　(a,(a,a))
　　对输入串(a,a）# 的规范归约过程为：
栈（stack）
剩余输入串
（input left）
动作（action）
#
#(
#( a
#( S
#( T
#( T,
#( T,a
#( T,S
#( T
#(T)
#S
(a,a)#...
a,a)#...
,a)#...
,a)#...
,a)#...
a)#...
)#...
)#...
)#...
#...
#...
Shift
Shift
Reduce by :S →a
Reduce by :T→S
Shift
Shift
Reduce by :S →a
Reduce by :T →T,S
Shift
Reduce by :S →(T)
Success!
(4) 对输入串（a,(a,a)）# 的规范归约过程为：
栈（stack）
剩余输入串
（input left）
动作（action）
#
#(
#( a
#( S
#( T
#( T,
#( T,(
#( T,(a
#( T,(S
#( T,(T
#( T,(T,
#( T,(T,a
#( T,(T,S
#( T,(T
#( T,(T)
#( T,(S
#( T
#( T)
#S
(a,(a,a))#...
a,(a,a))#...
,(a,a))#...
,(a,a))#...
,(a,a))#...
(a,a))#...
a,a))#...
,a))#...
,a))#...
,a))#...
a))#...
))#...
))#...
))#...
)#...
)#...
)#...
#...
#...
Shift
Shift
Reduce by :S →a
Reduce by :T→S
Shift
Shift
Shift
Reduce by :S →a
Reduce by :T →S
Shift
Shift
Reduce by :S →a
Reduce by :T →TS
Shift
Reduce by :S →(T)
Reduce by :T →T,S
Shift
Reduce by :S →(T)
Success!