上下文无关文法.doc

语言与计算理论导引 上下文无关文法
第三部分 上下文无关语言和下推自动机
前面介绍的有限自动机是计算的初级模型，它所接受的正规语言不太关心字符串自身的结构。上下文无关文法（CFL）是一种简单的描述语法规则的递归方法，语言中的字符串由这些规则产生。所有的正规语言都能用上下文无关文法描述，它也可以描述非正规语言。上下文无关文法描述的语法规则更复杂多变，可以在相当大的程度上，描述高级程序设计语言的语法和其他一些形式语言。
类似正则语言对应的抽象机模型是有限自动机，CFL也有对应的抽象机模型。CFL对应的计算模型是在有限自动机的基础上增加存储空间得到，并被设想成无限空间（对应有限自动机的有限空间），采用了一种简单的管理模式，栈（stack），这种新的计算模型（或抽象机）称为下推自动机（pushdown automata），下推是栈最典型的操作。有必要在下推自动机中保留非确定性，确定型下推自动机不能接受所有的CFL，但给定一个CFG，容易构造一个相应的非确定型下推自动机，它在识别字符串过程中的移动模拟了文法的推导过程，这个过程称为分析（parse）。分析不是一定需要下推自动机来完成。
CFL仍然不够通用，不能包括所有有意义的、或有用的形式语言。采用类似第五章的技术，我们将给出一些不是CFL的简单例子，这些技术也用于解决与CFL相关的判定问题。

1
陶晓鹏 Copyright 2003

语言与计算理论导引 上下文无关文法
6 上下文无关文法
6.1 上下文无关文法的定义
为了描述我们在第二部分考察的各种语言，包括一些非正则语言，我们引入一种语言的递归定义方法，称为文法。文法与我们熟悉的语言的语法描述相近，是描述语言和分析语言的有力工具。

问题：文法的形式化定义似乎可以模仿有限自动机，比如5元组或6元组之类。

例子6.1 正如我们在例子2.16中所见，字母表{a, b}上的回文语言pal可以用下面的递归方法描述：
1. L, a, bÎpal
2. 对每个SÎpal，aSa和bSb也属于pal
3. pal中不包含其他字符串

如果将上面的符号S看成一个变量，代表了所有我们希望计算（比如某种递归算法）的pal的元素，那么上面的规则1和规则2可以非正式地重新表述如下：
1. S的值可以是L, a, b
2. 每个S可以写成aSa或bSb的形式

如果我们用®表示“可以取值为”，则可以写出下面的式子：
S®aSa®abSba®abLba=abba
上面的产生过程可以总结成下面的两组产生式（或称规则）：
S®a | b | L
S®aSa | bSb
符号“|”表示“或”的含义。上式的含义是aSa或bSb，而不是a或b，即连接运算的优先级高于“|”。我们使用的这套术语中，小写字母a和b表示终结符，大写字母S表示非终结符，或称变量。总共有5条规则，或产生式（production）。符号S是非终结符，也是起始终结符，即我们生成字符串的起始符号是S，然后不断利用规则替换符号串中的非终结符，直到最终得到一个不含非终结符的符号串，就生成了规则所定义的语言的一个字符串。

例子2中的产生式具有除起始符S外的多个非终结符，我们设想S表示了语言中任意的字符串，其他非终结符表示了其他辅助性的字符串类型，他们可用来方便地生成S表示的字符串。

例子6.2 我们要构造一个生成所有在字母表{a, b}上的非回文字符串的文法，那样的字符串可以描述如下：从字符串的两端开始比较，也许能够发现一些相同的字符对，但最终能够发现一对不同的字符。对于前一种情况，我们可以借用回文语言的产生式：
S®aSa | bSb
如果加入产生式
S®a | b | L
则这种左右匹配的形式将体现在整个字符串上，为了中断这种左右匹配的情况，即体现上面提到的第二种情况，我们引入新的非终结符，比如D，表示那些左右两个端点上的字符不同的字符串。且所有符合D的字符串也符合S，因此有S®D。
非终结符的定义比较简单，它唯一的条件是左右两个端点的字符不相同，中间的字符串可以是任意的，我们用非终结符A表示任意的字符串，则有D®aAb | bAa。
A表示任意的字符串，因此A的产生式更简单了，不用添加新的非终结符来简化问题，它的产生式是，A®L | aA | bA。
我们把上面三个非终结符的产生式写在一起，就得到了描述所规定语言的产生式集：
S®aSa | bSb | D
D®aAb | bAa
A®L | aA | bA

