7.3 语言、形式语言、正则语言和正则表达式

在进一步介绍正则表达式之前，让我们先思考下语言的本质是什么、编译的本质又是什么？编译的输入是程序、输出也是程序，那么程序的本质又是什么？

程序本质上就是一个字符串，而语言呢，可以看成一个由合法程序组成的集合，也就是一个字符串集合。编译是干吗的？一个是判断输入程序是不是源语言中的合法程序，也就是判断一个元素是否属于一个集合，另一个是将源语言中的合法程序转换成目标语言中的合法程序，且两个程序的含义是一致的，也就是将一个集合中的元素映射到另一个集合中的元素上去。

编译原理和语言学的理论基础是集合论，下面用集合论的概念来对语言、程序做一个正式的定义。这些定义对于我们后面的语法分析是至关重要的。

首先介绍几个基本概念：

字母表 Σ 和符号 ： 字母表就是一个有限元素的集合，用 Σ 表示，里面的每个元素称为符号。如： Σ = {0, 1}, Σ = {a, b, …, z} 。从逻辑的角度来说，只要是一个有限的集合，都可以称为字母表，而不用管里面的元素具体是什么，实际使用时一般用字符的集合。

Σ 上的句子 sentence/string ： Σ 上的句子就是一串符号，里面每个符号都属于 Σ ，句子用 s 表示，即 s = θ1 θ2 … θn , θi ∈ Σ , n ∈ N （此处 N 特指自然数集合），如 abcd, “hello world”, 一个 C 源程序 等都是一个句子。

空句子 ε ： 空句子就是没有任何符号的句子，用 ε 表示，空句子也是一个句子，就是上面那个式子中 n = 0 的情况。

下面我们来给语言（language）和编译来下一个正式的定义：

语言 L （language） ： 一个语言就是一个句子集合（a set of sentences），用 L 表示，任何由句子组成的集合都可以被称为一个语言，如：英语就是所有符合英语语法的句子组成的集合，法语就是所有符合法语语法的句子组成的集合， C 语言就是所有能编译成功的 C 源文件的集合，只含一个句子 a 的集合 {a} 是一个语言，集合 {a, ab, abb, …} 也是一个语言， …… 。

编译 ：编译就是给定两个句子集合 Ls （源语言）和 Lo （目标语言）以及一个句子 ss ，判断 ss 是否属于 Ls ，以及在 Lo 中寻找出一个句子 so ，其意义和 ss 相同。

下面介绍一种最特别的语言：

• 形式语言 Σ （Formal language）：基于 Σ 的形式语言是指 Σ 上的所有句子的集合，用 Σ 表示，即： Σ* = { s | s = θ1 θ2 … θn , θi ∈ Σ, n ∈ N }。

可以看出所有语言都是形式语言 Σ 的一个子集。注意：这里说的是形式语言的 子集 ，并 不是 说所有语言都 *是 形式语言。

下面来介绍我们本章的重点：正则语言。

所谓 正则语言（Regular**language）**，是指这样的句子集合：

（1） 只有一个空句子的集合是一个正则语言，只有一个单符号句子的集合也是一个正则语言。如以下每个集合都是一个正则语言：

{ε}, {a}, {b}, …, {z}

注意上面每个集合中都只有一个句子，每个句子要么是空句子、要么只有一个字符。另外注意 {ε} 不要和空集搞混了，空集中没有任何元素，{ε} 中有一个空句子元素。

（2） 如果句子集合 R1 和 R2 是正则语言，则 R1 和 R2 的并集 R 也是一个正则语言，R = R1 ∩ R2。

（3） 如果句子集合 R1 和 R2 是正则语言，则 R1 和 R2 的连接集合 R 也是一个正则语言。连接集合 R = { s1 s2 | s1 ∈ R1, s2 ∈ R2 } 。

（4） 如果句子集合 R 是正则语言，则 R 的重复集合 R 也是一个正则语言，重复集合 R = { s1 s2 … sn | si ∈ R , n ∈ N }，此处 n 可以等于 0 ，此时 R* 中只有一个空句子。

一个正则语言就是一个句子集合，那么我们如何表示这个集合？对于集合，我们可以用枚举法来表示，也可以用特性法来表示。对于正则语言，我们用正则表达式来表示。每个正则语言（句子集合），都可以用一个正则表达式来代表它，同样，每个正则表达式，都有一个对应的句子集合。

正则表达式就是按正则语言的构造方式来表示的：

（1） 只有一个空句子的集合的正则表达式为 ε ，只有一个单符号句子的集合 {θ} 的正则表达式为 θ 。

（2） 如果正则语言 R1 和 R2 的正则表达式为 r1 和 r2 ，那么正则表达式 r1|r2 表示 R1 和 R2 的并集。

（3） 如果正则语言 R1 和 R2 的正则表达式为 r1 和 r2 ，那么正则表达式 r1 r2 表示 R1 和 R2 的连接集合。

（4） 如果正则语言 R 的正则表达式为 r ， 那么正则表达式 r 表示 R 的重复集合 R 。

（5） 正则表达式 (r) 和 r 是等价的。

例如：

正则表达式 a 表示集合 {a}， b 表示集合 {b} ， a|b 表示集合 {a, b} ， ab* 表示集合 {a, ab, abb, abbb, … } 。

以上例子中均用 粗体字 来表示正则表达式。

以上构造规则虽然简单，却可以搭建出复杂、表达功能强大的正则表达式，用简短的正则表达式可以表示出一个很大的句子集合。在这里再次强调一下：一个正则表达式就是一个句子集合，简单的正则表达式可以构造出复杂的正则表达式，也就是说简单的句子集合可以构造出复杂的句子集合。

一个句子如果属于一个正则表达式所代表的句子集合，则称这个句子和此正则表达式匹配。

在实际运用中，正则表达式一般都采用一些简写的方式，最常见的有：

（1）特殊字符

以下 11 个字符： [ ] ^ $ . | ? + ( ) 被保留作特殊用途，如果想使用这些字符的字面值，需要在前面加反斜杠 “\” 转义。另外，一些不便书写的字符可以通过在前面加 “\” 转义，如 \n 和 \t 分别表示换行符和制表符。

（2）字符集

如： [abferx] ，用方括号括起来的字符，表示匹配这些字符中的其中一个，相当于 (a|b|f|e|r|x) 。方括号内的特殊字符不需要转义（ [ ] - ^ 除外），如 [af({] 表示 匹配 “a”, “f”, “{”, “(” 中的其中一个。方扩号内可以使用 “-“ 来定义一个范围，且可以定义多个范围，如 [0-9] 表示匹配单个数字， [a-zA-Z] 表示匹配单个字母。

（3）取反字符集

如： [^abc] ，在方括号内的第一个字符为 ^ ，表示这是一个取反字符集，表示匹配一个不在方括号内部的字符。

（4）*、?和+

* 表示匹配前面的字符（或者由括号括起来的表达式、方括号括起来的字符集）0次或多次；

? 表示匹配前面的字符（或者由括号括起来的表达式、方括号括起来的字符集）0次或1次；

+ 表示匹配前面的字符（或者由括号括起来的表达式、方括号括起来的字符集）1次或多次。

（5）”.” 通配符

. 表示匹配除换行符外的任意字符一次。

正则表达式可以用来表示源程序中的 token ，如：

• 整数 ： [0-9]+
• 小数 ： [0-9]+.[0-9]
• 字符串 ： \”[^\”]\”
• 标识符 ： [_a-zA-Z][_a-zA-Z0-9]*
• 关键字 if ： if

下面再简单介绍一下正则表达式的实现原理：有限状态自动机。