编译器设计 - 正则表达式

• 

  简述

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

  正则表达式具有通过为有限的符号串定义模式来表达有限语言的能力。正则表达式定义的文法称为regular grammar. 由正则文法定义的语言称为regular language.

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

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

  运营

  对语言的各种操作是：

  • 两种语言 L 和 M 的并集写成
    L U M = {s | s is in L or s is in M}
  • 两种语言 L 和 M 的连接写成
    LM = {st | s is in L and t is in M}
  • 语言 L 的 Kleene 闭包写成
    L* = Zero or more occurrence of language L.
• 

  符号

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

  • Union: (r)|(s) 是表示 L(r) UL(s) 的正则表达式
  • Concatenation: (r)(s) 是表示 L(r)L(s) 的正则表达式
  • Kleene closure: (r)* 是表示 (L(r))* 的正则表达式
  • (r) 是表示 L(r) 的正则表达式
• 

  优先级和关联性

  • *、连接 (.) 和 | （管道符号）是左关联的
  • * 具有最高优先级
  • 连接 (.) 具有第二高的优先级。
  • | （管道符号）的优先级最低。

  用正则表达式表示一种语言的有效标记

  如果 x 是正则表达式，则：

  • x* 表示 x 出现零次或多次。
    即可以生成{ e, x, xx, xxx, xxxx, ... }
  • x+ 表示 x 出现一次或多次。
    即，它可以生成 { x, xx, xxx, xxxx … } 或 xx*
  • X？表示最多出现一次 x
    即，它可以生成 {x} 或 {e}。
  [az] 是英文的所有小写字母。
  [AZ] 是英文的全部大写字母。
  [0-9] 是数学中使用的所有自然数字。

  使用正则表达式表示符号的出现

  字母 = [a – z] 或 [A – Z]

  数字 = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 或 [0-9]

  符号 = [ + | - ]

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

  小数=（符号）^？(数字) ⁺

  标识符=（字母）（字母|数字）*

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