因此一个完整的非回文字符串“abbaaba”的产生过程是，
S®aSa®abSba®abDba®abbAaba®abbaAaba®abbaLaba®abbaaba

定义6.1 上下文无关文法（context-free grammar, CFG）是一个4元组G=(V, å, S, P)，其中，V和å是不相交的有限集，SÎV，P是一组有限的产生式规则，形如A®a，其中AÎV，且aÎ(VÈå)*。
V的元素称为非终结符（或变量），å的元素称为终结符，S是一个特殊的非终结符，称为起始符，P的元素称为语法规则，或产生式。

设G=(V, å, S, P)是一个CFG，我们将符号®保留给P的产生式专用，符号ÞG用于表示字符串的产生过程的每一步，如aÞGb表示字符串b能够通过替换a中的某些变量（根据P定义的产生式来替换）得到，即如果有
a=a1Aa2且A®gÎP，则b=a1ga2。
这里能够看到，我们命名为上下文无关（context-free）的含义，即我们在利用产生式规则，用一组符号替换某个非终结符时，与非终结符的上下文无关（此处，A的替换与a1和a2无关），替换是无限制的。
在没有多个文法出现，很清楚用到文法G是什么的情况下，推导符号ÞG可以简写成Þ。多步的推导可以写成Þ*G，即如果存在一组符号串，a=a0、a1、…、ak=b，每个后者都是前者的直接推导，则称为a可以多步推导出b，记为aÞ*Gb，简写成aÞ*b。

定义6.2 G=(V, å, S, P)是一个CFG，则G产生的语言是所有可由G产生的字符串组成的集合，即L(G)={xÎå* | SÞ*Gx}。一个语言L是上下文无关语言（context-free language, CFL），当且仅当存在一个CFG G，使得L=L(G)。

此处可以把文法设想成类似自动机的抽象模型，则一个语言L是CFL当且仅当存在一个CFG G接受它（或识别它），类似前面正则语言与有限自动机的关系，接受（或识别）的含义是两方面的，一方面凡是L中的字符串都能由G产生，另一方面，凡是不属于L的字符串都不能由G产生。前面的例子，能够比较容易地说明这两方面的限制，下面的例子则不是很明显。

例子6.3 考虑语言L={xÎ{0, 1}* | n0(x)=n1(x)}，其中ni(x)表示数字i在x中的出现次数（即含有相同数目0和1的语言）。写出生成L的CFG。
分析：既然CFG的本质是一个递归定义，那么类似例子6.1，我们可以先发现归纳基础，然后找到归纳推理。显然LÎL，另外如果存在一个字符串xÎL，那么得到更长的属于L的字符串的两个方法是，0x1和1x0，即分别在两端添加相同数量的0和1。（当然，还有很多生成方法，比如x01，x10，或在x中插入相同数量的0和1），这样得到三个产生式：
S®L | 0S1 | 1S0
显然，还遗漏了一些字符串，如0110。我们注意到L中任意两个元素的连接仍然属于L，因此可以增加一个产生式，S®SS。与前面的三个产生式合并，我们得到一个CFG G如下，
S®L | 0S1 | 1S0 | SS
显然G产生的字符串都满足0和1数目相等这个条件，即L(G)ÍL，现在只要证明LÍL(G)。
令d(x)=n0(x)-n1(x)。则字符串xÎL，当且仅当d(x)=0。因此只需证明每个满足d(x)=0的x，都有xÎL(G)。我们用数学归纳法来证明LÍL(G)。归纳对象是字符串的长度|x|。
1. 归纳基础，|x|=0且d(x)=0，则xÎL(G)，这是显然的，因为此时x=L，而L可以由产生式S®L得到。
2. 归纳推理，设k>=0，每个满足|y|<=k，d(y)=0的字符串y都属于L(G)。要证明每个长度等于k+1且d(x)=0的字符串x也属于L(G)。分情况讨论如下：
a) 如果x以0开始，以1结尾，则可以写成x=0y1，且d(y)=0，根据归纳假设yÎL(G)，即存在一组推导，SÞ*Gy。因此对于x，存在推导，SÞ0S1Þ*0y1Þx。
b) 如果x以1开始，以0结尾，类似a)的处理，能够得到从S到x的推导。
c) 如果x以0开始，且以0结尾。则x的长度至少为2，设x=0y0。现在考察x的所有前缀z的d(z)，其中
d(0)=1，d(0y)=d(0y0)-d(0)=-1，
而d(z)随着z的长度增1，至多增加1或减少1，而当前缀从0变化到0y时，d(z)从1变化到-1，因此存在某个长于0短于0y的前缀z，使得d(z)=0，则x=zw，显然d(w)=0，由于z、w的长度都<=k，因此z、w都属于L(G)，分别存在从S出发到z和w的推导。为了得到从S出发到x的推导，首先用产生式S®SS。
d) 如果x以1开始，且以1结尾，类似c)的处理。

