2.1  Lexical Tokens, Strings and Language在线视频

各位同学大家好，

这节课我们来学习

整个编译阶段的第一个阶段

词法分析的相应内容

我们看这里面，通过这个框图

我们就可以了解到

词法分析在整个编译过程当中

它的地位和作用

那么我们看

它是整个阶段当中的第一部分

它起到的作用就是

承接源程序和语法分析

也就是说，它可以第一个读到

源程序的相应的内容

然后把处理的结果

传递给语法分析器。

再往下分析，

我们看词法分析器

它的输入就是相应的源代码

也就是我们所说的源程序

而它的输出就是记号流

这个记号究竟是什么？

它究竟会输出什么

给接下来的语法分析器？

我们一起来了解一下。

我们看，对词法分析器来说，

它会处理源代码，

进而和语法分析器进行交互，

在整个过程当中

都会和符号表

进行一些数据上的沟通和交流

也就是说

语法分析器在整个过程当中

它是一个主导

通过它给词法分析器发送指令

那么词法分析器返回记号给语法分析器，

并且在这个过程当中，

会记录下当前这个词的相应的内容

到符号表里面去。

那么我们这一章主要的内容

包含两个方面：

第一就是词法单元、

以及词法记号的相应的概念

以及它的意义；

第二个就是词法记号，

我们知道它是什么之后，

我们应该如何描述它、

如何识别它。

那么我们首先来看一个中文的例子。

编译器来扫描源程序

就如同我们人类来看文本文件是一样的

那么以这样的一个中文的句子为例

比如说黄蓉是古代的才女

那么这样一句话

对于词法分析来说

顾名思义就是来分词分析词

这就叫词法分析

那么从中文的角度

我们看这句话

我们首先从词的切分上

可以分成“黄蓉”

这是一个代词

“是”这是一个动词

“古代的”这是一个形容词

进而，“才女”这是一个名词

那么这样分割完之后

我们就可以把句子或者单词

按照它的组成单位进行划分

划分结束之后

我们就可以得到一个句型

同理，我们再看一个例子

这个例子可以看成是

PASCAL语言的一个例子

那么其中L1是整个这句话的一个标识

我们可以用ID来表示

进而这是一个冒号

然后X等号，Y2加号，12

以及后面的分号

那也就是按照它的组成

我们可以给它划分成若干个词

那么编译的词法分析工作，

它的第一个阶段

就有点类似于分词的

这样的一个工作。

那么这个词法单元就称为单词，

也就是我们分出来的个词，

它是编程语言当中一个合法的字符串。

那么，我们来思考在这个例子当中

哪些是词法来源呢？

不错，也就是说，

这样画横线的、

所有的这些给出标识的这些（单词），

都可以称其为词法单元。

那么词法记号又是什么呢？

我们可以看这个例子里面，

所有的Y2、 X、L1等等，

这些都是用户自己起的名字。

对于这些（用户）自己起的名字，

我们可以给它设置成变量，

可以设置成标识。

所以我们给它统一的一个标号叫 ID 来表示

那么这个就称为词法记号。

用一个概念性的概括来说，

就是满足某种规则的词法单元

采用同一种记法来表示。

而这种记法就称为词法记号。

我们看给定的规则称为模式

也就是说，

我们希望把词法单元和词法记号

给它对应下来。

也就是说，在词法分析阶段

我并不关心当前的这个词

到底是A3、A4、A5

它是哪个变量

我只关心它的变量写的对不对？

它是变量还是一个操作符？

还是一个大于号、小于号的这样判断符等等

也就是说我们希望的是

把词法单元分割出来之后

通过一种模式

也叫规则的映射

把它得到对应的词法记号

进而传给接下来的语法分析阶段

那么我们再看

对于一个形容词来说

“古代的”是形容词

“现代的”也是形容词，漂亮的、潇洒的

以及其他的一些形容词

都可以用同样的标识来表示

因此词法阶段

需要把它们找出来

并用同样的标识给解释出来

那么从这里我们就可以看出

在这个阶段，词法的模式

也就是说，这种规律的寻找是特别重要的

那么对于 C 语言标识符来说

我们先思考一下

那么我们看哪些是正确的？哪些是错误的呢？

对于 C 语言标识符来说

我们知道它有一定的规律

这个规律就是必须是以字母

或者是下划线开始的字母和数字的组合

我们看，这就是识别C语言标识符的一个模式

或者叫规律

那么以这个模式为基础

我们就可以看出

这里面的“12”很明显是不合适的

