状态转换图

状态转换图是词法分析器的重要组件之一。

• 点（状态 state）：表示在识别词素时可能出现的情况

  状态看作是已处理部分的总结，某些状态为接受状态或最终状态，表明已经找到词素；

  开始状态（初始状态）：用Start边表示

• 边（转换 Transition）：从一个状态指向另一个状态

  边的标号是一个或多个符号，当前状态为s，下一个输入符号为a，就沿着从s离开，标号为a的边到达下一个状态

保留字和标识符的区别

在很多时候，保留字也符合标识符的模式，识别标识符的状态转换图也会识别保留字。

解决方法：

1. 在符号表中先填保留字，并指明它们不是普通标识符。

1. 为保留字建立独立的、高优先级的状态转换图

词法分析器的体系结构

从转换图构造词法分析器的方法：

• 变量State记录当前状态

• 一个switch根据State的值转到相应的代码

• 每个State对应于一段代码，这段代码根据读入的符号，确定下一个状态，如果找不到相应的边，则调用fail() 进行错误恢复

• 进入某个接受状态时，返回相应的词法单元，注意有* 标记时，需要回退forward 指针。

实际是模拟转换图的运行。

词法分析工具Lex/Flex

Lex/Flex是一个有用的词法分析器生成工具，Flex是最近的实现。支持用regexp描述词法单元的模式，给出一个词法分析器的规约。

• 输入表示：Lex语言

• 工具本身：是一个编译器，Lex编译器

• 核心：将输入的模式转换为状态转换图，并生成代码

通常和YACC/Bison一起使用，生成编译器的前端。

Lex中的冲突解决方法

冲突：多个输入前缀与某个模式相匹配，或者一个前缀与多个模式匹配

• 多个前缀可能匹配时，选择最长的前缀

• 某个前缀和多个模式匹配时，选择列在前面的模式（比如如果保留字的规则在标识符的规则之前，词法分析器将识别出保留字）