例子6.4 考查语言L={xÎ{0, 1}* | n0(x)¹n1(x)}，写出它的CFG。
分析：例子6.3看起来与本例关系很大，但实际上没有什么帮助，我们在第8章，将详细解释为什么一个语言的CFG并不能帮助发现它的补集语言的CFG。
L中的字符串可以分为两大类，一类含有的0的个数多于1，另一类含有1的个数多于0，前者组成集合L0，后者组成L1。如果能够发现L0和L1的CFG，由于L= L0ÈL1，就能够很容易找到L的CFG。
类似以前的做法，我们尽力找到语言L0的递归特征。显然0ÎL0，且如果xÎL0，则0x和x0也属于L0，由此得到三个产生式：
S®0 | S0 | 0S
我们无法保证L0中的字符串连接1仍然属于L0，但是如果两个L0中的字符串连接后再连接一个1能够保证新字符串仍然属于L0，因此得到另外三个产生式：
S®1SS | SS1 | S1S
合并这两组产生式就得到了生成L0的CFG G0如下，
S®0 | S0 | 0S | 1SS | SS1 | S1S
类似前面，我们只要证明L0ÍL(G0)。令d(x)=n0(x)-n1(x)，要证明凡是d(x)>0的x都能由G0产生，对x的长度应用数学归纳法。
1. 归纳基础，显然|x|=1且d(x)>0时，即x=0，x可由S®0推导，属于L(G0)。
2. 归纳推理，设k>=0，对每个|x|<=k且d(x)>0的x都属于L(G0)，要证明每个|x|<=k且d(x)>0的x也属于L(G0)。分情况讨论，此处仅讨论x=0y0的情况（即以0开始和结尾的情况），
a) x仅由0组成，易证。
b) x至少含有一个1。则x=w1z，现在证明d(w)>0且d(z)>0。设x含有n个1，n>=1，对每个1=<i<=n，令wi是x的前缀，紧接wi的下一个字符就是第i个1，则x=wi1zi。分两种情况1）不存在wi，使得d(wi)<=0，即所有的d(wi)>0，则d(wn)>0，令w=wn，z=zn，显然d(z)>0，得证；2）存在一个wi，使得d(wi)<=0，设i=m是第一个d(wi)<0的前缀，由于x以0开始，一定有d(w1)>0，且d(wm-1)=1>0，令w=wm-1，z=zm-1，易证d(zm-1)>0，因此得证。
其他两种情况，x以1开始，以1结尾证明略。

类似方法能够得到生成L1的产生式，我们用A表示生成L0的产生式，B表示生成L1的产生式，那么生成语言L的全部文法是：
S®A | B
A®0 | 0A | 1AA | AA1 | A1A
B®1 | 1B | 0BB | BB0 | B0B
注意其中的第一个规则，它恰如其分地表示了合集的含义。

6.2 更多地例子，包括一些熟悉的语言
例子6.5 我们前面已经提到了在计算机科学和其他领域应用很广泛的书写代数表达式的语言。一般地，我们允许任意的标识符和数字常数出现在表达式中，为了简化问题，我们规定只有一个标识符（字母a）、4种两项运算符（+、-、*、/）和左括号、右括号。我们用变量A表示这个简单的表达式语言。它可以嵌入到复杂的表达式语言中。
一个容易发现的递归现象是，如果存在两个表达式，那么可以利用运算符和括号，连接它们构成新的表达式。显然，除了单个标识符a，其他表达式都是通过这个递归过程构造的，因此我们得到下面的文法：
S®S+S | S-S | S*S | S/S | (S) | a
表达式a+(a*a)/a-a的推导过程如下，
SÞS-SÞS+S-SÞa+S-SÞa+S/S-SÞa+(S)/S-SÞa+(S*S)/S-SÞa+(a*S)/S-SÞ...Þa+(a*a)/a-a
还存在其他一些推导过程，如
SÞS/SÞS+S/SÞa+S/SÞa+(S)/SÞa+(S*S)/SÞa+(a*S)/SÞa+(a*a)/SÞa+(a*a)/S-SÞa+(a*a)/a-SÞa+(a*a)/a-a
显然，第一种推导比第二种更自然，它符合了通常的运算符的优先级和计算次序。比如，上述表达式通常的计算次序如下：
1. 计算a*a，记为A
2. 计算A/a，记为B
3. 计算a+B，记为C
4. 计算C-a

