近三万字长文！让你懂透编译原理(三)——第三章词法分析

超长文预警！

系列文章传送门：

万字长文+独家思维导图！让你懂透编译原理(一)——第一章引论


万字长文！让你懂透编译原理(二)——第二章高级语言及其语法描述


近三万字长文！让你懂透编译原理(三)——第三章词法分析


三万多字长文！让你懂透编译原理(四)——第四章语法分析—自上而下分析


六万多字长文！让你懂透编译原理(五)——第五章语法分析—自下而上分析


三万五千字长文！让你懂透编译原理(六)——第六章属性文法和语法制导翻译


六万字长文！让你懂透编译原理(七)——第七章语义分析和中间代码产生

文章目录

近三万字长文！让你懂透编译原理(三)——第三章词法分析

3.1 对于词法分析器的要求

3.1.1 词法分析器的功能和输出形式

功能:输入源程序、输出单词符号
单词符号的种类：

1)基本字：如 begin，repeat，…

2)标识符——表示各种名字：如变量名、数组名和过程名

3)常数：各种类型的常数

4)运算符：+，-，*，/，…

5)界符：逗号、分号、括号和空白
输出的单词符号的表示形式:

(单词种别，单词自身的值)
单词种别通常用整数编码表示。

1)若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定

基本字

、

运算符

和

界符

都是一符一种。

2)若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。

标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。
常数按类型分种；常数的值则表示成标准的二进制形式。

在这里插入图片描述

3.1.2 词法分析器作为一个独立子程序

词法分析作为一个独立的

阶段

，是否应当将其处理为一遍呢？

作为独立阶段的优点：

结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。

不一定不作为单独的一遍：

将其处理为一个子程序。

3.2 词法分析器的设计

3.2.1 输入、预处理

输入串放在输入缓冲区中。
预处理子程序：剔除无用的空白、跳格、回车和换行等编辑性字符;区分标号区、捻接续行和给出句末符等
扫描缓冲区

过程

预处理子程序在扫描器的调用下将源程序输入到缓冲区中，预处理子程序读取输入缓冲区中的字符进行文本的预处理，主要包括：

剔除无用的空白跳格、回车和换行等编辑性字符
区分标号区、捻接续行和给出句末符等

经过预处理后，规范性更好的文本被送入到扫描缓冲区中，预处理子程序返回扫描器，扫描器继续从缓冲区中读取预处理后的文本，根据词法规则，识别出单词符号。

在这里插入图片描述

该过程体现了分解解决复杂问题的计算思维：

将一些文本编辑性的，很少涉及词法规则的工作，如：无用符号的剔除，续行处理等预处理工作独立出来，交给预处理子程序专门处理，使得扫描器的工作变得简单，不用考虑一些琐碎的编辑处理，而集中精力按照语言词法规则识别单词。

扫描缓冲区的组织也有技巧：

扫描缓冲区存放了经过预处理的比较规范的字符串，扫描器就在该缓冲区中识别单词符号，扫描器通过两个指针（起点指示器和搜索指示器）进行扫描，起点指示器指向马上要识别的单词开始的位置，搜索指示器从开始位置前进，搜索单词的结尾。

在这里插入图片描述

实现问题：如果单词比较长，就可能单词前半段在扫描缓冲区中，而后半段没有进来。

比如一个长单词，WhatALong…Wo已经进入扫描缓冲区，但最后俩个字符rd没有进入

当搜索指示器扫描到缓冲区结尾，仍然没有找到单词的结尾，就会触发对预处理子程序的调用，预处理子程序从文件和数据缓冲区中处理一批字符，将结果送入到扫描缓冲区，但这样会把扫描缓冲区中原来的单词的前半段都冲掉，没办法记录单词的全部字符了

为了解决这个问题，首先想到将扫描缓冲区加长，但无论加到多长，我们都无法保证单词能不被缓冲区打断，甚至很短的单词也有可能被很长的缓冲区打断。

