正则表达式

复习

• 手写词法分析器：逐字符判断并产出词法单元
• 字符怎样组成词：词法单元的类别
• 语言与文法：用规则描述语言

TL;DR

• 正则表达式用组合规则描述一类字符串
• 常见运算：连接、选择、重复
• 它能精确描述大多数词法模式
• 把词法规则写成正则，清晰又简洁

正文

　　手写词法分析器时，我们是用文字描述的规则（“字母开头、后面跟字母数字”）。这一章介绍一种更精确、更紧凑的描述工具：正则表达式（regular expression）。

几个基本运算

　　正则表达式用寥寥几个运算，就能描述一大类字符串：

• 连接：把两段模式接起来，比如 ab 表示先 a 后 b
• 选择：用 | 表示“或”，比如 a|b 表示 a 或 b
• 重复：用 * 表示“零次或多次”，+ 表示“一次或多次”，? 表示“零次或一次”

　　再配合字符类，比如 [A-Za-z] 表示任意一个字母，[0-9] 表示任意一个数字，就能描述很多词法模式了。

描述词法规则

　　拿标识符来说，“字母或下划线开头，后面跟零个或多个字母、数字或下划线”，用正则写出来是：

[A-Za-z_][A-Za-z0-9_]*

　　数字字面量可以是：

[0-9]+

　　是不是又精确又简洁？一条正则，就对应一条词法规则。把每种词法单元都用一条正则描述出来，词法规则就一清二楚了。

它也有边界

　　不过，正则表达式的能力是有上限的。它能描述“重复”，却无法描述任意深度的嵌套。

　　比如“任意多层配对的括号”，就很难用正则表达。因为正则本质上没有“数数”“记住嵌套深度”的能力。而程序语言里，括号、语句块、函数嵌套到处都是——这就超出了正则的射程。

　　所以，正则适合处理词法层面的模式；而要处理嵌套的语法结构，就需要更强的工具：文法（下一组要讲的上下文无关文法）。先分清两层问题的边界，才不会用错工具。

　　那么，正则和词法分析器之间，有没有更省力的自动化桥梁？下一章来看。

思考题 1

正则表达式里的“重复”和“选择”运算，分别用来描述什么？

思考题 2

为什么正则表达式能描述标识符，却难以描述“任意嵌套的括号”？

小结

知识点

• 正则表达式用连接、选择、重复描述字符串模式
• 字符类可简洁表示一类字符
• 每条词法规则常可写成一条正则
• 正则无法描述任意深度的嵌套

参考资料

1. Wikipedia(zh)：正则表达式：描述字符串模式的形式语言
2. Wikipedia(zh)：正则语言：可由正则表达式描述的语言

思考题答案（仅供参考）

思考题 1

　　“重复”用来描述某个模式连续出现若干次，比如标识符后面可以跟任意多个字母数字；“选择”用来描述若干种可能中任选其一，比如一个字符可以是字母或下划线。

思考题 2

　　因为正则表达式没有“记住嵌套深度、成对匹配”的能力，它天生只适合描述有限状态能识别的模式。括号的任意嵌套需要“数层数”，超出了正则的表达范围，必须借助文法来描述。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