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

一，词法分析器的作用

词法分析是编译的第一阶段。词法分析器主要任务是读入源程序的输入字符、将他们组成词素，生成并输出一个词法单元序列，每个词法单元对应于一个词素。

分析部分：词法分析、语法分析（简化编译器设计、提高编译器效率、增强编译器可移植性）

1）词法单元：词法单元名和可选的属性值组成。关键字、操作符……

2）模式：词法单元词素可能具有的形式，当词法单元是关键字时，模式就是这个关键字的字符序列

3）词素：源程序中的一个字符序列，它和某个词法单元模式匹配。

4）词法错误：识别出某个错误词素，继续判断下一个词素

二，输入缓冲

1）我们至少向前看一个字符，才能判断当前词素是否到头。

2）对付大型源程序，需要处理大量字符。处理往往需要很多时间，我们采用两个交替读入的缓冲区。（详见73）

三，词法单元的规约

1）我们会不会用完缓冲区？通常对于比较长的字符串我们采用 ”+“的形式链接起来。

2）正则表达式：letter_（letter_ | digit) * 表示字母开头 0个或多个 字母或数字

3）正则表达式例子
a | b {a, b}
(a | b) (a | b ) {aa, ab, ba, bb}
aa | ab | ba | bb {aa, ab, ba, bb}
a* 由字母a构成的所有串集
(a | b)* 由a和b构成的所有串集
复杂的例子
( 00 | 11 | ( (01 | 10) (00 | 11) * (01 | 10) ) ) * 01001101000010000010111001

3）正则表达式扩展

1>一个或多个实例 一元后缀算符“+”的意思是“一个或多个实例”,即正规式a+表示一个或多个a的所有串的集合。算符+和算符*有同样的优先级和结合性。代数恒等式 r* = r+ |  和r+ = rr*表达了这两个算符之间的关系。
2>零个或一个实例 一元后缀算符？的意思是“零个或一个实例”，r？是r |  的缩写。如果r是正规式，那么(r)?是表示语言L(r)∪{ }的正规式。使用这两种缩写，可以用num  digit+ (.digit+)? (E (+ | )? digit+)?来描述无符号数。
3>字符组 [abc]（其中a、b和c是字母表的符号）表示正规式a | b | c。缩写字符组[az]表示正规式a | b | … | z。使用字符组，可以用正规式[AZaz][AZaz09] *描述标识符。

四，词法单元的识别

某些状态为接受状态或最终状态，表明已经找到一个词素。

1）关系符转换图

2）保留字和标识符转换图

3）无符号树转换图

4）空白转换图

五，词法分析器生成工具 Lex

1）Lex是Unix环境下非常著名的工具,主要功能是生成一个词法分析器(scanner)的C源码,描述规则采用正则表达式(regular expression)。描述词法分析器的文件*.l，经过lex编译后，生成一个lex.yy.c 的文件，然后由C编译器编译生成一个词法分析器。词法分析器，简单来说，其任务就是将输入的各种符号，转化成相应的标识符(token)，转化后的标识符 很容易被后续阶段处理

2）用Lex穿件一个词法分析器

3）Lex冲突解决

总是选择最长的前缀，如果最长前缀跟多个模式匹配，总是选择在Lex程序中先呗列出的模式

六，有穷自动机

1）有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。当然有穷自动机与正则表达式之间有着很密切的关系

2）有限自动机分成确定的和不确定的两种情况。“不确定”（Nondeterministic Finite Automata ,NFA）的含义是，存在这样的状态，对于某个输入符号，它存在不只一种转换。确定的和不确定的有限自动机都正好能识别正规集，也就是它们能识别的语言正好是正规式所能表达的语言。

3）NFA组成

4）转换表

5）从正则表达式r=(a|b) * abb 到NFA