为了解决这个问题，我们把缓冲区一分为二

分为两个半区，每次预处理程序只处理并送入半区的字符，而这两个半区互补使用。

先把前半部分装入左边半区，这时单词最后两个单词rd没能进入这个缓冲区中，还在预处理缓冲区中，起点指示器指向W，当搜索指示器扫描到缓冲区结尾，仍然没有找到单词的结尾，就会触发对预处理子程序的调用，再处理下一批字符，调用右边的半区，这样就有rd，此时搜索指示器依次扫描r,d,碰到后面空格，从而确定d为单词末尾，这样就识别出单词的头和尾

如果先用右半区，当搜索指示器扫描到缓冲区结尾，仍然没有找到单词的结尾，就会触发对预处理子程序的调用，再处理下一批字符，调用左边的半区，在左半区识别出单词的末尾。

只要单词的长度不超过半区的长度，就可以在另一个半区找到

半区的长度就是程序语言允许的最大长度

如果标始符的长度不能超过128，就可以推断出扫描缓冲区的长度为256

3.2.2 单词符号的识别:超前搜索

1 基本字识别:

例如:

DO99K=1，10 DO 99 K = 1，10

IF(5.EQ.M)GOTO55 IF (5.EQ.M) GOTO 55

DO99K=1.10

IF(5)=55

为了从1,2中识别出关键字DO和IF,我们必须要能够区别13和区别24。语句1、3的区别在于等号之后的第一个界符:一个为逗点“，”,另一个为句末符“

.

”。语句24的主要区别在于右括号后的第一个字符:一个为字母,另一个为等号。这就是说,为了识别12中的关键字,我们必须超前扫描许多个字符,超前到能够肯定词性的地方为止。对于1.3来说,尽管都以’D’和‘O’两字母开头,但不能一见‘DO’就认定是DO语句。我们必须超前扫描,跳过所有的字母和数字,看看是否有等号。如果有,再向前搜索。若下一个界符是逗号,则可以肯定D应为关键字。否则,DO不构成关键字,它只是用户标识符的头两个字母。所以,为了区别1和3,我们必须超前扫描到等号后的第一个界符处。对于语句2、4来说,必须超前扫描到与F后的左括号相对应的那个右括号之后的第一个字符为止。若此字符是字母,则得逻辑正。若此字符是数字,则得算术正。否则,就应认为是用户自定义标识符F。

在这里插入图片描述

3.2.3 状态转换图

1) 概念

在这里插入图片描述

若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于α，则称α被该状态转换图所

识别(接受)

2) 例子

助忆符：直接用编码表示不便于记忆，因此用助忆符来表示编码。

在这里插入图片描述

3) 状态转换图的实现

思想：每个状态结对应一小段程序。
做法:

(1)对不含回路的分叉结，可用一个CASE语句或一组IF-THEN-ELSE语句实现

在这里插入图片描述

(2)对含回路的状态结，可对应一段由WHILE结构和IF语句构成的程序

全局变量与过程

ch

字符变量、存放最新读入的源程序字符
strToken

字符数组，存放构成单词符号的字符串
GetChar

子程序过程，把下一个字符读入到 ch 中
GetBC

子程序过程，跳过空白符，直至 ch 中读入一非空白符
Concat

子程序，把ch中的字符连接到 strToken
IsLetter

和

IsDisgital

布尔函数，判断ch中字符是否为字母和数字
Reserve

整型函数，对于 strToken 中的字符串查找保留字表，若它是保留字则给出它的编码，否则回送0
Retract

子程序，把搜索指针回调一个字符位置
InsertId

整型函数，将strToken中的标识符插入符号表，返回符号表指针
InsertConst

整型函数过程，将strToken中的常数插入常数表，返回常数表指针。

4) 词法分析器的实现

识别标识符（0→1→2）

在这里插入图片描述

