状态转换图
状态转换图是词法分析器的重要组件之一。
点（状态 state）：表示在识别词素时可能出现的情况
状态看作是已处理部分的总结，某些状态为接受状态或最终状态，表明已经找到词素；
开始状态（初始状态）：用Start边表示
边（转换 Transition）：从一个状态指向另一个状态
边的标号是一个或多个符号，当前状态为s，下一个输入符号为a，就沿着从s离开，标号为a的边到达下一个状态
保留字和标识符的区别
在很多时候，保留字也符合标识符的模式，识别标识符的状态转换图也会识别保留字。
解决方法：
在符号表中先填保留字，并指明它们不是普通标识符。
为保留字建立独立的、高优先级的状态转换图
词法分析器的体系结构
从转换图构造词法分析器的方法：
变量State记录当前状态
一个switch根据State的值转到相应的代码
每个State对应于一段代码，这段代码根据读入的符号，确定下一个状态，如果找不到相应的边，则调用
fail()进行错误恢复进入某个接受状态时，返回相应的词法单元，注意有
*标记时，需要回退forward指针。
实际是模拟转换图的运行。
词法分析工具Lex/Flex
Lex/Flex是一个有用的词法分析器生成工具，Flex是最近的实现。支持用regexp描述词法单元的模式，给出一个词法分析器的规约。
输入表示：Lex语言
工具本身：是一个编译器，Lex编译器
核心：将输入的模式转换为状态转换图，并生成代码
通常和YACC/Bison一起使用，生成编译器的前端。
Lex中的冲突解决方法
冲突：多个输入前缀与某个模式相匹配，或者一个前缀与多个模式匹配
多个前缀可能匹配时，选择最长的前缀
某个前缀和多个模式匹配时，选择列在前面的模式（比如如果保留字的规则在标识符的规则之前，词法分析器将识别出保留字）
Last updated