尽管第二种推导不符合通常的表达式结构，或表达式语义，但整个推导是符合文法规定的，是一个合法的推导。一个可能的结论是本例给出的CFG不是最合理的，它没有体现出运算符和括号的优先级，另外好的CFG对每个字符串仅仅提供一种推导过程（如果忽略次序不同的一些简单替换），在6.4节我们将回到这个问题，它称为CFG的歧义。

例子6.6 上面的例子类似例子3.5和3.6，仅仅描述了程序设计语言（比如C和Pascal）的某个部分，本例将显示，CFG可用来描述程序设计语言的整个语法结构。
C语言有两大类语法结构，<statement>和<expression>。<statement>包括条件声明（<if-statement>）和循环声明（<for-statement>）等等，因此有，
<statement>®... | <if-statement> | <for-statement> | ...
<if-statement>®if (<expression>) <statement>
<for-statement>®for (<expression>; <expression>; <expression>) <statement>
...
可以类似构造多个声明连接而成的复合声明，以及<while-statement>等等。

例子6.7 高级程序设计语言的一个大的优点是写出的程序与英文陈述很接近，既然我们可以用CFG去描述高级程序设计语言，那么可不可以用来描述英语呢？
对于一些简单的英语语法，容易找到它的CFG，比如最基本、最典型的英语陈述句的结构是，<subject> <verb> <object>，因此可以构造出如下的产生式，
<declarative sentence>®<subject> <verb> <object>
可以进一步构造生成右部三个非终结符的产生式。写出一套合理的、具有广泛性、符合常用语法习惯的英语规则并不困难，且规则的数目也可以不是很多。困难的地方是防止产生不合语法，或合乎语法，然而不合语义，没有人会使用的英语句子。下面的产生式就是一个例子，
<declarative sentence>®<subject> <verb> <object>
<subject>®<proper noun>
<proper noun>®John | Jane
<verb>®reminded
<object>®<proper noun> | <reflexive pronoun>
<reflexive pronoun>®himself | herself

上面文法能够产生很多不“正确”的英语句子，如“John reminded herself”，“Jane reminded himself”。可以通过增加文法的复杂性（更多的非终结符和更多的产生式）来消除这种不正确的推导，比如修改产生式为，
<declarative sentence>®<masculine noun> <verb> <masculine reflexive pronoun>
而对于例如“Jane reminded Jane”还需要其他消除方法，因为句子“Jane reminded John”是一个好的英语句子。要想区别这两个句子，需要上下文信息，因此本章讨论的CFG无法很深入、精细地刻画自然语言的一些细微特征。

6.3 CFL的合并、连接和Kleene*运算
例子6.4我们构造了一个CFG，它生成的语言是另外两种语言的合集，而且找到了另外两种语言对应的CFG。例子6.4揭示的方法和处理连接和Kleene*运算的相应方法构成了下面定理的基础。

