摘自维基百科
http://en.wikipedia.org/wiki/
【形式文法】
在计算机科学中，形式语言是：某个字母表上，一些有限长字串的集合，而形式文法是描述这个集合的一种方法。形式文法之所以这样命名，是因为它与人类自然语言中的文法相似的缘故。
形式文法描述形式语言的基本想法是，从一个特殊的初始符合出发，不断的应用一些产生式规则，从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。
一个形式文法 G 是下述元素构成的一个四元组(N, Σ, P, S)：
- “非终结符号”集合 N。
- “终结符号”集合 Σ ，Σ 与 N 无交。
- 取如下形式的一组“产生式规则” P，
- (Σ ∪ N)*中的字符串 → (Σ ∪ 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年提出的。它包括四个层次：
- 0-型文法（无限制文法或短语结构文法）包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串，这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别，后者是前者的一个真子集，是能够被一个总停机的图灵机判定的语言。
- 1-型文法（上下文相关文法）生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号，而 α, β 和 γ 是包含非终结符号与终结符号的字串；α, β 可以是空串，但 γ 必须不能是空串；这种文法也可以包含规则 S->ε ，但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。
- 2-型文法生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号，γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。
- 3-型文法（正规文法）生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号；如果所有产生式的右侧都不含初始符号 S ，规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受，也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。
正规语言类包含于上下文无关语言类，上下文无关语言类包含于上下文相关语言类，上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系，也就是说：存在递归可枚举语言不属于上下文相关语言类，存在上下文相关语言不属于上下文无关语言类，存在上下文无关语言不属于正规语言类。
下表总结了上述四种类型的文法的主要特点：
| 文法 |
语言 |
自动机 |
产生式规则 |
| 0-型 |
递归可枚举语言 |
图灵机 |
无限制 |
| 1-型 |
上下文相关语言 |
线性有界非确定图灵机 |
αAβ -> αγβ |
| 2-型 |
上下文无关语言 |
非确定下推自动机 |
A -> γ |
| 3-型 |
正规语言 |
有限状态自动机 |
A -> aB
A -> a
|
这个分类谱系把所有的文法分成四种类型：无限制文法、上下文相关文法、上下文无关文法和正规文法。四类文法对应的语言类分别是递归可枚举语言、上下文相关语言、上下文无关语言和正规语言。这四种文法类型依次拥有越来越严格的产生式规则，同时文法所能表达的语言也越来越少。尽管表达能力比无限制文法和上下文相关文法要弱，但由于能高效率的实现，四类文法中最重要的是上下文无关文法和正规文法。例如对上下文无关语言存在算法可以生成高效率的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 的字串为 Σn ， Σ* 为 Σ0∪Σ1∪…∪Σn∪…， 语言 L 定义为 Σ* 的任意子集。
注记：Σ* 的空子集 ∅ 与 {ε} 是两个不同的语言。
语言间的运算
语言间的运算就是 Σ*幂集上的运算。
- 字符串集合的交并补等运算。
- 连接运算：L1L2 = { xy | x 属于L1并且 y 属于L2 }。
- 幂运算：Ln = L … L （共 n 个 L 连接在一起），L0 = {ε}。
- 闭包运算：L* = L0∪L1∪…∪Ln∪…。
- 右商运算：L1/L2 = {x | 存在 y 属于L2使得 xy 属于L1}。
- 设 S ⊆ Σ* 是一个语言，S 的补语言定义为集合 {ω | ω ∈ Σ* 且 ω ∉ S}
语言的表示方法
一个形式语言可以通过多种方法来限定自身，比如：