编译原理3——词法分析

3.1词法分析器的作用

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

但在这个过程中，词法分析器还要和语法分析器进行交互。交互：语法分析器通过一个指令调用词法分析器，让词法分析器从它的输入中不断读取字符，直到识别出下一个词素为止，词法分析器根据这个词素生成下一个词法单元并返回给语法分析器。

词法分析器还会完成一些额外的任务：

过滤掉源程序中的注释和空白（空格、换行符、制表符以及在输入中用于分隔词法单元的其他字符）
将编译器生成的错误信息与源程序的位置联系起来。

总结：词法分析器可以分为两个联级阶段

扫描阶段主要负责完成一些不需要生成词法单元的简单处理，比如删除注释和将多个连续的空白字符压缩成一个字符。
词法分析阶段是较为复杂的部分，它处理扫描阶段的输出并生成词法单元。

3.1.1词法分析及语法分析

把编译过程的分析部分划分成词法分析和语法分析两个阶段的原因：

简化编译器的设计。比如：如果在语法分析中还要处理关于一些注释或者空白字符的问题，那么将会更加复杂。
提高编译器的效率。二者独立实现一些功能提高对某个环节处理的专业性。
增强编译器的可移植性。输入设备相关的特殊性可以被限制在词法分析过程中。

3.1.2词法单元、模式和词素

词法单元：词法单元名+可选择的属性。
模式：是一种解释，描述了一个词法单元的词素可能具有的形式。
词素：就是可以被词法分析器识别为该词法单元的一个实例。

大部分的词法单元：

每个关键字有一个词法单元。一个关键字的模式就是该关键字本身。
表示运算符的词法单元。它可以表示单个运算符，也可以表示一类运算符。
一个表示所有标识符的词法单元。
一个或多个表示常量的词法单元。
每个标点符号有一个词法单元，比如左括号、逗号和分号。

3.1.3词法单元的属性

词法分析器不仅仅向语法分析器返回一个词法单元名字，还会返回一个描述该词法单元的词素的属性值。这个属性则会影响语法分析之后对这个词法单元的翻译。

3.2词法单元的规约

正则表达式是一种用来描述词素模式的重要表示方法。

3.2.1串和语言

串s的长度，通常记作|s|，是指s中符号出现的次数。

语言是某个给定字母表上一个任意的可数的串集合。

串的各部分术语：

串s的前缀（prefix）：从s的尾部删除0个或多个符号后得到的串。
串s的后缀（suffix）：从s的开始处删除0个或多个符号后得到的串。
串s的子串（substring）：删除s的某个前缀和某个后缀之后得到的串。
串s的真前缀、真后缀、真子串：既不等于空，也不等于s本身的前缀、后缀、子串。
串s的子序列（subsequence）：从s中删除0个或多个符号后得到的串，这些被删除的符号可能不相邻。

如果x和y是串，那么x和y的连接（concatenation）是把y附加到x后面而形成的串。例如：x = handsome 且 y = you 。那么xy = handsomeyou 。

3.2.2语言上的运算

L和M的并：就是简单的合并成一个集合
L和M的连接：以各种可能的方式，从第一个语言中任取一个串，再从第二个语言中任取一个串，然后将它们连接后得到的串集。
L的Kleene闭包（L*）：就是将L连接0次或多次后得到的串集。
L的正闭包：只不过是去掉空串。

3.2.3正则表达式

正则表达式可以由较小的正则表达式按照如下规则递归地构建。

归纳基础：e是一个正则表达式，L(e)={e}，即该语言只包含空串。

归纳步骤：由小的正则表达式构造较大的正则表达式的步骤有四个部分。假定r和s都是正则表达式，分别表示语言L(r)和L(s)。

(r)|(s)是一个正则表达式，表示语言L(r) U L(s)。
(r)(s)是一个正则表达式，表示语言L(r)L(s)。
(r)*是一个正则表达式，表示语言(L(r))*。
(r)是一个正则表达式，表示语言L(r)。最后这个规则是说在表达式的两边加上括号并不影响表达式所表示的语言。

当然，有时候是可以去掉括号的，*具有最高优先级且是左结合的，连接具有次高优先级且是左结合的，|的优先级最低且是左结合的。

