文法是用于描述语言的语法结构的形式规则。形式语言的理论自1956年由乔姆斯基（Chomsky）建立以来，发展很快，对计算机科学有着深刻影响。常见的描述语言的文法有：蒙塔格文法（Montague Grammar），基于知识的概念依存文法，语义描述的格文法以及Chomsky的转换生成文法。Chomsky 的转换生成文法分为四类，即短语文法（0型文法）、上下文有关文法（1型文法）、上下文无关文法（2型文法）和正规文法（3型文法），其中正规文法又被称为线性文法，分为左线性文法和右线性文法两种形式。正规文法是正规语言的形式化描述，用于正规语言的形式化表示和理论研究， 主要用来描述符号串, 在编译程序设计中常用来识别单词。
文法的终结符和非终结符：\(\alpha \rightarrow \beta\)
终结符：不能够单独出现在推导式左端的符号；一个程序可以推导出很多语句来，终结符属于最终状态的原子量，不可以拆分，一般小写字母表示，如 a, b。
非终结符：可以拆分的元素，通常用大写字母表示，如A，B，S等。
- 0型文法： \(G = (V_N, V_T,P, S)\)，其中 \(V_N\), \(V_T\), \(P\), \(S\) 分别表示非终结符、终结符、规则集合以及开发符号，如果它的每个产生式 \(\alpha \rightarrow \beta\)都是 \(\alpha \in (V_N \cup V_T)^*\)且至少含有一个非终结符，而\(\beta\in (V_N \cup V_T)^*\)，则 G 是一个 0 型文法。
- 1型文法：在0型文法的基础上，每一个 \(\alpha \rightarrow \beta\) 都有 \(|\beta|>=|\alpha|\)，即后面这个量的长度大于等于前面的量的长度。注意特例：\(\alpha \rightarrow ε\)，\(ε\)表示空白符，可作为终结符。
- 2型文法：是在1型文法的基础上再满足：每一个\(\alpha \rightarrow \beta\)都有 α 是非终结符。如 A->Ba,符合2型文法要求。
- 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型文法要求。
正规式与正规文法之间的转换：
文法产生式 正规式
规则1：A->xB, B->y A=xy
规则2：A->xA|y A=x*y
规则3：A->x, A->y A = x|y
2. 什么是有限自动机？
1. DFA ：一个确定的有限自动机（记作 DFAM），M 是一个五元组；\(M=(S,\Sigma,f,S_0,Z)\)，其中
- S 是一个有限状态集合；
- \(\Sigma\) 是一个字母表，它的每个元素称为一个输入字符；
- f 是一个从 \(S \times \Sigma\) 到 S 的单值部分映射。\(f(S,a) = S'\)意味着 状态为S, 输入字符为a 时，将转换到下一个状态 \(S'\)。称 \(S'\) 为 S 的一个后继状态；
- \(S_0 \in S\) 是唯一的初态；
- \(Z \subseteq S\) 是一个终态集。
DFA = \((\{S,A,B,C,f\},\{1,0\}, F,S,\{f\})\)，其中 F(S,0) = B, F(S,1) = A, F(A,0) = f, F(A,1) = C, F(B, 0) = C, F(B, 1) = f, F(C, 0) = f, F(C, 1) = f，对应的状态转换图如下所示：
NFA ：不确定的有限自动机，定义与DFA基本一致，唯一区别在于\(S_0 \subseteq S\) 是一个非空初态集；
2. NFA 转化为 DFA
从一个状态输入一个值，不能得到一个确定的状态，如 F(3,0)=4, 或 F (3,0) = 5 或 F (3,0) = Z
| 当前状态：I | 输入0之后得到的状态：I0 | 输入1之后得到的状态：I1 |
| {S,1,2,3} | {1,3,4,5,Z} | {2,3} |
| {1,3,4,5,Z} | T1= {1,3,4,5,6} | T3 = {} |
| {2,3} | {4,5,Z} | {2,3} |
| T2 = {4，5，Z} | {6} | T3 |
| T1 | {1,3,4,5,6,Z} | {5,Z} |
| {6} | T3 | {5,Z} |
| {5,Z} | {6} | T3 |
| 当前状态：I | 输入0之后得到的状态：I0 | 输入1之后得到的状态：I1 |
| {S,1,2,3} 新的0状态 | {1,3,4,5,Z}新的1状态 | {2,3}新的2状态 |
| {1,3,4,5,Z}新的1状态 | T1= {1,3,4,5,6，Z} 新的6状态 |
T3 = {} |
| {2,3} | {4,5,Z}新的3状态 | {2,3} |
| T2 = {4，5，Z} | {6} | T3 |
| T1 新的6状态 | {1,3,4,5,6,Z} | {5,Z} |
| {6} | T3 = {} | {5,Z}新的5状态 |
| {5,Z} | {6}新的4状态 | T3 = {} |
3. 正规式与有限自动机之间的转化规则：
例题：把下面的正规式转成有限自动机：\((\_ | a)(\_|a|d)^*\)
扩展：
- 乔姆斯基（Avram Noam Chomsky，1928年12月7日—），美国哲学家。是麻省理工学院语言学的荣誉退休教授。乔姆斯基的《句法结构》被认为是20世纪理论语言学研究上最伟大的贡献。乔姆斯基的文法理论，在计算机领域中真正被使用的只有两者：3型文法和2型文法。前者的特征是语法中不存在递归下降结构，它的代表是基本正则表达式（扩展后的正则表达式情况略有不同）；而二型文法即上下文无关文法，特征是任何语言元素在任何上下文中的含义始终保持一致。事实上，多数如今的程序设计语言语法都以此为基础。以上两者构成了如今所有实用计算机程序设计语言的分析器理论基础，也有成熟的数据结构和算法支持：三型文法的 NFA/DFA，以及二型文法的递归下降/LL(x)/LR(x)/LALR(x)。而再向上的一型文法（上下文有关文法）和零型文法（任意图灵机可识别文法），计算机工程界则通常不会涉足。虽然有些时候，我们会开玩笑地将一些语法发展得极其复杂的语言称为上下文有关语言，比如 Perl；但事实上，这类语言仍然是通过二型文法进行分析，只是通过增补一部分规则来解决；至于真正可以解析上下文有关文法的线性有界自动机，则可以肯定地说，没有程序语言开发者会试图实现。顺便说一句，1型文法事实上可以用来表述许多自然语言，拿来表述程序设计语言，多少有点杀鸡用牛刀的意思。
PDF下载：正规文法与有限自动机的等价性_1109.pdf
参考资料：