第3章 语 法 分 析
本章阐述编译器常用的语法分析方法，首先介绍描述语法结构的上下文无关文法的相关概念，然后介绍自上而下的语法分析方法，接下来介绍自下而上的语法分析方法，最后介绍语法分析器的自动生成工具YACC
软件。
3.1 上下文无关文法
要进行语法分析，必须对语言的语法结构进行描述。采用正规文法可以描述和识别语言的单词符号，而采用上下文无关文法则可以用来描述语法规则。
3.1.1 上下文无关文法的定义
在第2章用正规文法定义了一些简单的语言，比如C语言标识符组成的语言和无符号整数组成的语言，但是有很多相对复杂的语言是不能用正规文法来定义的，比如，由配对括号构成的串所组成的集合就不能用正规文法来描述。为了定义比正规文法描述能力更强的文法，这里介绍上下文无关文法。
定义3.1 （上下文无关文法） 一个上下文无关文法是一个四元式G=(VT，VN，P，S)，其中：
1）VT为终结符组成的非空有限集。
2）VN为非终结符组成的非空有限集，VN和VT不含公共的元素，即VN ∩ VT = ?。
3）P为产生式组成的集合，每个产生式形如A→α，A∈VN，α∈ (VT ?∪? VN)*。
4）S称为文法的开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。
之所以称之为上下文无关文法，是因为其所定义的语法范畴（语法单元）是完全独立于这种范畴可能出现的环境的。由正规文法和上下文无关文法的定义可知，正规文法是一类特殊的上下文无关文法。以后如果不做特殊说明，我们所指的文法就是上下文无关文法。
例3.1 只含+、的简单算术表达式的文法可定义为G= （{i，+，，(，)}，{E}，E，P），其中，P由下列产生式组成：
E→i
E→E+E
E→E*E
E→(E)
同样可以只用开始符号和产生式来表示上下文无关文法，因此该文法还可表示为：
G(E)：E→i | E+E | E*E | (E)(3.1)
3.1.2 语法树和推导
为了描述文法所定义的语言，需要使用推导的概念，所谓的推导就是把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替，其定义如下。
定义3.2 （直接推导和推导） 称αAβ直接推出αγβ当且仅当A→γ是一个产生式，且α、β∈(VT?∪?VN)* ，记作αAβ?αγβ。如果α1?α2?…?αn，则称这个序列是从α1到αn的一个推导。若存在一个从α1到αn的推导，则称α1可以推导出αn。
通常，用α1?+αn表示从α1出发，经过一步或若干步，可以推出αn。用α1?αn表示：从α1出发，经过0步或若干步，可以推出αn。所以，α?β即α=β或α?+β。
定义3.3 （文法的句型、句子、语言和上下文无关语言） 假定G是一个文法，S是它的开始符号。如果S?*α，则称α是该文法的一个句型。仅含终结符号的句型称为句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。上下文无关文法所产生的语言称为上下文无关语言。
在以后的使用中，将对上下文无关文法G=(VT，VN，P，S)做如下限制：
1）不能含有形为A→A的产生式。它对描述语言显然是没有必要的，其只会引起文法的二义性。
2）每个非终结符A必须有用处，也即必须满足如下两个条件：
① A必须在某句型中出现。即有S?αAβ，其中α、β属于(VT?∪?VN) 。
② 必须能够从A推出终结符号串w来。即A?w，其中w∈VT。
例3.2 证明(i*i+i)是式（3.1）文法的一个句子。
证明： 因为E ? (E) ? (E+E)? (EE+E) ? (iE+E)? (ii+E) ? (ii+i)
是从E到(ii+i)的一个推导。并且(ii+i)是只有终结符组成的字符串。所以，(i*i+i)是文法G(E)的一个句子。
例3.3 对于文法G(S)，它有如下产生式：
S→(S) S | ε
试证明该文法所产生的语言L(G) ={配对的括号串}
证明：首先按推导步数进行归纳证明S所产生的每个句子都是配对的括号串。
归纳基础：S ? ε。S经过一步推导能推导出来的终结符串只有空串，它是配对的。
归纳假设：少于n步的推导都产生配对的括号串。
归纳步骤：n步的一个推导如下。
S ? (S)S ? (x) S ? (x) y
因为从S到x和y的推导都少于n步，所以由归纳假设，可得x和y都是配对的括号串，从而(x) y也是配对的括号串。
然后按串长进行归纳证明任何配对的括号串都可由S产生。
归纳基础：由S ? ε可知，空串可以从S推导出。
归纳假设：长度小于2n的配对括号串都可以从S推导出来。
归纳步骤：考虑长度为2n(n≥1)的括号串w = (x) y，其中x和y都是配对括号串，其长度都小于2n。由归纳假设可知，它们都可以从S推导出来，所以有如下推导
S ? (S)S ? (x) S ? (x) y
从而w = (x) y也可以从S推导出。
例3.4 对于文法G(S)，它有两个产生式：
S→aSb
S→ab
试证明该文法所产生的语言L(G)={anbn∣n≥1}。
证明：考虑从S开始进行推导，若先用G中第二个产生式，则S?ab，就不能再往下推导了，此时相当于语言中n=1的情况。
若从S出发，先用n-1次第一个产生式，即S ? aSb ? aaSbb ? … ? an-1S bn-1，最后再使用第二个产生式一次，得到S ?*anbn，其中n＞1。
再加上n=1的情况，即可得到L(G)={an bn∣n≥1}。
例3.5 构造一个文法，使其能产生语言L={wwR∣w∈{a，b}+ }，其中wR是w的逆转。
解：wwR是由偶数个a、b组成且由中心开始左右对称的串，处于wwR中间的两个符号一定是同样的，不是aa就是bb，我们先用产生式来产生它们，然后再向左右两边扩充。由于要保持对称性，因此扩充的左右两边符号一定要相同（a或者b）。基于以上考虑，可以写出下面一组产生式。
1）S→aa
2）S→bb
3）S→aSa
4）S→bSb
下面证明由上面4个产生式组成的文法能够产生语言L。
如果要产生长度为2的句子，只用前两个产生式就行了。如果要产生所有长度为4的句子，则用后两个式子各一次，然后中间的S用前两个式子分别代入即可。也就是用以下的
推导：
S ? aSa ? aaaa，S ? aSa ? abba，
S ? bSb ? baab，S ? bsb ? bbbb。
一般地，设S已能推导出一切长度为2m（m≥2）的串，我们就可以从S推导出一切长度为2（m+1）的串。办法是用后两个产生式中的一个，在原来长度为2m的串上，左右两边都加上a（或b），就可以得到长度为2（m+1）的串。
例3.6 构造能产生全部十进制整数（每个整数前可有若干个0）的文法。
解：首先要有产生式能产生单个的十进制数字，然后再用递归的方法产生任意多位的十进制数。于是我们有文法G1(N)。
D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9
N→D∣DN
还可以有如下的另一个文法G2(N)：
N→0∣1∣2∣3∣4∣5∣6∣7∣8∣9
N→0N∣1N∣2N∣3N∣4N∣5N∣6N∣7N∣8N∣9N
G2(N)同样能产生全部十进制整数。可以看出，G2相当于在G1中将第一组产生式中D的各右部“代入”第二组产生式中而获得，它比G1少了一个变元D，但是产生式的个数由原来的12个扩充为20个。
定义3.4（文法的等价性） 对于两个不同的文法G1=(VT1，VN1，P1，S1），G2=(VT2，VN2，P2，S2)，如果L(G1)=L(G2)，则称文法G1与G2等价。
同一个语言可以由不同的文法产生。在例3.6中已经看到，一个很简单的十进制整数（每个整数前可有若干个0）所组成的语言就可由两个不同的文法产生。文法是用四元组定义的，在两个四元组的各对应部分中，只要有一点点的不同就应当看作不同的文法。如在一个已有的文法上随意加上一些变元、一些终结符，或一些不影响S推导结果的产生式等，都会变成新的文法。在这个意义下，任何一个语言都可以有无穷多个文法产生它。
从一个句型到另一个句型的推导往往不唯一。例如，对于式（3.1）文法，关于i+i就存在如下两个不同的推导：
E?E+E?i+E?i+i E?E+E?E+i?i+i
为了对句子结构进行确定性分析，我们往往只考虑最左推导或最右推导。
定义3.5（最左推导和最右推导） 所谓的最左推导是指任何一步α ? β都是对α中的最左非终结符进行替换。所谓的最右推导是指任何一步α ? β都是对α中的最右非终结符进行替换。最右推导又称为规范推导，由规范推导所得到的句型称为规范句型。
例3.7 式（3.1）文法关于i*i+i的最左推导为
E ?E+E?E*E+E
?iE+E?ii+E?i*i+i
最右推导为
E ?E+E?E+i
?EE+i?Ei+i?i*i+i
可以使用图形来表示推导，这种表示称为语法分析树，或简称语法树，其能更清楚、直观地表示句型或者句子的语法结构。
定义3.6（语法分析树） 给定上下文无关文法G=(VT，VN，P，S)，满足下列要求的一棵树称为关于G的语法分析树：
1）树的每个结点带有一个标记，它是VT?∪?VN?∪?{ε}中的一个符号。
2）根结点的标记是S。
3）树的内部结点（非叶结点）只能以VN中的符号作为标记。
4）如果结点n带有标记A，结点n1，n2，…，nk 是结点n从左到右的儿子结点，并分别带有标记X1，X2，…，Xk、则A→X1X2…Xk必须是P中的一个产生式。
5）如果结点带有标记ε，则该结点是它父结点的唯一的儿子结点。
可以采用如下方法为文法的某一个句型构造语法分析树：
1）开始符号作为根结点。
2）如果非终结符被它的某个候选式所代替，则产生下一代新结点，并且候选式中自左向右每一个符号对应一个新结点，并用这些符号标记相应的新结点。
3）每个新结点与其父结点之间都有一条连线。
例3.8 式（3.1）文法关于句子i*i+i的语法分析树的生成过程如图3-1所示。
定义3.7（短语、直接短语和句柄） 对于一个给定的文法G(S)，假定αβδ是它的一个句型，如果有
S?*αAδ且A?+β
则称β是句型αβδ相对于非终结符A的短语。特别是，如果有
A?β
则称β是句型αβδ相对于产生式A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。
直观理解：短语就是某句型中的一个子串，这个子串是由某个非终结符通过至少一步推导得到，而直接短语是由某个非终结符通过一步推导得到的子串。基于上述理解，在一个句型对应的语法树中，以某非终结符为根的两代和两代以上的子树的所有末端结点从左到右排列所得到的子串，就是相对于该非终结符的一个短语；如果子树只有两代，则该短语就是直接短语。
例3.9 考虑文法G(E)：
（1）E→E+T
（2）E→T
（3）T→T*F
（4）T→F
（5）F→(E)
（6）F→i（3.2）
和句型i1*i2+i3。因为
E ? E+T ? E+F ? E+i3 ? T+i3
? TF+i3 ? Ti2+i3 ? F*i2+i3
? i1*i2+i3
所以i1、i2、i3、i1i2和i1i2+i3是句型i1*i2+i3的所有短语，并且i1、i2和i3是直接短语，i1是句柄。
3.1.3 二义性
一棵语法分析树表示了一个句型的多种可能推导，包括最左推导和最右推导，如果坚持使用最左（最右）推导，那么，一棵语法分析树就完全等价于一个最左（最右）推导，这种等价包括树的步步成长和推导的步步展开之间的完全一致性。但是并不是每一个句型只对应一棵语法分析树，也就是说并不是每一个句型只有一个最左推导或者最右推导。
定义3.8 （文法的二义性） 如果一个文法存在某个句子对应两棵不同的语法分析树，也即两个不同的最左（右）推导，则称这个文法是二义的。
例3.10 证明式（3.1）文法是二义文法。
证明：在例3.2中已经证明(ii+i)是式（3.1）文法的一个句子。又因为式（3.1）文法关于(ii+i)存在如下两个不同的最左推导。
E?(E)?(E+E)?(EE+E)?(iE+E)?(ii+E)?(ii+i)
E?(E)?(EE)?(iE)?(iE+E)?(ii+E)?(i*i+i)
所以式（3.1）文法是二义文法。
一个文法是二义性的，并不能说明该文法所描述的语言也是二义性的。也即，对于一个二义性文法G(S)，如果能找到一个非二义性文法G'(S)，使得L(G')=L(G)，则该二义性文法的二义性是可以消除的。如果找不到这样的G'(S)，则该二义性文法所描述的语言为先天二义性。
定义3.9（语言二义性） 一个语言是二义性的，如果不存在产生该语言的无二义性文法。
例3.11 {aibicj | i, j≥1}?∪?{aibjcj | i, j≥1}就是一个二义性语言，对于n≥1，anbncn都是二义性句子。
已经证明二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的，但通常可以找到一组充分条件能够将一个二义文法等价地转化为无二义文法。
例3.12 消除式（3.1）文法的二义性。
解：造成式（3.1）文法二义性的原因是该文法中没有体现出运算符的结合律和优先级。要想体现做了乘、除运算之后才能做加、减运算，就必须将乘、除运算表示成另一种较高层次的语法单元，只有这个成分才有资格参加加、减运算。为此引入下面相关概念。
1）因子：因子是运算的最基本单位，通常包含常数、标识符、加括号的表达式等，用F表示。
2）项：一个因子是一个项，一个项乘以一个因子也是一个项，用T表示。
3）表达式：一个项是一个表达式，一个表达式加上一个项也是一个表达式，用E表示。
将上述内容用产生式的形式表示出来，就得到如式（3.2）文法所示的无二义文法。对于式（3.2）文法的句子（i*i+i），则有如下唯一的最左推导：
E ?T?F?(E)
?(E+T)?(T+T)
?(TF+T)?(FF+T)
?(iF+T)?(ii+T)
?(ii+F)?(ii+i)
例3.13 已知有如下文法G(stmt)：
stmt→ if expr then stmt
| if expr then stmt else stmt
| other（3.3）
这里的other代表任何其他的语句。因为存在句子if expr then if expr then stmt else stmt 有两个不同的最左推导：
stmt ? if expr then stmt
? if expr then if expr then stmt else stmt
stmt ? if expr then stmt else stmt
? if expr then if expr then stmt else stmt
所以这是一个二义性文法。为了避免二义性，在所有允许这两种形式条件语句的程序设计语言中，都规定“else 必须匹配离它最近的那个未匹配的then”。根据这个原则，出现在then和else之间的语句必须是配对的，而所谓的配对语句是指那些不是条件语句的语句，还有那些只含配对语句的if-then-else语句。基于此，式（3.3）文法可改写为如下无二义文法：
stmt→matched_stmt | unmatched_stmt
matched_stmt→ if expr then matched_stmt else matched_stmt
| other
unmatched_stmt→ if expr then matched_stmt else unmatched_stmt
| if expr then stmt