正则表达式的代数定律：只记录特殊的一条，r** = r* 。具有幂等性。

取自某学习视频：

限定符：

a*：a出现次或多次
a+：a出现1次或多次
a？：a出现0次或1次
a{6}：a出现6次
a{2，6}：a出现2-6次
a{2，}：a出现两次以上

运算符：

（a|b）：匹配a或者b
（ab）|（cd）：匹配ab或者cd

字符类：

[abc]：匹配a或者b或者c
[a-c]：同上
[a-fA-F0-9]：匹配小写+大写英文字符以及数字
[^0-9]：匹配非数字字符

元字符：

\d：匹配数字字符
\D：匹配非数字字符
\w：匹配单词字符（字母数字下划线）
\W：匹配非单词字符
\s：匹配空白符
\S：匹配非空白字符
. ：匹配任意字符（换行符除外）
\b：标注字符的边界
^：匹配行首
$：匹配行尾

3.3词法单元的识别

3.3.1状态转换图

接下来将通过一张图来解释

有一组被称为“状态”的结点或圆圈。状态图中的边从图的一个状态指向另一个状态（定向搜索，可能性也就只有1）。图中的双层的圈就是“接受状态”或“最终状态”。由一条没有出发结点的箭头指向的是“开始状态”或“初始状态”。如果需要将指针回退到上一个位置，则需要在接受状态的附近加上一个*，若是多个位置，就加多个*。

3.3.2保留字和标识符的识别

主要目的就是防止一些关键字被识别成标识符。

解决方法通常有两种：

将所有可能用到的关键字一一列举在符号表中
为每个关键字设定一个状态转换图，但是在最后的接受状态要添加一个“非字母或数字”的测试，来确保这个状态转换图确实不会成为一个标识符。

3.3.3基于状态转换图的词法分析器的体系结构

用一个函数来模拟状态转换图的实现。不同的词法单元分析有不同的状态转换图，但是为了实现对某个未知的词法单元进行词法分析，你首先要做的就是选定某个状态转换图。

依次调用所有的状态转换图，直到分析出。
同时调用所有的状态转换图，选择最长匹配。
将所有状态转换图归成一个状态转换图。

3.4词法分析器生成工具Lex

Lex最近也叫Flex，这个F就是Fast的意思。它的核心功能就是将输入的模式转换成一个状态转换图，并生成相应的实现代码。

3.4.1 Lex的使用

使用者本身首先要使用Lex语言写一个.l文件，然后运用配置好的Lex编译器，在终端输入相关指令，将.l文件转换成lex.yy.c文件。

3.4.2 Lex程序的结构

%{
....     //声明部分%}//给一些正则表达式typedef一下%%
//转换规则
//正则表达式      {实现的操作}[a-zA-Z]+				{ words++; chars += strlen(yytext); }
%%//辅助函数部分main()
{yylex();return 0;
}

声明部分、辅助函数部分都被直接拷贝到.c文件中
yytext 是一个指向词素开头的指针
yyleng 存放刚找到的词素的长度

3.4.3 Lex中的冲突解决

当输入的多个前缀与一个或多个模式匹配时，Lex用如下规则选择正确的词素：

总是选择最长的浅醉。
如果最长的可能前缀与多个模式匹配，总是选择在Lex程序中先被列出的模式。（将关键字的定义靠前列出）

3.4.4 向前看运算符

在一些语言中，存在 IF 是一个数组的名字，而不是关键字，这样的使用就给词法分析带来了很大的困扰。

所以要采用一种新的方法，用斜号来指明该模式中和词素实际匹配的部分的结尾，斜号 / 之后的内容表示一个附加的模式，只有附加模式也匹配成功了，最后才能进行返回自己要找的词法单元并进行输出（不包含附加内容）。

举例：这里的IF就变成了：IF / $ . * $ {letter}

3.5 有穷自动机

自动机在本质上是与状态转换图类似的图，但存在几点不同：

有穷自动机是识别器，它们只能对每个可能得输入串简单地回答“是”或“否”。
不确定的有穷自动机（NFA）：堆其边上的标号没有任何限制，一个标号可以标记离开同一状态的多条边，并且空串ε也可以作为标记。
确定的有穷自动机（DFA）：就只有一条离开该状态的边，且这个边上的标记只能用一次。