形式文法

维基百科,自由的百科全书
跳转到: 导航, 搜索

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

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

  • 非终结符号”集合 N
  • 终结符号”集合 Σ ,Σ 与 N 无交。
  • 取如下形式的一组“产生式规则P
(Σ ∪ N)*中的字符串 → (Σ ∪ N)* 中的字符串,并且产生式左侧的字符串中必须至少包括一个非终结符号。
  • 起始符号SS 属于 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 的字串。

又如以下的文法G,其中N = {S, D}, Σ = {-, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, P包含如下规则:

1. S -> -D
2. S -> D
3. D -> 0D
4. D -> 1D
5. D -> 2D
...
12. D -> 9D
13. D -> 0
14. D -> 1
15. D -> 2
...
22. D -> 9

S为初始符号。以此文法可以产生所有整数。

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

[编辑] 文法的分类

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

[编辑] 上下文无关文法

上下文无关文法要求产生式左侧只能包含一个非终结符号。上例定义的语言并不是一个上下文无关语言,但 { anbn | n > 0 }是一个上下文无关语言。具体如下,文法G2 包括 N={S}, Σ={a,b}, S 是起始符号,产生式规则有:

1. S -> aSb
2. S -> ab

[编辑] 正规文法

正规文法有多种等价的定义,我们可以用左线性文法或者右线性文法来等价地定义正规文法:

  • 左线性文法要求产生式的左侧只能包含一个非终结符号,产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号
  • 右线性文法要求产生式的左侧只能包含一个非终结符号,产生式的右侧只能是空串、一个终结符号或者一个终结符号后随一个非终结符号

上例定义的语言 { anbn | n > 0 } 不是一个正规语言。下面给出一个正规语言的例子,语言 { anbm | m,n > 0 } 是一个正规语言。文法G3 包括 N={S,A,B}, Σ={a,b}, S 是起始符号,产生式规则有:

1. S -> aA
2. A -> aA
3. A -> bB
4. B -> bB
5. B -> ε

[编辑] 引用


[编辑] 参见

[编辑] 外部链接


自动机理论: 形式语言和形式文法
乔姆斯基层级 文法 语言 极小自动机
类型 0 无限制 递归可枚举 图灵机
n/a (无公用名) 递归 判定器
类型 1 上下文有关 上下文有关 线性有界
n/a 附标 附标 嵌套堆栈
n/a 树-邻接 适度上下文有关 嵌入下推
类型 2 上下文无关 上下文无关 非确定下推
n/a 确定上下文无关 确定上下文无关 确定下推
类型 3 正则 正则 有限
每个语言或文法范畴都是其直接上面的范畴的真子集
::...
免责声明:
当前网页内容, 由 大妈 ZoomQuiet 使用工具: ScrapBook :: Firefox Extension 人工从互联网中收集并分享;
内容版权归原作者所有;
本人对内容的有效性/合法性不承担任何强制性责任.
若有不妥, 欢迎评注提醒:

或是邮件反馈可也:
askdama[AT]googlegroups.com


点击注册~> 获得 100$ 体验券: DigitalOcean Referral Badge

订阅 substack 体验古早写作:


关注公众号, 持续获得相关各种嗯哼:
zoomquiet


自怼圈/年度番新

DU22.4
关于 ~ DebugUself with DAMA ;-)
粤ICP备18025058号-1
公安备案号: 44049002000656 ...::