定理6.1 L1和L2是两个CFL，则语言L1ÈL2、L1L2和L1*也是CFL。
证明：我们用构造法证明。假设生成L1和L2的文法分别是G1=(V1, å, S1, P1)和G2=(V2, å, S2, P2)，以此为基础，分别构造生成上面三种新语言的CFG。
首先假设V1ÇV2=f（否则可以通过改名来到达目的），设生成L1ÈL2的文法Gu=(Vu, å, Su, Pu)，其中，Su是不属于V1和V2的新增非终结符，Vu=V1ÈV2È{Su}，Pu=P1ÈP2È{Su®S1 | S2}。
现在证明L(Gu)=L1ÈL2。一方面，任取xÎL1=L(G1)，则S1Þ*x，又由于存在产生式SuÞS1，因此SuÞ*x。类似地，任取xÎL1，也有SÞ*x。因此L1ÈL2ÍL(Gu)。另一方面，任取xÎL(Gu)，则存在SÞ*x，则存在S1Þ*x或S2Þ*x，因此L(Gu)ÍL1ÈL2。得证。
类似处理连接运算，文法Gc=(Vc, å, Sc, Pc)，其中Sc是不属于V1和V2的新增非终结符。定义Vc=V1ÈV2È{Sc}，Pc=P1ÈP2È{Sc®S1S2}。任给xÎL1L2，则x=x1x2，x1ÎL1，x2ÎL2。因此有SÞS1S2Þ*x1S2Þ*x1x2=x，即L1L2ÍL(Gc)。任给xÎL(Gc)，即SÞ*x，则有S1S2Þ*x，由于V1和V2不相交，则存在x1x2=x，满足S1Þ*x1，S2Þ*x2，因此L(Gc)ÍL1L2。
文法G*=(V, å, S, P)生成语言L1*，其中，S是不属于V的新增非终结符。语言L1*所含字符串x的形式是x=x1x2...xk，其中每个xiÎL1，如果能够S连续地产生k个S1，则S能够推导出x，因此得到下面的产生式，S®S1S | L，而P=P1È{S®S1S | L}。显然，L1*ÍL(G1*)。任给xÎL(G1*)，则存在SÞ*x，而S推导的第一步一定是SÞS1k，因此xÎL(G1)kÍL(G1)*。得证。

下面的例子说明了证明的第一步消除V1和V2中的同名是很重要的。比如有两个CFG如下：
S1®XA, X®c, A®a
S2®XB, X®d, B®b
此处非终结符X出现在两个文法中，如果不改名将带来混乱。如SÞS1ÞXAÞdAÞda，而事实上S1无法推导出da。

推论6.1 每个正则语言都是CFL。
证明：根据正则语言的递归定义（定义3.1），每个正则语言是以三种简单的字符（f、{L}、{a}）为基础，多次施加三种运算（合并、连接、Kleeen*）得到。显然三种简单的字符组成的语言是CFL，又根据定理6.1，三种运算保持了CFL的性质，因此根据结构归纳法，命题得证。

例子6.8 语言L是正则表达式，(011+1)*(01)*，表示的正则语言，写出它对应的CFG。
分析：定理6.1的证明过程给出了发现一个CFL的CFG的方法。分别考虑(011+1)*和(01)*。而(011+1)*可进一步转化成考虑(011+1)，得到A®011 | 1，然后加上Kleene*运算，得到，
B®AB | L
类似地，对应正则表达式(01)*的产生式是，
C®DC | L, D®01
最后应用连接运算，得到语言L对应的CFG是
S®BC
B®AB | L
A®011 | 1
C®DC | L
D®01
最后引入的符号S是非终结符，构造过程中引入的符号是辅助非终结符。

例子6.9 语言L={0i1j0k | j>i+k}的CFG。
分析：一个直观的观察是L的每个字符串都是三部分连接而成的：0i、1j、0k。因此似乎可以分别构造三部分语言的CFG，然后通过连接运算构造整个语言的CFG。这种方法是错误的，因为本例语言的三部分是相互关联的，而不是相互独立的，定理6.1揭示的方法仅仅用在相互独立的两个CFG之间的运算。
可行的方法是，将本例中具有关系的参数i、j、k转换成相互无关的参数。由于j>i+k，不妨令j=i+k+m，m>0。则0i1j0k=0i1i1m1k0k。此处的三个参数i、m、k相互独立，因此语言L=L1L2L3，其中，
L1={0i1i | i>=0}
L2={1m | m>0}
L3={1k0k | k>=0}
先分别构造语言L1、L2、L3的CFG，然后利用连接运算构造L的CFG。L1和L3类似，L2易于构造。发现L1的递归性质，LÎL1，对每个xÎL1，都有0x1ÎL1。因此得到L1的CFG，A®0A1 | L。类似地，L3的CFG是C®1C0 | L。L2的CFG是B®1B | 1（注意，不是B®L，因为L2的字符串长度至少为1）。
因此连接三部分，得到最终的CFG G=(V, å, S, P)，其中，V={S, A, B, C}，å={0, 1}，P={S®ABC, A®0A1 | L, B®1B | 1, C®1C0 | L}。
字符串01402=(01)(1)(1202)的推导过程如下，
SÞABCÞ0A1BCÞ0L1BCÞ011CÞ0111C0Þ01111C00Þ01111L00Þ0111100

