woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

形式文法

形式文法

  在计算机科学中,形式语言是某个字母表上一些有限长字串的集合,而形式文法是描述这个集合的一种方法。形式文法之所以这样命名,是因为它与人类自然语言中的文法相似的缘故。

  形式文法描述形式语言的基本想法是,从一个特殊的初始符合出发,不断的应用一些产生式规则,从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。举例来说,假设字母表只包含 '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 中的产生式规则而得到。

例子

  考虑如下的文法 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-系统可以用于模拟细胞的生长,所以又被称为发展系统。

[编辑本段]

文法的分类

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

0型文法

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

1型文法

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

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

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

2型文法

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

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

3型文法

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型文法。

  注意:上面例子中的大写字母表示的是非终结符,而小写字母表示的是终结符。

posted on 2009-03-23 13:05 肥仔 阅读(349) 评论(0)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理