编译器设计 - 正则表达式
词法分析器需要扫描并识别属于手头语言的一组有限的有效字符串/标记/词素。它会搜索语言规则定义的模式。
正则表达式能够通过为有限符号字符串定义模式来表达有限语言。由正则表达式定义的语法称为正则语法。由正则语法定义的语言称为正则语言。
正则表达式是指定模式的重要符号。每个模式匹配一组字符串，因此正则表达式可用作一组字符串的名称。编程语言标记可以用正则语言来描述。正则表达式的规范是递归定义的一个例子。正则语言易于理解，实现高效。
正则表达式遵循许多代数定律，这些定律可用于将正则表达式转换为等效形式。
操作
语言的各种操作包括：
两种语言 L 和 M 的并集写为
L U M = {s | s 在 L 中或 s 在 M 中
两种语言 L 和 M 的串联写为
LM = {st | s 在 L 中，t 在 M 中
语言 L 的 Kleene 闭包写为
L* = 语言 L 出现零次或多次。
符号
如果 r 和 s 是表示语言 L(r) 和 L(s) 的正则表达式，则
Union : (r)|(s) 是一个表示 L(r) U L(s) 的正则表达式
Concatenation : (r)(s) 是一个表示 L(r)L(s) 的正则表达式
Kleene 闭包 : (r)* 是一个表示 (L(r))* 的正则表达式
(r) 是一个表示 L(r) 的正则表达式
优先级和结合性
- *、连接 (.) 和 | (管道符号) 是左结合的
- * 具有最高优先级
- 连接 (.) 具有第二高的优先级。
- | （管道符号）的优先级最低。
用正则表达式表示语言的有效标记
如果 x 是正则表达式，则：
x* 表示 x 出现零次或多次。
即，它可以生成 { e, x, xx, xxx, xxxx, …
x+ 表示 x 出现一次或多次。
即，它可以生成 { x, xx, xxx, xxxx … } 或 x.x*
x? 表示 x 最多出现一次
即，它可以生成 {x} 或 {e}。
[a-z] 是所有英语小写字母。
[A-Z] 是所有英语大写字母。
[0-9] 是数学中使用的所有自然数字。
使用正则表达式表示符号的出现
字母 = [a – z] 或 [A – Z]
数字 = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 或 [0-9]
符号 = [ + | - ]
使用正则表达式表示语言标记
十进制 = (符号)?(数字)+
标识符 = (字母)(字母 | 数字)*
词法分析器剩下的唯一问题是如何验证用于指定语言关键字模式的正则表达式的有效性。一个广为接受的解决方案是使用有限自动机进行验证。
