编译原理 - 正则表达式

词法分析器需要扫描并识别属于当前语言的有限集合的有效字符串/标记/词素。它搜索由语言规则定义的模式。

正则表达式能够通过定义有限符号串的模式来表达有限语言。由正则表达式定义的语法称为正则语法。由正则语法定义的语言称为正则语言。

正则表达式是指定模式的重要表示法。每个模式匹配一组字符串，因此正则表达式充当一组字符串的名称。编程语言标记可以用正则语言来描述。正则表达式的规范是递归定义的一个例子。正则语言易于理解且具有高效的实现。

正则表达式遵循许多代数定律，这些定律可用于将正则表达式操作成等价形式。

运算

语言上的各种运算有：

• 两个语言L和M的并集写成

  L U M = {s | s属于L或s属于M}

• 两个语言L和M的连接写成

  LM = {st | s属于L且t属于M}

• 语言L的克林闭包写成

  L* = 语言L的零次或多次出现。

表示法

如果r和s是表示语言L(r)和L(s)的正则表达式，则

• 并集：(r)|(s)是表示L(r) U L(s)的正则表达式

• 连接：(r)(s)是表示L(r)L(s)的正则表达式

• 克林闭包：(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]

符号 = [ + | - ]

使用正则表达式表示语言标记

十进制 = (符号)^?(数字)⁺

标识符 = (字母)(字母 | 数字)*

词法分析器剩下的唯一问题是如何验证用于指定语言关键字模式的正则表达式的有效性。一个被广泛接受的解决方案是使用有限自动机进行验证。