AllenYoung

2008-03-05

关键字: 正则表达式

正则表达式想必大家都用过，确实是很好很强大的东东。但是正则表达式的形式化定义各位知道吗？最近无聊看一本编译方面的书时，里面正好讲到了这个，还是挺有意思的。发出来和大家分享。

首先，正则表达式是一种符号表示法，是为了用有限的描述来详细说明（可能）无限的语言。也就是说正则表达式是针对某个特定语言的，可以说每个正则表达式都定义了一种语言。每个正则表达式代表一个字符集。在正则表达式中，需要定义如下几个概念：

符号：对语言字母表中的每个符号a，正则表达式a表示仅包含字符串a的语言。
或：对于给定的两个正则表达式M和N，可以利用或操作（|）连接为一个新的正则表达式：M|N。若一个字符串属于语言M或语言N，那么此串也属于语言M|N。因此，语言a|b包含两个字符串a和b。
并：对于给定的两个正则表达式M和N，可以利用并操作（·）将其连接为新的正则表达式M·N。设α是语言M的字符串，β是语言N的字符串，若一个字符串是α与β的并，那么这个字符串属于语言M·N。因此，正则表达式(a|b)·a定义包含两个字符串aa和ba的语言。
ε：正则表达式ε代表了一个只包含空串的语言。因此(a·b)|ε表示语言{"", "ab"}。
重复：对于正则表达式M，其Kleene闭包是M*。若一个字符串为空或者它是M中所有字符串经过并操作所得到的结果，那么它就属于M*。

以上这些概念就完整的定义了正则表达式，其中并没有我们所熟悉的那一套规则。不过其实那些规则都是用以上这些概念推导出来的，下面举几个简单的例子。在举例之前，再交代一下，并操作符和ε在书写时是可以省略的，而Kleene闭包的优先级高于并操作，并操作的优先级高于或操作。

你看，现在的正在表达式已经像回事儿了。接下去要做的无非就是引入特殊字符（.，\w，\s之类的）、贪婪模式、分组匹配等东东，不过核心的形式化模型就是上面的那些概念。

还真是佩服研究这种东西的人，可以把一个东东做的在理论和实战领域都这么优雅。