6.4 推导树和歧义
对于一个自然语言，比如英语，理解它的句子从理解它的语法结构开始，即了解句子是怎样根据语言的句法规则产生的。给定一个CFG和一个它所生成的字符串x，知道了x的推导过程有助于正确理解x的含义。一个展示推导过程（或推导结构）的自然的方法是画出推导树或分析树。树的根部是文法的起始非终结符，它是推导的起点。树的内部节点对应文法的一个非终结符，比如A，A的子节点对应形如A®a的产生式的右部a的每个符号。对于形如A®L的产生式，标记为A的内部节点的子节点只有一个，即L。
以例子6.5文法为例，S®S+S | S-S | S*S | S/S | (S) | a，存在一个字符串的推导，SÞS-SÞS*S-SÞa*S-SÞa*a-SÞa*a-a，它对应的推导树如图6-1a所示。另一个字符串的推导，SÞS-SÞS-S/SÞ...Þa-a/a的推导树如图6-1b。
这两个代数表达式常常用表达式树（expression trees）表示，表达式树是一个二叉树，它的叶节点是标识符或常量，内部节点是运算符（参见图6-2）。表达式树显示了表达式的结构和推导过程，本节提出的推导树类似于这种表达式树。
在一个CFL的字符串的完整推导树上，根节点对应文法的起始非终结符，叶节点（或称终端节点）对应终结符或L。有时我们也用推导树表示起于某个普通非终结符的推导结构，或部分推导过程，这种推导树的根节点不一定是起始非终结符，叶节点也不一定是终结符。
推导的每一步都是用某个产生式的右部代替左部的非终结符，每个推导都由一组这样的替换按照一定顺序组成。替换的顺序很重要，因此推导SÞS+SÞa+SÞa+a和SÞS+SÞS+aÞa+a是不同的推导。这种差异是在细节上，当得到S+S时，前者选取了最左非终结符，后者选取了最右非终结符。两种推导对应的推导树是完全一样的，因此可以认为推导过程中的细微的次序差异是不重要的。推导树完全反映了推导中用到的产生式，但不关心推导中用到的临时节点，或某些产生式的应用次序，这些次序也与字符串的语法结构无关，因此对应相同推导树的推导都认为是相同的推导。
另一个比较两个推导的方法是将推导的过程标准化，比如采用最左原则，即每次替换最左（或第一个）非终结符。如果两个遵循最左原则的推导是不同的，那么认为是“本质”不同的推导。
实际上，最左原则和推导树原则是两个相当的判定标准。一方面，对应不同推导树的最左推导过程是显然不同的。另一方面，对应不同最左推导过程的推导树也是不同的。比如设下面的推导是第一次出现差异的情况，
xAbÞxa1b
xAbÞxa2b
其中，x是终结符组成的字符串，A是非终结符，且a1¹a2，因此体现在推导树则一定不同。
现在定义，一个字符串具有多个（超过1个）推导树当且仅当具有多个最左推导。注意我们也可以采用最右原则，关键是消除一些细节上的差异。
我们发现许多CFG生成的字符串具有多个“本质”不同的生成办法。

定义6.3 CFG G是歧义的（ambiguous）当且仅当存在一个xÎL(G)具有多个推导树（或最左推导过程）。

显然，上面定义的歧义很接近我们日常应用的自然语言句子的歧义。比如一个记者用到的标题“Disabled Fly to See Carter”，如果它出现在美国第39任总统当政时期，对应的推导是：S®<collective noun> <verb> ...。但通常更多的解释是：S®<adjective> <noun> ...。此处，正确理解一个新闻标题的关键是选择相应的语法推导。

例子6.10 回到例子6.5给出的代数表达式的CFG，我们考察了字符串a+(a*a)/a-a具有的本质不同的推导过程。
分析：本例的CFG形如，S®S+S | S-S | S*S | S/S | (s) | a，看一个简单的例子“a+a+a”，存在两个不同的最左推导：
SÞS+SÞa+SÞa+S+SÞa+a+SÞa+a+a
SÞS+SÞS+S+SÞa+S+SÞa+a+SÞa+a+a
它们对应的推导树分别见图6-3a和图6-3b。如果结合具体的代数运算符含义，两者最终含义是相同的，前者等同于a+(a+a)，后者等同于(a+a)+a。可见括号具有消除歧义的作用。