int code, value;
strToken := “ ”;	/*置strToken为空串*/
GetChar();         //读入一个字符
GetBC();           //跳过所有空白符，直至 ch 中读入一非空白符
if (IsLetter())    //如果是字母，从0出发，转入状态1
begin              //1：
	while (IsLetter() or IsDigit()) //自圈，实现为while，如果字符是字母/数字
	begin
		Concat(); GetChar(); //把ch中的字符连接到strToken中，再读入下一个字符
	end                      //循环在读入字符不是字母/数字时退出，转入状态2
	Retract();               //终态2上面有*，需要回退，刚刚读入进入状态2的字符不属于标识符
	code := Reserve();       //通过Reserve，查找保留字表，若它是保留字则给出它的编码，否则是用户自定义的标始符返回0，将返回的结果放在code变量里面
	if (code = 0)            //当前strToken中的字符串，是用户自定义的标始符
	begin
		value := InsertId(strToken); //将strToken中的标识符插入符号表，返回标识符在符号表指针(入口)，记录在value作为单词自身的值
		return ($ID, value);         //返回种别编码和自身的值
	end
	else                             //当前strToken中的字符串，是保留字
		return (code, -);	         //此时code中已经是该保留字的种别编码，直接返回种别编码，没有自身的值
end

识别整常数，=，+（0→3→4，0→5，0→6）

在这里插入图片描述

else if (IsDigit())                //如果不是前面的分支的话，判断是不是数字
begin                              //是数字，进入状态3
	while (IsDigit())              //状态3有自圈，实现为while，如果字符是数字
	begin         
		Concat( ); GetChar( );     //把ch中的字符连接到strToken中，再读入下一个字符
	end                            //循环在读入字符不是数字时退出，转入状态4
	Retract();                     //终态4上面有*，需要回退，刚刚读入进入状态4的字符不属于标识符
	value := InsertConst(strToken);//将strToken中的常数插入常数表，返回常熟在常数表指针(入口)，记录在value作为常熟自身的值
	return($INT, value);           //返回整常数的编码和刚刚返回的整常数在符号表中的入口(自身的值)作为二元组返回
end
else if (ch =‘=’) return ($ASSIGN, -); //如果ch为=号，返回=的种别编码(状态5代码)
else if (ch =‘+’) return ($PLUS, -);   //如果ch为+号，返回它的种别编码(状态6代码)

识别* | , | ( | )

在这里插入图片描述

else if (ch =‘*’)                    //识别的是*，进入状态7
begin
	GetChar();                       //读入下一个字符
	if (ch =‘*’) return ($POWER, -); //下一个字符还是*，进入9，返回乘方符号种别编码
	Retract();                       //下一个字符不是*，进入8，回退
	return ($STAR, -);               //前一个*单独构成乘号，种别编码$STAR
end
else if (ch =‘,’) return ($SEMICOLON, -); //状态10
else if (ch =‘(’) return ($LPAR, -);      //状态11
else if (ch =‘)’) return ($RPAR, -);      //状态12
else ProcError( );		                  //状态13 错误处理

5) 将状态图代码一般化

在这里插入图片描述

6) 小结

词法分析器的功能

输入源程序、输出单词符号
词法分析器的设计

给出程序设计语言的单词规范——单词表
对照单词表设计识别该语言所有单词的状态转换图根据状态转换图编写词法分析程序
是否有自动的方法产生词法分析程序

3.3 正规表达式与有限自动机

回顾

词法分析的任务是识别单词符号，单词符号是一些特殊的字符串，但并非所有的字符串都能成为一个程序设计语言合法的单词。

下列单词表给出了这个语言所有合法的单词符号。只有这样的字符串才是合法单词，为了把能够构成单词的那一部分字符串描述出来进行分析，引入

正规集：程序设计语言定义的合法的单词的集合
正规表达式(正规式)

二者是对应的概念

几个概念:

