词法分析的问题
术语
- 模式(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)的正规式。
记号的识别——有限自动机
模式的描述―正规式，记号的识别―有限自动机
NFA
定义
M =（S，∑，move，s0，F），其中
- S是有限个状态（state）的集合；
- ∑是有限个输入字符（包括ε）的集合；
- move是一个状态转移函数，move(si，ch)=sj表示，当前状态si下若遇到输入字符ch，则转移到状态sj；
- s0是唯一的初态（也称开始状态）；
- F是终态集（也称接受状态集），它是S的子集，包含了所有的终态。
说明
最长识别原则：如<=的识别。
不确定性：在当前状态下对同一字符有多于一个的下一状态转移。 （反复试探，指数增长，大量回溯）
DFA
NFA的特例(确定性)
- 没有状态具有 ε 状态转移
- 对每个状态 s 和每个字符 a ，最多有一个下一状态。
FA的等价
若有限自动机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构造词法分析器
- 表驱动型的词法分析器
- 直接编码的词法分析器
| 区分 | 表驱动 | 直接编码 |
|---|---|---|
| 分析器的速度 | 慢 | 快 |
| 程序与模式的关系 | 无关 | 有关 |
| 分析器的规模 | 较大 | 较小 |
| 适合的编写方法 | 工具生成 | 手工编写 |
网友评论