上下文无关文法

1、上下文无关文法 百科名片形式语言理论中一种重要的变换文法，用来描述上下文无关语言,在乔姆斯基分层中称为2型文法。由于程序设计语言的语法基本上都是上下文无关文法，因此应用十分广泛。 目录隐藏简介 例子 范式 同态映射下的性质 文法形式和文法的相似性 文法的二义性 子文法类 编辑本段简介上下文无关文法（Content-Free Grammar, CFG） 在计算机科学中，若一个形式文法 G = (N, , P, S) 的 上下文无关文法产生式规则都取如下的形式：V -> w，则称之为上下文无关的，其中 VN ，w(N)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字

2、串 w 自由替换，而无需考虑字符 V 出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的条目上下文无关语言。 上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；实际上，几乎所有程序设计语言都是通 上下文无关文法过上下文无关文法来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见 LR 分析器和 LL 分析器。 BNF 巴克斯-诺尔范式经常用来表达上下文无关文法。 文法规则使用相似的表示法。名字用斜体表示（但它是一种不同的 上下文无关文法字体，所以可与正则

3、表达式相区分）。竖线仍表示作为选择的元符号。并置也用作一种标准运算。但是这里没有重复的元符号（如正则表达式中的星号*），稍后还会再讲到它。表示法中的另一个差别是现在用箭头符号“”代替了等号来表示名字的定义。这是由于现在的名字不能简单地由其定义取代，而需要更为复杂的定义过程来表示，这是由定义的递归本质决定的。 同正则表达式类似，文法规则是定义在一个字母表或 上下文无关文法符号集之上。在正则表达式中，这些符号通常就是字符，而在文法规则中，符号通常是表示字符串的记号。我们利用C中的枚举类型定义了在扫描程序中的记号；为了避免涉及到特定实现语言（例如C）中表示记号的细节，就使用了正则表达式本身来表示记号

4、。此时的记号就是一个固定的符号，如同在保留字 while 中或诸如+或: =这样的特殊符号一样，对于作为表示多于一个串的标识符和数的记号来说，代码字体为斜体，这就同假设这个记号是正则表达式的名字（这是它经常的表示）一样。 上下文无关文法的却利用了与正则表达式中极为类似的命名惯例和运算，二者的主要区别在于上下文无关文法的规则是递归的（recursive）。 编辑本段例子例子 1 一个简单的上下文无关文法的例子是：S -> aSb | 上下文无关文法。这个文法产生了语言 anbn : n 0 。不难证明这个语言不是正规的。 例子 2 这个例子可以产生变量 x,y,z 的算术表达式： S -&

5、gt; 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 的数目的所有字

6、串， V 可以产生 a 的数目少于 b 的数目的所有字串。 编辑本段范式每一个不生成空串的上下文无关文法都可以转化为等价的 C 上下文无关文法homsky 范式或 Greibach 范式。这里两个文法等价的含义指它们生成相同的语言。 由于 Chomsky 范式在形式上非常简单，所以它在理论和实践上都有应用。比如，对每一个上下文无关语言，我们可以利用 Chomsky 范式构造一个多项式算法，用它来判断一个给定字串是否属于这个语言CYK 算法。 编辑本段同态映射下的性质对任意正整数 n,令 上下文无关文法，an，'na'1，a 上下文无关文法'n,定义乔姆斯基变换文法G(，

7、V，S，P)为(n'n,S,S,PS,SSaiSa'iS|1in)。这个文法生成的语言称为代克集。如果把ai看作开括号，把a'i看作相应的闭括号，则n维代克集Dn就是由几种不同的括号对组成的配对序列之集合。例如,a1a2a2a'2a2a'1和a1a'1a2a'2a1a'1都属于D2，用括号表示时可以写成（ ）和（ ） （ ）。 代克集是把正则语言族扩大成上下文无关语言族的工具。对任一上下文无关语言L,必存在两个同态映射h1和h2，以及一个正则语言R，使Lh2【h1(D2)R】,其中D2是二维代克集，反之亦然。 更进一步，上下文无关

8、语言族是包含D2，且在同态、逆同态和与正则语言相交三种代数运算下封闭的最小语言族。加上乘积和乘幂闭包两种运算后，此结论仍真。 编辑本段文法形式和文法的相似性在两种符号置换的意义下(终结符和非终结符分别替换), 许多文法之间有着相似性。把一组彼此相似的文法抽象成一个更高级的形式体系，就叫作文法形式。迄今，文法形 上下文无关文法式的研究主要集中在上下文无关文法上。 文法形式的具体定义是：给定无限的终结符表和无限的非终结符表V。任取和V的非空子集和V,按构造普通文法的方法定义一个四元组G=(，V，S，P)。在G确定以后，任取映射函数，把中每一元素a映为中一有限子集(a)，把V中每一元素A映为V中一个

9、有限子集(A),且当A厵B时有(A)(B)=。就是所需的置换。通过它得到一个具体文法(G)=【()，(V),(S),(P)】,其中(P)是把P中所有产生式中的符号作置换后得到的一组新产生式，(),(V)和(S)分别是(P)中出现的终结符集，非终 上下文无关文法结符集和出发符号。 这样的G称为文法形式，称为G 的一个解释，(G)是G的一个解释文法，被认为是相似于G。令遍历各种可能的解释,得到的(G)集合称为G的文法性语言族，由此生成的语言集合(G)称为G的文法性语言族。例如，文法形式SaS，Sa的文法性语言族是正则语言集;SSS，Sa的文法性语言族是上下文无关语言集。 若文法形式G作为普通文法时

10、生成的语言(G)是无限集，则称G为非平凡的。此时文法性语言族(G)是一个满主半AFL，反之不然。如满主半AFL(abn1)，不是一个文法性语言族。 以1·G2表文法性语言族G1和G2的乘积,12表 上下文无关文法两者之并,它们仍是文法性语言族。当吇G1G2时，必有G吇G1或G吇G2成立，则称G是素的。正则语言集和线性语言集都是素文法性语言族。任一文法性语言族G必可唯一地分解为它的素因子乘积和：G=(111n1)(m1mnm)。其中每个Gij都是素因子。这个分解在乘积运算可交换的意义下是唯一的。 编辑本段文法的二义性从文法生成语言，可有多种推导公式。例如文法SAB， 上下文无关文法Aa

11、,Bb可有两种推导：S崊AB崊aB崊ab及S崊AB崊Ab崊ab。若每次都取最左边的非终结符进行推导，如上例中的前一种方式那样，则称为左推导。如果有两种不同的左推导推出同一结果，则称此文法是二义性的，反之是无二义文法。对有些二义性文法，可找到一个等价的无二义文法，生成同一个语言。不具有无二义文法的语言称为本质二义性语言。例如，SA,Sa,Aa是二义性文法。 上下文无关文法上下文无关文法是本质二义性语言。 编辑本段子文法类可以根据不同的观点取上下文无关文法的子文法。一种观点是根据文法的外形和它们生成的语言族在代数运算下的封闭性。例如,若文法G 的产生式只具有下列三种形式之一：AB，C和S ，其中A，B，CV，(V),且中至多含k个非终结符，S是出发符号,则称G为k线性文法。1线性文法又称线性文法。全体 k线性文法之集合称为元线性文法。元线性语言族在联合和乘积运算下是封闭的，但在求交,求补,乘幂闭包和置换等运算下都不封闭。从包含关系说，正则语言族真包含于线性语言族。对任一k1，k线性语言族真包含于k 1线性语言族，元线性语言族真包含于上下文无关语言