国防科技大学编译原理第4讲词法分析1

课程主页：

https://www.icourse163.org/course/NUDT-1003101005?tid=1460976445

这次回顾第4讲：词法分析1。

第4讲词法分析1

词法分析概述

词法分析的任务

词法分析的任务
- 从左至右逐个字符地对源程序进行扫描，产生一个个单词符号
词法分析器(Lexical Analyzer)
- 扫描器(Scanner)
- 执行词法分析的程序

词法分析器的功能

功能
- 输入源程序、输出单词符号
单词符号的种类
- 基本字：如begin，repeat，for，…
- 标识符：用来表示各种名字，如变量名、数组名和过程名
- 常数：各种类型的常数
- 运算符：+，-，*，/，…
- 界符：逗号、分号、括号和空白

词法分析器的输出

输出的单词符号的表示形式
- (单词种别，单词自身的值)
单词种别通常用整数编码表示
- 若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和界符都是一符一种。
- 若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。
  - 标识符单列一种；标识符自身的值表示成按机器字节划分的内部码
  - 常数按类型分种；常数的值则表示成标准的二进制形式

来看两个例子：

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

词法分析作为一个独立的阶段
- 结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题
但不一定不作为单独的一遍
- 将其处理为一个子程序

词法分析器在编译器中地位

词法分析器的结构

整体结构如下：

扫描缓冲区

超前搜索

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

基本字识别
- 例如
  DO99K=1，10(等价于DO 99 K = 1，10)
  DO99K=1.10
  IF(5.EQ.M)GOTO55(等价于IF (5.EQ.M) GOTO 55)
  IF(5)=55
- 需要超前搜索才能确定哪些是基本字
标识符识别
- 字母开头的字母数字串，后跟界符或算符
常数识别
- 识别出算术常数并将其转变为二进制内码表示
  5.EQ.M
  5.E08
算符和界符的识别
- 把多字符组成的算符和界符拼合成一个单词符号
```
:=， **， .EQ. ， ++，--，>=
```

几点限制——不必使用超前搜索

所有基本字都是保留字；用户不能用它们作自己的标识符
基本字作为特殊的标识符来处理，使用保留字表
如果基本字、标识符和常数(或标号)之间没有确定的运算符或界符作间隔，则必须使用一个空白符作间隔
- DO99K=1，10
- 要写成DO 99 K=1，10

状态转换图

状态转换图是一张有限方向图
- 结点代表状态，用圆圈表示
- 双圆圈表示接受状态，双圆圈上方加$\star$表示最后读入的字符不属于刚才的单词
- 状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类
- 一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态
状态转换图可用于识别(或接受)一定的字符串
- 若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于$α$，则称$α$被该状态转换图所识别(接受)

词法分析器的设计示例

一个简单的程序设计语言
- 单词表
- 设计状态转换图

状态转换图的程序实现

还是以之前的状态转换图为例：

每个状态结点对应一小段程序：

不含回路的分叉结点
- 可用一个CASE语句或一组IF-THEN-ELSE语句实现
含回路的状态结点
- 对应一段由WHILE结构和IF语句构成的程序
终态结点
- 表示识别出某种单词符号，对应返回语句

完整实现

首先定义如下符号：

全局变量与过程
- ch字符变量，存放最新读入的源程序字符
- strToken字符数组，存放构成单词符号的字符串
- GetChar子程序过程，把下一个字符读入到ch中
- GetBC子程序过程，跳过空白符，直至ch中读入一非空白符
- Concat子程序，把ch中的字符连接到strToken
- IsLetter和IsDisgital 布尔函数，判断ch中字符是否为字母和数字
- Reserve整型函数，对于strToken中的字符串查找保留字表，若它是保留字则给出它的编码，否则回送0
- Retract子程序，把搜索指针回调一个字符位置
- InsertId整型函数，将strToken中的标识符插入符号表，返回符号表指针
- InsertConst 整型函数过程，将strToken中的常数插入常数表，返回常数表指针

int code, value;
strToken := “ ”;	/*置strToken为空串*/
GetChar(); GetBC();
if (IsLetter())
begin
	while (IsLetter() or IsDigit())
	begin
		Concat(); GetChar(); 
	end
	Retract();
	code := Reserve();
	if (code = 0)
	begin
		value := InsertId(strToken);
		return ($ID, value);
	end
	else
		return (code, -);	
end

else if (IsDigit())
begin
	while (IsDigit())
	begin
		Concat( ); GetChar( );
	end
	Retract();
	value := InsertConst(strToken);
	return($INT, value);
end
else if (ch =‘=’) return ($ASSIGN, -);
else if (ch =‘+’) return ($PLUS, -);

else if (ch =‘*’)
begin
	GetChar();
	if (ch =‘*’) return ($POWER, -);
	Retract(); return ($STAR, -);
end
else if (ch =‘,’) return ($COMMA, -);
else if (ch =‘(’) return ($LPAR, -);
else if (ch =‘)’) return ($RPAR, -);
else ProcError( );		/* 错误处理*/

将状态图的代码一般化

变量$\text{curState}$用于保存现有的状态
用二维数组表示状态图：$\text{stateTrans[state][ch]}$
通用框架如下：

curState = 初态
GetChar();
while( stateTrans[curState][ch]有定义){
   //存在后继状态，读入、拼接
   Concat();
   //转换入下一状态，读入下一字符
   curState= stateTrans[curState][ch];
   if curState是终态 then 返回strToken中的单词
   GetChar( ); 
}

第4讲 词法分析1

词法分析概述

词法分析的任务

词法分析器的功能

词法分析器的输出

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

词法分析器在编译器中地位

词法分析器的结构

扫描缓冲区

超前搜索

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

几点限制——不必使用超前搜索

状态转换图

词法分析器的设计示例

状态转换图的程序实现

完整实现

将状态图的代码一般化

第4讲词法分析1