上下文无关文法与上下文有关文法.doc

上下文无关文法 形式语言理论中一种重要的变换文法，用来描述上下文无关语言，在乔姆斯基分层中称为2型文法。由于程序设计语言的语法基本上都是上下文无关文法，因此应用十分广泛。 简介 上下文无关文法（Context-Free Grammar, CFG） 　　 在计算机科学中，若一个形式文法 G = (N, Σ, P, S) 的产生式规则都取如下的形式：V - w，则称之为上下文无关的，其中 V∈N ，w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换，而无需考虑字符 V 出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的﹙条目上下文无关语言﹚。 　　 上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；实际上，几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见 LR 分析器和 LL 分析器。 　　 BNF ﹙巴克斯-诺尔范式﹚经常用来表达上下文无关文法。 　　 文法规则使用相似的表示法。名字用斜体表示（但它是一种不同的字体，所以可与正则表达式相区分）。竖线仍表示作为选择的元符号。并置也用作一种标准运算。但是这里没有重复的元符号（如正则表达式中的星号*），稍后还会再讲到它。表示法中的另一个差别是现在用箭头符号“→”代替了等号来表示名字的定义。这是由于现在的名字不能简单地由其定义取代，而需要更为复杂的定义过程来表示，这是由定义的递归本质决定的。 　 　 同正则表达式类似，文法规则是定义在一个字母表或 符号集之上。在正则表达式中，这些符号通常就是字符，而在文法规则中，符号通常是表示字符串的记号。我们利用C中的枚举类型定义了在扫描程序中的记号；为了避免涉及到特定实现语言（例如C）中表示记号的细节，就使用了正则表达式本身来表示记号。此时的记号就是一个固定的符号，如同在保留字 while 中或诸如+或: =这样的特殊符号一样，对于作为表示多于一个串的标识符和数的记号来说，代码字体为斜体，这就同假设这个记号是正则表达式的名字（这是它经常的表示）一样。 　　 上下文无关文法的却利用了与正则表达式中极为类似的命名惯例和运算，二者的主要区别在于上下文无关文法的规则是递归的（recursive）。 例子 例子 1 　　一个简单的上下文无关文法的例子是：S - aSb | ε 。这个文法产生了语言 {anbn : n ≥ 0} 。不难证明这个语言不是正规的。 　　 例子 2 　　 这个例子可以产生变量 x,y,z 的算术表达式： 　　 S - T + S | T - S | T 　　 T - T * T | T / T | ( S ) | x | y | z 　　 例如字串 ( x + y ) * x - z * y / ( x + x ) 就可以用这个文法来产生。 　　 例子 3 　　 字母表 {a,b} 上 a 和 b 数目不相等的所有字串可以由下述文法产生： 　　 S - U | V 　　 U - TaU | TaT 　　 V - TbV | TbT 　　 T - aTbT | bTaT | ε 　　 这里 T 可以产生 a 和 b 数目相等的所有字串，U 可以产生 a 的数目多于 b 的数目的所有字串， V 可以产生 a 的数目少于 b 的数目的所有字串。 范式 每一个不生成空串的上下文无关文法都可以转化为等价的Chomsky 范式或 Greibach 范式。这里两个文法等价的含义指它们生成相同的语言。 　　 由于 Chomsky 范式在形式上非常简单，所以它在理论和实践上都有应用。比如，对每一个上下文无关语言，我们可以利用 Chomsky 范式构造一个多项式算法，用它来判断一个给定字串是否属于这个语言﹙CYK 算法﹚。 同态映射下的性质 对任意正整数 n,令 …，an}，Σn={a1，…，an},定义乔姆斯基变换文法G=(Σ，V，S，P)为(Σn∪Σn,S,S,P={S→,S→SaiSaiS|1≤i≤n})。这个文法生成的语言称为代克集。如果把ai看作开括号，把ai看作相应的闭括号，则n维代克集Dn就是由几种不同的括号对组成的配对序列之集合。例如,a1a2a2a2a2a1和a1a1a2a2a1a1都属于D2，用括号表示时可以写成（〔（ ）〕）和（ ）〔 〕（ ）。 　　 代克集是把正则语言族扩大成上下文无关语言族的工具。对任一上下文无关语言L,必存在两个同态映射h1和h2，以及一个正则语言R，使L=h2【h1(D2)∩R】,其中D2是二维代克集，反之亦然。 　　 更进一步，上下文无关语言族是包含D2，且在