词法分析
任务：扫描源程序，输出单词符号
单词符号类别：基本字，标识符，常数，运算符，界符
问题：单词过长（总是有单词只进来一部分）
解决方法：扫描缓冲区两个半区互补
问题：超前搜索
解决方法：基本字作为保留字；使用保留字表；使用空白符做间隔
设计：
- 给出程序设计语言的单词规范——单词表
- 对照单词表设计识别该语言所有单词的状态转换图
- 根据状态转换图编写词法分析程序
仅由有限次使用上述三步骤而定义的表达式才是S上的正规式，仅由这些正规式表示的字集才是S上的正规集。
正规式的性质
交换律：e1|e2 = e2|e1
结合律：e1 |(e2|e3) = (e1|e2)|e3 ; e1(e2e3) = (e1e2)e3
分配律：e1(e2|e3) = e1e2|e1e3 ；(e2|e3)e1 = e2e1|e3 e1
ee = e e = e e1e2 <> e2 e1
|
DFA |
NFA |
|
初态只有一个 |
初态可有多个 |
|
状态图上弧只能是单个字符 |
状态图上弧可以是正规式或e |
|
不可以 |
同一个字可能出现在同状态射出的多条弧上 |
|
DFA是NFA的特例；但是识别能力相同 |
|