上下文无关文法
wish8088 · 2010-03-13 11:18 · 42049 次点击
范式上下文无关文法可以化为两种简单的范式之一,即任一上下文无关语言可用如下两种标准文法的任意一种生成:其一是乔姆斯基范式,它的产生式均取A→BC或A→α的形式;其二是格拉巴赫范式,它的产生式均取A→aBC或A→α的形式。其中A,B,C∈V,是非终结符,a∈Σ,是终结符;α∈Σ,是终结符串。
同态映射下的性质对任意正整数n,令data/attachment/portal/201111/06/143743e63e8kevrlsl4ell.gif…,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(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的文法性语言族,由此生成的语言集合data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif(ψ(G))称为G的文法性语言族。例如,文法形式{S→aS,S→a}的文法性语言族是正则语言集;{S→SS,S→a}的文法性语言族是上下文无关语言集。
若文法形式G作为普通文法时生成的语言data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif(G)是无限集,则称G为非平凡的。此时文法性语言族data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif(G)是一个满主半AFL,反之不然。如满主半AFL({ab│n≥1}),不是一个文法性语言族。
以data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif1·data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif2表文法性语言族data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif1和data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif2的乘积,data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif1∩data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif2表两者之并,它们仍是文法性语言族。当data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif吇data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif1data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif2时,必有data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif吇data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif1或data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif吇data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif2成立,则称data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif是素的。正则语言集和线性语言集都是素文法性语言族。任一文法性语言族data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif必可唯一地分解为它的素因子乘积和:data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif=(data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif11…data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gif1n1)∪…∪(data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gifdata/attachment/portal/201111/06/143746ijcdzcc1m4sqire6.gif…data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gifmnm)。其中每个data/attachment/portal/201111/06/143745wgaj0d9c57gp7e9q.gifij都是素因子。这个分解在乘积运算∪可交换的意义下是唯一的。
文法的二义性从文法生成语言,可有多种推导公式。例如文法{S→AB,A→a,B→b}可有两种推导:S崊AB崊aB崊ab及S崊AB崊Ab崊ab。若每次都取最左边的非终结符进行推导,如上例中的前一种方式那样,则称为左推导。如果有两种不同的左推导推出同一结果,则称此文法是二义性的,反之是无二义文法。对有些二义性文法,可找到一个等价的无二义文法,生成同一个语言。不具有无二义文法的语言称为本质二义性语言。例如,{S→A,S→a,A→a}是二义性文法。
data/attachment/portal/201111/06/143746qyuqu0ct0av60uur.gifdata/attachment/portal/201111/06/143748rr3p3y834o4gr43x.gif是本质二义性语言。
子文法类可以根据不同的观点取上下文无关文法的子文法。一种观点是根据文法的外形和它们生成的语言族在代数运算下的封闭性。例如,若文法G的产生式只具有下列三种形式之一:A→αBβ,C→γ和S→δ,其中A,B,C∈V,αβγ∈Σ,δ∈(Σ∪V),且δ中至多含k个非终结符,S是出发符号,则称G为k线性文法。1线性文法又称线性文法。全体k线性文法之集合称为元线性文法。元线性语言族在联合和乘积运算下是封闭的,但在求交,求补,乘幂闭包和置换等运算下都不封闭。从包含关系说,正则语言族真包含于线性语言族。对任一k≥1,k线性语言族真包含于k1线性语言族,元线性语言族真包含于上下文无关语言族。
由于上下文无关文法被广泛地应用于描述计算机语言的语法,因此更重要的是从机械执行语法分解的角度取上下文无关文法的子文法,最重要的一类就是无二义的上下文无关文法,因为无二义性对于计算机语言的语法分解至为重要。在无二义的上下文无关文法中最重要的子类是LR(k)文法,它只要求向前看k个符号即能作正确的自左至右语法分解。LR(k)文法能描述所有的确定型上下文无关语言。