实际项目中，
有很多需要处理字符串的场景，
判断用户输入的文本是否合法，
从一段文本中提取一些信息，
等等。
正则表达式，
简直是神兵利器，
一般的问题，都可以轻易解决。
然而，
它也不是万能的，
有着自身的能力范围。
例如，
我们无法用正则表达式处理JSON，
无法用正则表达式分析HTML，
甚至无法从一段代码中把嵌套注释提取出来。
是不是我们写的不好，
有没有精巧的写法，
来达到上述目的呢？
一般而言，
要证明可以，只需要一个例子就行，
而要证明不可以，就很难了。
所以，
我们要好好学习一下理论基础，
看一下正则表达式的真面目。
形式语言
日常生活中，
也有这样的认识，
我们所了解的汉字是有限的，
但是我们能说的话，却是无限的。
因为，至少我们可以说出任意长度的汉字序列。
程序语言也是如此。
有人说编程，不就是输入A到Z吗，
指的就是这个编程语言的“字母表”，
字母表所包含的字母，是有限的，
但是可以写出无限多个“句子”。
“语言”，正是这些“句子”的集合。
事实上，
以上简短的描述中，
包含了很深刻的思想。
当初，为了研究语言的性质，
人们从两个角度出发，
一个是从语言的识别角度来看，
有一套自动机理论。
另一个是从语言的生成角度来看，
有乔姆斯基开创的形式语言理论。
而这两个理论之间，
又是互相关联的。
在形式语言理论中，
一个形式语言，
是一个字母表上的某些有限长字符串的集合。
这给了我们用有限来描述无限的能力。
文法
为了描述语言的结构，
John Backus和Peter Naur创造了一种语言的描述方法，
称为BNF（Backus-Naur Form）。
expr ::= term {"+" term | "-" term}.
term ::= factor {"*" factor | "/" factor}.
factor ::= "(" expr ")".
BNF表示中的每一行，称为一个“产生式”，
::=表示左边的项可以由右边的项来产生。
其中，用引号括起来的项，称为“终结符”，相当于字面量。
不用引号括起来的项，称为“非终结符”，它们可以由其他项组成。
{...}是约定好了的符号，
用来表示它包含的项可以出现0次或更多次。
常用的还有[...]，
用来表示，可以出现也可以不出现。
以上BNF描述了算术表达式的语法。
例如：1*(2+3)，可以从exp开始生成出来，
expr
=> factor "*" factor
=> factor "*" "(" expr ")"
=> factor "*" "(" term "+" term ")"
=> 1 "*" "(" 2 "+" 3 ")"
expr称为“开始符号”。
综上，
一个语言的所有终结符，非终结符，产生式，开始符号，
构成了这个语言的文法。
语言的分类
乔姆斯基，根据语言文法产生式的特点，
把语言分为了4类。
不同的文法，能描述不能范围的语言集合。
虽然它们都是无限集。
0型文法，能力最强，可以产生递归可枚举语言。
1型文法，能力稍弱，可以产生上下文有关语言。
2型文法，能力次之，可以产生上下文无关语言。
3型文法，能力最弱，可以产生正则语言。
这些文法，
建立了一个从大到小，互相包含的，
语言集合的层次关系。
例如：
正则语言，一定是上下文无关语言，
反之，则不成立。
其中，
2型和3型文法用的最多，有特殊的名字，
称为，上下文无关文法，正则文法。
我们似乎发现了，
这里也出现了“正则”两个字，
难道与正则表达式有关？
确实，
正则表达式，是正则文法的便利写法。
正则表达式所描述的语言，是正则语言。
而JSON，HTML，包含嵌套注释文本，
它们都属于上下文无关语言，
正则表达式是无能为力的。
那么如何判断语言不是正则语言呢？
这还需要用到泵引理这个重要工具。
水深危险。
自动机
自动机，是一种假想的机器，
常被人提及的是“图灵机”。
它是各种自动机中运算能力最强的机器。
当初为了准确定义什么是“算法”，
图灵发明了它。
图灵机有一条无限长的纸带，
纸带分成了一个个小方格，每个方格有不同的颜色。
有一个具有内部状态的机器头在纸带上移来移去。
机器头根据自身状态和当前方格的颜色，
来决定下一步的位置。
这么简易的装置，
居然具有和现代计算机同等的计算能力。
实际上，现代计算机就是从这个思想逐渐演化而来的。
自动机，也可以用来识别语言。
而且，与形式语言还有着优美的对应关系。
图灵机，能识别0型文法所生成的语言。
为图灵机加上限制，下推自动机，识别上下文无关语言，
有穷自动机，识别正则语言。
在程序语言的编译器设计中，
这些理论是非常重要的。
我们通过正则文法，构建有穷自动机，
对字符流进行分词（tokenize）。
通过上下文无关文法，构建下推自动机，
对词汇流进行解析（parse）。
计算模型
形式语言和自动机，
可以看做是两种计算模型，
它们从不同的角度描述了同一个问题。
其他的计算模型，还有很多。
lambda演算就是一个，
它是一个符号化的形式系统，
用来研究函数及其函数的调用。
递归函数论，又是一个，
它从递归的角度，
为可计算性划分了界限。
命题逻辑，也是，
它是逻辑系统的演算规则，
用来研究推理过程。
然而，这些计算模型的计算能力，
都等价于图灵机。
这一结论称为，Church-Turing论题。
结语
各种计算模型，虽然在能力上是相同的，
但是它们各有所长，
于是被用到了形形色色的地方。
例如，
形式语言，可以用来研究语言的结构，
自动机，可以用来识别语言。
lambda演算，可以用来研究语言的操作语义。
递归函数论，可以用来研究语言的指称语义。
命题逻辑，可以用来研究语言的类型系统。
编程世界，
原来这么好玩。
其实编程，不就是输入A到Z吗？
参考：
A Mathematical Introduction to Logic
Language Implementation Patterns
Lambda-Calculus and Combinators