从例子6.10容易看到，凡是具有形如A®AaA的产生式的CFG都是有歧义的。然而有很多种引入歧义的方式，有时很难发现并排除它们。

例子6.11 程序设计语言歧义的一个标准的例子是“dangling else”，考虑下面的产生式：
<statement>® if (<expression>) <statement> |
if (<expression>) <statement> else <statement> |
<otherstatement>
现在考虑声明：if (expr1) if (expr2) f(); else g();
根据上面的产生式，可以有两个推导树，一种将else看成与第一个if相关，另一种将else看成与第二个if相关。参见图6-4a和图6-4b。在C语言中，为了消除歧义，常常引入括号，如，
if (expr1) {if (expr2) f();} else g();
if (expr1) {if (expr2) f(); else g();}
或者修改文法，如
<statement>® <st1> | <st2>
<st1>® if (<expression>) <st1> else <st1> | <otherstatement>
<st2>® if (<expression>) <statement> |
if (<expression>) <st1> else <st2>
目前我们无法证明为什么新文法消除了歧义，但可以直观地解释。<st1>生成的都是if-else匹配的情况，<st2>生成的是if-else不匹配的情况。而且出现在else之前的都是<st1>，因此不匹配的情况出现在else之后，即else总是与最接近的if匹配。
程序设计语言Modula-2使用了类似括号的方法消除歧义，
<statement>® IF <expression> THEN <statementsequence> END |
IF <expression> THEN <statementsequence>
ELSE <statementsequence> END |
<otherstatement>
在上面文法下，图6-4a和图6-4b对应的字符串分别是
IF A1 THEN IF A2 THEN S1 END ELSE S2 END
IF A1 THEN IF A2 THEN S1 ELSE S2 END END

6.5 一个无歧义的代数表达式
尽管有些CFL是“内在”歧义的，即只能由有歧义的CFG生成，但通常意义的歧义是针对文法而言，而不是语言。如果一个CFG是歧义的，常常可能存在（也是我们希望发现的）一个与其相当的非歧义的CFG，本节我们消除例子6.5给出的代数表达式的文法的歧义。
为了简化问题，我们仅仅使用两个运算符“+”和“*”，得到产生式如下，
S®S+S | S*S | (S) | a
如果消除了这两个运算符的歧义，能够类似地消除“-”和“/”的歧义。正如前面讲到，产生式S®S+S能够带来歧义，我们需要消除这种类型的产生式，同时保持各种运算符的优先级，比如*的优先级高于+，且位于前面的+优先级高于后面的+。新文法G1的产生式如下，
S®S+T | T
T®T*F | F
F®(S) | a
需要证明两个方面：1）G1与G相当；2）G1没有歧义。为了证明方便，G1中的起始符号改写成S1。

定理6.2 文法G的产生式是S®S+S | S*S | (S) | a，文法G1的产生式是
S1®S1+T | T
T®T*F | F
F®(S1) | a
则L(G)=L(G1)。
证明：首先证明L(G1)ÍL(G)。对属于L(G1)的字符串x的长度使用数学归纳法。
1. 归纳基础，x=a时，显然xÎL(G)
2. 归纳推理，设k>=1，每个属于L(G1)、长度<=k的字符串y也属于L(G)，要证明如果xÎL(G1)且|x|=k+1，则xÎL(G)。显然G1推导x的第一步是下面三种情况之一，
S1ÞS1+T
S1ÞTÞT*F
S1ÞTÞ(S1)
如果是情况一，则x=y+z，S1Þ*y，TÞ*z，由于S1Þ*T，因此也有S1Þ*z，由于y和z的长度都<=k，因此y和z都属于L(G)，而文法G有产生式S®S+S，因此SÞ*x成立，即xÎL(G)。情况二和情况三可类似说明。
然后证明L(G)ÍL(G1)，仍然对|x|使用数学归纳法。归纳基础显然。设k>=1，对每个yÎL(G)且|y|<=k，yÎL(G1)也成立，要证明如果xÎL(G)且|x|=k+1，则xÎL(G1)。设x在G上的第一步推导是SÞ(S)，对应x=(y)，则|y|<k，yÎL(G1)，因此S1Þ*y，又有S1ÞTÞFÞ(S1)Þ*(y)=x，因此xÎL(G1)。
设第一步推导为SÞS+S的情况。则x=y+z，y和z都属于L(G1)，如果能够得到TÞ*z，那么根据S1ÞS1+T，就能得到S1Þ*x。设x=x1+x2+...+xn，xiÎL(G1)，n是这种形式的最大值，因此所有的xi都是由T而不是S1推导得到（如果是S1，则n不是最大值），令
y=x1+x2+...+xn-1，z=xn，
即TÞ*z，得证。
类似证明第一步推导为SÞS*S的情况。设x= x1*x2*...*xn，n是这种形式的最大值，则一定有FÞ*xn，根据S1ÞTÞT*F，得证。

