形式文法
维基百科，自由的百科全书
在计算机科学中，形式语言是某个字母表上一些有限长字串的集合，而形式文法是描述这个集合的一种方法。形式文法之所以这样命名，是因为它与人类自然语言中的文法相似的缘故。
形式文法描述形式语言的基本想法是，从一个特殊的初始符合出发，不断的应用一些产生式规则，从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。举例来说，假设字母表只包含 '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)* 中的字串字串，并且产生式左侧的字串中必须至少包括一个非终结符号。
- 起始符号 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-系统可以用于模拟细胞的生长，所以又被称为发展系统。
[编辑] 文法的分类
某些类型的文法及其产生的语言得到了细致的研究并被单独命名。最常见的文法的分类系统是诺姆·乔姆斯基于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 -> ε
