词法分析
Last updated
Last updated
词法分析是编译的第一个阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词法分析程序或扫描程序。
功能：输入源程序，输出单词符号。
词法分析器所输出的单词符号常常表示成如下的二元式：（单词种别，单词符号的属性值)
输入、预处理 词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。词法分析的工作（单词符号的识别）可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。
预处理的主要工作：
某些跳格符、回车符和换行符等编辑性字符，在别处的任何出现都没有意义，预处理时可以将其剔掉。
注解部分—仅在于改善程序的易读性和易理解性。对于它们，预处理时可以将其剔掉。
空白符（一个或相继数个）用作单词符号之间的间隔，即用作界符。在这种情况下，预处理时可把相继的若干个空白结合成一个。
单词符号的识别：超前搜索
状态转换图 状态转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。
正规式也称正则表达式（regular expression），是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。
定义： 设字母表为$\sum$，辅助字母表$\sum '= \lbrace \emptyset,\epsilon,|,.,*,(,) \rbrace$。
$\epsilon$和$\emptyset$都是$\sum$上的正规式，它们所表示的正规集分别为{$\epsilon$}和$\emptyset$；
任何$a\in \sum$，a是$\sum$上的一个正规式，它所表示的正规集为{a}；
假定e1和e2都是$\sum$上的正规式，它们所表示的正规集分别是L(e1)和L(e2)，那么，(e1)，e1|e2，e1$\cdot$e2和$e_1^*$也都是正规式，它们所表示的正规集分别为L(e1)，L(e1)$\bigcup$L(e2)，L(e1)L(e2)和$(L(e1))^*$；
仅由有限次使用上述三步骤而定义的表达式才是$\sum$上的正规式，仅由这些正规式所表示的字集才是$\sum$上的正规集。
其中，“|”读为“或”，“.”读为“连接”，“*”读为“闭包”。均为正规式运算符。
正规式的等价性： 若两个正规式e1和e2所表示的正规集相同，则说e1和e2等价，写作e1=e2。
设U、V、W为正规式，正规式服从的代数规律有：
U|V=V|U “或”满足交换律
U|(V|W)=(U|V)|W “或”的可结合律
(UV)W=U(VW) “连接”的可结合律
U(V|W)=UV|UW 分配律 (U|V)W=UW|VW
$\epsilon U$=U $\epsilon$是“连接”的恒等元素 $U \epsilon$=U
U|U=U “或”的抽取律
有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。
有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata) 。
DEA定义： 一个确定的有穷自动机M是一个五元组：M=（K，Σ，f，s0 ，Z）,其中：
K是一个有穷状态集，它的每个元素称为一个状态；
Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；
f是转换函数，是在K×Σ→K上的单值部分映射。即，如果 f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；
s0 ∈K是唯一的一个初态；
Z$\subset$K是一个终态集（可空），终态也称可接受状态或结束状态。
《编译原理（第2版）》张素琴 吕映芝 蒋维杜 戴桂兰 著