考虑一个有穷字母表∑ 字符集
其中每一个元素称为一个字符
∑上的字(也叫字符串) 是指由∑中的字符所构成的一个有穷序列
不包含任何字符的序列称为空字，记为ε
用
$∑^* ∑ ∗ 表示 ∑ ∑ ∑ 上的所有字的全体,包含空字ε 例如: 设 ∑ ∑ ∑ ={a， b}，则 ∑ ∗ ∑^* ∑ ∗ ={ε,a,b,aa,ab,ba,bb,aaa,…}$

在这里插入图片描述

3.3.1 正规式和正规集

正规集

可以用

正规表达式

（简称

正规式

）表示。
正规表达式

是表示

正规集

一种方法。
一个字集合是

正规集

当且仅当它能用

正规式

表示。

正规式和正规集的递归定义：

对给定的字母表

∑

$\sum$

1)

ε

$ε$

和

Ф

$Ф$

都是

∑

$\sum$

上的正规式，它们所表示的正规集为{

ε

$ε$

}和

Ф

$Ф$

;

2) 任何

∈

∑

a∈ ∑

$a \in \sum$

，a是

∑

$\sum$

上的正规式，它所表示的正规集为{a} ;

3) 假定e1和e2都是

∑

$\sum$

上的正规式，它们所表示的正规集为L(e1)和L(e2)，则

i) (e1|e2)为正规式，它所表示的正规集为L(e1)∪L(e2)，（两个正规集的并还是正规集）
ii) (e1.e2)为正规式，它所表示的正规集为L(e1)L(e2)，（两个正规集的连接还是正规集）
iii)
$(e1)^* ( e 1 ) ∗ 为正规式，它所表示的正规集为 ( L ( e 1 ) ) ∗ (L(e1))^* ( L ( e 1 ) ) ∗ ，（一个正规集的闭包还是正规集）$

仅由

有限次

使用上述三步骤而定义的表达式才是

∑

$\sum$

上的正规式，仅由这些正规式表示的字集才是

∑

$\sum$

上的正规集

Ф

$Ф$

/{ }既是集合也是正规式也是正规集

不是字符也不是由字母表字符构成的字符串，因此其不是字

ε

$ε$

既是字也是正规式，其正规集是{

ε

$ε$

}

a是字母表中的字符

则a是字符，当然a也可以看成一个由一个字符a构成的长度为1的字符串，因此a是字

根据定义a也是正规式

其对应的正规集为{a}

正规式的等价性

将正规式的等价转换为集合的等价来进行证明。

在这里插入图片描述

运算律的证明也可以利用集合运算的交换律来进行

在这里插入图片描述

小结: 正规式和正规集

保留字，标识符，整常数等合法的单词符号构成正规集，每个正规集抽象成一个正规表达式。

上面集合也可以用正规表达式表达出来:

先把每一类单词表示成正规式

DIM正规式→{DIM}正规集

IF正规式→{IF}正规集

letter(letter|digit)*

digit(digit)*

在这里插入图片描述

3.3.2 确定有限自动机(DFA)

在这里插入图片描述

DFA允许没有终止状态

DFA可以表示为状态转换图。

假定DFA M含有

m个状态

和

n个输入字符
这个图含有

m个状态结点

，每个结点顶多含有

n条箭弧射出

，且每条箭弧用Σ上的不同的输入字符来作标记
对于Σ
^*
中的任何字α，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于α，则称α为DFA M所

识别(接收)
DFA M所识别的字的全体记为L(M)。

在这里插入图片描述

A:能识别空字

ε

$ε$

，系统初始就是q0状态，这个时候不读入任何字符，也是停留在q0状态，而q0又是终态。

或者说我从q0到q0是一条初态到终态的通路，这个通路上的边上的标记没有读入任何符号，所以没有转换关系，路径长度为0，字符串长度为0，但它又是从初态到终态的一条通路，这条通路上所标记的字符串就是空字

ε

$ε$

，所以说其能识别空字

ε

$ε$

。

即相当于从初态q0出发，读入了长度为0的字符串之后，继续停留在终止状态q0，也就是识别了空字

ε

$ε$

。