《上下文无关文法》由会员分享，可在线阅读，更多相关《上下文无关文法（15页珍藏版）》请在金锄头文库上搜索。
1、第三部分 上下文无关语言和下推自动机 前面介绍的有限自动机是计算的初级模型，它所接受的正规语言不太关心字符串自身的结构。 上下文无关文法（CFL）是一种简单的描述语法规则的递归方法，语言中的字符串由这些规则 产生。所有的正规语言都能用上下文无关文法描述，它也可以描述非正规语言。上下文无关文 法描述的语法规则更复杂多变，可以在相当大的程度上，描述高级程序设计语言的语法和其他 一些形式语言。类似正则语言对应的抽象机模型是有限自动机，CFL也有对应的抽象机模型。CFL对应的计算 模型是在有限自动机的基础上增加存储空间得到，并被设想成无限空间（对应有限自动机的有 限空间），采用了一种简单的管理模式，栈
2、（stack），这种新的计算模型（或抽象机）称为下 推自动机（pushdown automata），下推是栈最典型的操作。有必要在下推自动机中保留非确定 性，确定型下推自动机不能接受所有的CFL，但给定一个CFG，容易构造一个相应的非确定型 下推自动机，它在识别字符串过程中的移动模拟了文法的推导过程，这个过程称为分析（parse）。 分析不是一定需要下推自动机来完成。CFL仍然不够通用，不能包括所有有意义的、或有用的形式语言。采用类似第五章的技术，我 们将给出一些不是CFL的简单例子，这些技术也用于解决与CFL相关的判定问题。6 上下文无关文法6.1 上下文无关文法的定义为了描述我们在第二部分
3、考察的各种语言，包括一些非正则语言，我们引入一种语言的递 归定义方法，称为文法。文法与我们熟悉的语言的语法描述相近，是描述语言和分析语言的有 力工具。问题：文法的形式化定义似乎可以模仿有限自动机，比如 5元组或6元组之类。例子6.1正如我们在例子2.16中所见，字母表a, b上的回文语言pal可以用下面的递归方 法描述：1. A, a, b epal2. 对每个Sepal, aSa和bSb也属于pal3. pal中不包含其他字符串如果将上面的符号S看成一个变量，代表了所有我们希望计算（比如某种递归算法）的pal 的元素，那么上面的规则 1 和规则2可以非正式地重新表述如下：1. S的值可以是A
4、, a, b2. 每个S可以写成aSa或bSb的形式如果我们用T表示“可以取值为”，贝阿以写出下面的式子：SaSaTabSbaTab Aba=abba 上面的产生过程可以总结成下面的两组产生式（或称规则）： STa | b |ASTaSa | bSb符号“I”表示“或”的含义。上式的含义是aSa或bSb，而不是a或b,即连接运算的优 先级高于“|”。我们使用的这套术语中，小写字母a和b表示终结符，大写字母S表示非终结 符，或称变量。总共有5条规则，或产生式（production）。符号S是非终结符，也是起始终结 符，即我们生成字符串的起始符号是S,然后不断利用规则替换符号串中的非终结符，直到最
5、 终得到一个不含非终结符的符号串，就生成了规则所定义的语言的一个字符串。例子2中的产生式具有除起始符S外的多个非终结符，我们设想S表示了语言中任意的字 符串，其他非终结符表示了其他辅助性的字符串类型，他们可用来方便地生成S表示的字符串。例子6.2我们要构造一个生成所有在字母表a, b上的非回文字符串的文法，那样的字符串 可以描述如下：从字符串的两端开始比较，也许能够发现一些相同的字符对，但最终能够发现 一对不同的字符。对于前一种情况，我们可以借用回文语言的产生式：SaSa I bSb如果加入产生式Sa I b I A 则这种左右匹配的形式将体现在整个字符串上，为了中断这种左右匹配的情况，即体现
6、上面提 到的第二种情况，我们引入新的非终结符，比如D,表示那些左右两个端点上的字符不同的字 符串。且所有符合D的字符串也符合S,因此有SDo非终结符的定义比较简单，它唯一的条件是左右两个端点的字符不相同，中间的字符串可 以是任意的，我们用非终结符A表示任意的字符串，则有DaAb I bAaoA表示任意的字符串，因此A的产生式更简单了，不用添加新的非终结符来简化问题，它 的产生式是， AA I aA I bA。我们把上面三个非终结符的产生式写在一起，就得到了描述所规定语言的产生式集：SaSa I bSb I DDaAb I bAaAA I aA I bA因此一个完整的非回文字符串“abbaaba
7、”的产生过程是，S aSaabSbaabDbaabbAabaabbaAabaabbaAabaabbaaba定义6.1上下文无关文法(context-free grammar, CFG)是一个4元组G=(V,工,S, P),其中， V和工是不相交的有限集，S eV，P是一组有限的产生式规则，形如 Aa，其中AeV，且 ae(VuE)*oV的元素称为非终结符(或变量)，工的元素称为终结符，S是一个特殊的非终结符，称为 起始符， P 的元素称为语法规则，或产生式。设G=(V,工,S, P)是一个CFG,我们将符号保留给P的产生式专用，符号nG用于表示字G符串的产生过程的每一步，如anG卩表示字符串卩
8、能够通过替换a中的某些变量(根据P定义的 产生式来替换)得到，即如果有a =a1Aa2 且 AyeP，则B=aja2。这里能够看到，我们命名为上下文无关(context-free)的含义，即我们在利用产生式规则, 用一组符号替换某个非终结符时，与非终结符的上下文无关(此处，A的替换与a 1和a2无关)， 替换是无限制的。在没有多个文法出现，很清楚用到文法G是什么的情况下，推导符号n可以简写成二。G多步的推导可以写成n*G，即如果存在一组符号串，a=a0、a 1、ak=p，每个后者都是前者 的直接推导，则称为a可以多步推导出卩，记为an*G卩，简写成an*卩。定义6.2 G=(V, Z, S,
9、P)是一个CFG,则G产生的语言是所有可由G产生的字符串组成的集 合，即 L(G)=xeZ* | S n*Gxo 一个语言 L 是上下文无关语言(context-free language, CFL ), 当且仅当存在一个CFG G,使得L=L(G)o此处可以把文法设想成类似自动机的抽象模型，则一个语言 L 是 CFL 当且仅当存在一个 CFG G 接受它(或识别它)，类似前面正则语言与有限自动机的关系，接受(或识别)的含义 是两方面的，一方面凡是L中的字符串都能由G产生，另一方面，凡是不属于L的字符串都不 能由G产生。前面的例子，能够比较容易地说明这两方面的限制，下面的例子则不是很明显。例子
10、6.3考虑语言L=xw0, 1* I n0(x)=n(x),其中ni(x)表示数字i在x中的出现次数(即 含有相同数目0和1的语言)。写出生成L的CFG。1分析：既然 CFG 的本质是一个递归定义，那么类似例子 6.1，我们可以先发现归纳基础， 然后找到归纳推理。显然AeL,另外如果存在一个字符串xeL，那么得到更长的属于L的字符 串的两个方法是，0x1和1x0,即分别在两端添加相同数量的0和1。(当然，还有很多生成方 法，比如x01, x10，或在x中插入相同数量的0和1),这样得到三个产生式：StA I 0S1 I 1S0显然，还遗漏了一些字符串，如0110。我们注意到L中任意两个元素的连
11、接仍然属于L, 因此可以增加一个产生式，StSSo与前面的三个产生式合并，我们得到一个CFG G如下，StA I 0S1 I 1S0 I SS显然G产生的字符串都满足0和1数目相等这个条件，即L(G)cL,现在只要证明LcL(G)o令d(x)=n0(x)-n1(x)o则字符串xeL,当且仅当d(x)=0。因此只需证明每个满足d(x)=0的x, 都有xeL(G)。我们用数学归纳法来证明LcL(G)o归纳对象是字符串的长度1x1。1. 归纳基础，1x1=0且d(x)=0,则xeL(G)，这是显然的，因为此时x=A，而A可以由产生 式StA得到。2. 归纳推理，设k=0，每个满足Iylv=k, d(
12、y)=0的字符串y都属于L(G)。要证明每个长 度等于k+1且d(x)=0的字符串x也属于L(G)o分情况讨论如下：a) 如果x以0开始，以1结尾，则可以写成x=0y1,且d(y)=0,根据归纳假设yeL(G), 即存在一组推导，Sn*Gy。因此对于x,存在推导，Sn0S1n*0y1nx。Gb) 如果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变化到0
13、y时，d(z) 从1变化到-1，因此存在某个长于0短于0y的前缀z,使得d(z)=0,则x=zw，显 然d(w)=0，由于z、w的长度都0的x都能由 G0 产生，对 x 的长度应用数学归纳法。1. 归纳基础，显然1x1=1且d(x)0时，即x=0, x可由StO推导，属于L(GO)。2. 归纳推理，设k=0，对每个lxlv=k且d(x)0的x都属于L(G0)，要证明每个lxlv=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=viv=n，令w.是x的前缀，紧接wi的下一个字符就是第i个1,则x=w.1z.。ii i分两种情况1)不存在wi,使得d(wi)0，则d(wn)0，令 w=wn, z=zn，显然d(z)0,得证；2)存在一个wi,使得d(wi)=0，设i=m是第 一个d(wi)0,且d(wm-1)=10,令 w=wm-1, z=zm-1，易证 d(zm-1)0,因此得证。其他两种情况， x 以 1 开始，以 1 结尾证明略。类似方法能够得到生成L1的产生式，我们用A表示生成L0的产生式，B表示生成L1的 产生式，那么生成语言L的全部文法是：StA l B