也就是，它是不符合规则的

对于词法分析来说要做的事情就是

把这里面的词拆分出来之后

并且用这种规则，可以说是模式

来把对应的词对应到相应的记号上面去

这就是词法模式它的作用。

那么我们可以先看一些

常见的记号以及模式的例子

比如说词法单元struct

这个词是在程序语言当中

规定好的一个关键词

所以它对应的记号就是它的本身

它的描述也就是这个单词本身

类似的

比如说 for、relop 关系运算符等等

这都是一样的

那么下面这两个和上面

有一些区别的是什么呢

像下面的relop记号

对应的有很多个

也就是这样的关系运算符用统一的一个记号relop

来表示

下面的ID就是由下划线、字母

和数字组成的串

那么要由下划线和字母开始

这就是属于一种概括的形式了

包括下面number这个记号

对应的就是数字

然后是这个字符串

用双引号引起来的

也是一种它的规则的描述

我们可以看出

以上的这些描述、红框框起来的

这是一些简单的

也就是说对应记号

只有一类物体

或者说只有一个词

那么它自己就称其为一个记号

而下面的是稍微复杂一些的例子

那么对于每一个记号

它后面都有很多符合规则的

一系列的这样的例子

我们也可以从一些文本上的

也就是汉语语言上的表示

是来更好地理解一下

词法单元以及词法记号的内容

那么我们看

对应的这一列是词法单元的列举

然后后面是对这个单元

究竟表示什么的一个概括

然后最左侧的这一列是词法记号

我们可以看出

这里面

大连、软件、大黑山等等

这些都是一些列举

那么它们都是什么呢？

统一的记号就是名词

然后它的一个概括

也可以说是它的规则

或者说模式

就是表示名称的词

与此类似的

我们看有胡锦涛、毛泽东

那么统一的记号

都是中国人

那么对应它的规则是什么

也就是它有什么样的共同的特点

就是具有中国国籍的人

通过这种方式

我们就可以把对应的词

给它对应到相应的记号上

但很明显这种方式

不符合计算机能够操作的范畴

也就是说对于编译器来说

我们也是一个程序

希望能够用一种比较规范的形式

能把它整个规则表示出来

很显然这种形式是远远不够的

除此之外

我们看在整个的过程当中

如果只是把词法分析器

得到的记号给语法分析器

那么相应的有些内容就会丢失

究竟会丢失哪些内容呢？

它的存在即符号表的存在

又有什么意义呢？

我们来看一下

如果只是把相应的记号

给了下面的语法分析器

那么对于这样的一句话

“黄蓉是美女”的话

翻译官得到的

接下来的内容

也就是语法分析

得到的内容

就是 主语谓语宾语

那么如果是主谓宾的这样的结构

它可以表示很多的文字

不光是“黄蓉是美女”

也可能是“黄蓉是丑女”

那么我根本不知道这句话

究竟描述了怎样的内容

因此我们说

应该把它里面每一个代词

它的动词

还有最后的宾语

究竟是怎样的含义

我们应该给它记录下来

那么怎么样来记录下来呢

我们看可以通过符号表

也就是通过符号表的内容

把每个词对应的意义给它联系起来

那么符号表

通常都包含这样的几项内容

比如说第1个说是ID

那么它的名称是什么呢

L1 表示的是什么呢？

是一个标号

它是一个label

然后第2个ID名称是X，表示的是一个变量

类型是int

那么这个符号表

就好像是一个记录员一样

把当前这个词

究竟是什么样的含义

给它保存起来

以便后面再分析使用

那么对于记号我们再看一下

刚才说了很多

我们需要把 词 变成相应的记号

究竟这个记号是什么样子的

我们来看一下

对于当前的这样的一句话

我们可以给他写到

PASCAL的程序里面

就是 position 等于 initial 加上 rate 乘以 60

那么对于词法分析来说

按照我们刚才所讲的

第一部分

就是要把它拆分成各个词

拆分之后我们看position

就是一个变量

也就是一个ID

那么这就是我们看用尖括号

表示它的第一元

这是记号的第一元

那么整个记号的第二元是什么

不光要给语法分析记号

还要给语法分析

当前记号的详细内容是什么

因此第二元一般是一个指针

指向的就是当前ID所在的符号表的位置

同理

接下来是一个赋值运算符

那么这个赋值运算符

本身就占一个记号

因此就不用第二元

再给它详细信息了

接下来以 initial 和 rate

这两种情况

和 position 都是相同的

最后 60 是一个number

