词法分析的几个问题
术语
- 模式(pattern)：产生和识别元素的规则
- 记号(token)： 按照某个模式(或规则)识别出的元素(一组)。记号的区分:记号=记号的类别+记号的属性
- 单词(lexeme)：被识别出的元素自身的值(一个)，也称为词值
作用
- 滤掉源程序无用成分
- 处理与平台有关输入
- 根据模式识别记号，并交给语法分析器
- 调用符号表管理器或出错处理器，进行相关处理 。
工作方式
- 单独扫描，产生记号流供语法分析器使用。
- 作为语法分析器的子程序，并行工作。
模式的形式化描述
语言L是有限字母表∑上有限长度字符串的集合。（注意：字符表有限，字符串长度有限）
令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下:
- ε是正规式，它表示集合L(ε)={ε}
- 若a是Σ上的字符，则a是正规式，它表示集合L(a)={a}
- 若正规式r和s分别表示集合L(r)和L(s)，则
- r|s是正规式，表示集合L(r)∪L(s)，
- rs是正规式，表示集合L(r)L(s)，
- r*是正规式，表示集合(L(r))*，
- (r)是正规式，表示的集合仍然是L(r)
可用正规式描述的语言称为正规语言或正规集。
运算性质
- 三种运算(并，连接，闭包)具有左结合性
- 优先级：闭包>连接>或。
- 不同正规式可表示同一个正规集，即正规式与正规集是多对一。
- 若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P = Q。
- 等价性判断：根据定义或代数性质。
- r | s = s | r
- ( r s ) t = r ( s t )
- r | ( s | t ) = ( r | s ) | t
- ε r = r, r ε = r
- r ( s | t ) = r s | r t
- r* = ( r+ | ε )
- ( s | t ) r = s r | t r
- r** = r*
简化正规式的几个技巧
- 正闭包：r+ = r r* = r* r，r* = r+ | ε
- 可缺省：r?=r|ε
- 仅由|运算构成的正规式，则可改写为[r]，其中包括枚举或分段。
- [r]是一个字符组形式的正规式，则[^r]是表示∑ - L(r)的正规式。
记号的识别——有限自动机
模式的描述使用正规式，记号的识别使用有限自动机。
有限自动机：M =（S，∑，move，s0，F），其中
- S是有限个状态（state）的集合；
- ∑是有限个输入字符（包括ε）的集合；
- move是一个状态转移函数，move(si，ch)=sj表示，当前状态si下若遇到输入字符ch，则转移到状态sj；
- s0是唯一的初态（也称开始状态）；
- F是终态集（也称接受状态集），它是S的子集，包含了所有的终态。
有限自动机的几点说明
- 最长识别原则：如<=的识别。
- 不确定性：在当前状态下对同一字符有多于一个的下一状态转移。 （反复试探，指数增长，大量回溯）
DFA：NFA的特例，具有确定性。
- 没有状态具有 ε 状态转移
- 对每个状态 s 和每个字符 a ，最多有一个下一状态。
有限自动机之间的等价性： 若有限自动机M和M’识别同一正规集，则称M和M’是等价的，记为M=M’。
正规式与有限自动机从两个侧面表示正规集。正规式是描述，自动机是识别。因此，当它们表示相同集合时，均存在等价的问题。
从正规式到词法分析器
步骤： 描述（正规式描述模式）-构造NFA（一对一构造）-确定化（等价的DFA）-最小化（最少的状态数）-构造词法分析器
从正规式到NFA：Thompson算法
先用语法树右分解正规式，再自下而上构造NFA。
- 对ε，构造NFA N(ε) 接受{ε}：直接构造
- 对∑上的每个字符a，构造NFA N(a) 接受{a}：直接构造
- 若N(p)和N(q)是正规式p和q的NFA，则
- 对正规式p|q，构造NFA N(p|q)：接受L(p)∪L(q):把初态和终态取出合并，且增加初态和终态两条ε的路径
- 对正规式pq，构造NFA N(pq) 接受L(p)L(q):把N(p)的终态和N(q)初态合并
- 对正规式p*，构造NFA N(p*) 接受L(p*)：增加从初态到终态的ε路径，且在N(p)内部有从最后指向最前的ε路径
- 对于正规式(p)，使用p本身的NFA，不再构造。
确定化：从NFA到DFA
- 并行 用状态集取代状态，将不确定的下一状态确定化。 状态集：ε闭包（路径上是ε相连的状态）+ smove(S,a)
- 子集法 将路径确定化并记录下来，得到等价的DFA。
方法：将并行法每一个状态集编号，得到编号之间的转换关系。
最小化DFA
若从s和t来分析序列w均可得到相同的结果，则s,t是不可区分的，即可合并的。最小化就是反向利用可区分。一开始，仅有非终态和各终态是可区分的，经过划分，把可区分的状态分离，直到不可分离，最后不可区分的状态合并成一个状态。
算法：
- 初始划分：分为终态和非终态。
- 反复分裂划分组：若某个集合某个元素可以指向已经被划分出来的元素，则将该元素划分出来，直到不可再分裂。
- 选取代表，修改状态转移。
- 消除死状态和不可达状态。
DFA构造词法分析器
- 表驱动型的词法分析器:速度慢，程序与模式无关，规模大，可用工具生成
- 直接编码的词法分析器：速度快，程序与模式有关，规模较小，需要手工编写
