1.3 正则 与 词法表示

从现在开始，我们以一种新定义的语言 Tiger 为例。我们使用正则表达式来定义 Tiger 的词法。

Tiger 的 Token 定义如下：

• KEYWORD："else" | "if" | "let" | "var" | "type" | "for" | "function" | "do" | "while" | "then" | "end" | ...；
• NUMBER：[0-9]+（某些编程语言的 re 库中表示为 \d+）；
• ID：[a-zA-Z_][a-zA-Z_0-9]*；
• WHITESPACE：(' ' | '\t' | '\n')+（re: \s）；
• LEFTPAR / RIGHTPAR：'(' / ')'；
• OPERATORS：'+' | '-' | '*' | '/'；
• ……

可能有些 Lexeme 符合多种 token 的定义，因此会规定 token 优先级。

规定了一种语言的词法，接下来要考虑的是如何实现。那么如何实现正则表达式？答案是采用一种特殊的数据结构：有限自动机（FA）。

总体路径如下：

RegExp -> NFA -> DFA -> Tables；