它统一的记号就是一个number

然后它表示的就是整数的数值60

由此我们可以归纳一下

所谓的词法记号就是一个二元组

第一元表示它的记号

那么第二元表示

它在符号表当中的位置

那么也可以

第二元是它具体的数值

就像number一样

接下来我们来看

为了能够把词对应到记号

在这里面起到决定性作用的

就是这种规则的描述

也就是这个模式

在这里我们称其为模式

那么这个模式

我们应该怎样描述

我们说有语言上的描述

那么这种语言上的描述

很显然不能够直接运用到程序语言当中

因此我们希望

能够用一种比较规范化的

数学上的形式来描述

那么这里我们来看一下

比如说我们先给出几个定义

第1个就是字母表

字母表是一个符号的有限集合

比如说用 ∑ 来表示

上面表示的

就是能够构成当前词

或者句子的这样的串

那么接下来这个串

就是由字母表来扩展形成的

也就是说把字母表上的这样的字

给它结合到一起就形成了串

也可以看成是我们汉语言当中的词

这里有一个特殊的串 叫 ε

它的长度是零

这一点需要注意一下

那么接下来“语言”是什么意思呢

语言就是字母表上的一个串集

也就是说串表示词

那么语言就是各个词

组合在一起的这样的一个结果

也可能是空串

如果这个语言没有任何文字

那么它就是一个空集

如果只有一个空串

我们看

可以用这样的形式来表示

整个上面讲的

我们可以用这样的一个框图

来总结

就是说先有一系列字母

就好像我们有汉语言的很多汉字一样

那么通过这些字的组合就形成了串

也就是一个一个的词

最后再通过一个集合

我们就可以得到当前的语言

那么其中串的长度

我们可以用一个类似绝对值的这样的形式

把串放到里面

就可以得到当前这个串里面还有多少个字

关于串有一系列的运算

基本的两个运算就是连接和积运算

所谓连接运算就是两个串连接到一起

那么任何串和空集的连接

都是当前的串本身

接下来 积 也就是指数运算

零次幂的结果就是 ε

那么一次幂就是它的本身

S表示一个串

它自身的 i 次幂

就是S本身和S的 i 减一次幂的一个连接

也就是说 积 或者叫指数运算

实际上是连接运算的一个自连接的这样的一种表示形式

接下来我们可以看一些相对复杂的例子

比如说这里面还有一些 和 运算

和 实际上 是并集 一个并运算

那么这个并运算

就是指

如果S串是属于L语言的

然后S串也是属于M语言的

那么它的并集表示

要么属于这个语言 要么属于那个语言

把它两个的串合并到一起

同理连接运算 S属于L T属于M

那么连接就是把这两个串

一个放在前面 一个放在后面

连接到一起

指数运算就是自身和自身的连接

这里需要注意

指数运算自己的零次幂

得到的语言里面 只有一个 ε 串

这里面接下来有两个

我们之前在离散这个课程当中

学习过的（运算）

叫闭包和正闭包

所谓闭包

就是指自身的零次幂和一次幂两次幂

以及一系列的这样的一个并集

也就是说通过闭包

我们可以得到

还有无穷无尽的串的集合

串的长度

也是想要多长有多长 无穷无尽的

那么正闭包

就是把零次幂的闭包给去掉

从这里我们可以看出来什么呢？

这里面的正闭包

实际上就是把正闭包和它的零次幂并到一起

就是我们闭包的这样的一个表示

在咱们书上的2.2的例子里

有这样的一个练习题

希望大家根据我们学习到的这些概念

能把下面的练习题完成好

最后在我们这一节课里

我们来了解一下

如果出现错误应该怎么办

也就是说

在检查源程序的过程当中

有可能会出现词法错误

比如说你的词

你的定义写错了

那么我们应该怎么样来对付这种错误呢？

也就是说编译器当遇到错误的时候

我们应该怎么处理呢

那么我们讲几种恢复策略

有紧急的这种方式

还有错误的补偿的方式

所谓紧急的方式

就是说

我把这个错误的位置给记录下来

只要报告一下就可以了

那么第2种就是错误的补偿方式

这种补偿方式有以下几种

第1个就是

可以删除一个多余的字符

因为通过统计 一般的错误

都是由以下这样4种方式构成的

所以可以通过删除字符

插入遗漏的字符

或者是用正确的（字符）代替不正确的（字符）

或者交换两个相邻的字符来表示

这是编译器常用的处理错误的方式

以上就是我们这节课所讲的内容

谢谢大家