为了证明文法的无歧义性，关键是说明括号的无歧义性。参见练习5.11。

定义6.4 一个字符串的左括号和右括号是平衡的，指的是，它的左括号和右括号的数目相当，而且每个前缀的左括号数目不少于右括号。左括号的配偶（mate）指的是，从该做括号起到与其平衡的右括号。

平衡字符串的每个左括号都有一个配偶。从G1生成的所有字符串都是平衡的。设xÎL(G1)，如果能够说明x每步都只有一个最左替换，就证明了G1的无歧义性。

定理6.3 CFG G1的产生式如下，
S1®S1+T | T
T®T*F | F
F®(S1) | a
则G1无歧义。
证明：我们证明L(G1)的每个字符串x都只有一个最左推导。对|x|使用数学归纳法。可以证明一个更普遍的情况，即任何一个从S1、T、F推导出来的字符串x都只有一个最左推导。
1. 归纳基础，|x|=1，x=a，显然成立
2. 归纳推理，设k>=1，任何一个从S1、T、F推导出来的长度<=k的字符串y都只有最左推导，要证明对于|x|=k+1的x也成立。分情况讨论：1）设x至少有一个“+”不在括号中，且设此处的“+”是最右一个不在括号内的“+”号，则任何从S1到x的最左推导都是下面的形式，S1ÞS1+TÞ*y+TÞ*y+z，y和z都只有一个最左推导，因此x也只有一个最左推导；2）设x没有一个“+”不在括号内，但有“*”不在括号内，设此处的“*”是最右一个不在括号内的“*”号，则所有的最左推导中一定存在下面的一步最左推导步骤，S1ÞTÞT*FÞ*y*FÞ*y*z。y和z都只有一个最左推导，因此x也只有一个最左推导；3）设x的所有“+”和“*”都在括号内，则最初的推导一定是S1ÞTÞFÞ(S1)，即x=(y)，而y只有一个最左推导，因此x也只有一个最左推导。

6.6 简化形式和规范形式
歧义是CFG一个不好的性质，本节继续讨论一些直观的方法改善CFG的质量，首先删除一些特定类型（带来麻烦）的产生式，然后将产生式写成标准化的形式，即规范形式。
我们从删除空产生式（L-production，形如A®L）和单一产生式（一个非终结符被另一个非终结符代替，形如A®B）开始。用一个例子来说明它的作用，文法G上存在一个推导aÞb，如果G没有空产生式，则b的长度不小于a，如果G没有单一产生式，则b的长度大于a。如果l和t分别表示当前字符串的长度和字符串中终结符的个数，则l+t的值每步推导至少增加1，起始终结符S的l+t值为1，长度为k的字符串的l+t值为2k，因此从S到x的推导步骤至多2k-1步。有了推导的上限，就可以用枚举的方法解决一些问题，比如|x|=k，则尝试所有不超过2k-1步的推导过程，考察是否某个推导得到了字符串x，尽管这不是一个高效的方法，但至少提供了一个方法判定x能够被G生成。
显然，如果L在语言L(G)之中，则不能消除所有空产生式。我们可以将问题局限在讨论不含L的语言和它对应的文法G。

例子6.12 G是一个具有下面产生式的文法
S®ABCBCDA
A®CD
B®Cb
C®a | L
D®bD | L
分析：显然不能仅仅扔掉空产生式。比如如果扔掉D®L，则推导中的D将无法再消除，则文法无法生成任何字符串。因此需要添加一些产生式弥补空产生式的缺失。我们将S®ABCBCDA改写成S®ABC1BC2DA，其中的C1、C2和D都可能取空值或非空值，如