编译原理之正则文法和有限自动机

手工打造词法分析器的过程，就是写出正则表达式，画出有限自动机的图形，然后根据图形直观地写出解析代码的过程。

• 先来解析一下“age >= 45”这个关系表达式，这样就能理解有限自动机的概念，知道它是做词法解析的核心机制了。

解析关系表达式

词法分析中的有限自动机示意图

• 标识符、比较操作符和数字字面量这三种 Token 的词法规则
  • 标识符：第一个字符必须是字母，后面的字符可以是字母或数字。
  • 比较操作符：> 和 >=（其他比较操作符暂时忽略）。
  • 数字字面量：全部由数字构成（像带小数点的浮点数，暂时不管它）。

有限自动机图示

• 上图中圆圈有单线的也有双线的。双线的意思是这个状态已经是一个合法的 Token 了，单线的意思是这个状态还是临时状态。

解释上图的 5 种状态

1. 初始状态：刚开始启动词法分析的时候，程序所处的状态。
2. 标识符状态：在初始状态时，当第一个字符是字母的时候，迁移到状态 2。当后续字符是字母和数字时，保留在状态 2。如果不是，就离开状态 2，写下该 Token，回到初始状态。
3. 大于操作符（GT）：在初始状态时，当第一个字符是 > 时，进入这个状态。它是比较操作符的一种情况。
4. 大于等于操作符（GE）：如果状态 3 的下一个字符是 =，就进入状态 4，变成 >=。它也是比较操作符的一种情况。
5. 数字字面量：在初始状态时，下一个字符是数字，进入这个状态。如果后续仍是数字，就保持在状态 5。

依据构造好的有限自动机，在不同的状态中迁移，从而解析出 Token 来。只要再扩展这个有限自动机，增加里面的状态和迁移路线，就可以逐步实现一个完整的词法分析器了。

正则表达式

• 第一个字符必须是字母，后面的字符可以是字母或数字。这样描述规则并不精确，需要换一种严谨的表达方式，这种方式就是正则表达式。
• age >= 45涉及了 4 种 Token，这 4 种 Token 用正则表达式表达，是下面的样子：

Id :        [a-zA-Z_] ([a-zA-Z_] | [0-9])*
IntLiteral: [0-9]+
GT :        '>'
GE :        '>='

那么在词法分析器中，如何把关键字和保留字跟标识符区分开呢？

• 以“int age = 40”为例，我们把有限自动机修改成下面的样子，借此解决关键字和标识符的冲突。