什么是上下文无关文法?

什么是上下文无关文法?

[拼音]：shangxiawen wuguan wenfa

[外文]：context-free grammar

形式语言理论中一种重要的变换文法，用来描述上下文无关语言，在乔姆斯基分层中称为2型文法。由于程序设计语言的语法基本上都是上下文无关文法，因此应用十分广泛。

范式

上下文无关文法可以化为两种简单的范式之一，即任一上下文无关语言可用如下两种标准文法的任意一种生成：其一是乔姆斯基范式，它的产生式均取A→BC或A→α的形式；其二是格拉巴赫范式，它的产生式均取A→aBC或A→α的形式。其中A，B，C∈V，是非终结符，a∈Σ，是终结符；α∈Σ*，是终结符串。

同态映射下的性质

对任意正整数 n，令


…，an｝，Σ'n＝｛a'1，…，a'n｝，定义乔姆斯基变换文法G＝(Σ，V，S，P)为(Σn∪Σ'n，S，S，P＝｛S→，S→SaiSa'iS|1≤i≤n｝)。这个文法生成的语言称为代克集。如果把ai看作开括号，把a'i看作相应的闭括号，则n维代克集Dn就是由几种不同的括号对组成的配对序列之集合。例如，a1a2a2a'2a2a'1和a1a'1a2a'2a1a'1都属于D2，用括号表示时可以写成（〔（ ）〕）和（ ）〔 〕（ ）。

代克集是把正则语言族扩大成上下文无关语言族的工具。对任一上下文无关语言L，必存在两个同态映射h1和h2，以及一个正则语言R，使L＝h2[h1-1(D2)∩R]，其中D2是二维代克集，反之亦然。

更进一步，上下文无关语言族是包含D2，且在同态、逆同态和与正则语言相交三种代数运算下封闭的最小语言族。加上乘积和乘幂闭包两种运算后，此结论仍真。

文法形式和文法的相似性

在两种符号置换的意义下(终结符和非终结符分别替换)， 许多文法之间有着相似性。把一组彼此相似的文法抽象成一个更高级的形式体系，就叫作文法形式。迄今，文法形式的研究主要集中在上下文无关文法上。

文法形式的具体定义是：给定无限的终结符表Σ∞和无限的非终结符表V∞。任取Σ∞和V∞的非空子集Σ和V，按构造普通文法的方法定义一个四元组G=(Σ，V，S，P)。在G确定以后，任取映射函数ψ，把Σ中每一元素a映为Σ∞中一有限子集ψ(a)，把V中每一元素A映为V∞中一个有限子集ψ(A)，且当A厵B时有ψ(A)∩ψ(B)=φ。ψ就是所需的置换。通过它得到一个具体文法ψ(G)=[ψ(Σ)，ψ(V)，ψ(S)，ψ(P)]，其中ψ(P)是把P中所有产生式中的符号作ψ置换后得到的一组新产生式，ψ(Σ)，ψ(V)和ψ(S)分别是ψ(P)中出现的终结符集，非终结符集和出发符号。

这样的G称为文法形式，ψ称为G 的一个解释，ψ(G)是G的一个解释文法，被认为是相似于G。令ψ遍历各种可能的解释，得到的ψ(G)集合称为G的文法性语言族，由此生成的语言集合


(ψ(G))称为G的文法性语言族。例如，文法形式｛S→aS，S→a｝的文法性语言族是正则语言集;｛S→SS，S→a｝的文法性语言族是上下文无关语言集。

若文法形式G作为普通文法时生成的语言


(G)是无限集，则称G为非平凡的。此时文法性语言族


(G)是一个满主半AFL，反之不然。如满主半AFL(｛anbn│n≥1｝)，不是一个文法性语言族。

以


1·


2表文法性语言族


1和


2的乘积，


1∩


2表两者之并，它们仍是文法性语言族。当


吇


1


2时，必有


吇


1或


吇


2成立，则称


是素的。正则语言集和线性语言集都是素文法性语言族。任一文法性语言族


必可唯一地分解为它的素因子乘积和：


=(


11…


1n1)∪…∪(





…


mnm)。其中每个


ij都是素因子。这个分解在乘积运算∪可交换的意义下是唯一的。

文法的二义性

从文法生成语言，可有多种推导公式。例如文法｛S→AB，A→a，B→b｝可有两种推导：S崊AB崊aB崊ab及S崊AB崊Ab崊ab。若每次都取最左边的非终结符进行推导，如上例中的前一种方式那样，则称为左推导。如果有两种不同的左推导推出同一结果，则称此文法是二义性的，反之是无二义文法。对有些二义性文法，可找到一个等价的无二义文法，生成同一个语言。不具有无二义文法的语言称为本质二义性语言。例如，｛S→A，S→a，A→a｝是二义性文法。

是本质二义性语言。

子文法类

可以根据不同的观点取上下文无关文法的子文法。一种观点是根据文法的外形和它们生成的语言族在代数运算下的封闭性。例如，若文法G 的产生式只具有下列三种形式之一：A→αBβ，C→γ和S →δ，其中A，B，C∈V，αβγ∈Σ*，δ∈(Σ∪V)*，且δ中至多含k个非终结符，S是出发符号，则称G为k线性文法。1线性文法又称线性文法。全体 k线性文法之集合称为元线性文法。元线性语言族在联合和乘积运算下是封闭的，但在求交，求补，乘幂闭包和置换等运算下都不封闭。从包含关系说，正则语言族真包含于线性语言族。对任一k≥1，k线性语言族真包含于k+1线性语言族，元线性语言族真包含于上下文无关语言族。

由于上下文无关文法被广泛地应用于描述计算机语言的语法，因此更重要的是从机械执行语法分解的角度取上下文无关文法的子文法，最重要的一类就是无二义的上下文无关文法，因为无二义性对于计算机语言的语法分解至为重要。在无二义的上下文无关文法中最重要的子类是LR(k)文法，它只要求向前看k个符号即能作正确的自左至右语法分解。LR(k)文法能描述所有的确定型上下文无关语言。