【编译原理】第三章 词法分析

正则表达式(Regular Expression，RE)是一种用来描述正则语言的更紧凑的表示方法
例：正则语言L={a}{a,b} *({ε}∪({.,_}{a,b}{a,b} *))
正则表达式r = a(a|b) *( ε | (.| _)(a|b)(a|b) *)
正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式 r定义（表示）一个语言，记为L(r )。这个语言也是根据r的子表达式所表示的语言递归定义的

1、正则表达式的定义

ε是一个RE，L(ε) = {ε}
如果 a∈∑，则a是一个RE，L(a) = {a}
假设 r和 s都是 RE，表示的语言分别是 L®和L(s)，则
➢ r|s 是一个RE，L( r|s ) = L(r )∪L(s)
➢ rs 是一个RE，L( rs ) = L(r ) L(s)
➢ r* 是一个RE，L( r* )= (L(r ))*
➢ (r ) 是一个RE，L( (r ) ) = L(r )
运算的优先级：*、连接、|

2、正则语言

可以用RE定义的语言叫做正则语言(regular language)或正则集合(regular set)

3、正则表达式的代数定律

4、正则文法与正则表达式等价

对任何正则文法 G，存在定义同一语言的正则表达式 r
对任何正则表达式 r，存在生成同一语言的正则文法 G

5、正则定义

正则定义是具有如下形式的定义序列：
d1→r1
d2→r2
…
dn→rn
每个di都是一个新符号，它们都不在字母表 Σ中， 而且各不相同
每个ri是字母表 Σ∪{d1 ,d2 , … ,di-1}上的正则表达式

3.2 单词的识别

1、有穷自动机

（1）FA

一类处理系统建立的数学模型
这类系统具有一系列离散的输入输出信息和有穷数目的内部状态（状态：概括了对过去输入信息处理的状况）
系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变

（2）FA的典型例子

（3）FA模型

（4）FA的表示

（5）FA定义（接收）的语言

（6）最长子串匹配原则

当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配
在到达某个终态之后，只要输入带上还有符号，DFA就继续前进，以便寻找尽可能长的匹配

2、有穷自动机的分类

（1）确定的有穷自动机 (DFA)

（2）非确定的有穷自动机(NFA)

（3）DFA和NFA的等价性

对任何NFA N ，存在定义同一语言的DFA D
对任何DFA D ，存在定义同一语言的NFA N

（4）带有“ε-边”的NFA

（5）带有和不带有“ε-边”的NFA 的等价性

（6）DFA的算法实现

3、从正则表达式到有穷自动机

（1）根据RE 构造NFA

例：r=(a|b)*abb 对应的NFA

（2）从NFA到DFA的转换

（3）子集构造法

（4）计算 ε-closure (T )

4、识别单词的DFA

（1）识别标识符的DFA

（2）识别无符号数的DFA

（3）识别各进制无符号整数的DFA

（4）识别注释的DFA

（5）识别Token的DFA

3.3 词法分析阶段的错误处理

1、错误类型

单词拼写错误 例：int i = 0x3G; float j =1.05e;
非法字符 例：~ @

2、错误检测

如果当前状态与当前输入符号在转换表对应项中的信息为空，而当前状态又不是终止状态，则调用错误处理程序

3、错误处理

4、错误恢复策略

最简单的错误恢复策略： “恐慌模式 (panic mode)”恢复：从剩余的输入中不断删除字符，直到词法分析器能够在剩余输入的开头发现一个正确的字符为止

3.4 词法分析器生成工具Lex

1、Lex的构成

Lex语言、Lex编译器

2、Lex的使用

3、Lex程序结构

4、扫描器自动生成的意义

本章小结