词法单元的识别

状态转换图

作为构造词法分析器的一个中间步骤，我们首先将模式转换成具有特定风格的流图，称为“状态转换图”。

状态转换图(transition diagram)有一组被称为“状态(state)”的节点或者圆圈。词法分析器在扫描输入串的过程中寻找和某个模式匹配的词素，而转换图中的每个状态代表一个可能在这个过程中出现的情况。

一些重要约定：

1. 某些状态称为接受状态或者最终状态。
2. 如果要将forward回退一个位置，那么我们将在该接受状态附近加一个“*”。
3. 有一个状态被指定为开始状态或称初始状态，该状态由一条没有出发节点、标号为”start”的边指明。

保留字和标识符的识别

识别关键字及标识符时有一个问题要解决。通常像if或者then这样的关键字是被保留的，因此它们虽然看起来像标识符，但它们不是标识符。

id和关键字的状态转换图

我们可以使用两种方法来处理那些看起来像标识符的保留字：

1. 初始化时就将各个保留字填入符号表。符号表条目指明这些不是普通的标识符。
2. 为每个关键字建立单独的状态装换图。

假想的关键字then的状态转换图

基于状态转换图的词法分析器的体系结构

有几种方法可以根据一组状态转换图构造出一个词法分析器。不管整体策略是什么，每个状态总是对应一段代码。
假如有一个变量state保存了一个状态转换图的当前状态编号。有一个switch语句根据state的值将我们转到对应于各个可能状态的相应代码段，执行所需操作。（CRE：switch状态机）

• 几种将switch代码整合到词法分析器中的方法

1. 可以让词法分析器顺序地尝试各个词法单元的状态转换图。然后在每次fail时，它重置forward指针并启动下一个状态转换图。
2. 可以并行地运行各个状态转换图，将下一个输入字符提供给所有的状态转换图，并使每个状态转换图做出它应该执行的转换。
3. 更好的办法，就是将所有的状态转换图合并为一个图。

（END）