词法分析

词法分析：按序扫描源程序，识别出单词，得到单词记录（单词记号(token)、属性值）

案例：

源代码

1
int a = 10;

得到的词法分析

1
2
3
4
5
类型标识   int
标识符     a
赋值运算符(=)
整数常量   10
分号(;)

单词描述工具

扩展巴克斯范式（EBNF）

1726639227633

状态转换图

1726639252333

需要注意的技术细节

  • 如何识别保留字
  • 字符退还：在遇到<后，为了判断是否是<=运算符，需要额外读取一个字符，此时若不是=则需要退还

词法分析程序的自动构造

  1. 定义正规表达式，如$(0+1)^*$
  2. RE → ε-NFA
  3. 把每个ε-NFA整合成一个大的ε-NFA
  4. ε-NFA → DFA
  5. DFA最小化

注： 对于部分情况，直接设计DFA可能会比设计RE更容易，此时可以直接设计DFA