求真百科欢迎当事人提供第一手真实资料,洗刷冤屈,终结网路霸凌。

形式文法查看源代码讨论查看历史

事实揭露 揭密真相
跳转至: 导航搜索
形式文法

形式文法,计算机科学中的概念,在计算机科学中,形式语言是某个字母表上一些有限长字串的集合,而形式文法是描述这个集合的一种方法。形式文法之所以这样命名,是因为它与人类自然语言中的文法相似的缘故。形式文法描述形式语言的基本想法是,从一个特殊的初始符号出发,不断的应用一些产生式规则,从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。

目录

形式文法举例

形式定义

例子

类别

0型文法

1型文法

2型文法

3型文法

形式文法举例

举例来说,假设字母表只包含 'a' 和 'b' 两个字符,初始符号是 'S' ,我们应用下述规则:

1. S -> aSb

2. S -> ba

于是我们可以通过把 "S" 重写为 "aSb"(规则1),我们还可以继续应用这条规则把 "aSb" 重写为 "aaSbb"。这个重写的过程不断重复,直到结果中只包含字母表中的字母为止。在例子中,我们可以得到 S -> aSb -> aaSbb -> aababb 这样的结果。由文法刻画的语言包含了所有可以这样产生的字串,比如 ba, abab, aababb, aaababbb 等等。

形式定义

一个形式文法 G 是下述元素构成的一个元组(N, Σ, P, S):----有些书上也写成(V,T,S,P)

非终结符号集合 N。

终结符号集合 Σ ,Σ 与 N 无交。

取如下形式的一组产生式规则 P,

(Σ ∪ N)*中的字串 -> (Σ ∪ N)* 中的字串字串,并且产生式左侧的字串中必须至少包括一个非终结符号。

起始符号 S,S 属于 N。

一个由形式文法 G = (N, Σ, P, S) 产生的语言是所有如下形式字串的集合,这些字串全部由终结符号集 Σ 中符号构成,并且可以从初始符号 S 出发,不断应用 P 中的产生式规则而得到。

3例子

考虑如下的文法 G ,其中 N = {S, B}, Σ = {a, b, c}, P 包含下述规则

1. S -> aBSc

2. S -> abc

3. Ba -> aB

4. Bb -> bb

非终结符号 S 作为初始符号。下面给出字串推导的例子:(推导使用的产生规则用括号标出,替换的字串用黑体标出)

S -> (2) abc

S -> (1) aBSc -> (2) aBabcc -> (3) aaBbcc -> (4) aabbcc

S -> (1) aBSc -> (1) aBaBScc -> (2) aBaBabccc -> (3) aaBBabccc -> (3) aaBaBbccc -> (3) aaaBBbccc -> (4) aaaBbbccc -> (4) aaabbbccc

很清楚这个文法定义了语言 { anbncn| n > 0 } ,这里 an表示含有 n 个 a 的字串。

形式文法与 Lindenmayer 系统(L-系统)类似, 但有几点不同:L-系统不区分终结符号和非终结符号;L-系统限制规则的应用顺序;L-系统能不停地运行,产生一个无限长的字串行。通常情况下,每一个字串同空间中的一个点集联系起来,而L-系统的输出就是这个点集列的极限。L-系统可以用于模拟细胞的生长,所以又被称为发展系统。

4类别

某些类型的文法及其产生的语言得到了细致的研究并被单独命名。最常见的文法的分类系统是诺姆·乔姆斯基于1950年发展的乔姆斯基谱系,这个分类谱系把所有的文法分成四种类型:即0型、1型、2型和3型,又可以分别称为无限制文法、上下文相关文法、上下文无关文法和正规文法。任何语言都可以由无限制文法来表达,余下的三类文法对应的语言类分别是递归可枚举语言、上下文无关语言和正规语言。这四种文法类型依次拥有越来越严格的产生式规则,同时文法所能表达的语言也越来越少。尽管表达能力比无限制文法和上下文相关文法要弱,但由于能高效率的实现,四类文法中最重要的是上下文无关文法和正规文法。例如对上下文无关语言存在算法可以生成高效率的LL 分析器和LR 分析器。

50型文法

设G=(VN,VT,P,S),如果它的每个产生式α→β是这样一种结构:α∈(VN∪VT)*且至少含有一个非终结符,而β∈(VN∪VT)*,则G是一个0型文法。0型文法也称短语文法。一个非常重要的理论结果是:0型文法的能力相当于图灵机(Turing)。或者说,任何0型文语言都是递归可枚举的,反之,递归可枚举集必定是一个0型语言。0型文法是这几类文法中,限制最少的一个,所以我们在试题中见到的,至少是0型文法。

61型文法

1型文法也叫上下文有关文法,此文法对应于线性有界自动机。它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。

注意:虽然要求|β|>=|α|,但有一特例:α→ε也满足1型文法。

如有A->Ba则|β|=2,|α|=1符合1型文法要求。反之,如aA->a,则不符合1型文法。

72型文法[1]

2型文法也叫上下文无关文法,它对应于下推自动机。2型文法是在1型文法的基础上,再满足:每一个α→β都有α是非终结符。如A->Ba,符合2型文法要求。

如Ab->Bab虽然符合1型文法要求,但不符合2型文法要求,因为其α=Ab,而Ab不是一个非终结符

83型文法

3型文法也叫正规文法,它对应于有限状态自动机。正规文法有多种等价的定义,我们可以用左线性文法或者右线性文法来等价地定义正规文法。左线性文法要求产生式的左侧只能包含一个非终结符号,产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号。右线性文法要求产生式的左侧只能包含一个非终结符号,产生式的右侧只能是空串、一个终结符号或者一个终结符号后随一个非终结符号。 它是在2型文法的基础上满足:A→α|αB(右线性)或A→α|Bα(左线性)。

如有:A->a,A->aB,B->a,B->cB,则符合3型文法的要求。但如果推导为:A->ab,A->aB,B->a,B->cB或推导为:A->a,A->Ba,B->a,B->cB则不符合3型方法的要求了。具体的说,例子A->ab,A->aB,B->a,B->cB中的A->ab不符合3型文法的定义,如果把后面的ab,改成“一个终结符+一个非终结符”的形式(即为aB)就对了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改为B->Bc的形式就对了,因为A→α|αB(右线性)和A→α|Bα(左线性)两套规则不能同时在一个语法中出现,只能完全满足其中的一个,才能算3型文法。

参考资料

  1. 形式文法,搜狗, 2016-05-13