程序设计语言 编译原理(第三版)第3章

第3章 词法分析任务：从左至右逐个字符地对源程序进行扫 描，产生一个个的单词符号，把作为 字符串的源程序改造成为单词符号串。 §3.1 §3.2 §3.3 §3.4 对于词法分析器的要求 词法分析器的设计 正规表达式与有限自动机 词法分析器的自动产生(LEX) —略1

§3.1 对于词法分析器的要求 一.功能和输出形式 二.接口设计

§3.1对于词法分析器的要求一. 功能和输出形式1.功能：输入源程序，输出单词符号 2.单词符号的分类 (1)关键字:由程序语言定义的具有固定意义的标识符，也 称为保留字或基本字。 例如：Pascal 语言中 begin (2)标识符：用来表示各种名字。 end if while 等。

如变量名、数组名、过程名等。 (3)常数：整型、实型、布尔型、文字型等 例：100 (5)界符： , ; 3.14159 ( ) true 等 sample (4)运算符：+、-、*、/3

§3.1对于词法分析器的要求3.输出的单词符号形式 二元式：(单词种别，单词符号的属性值)通常用“整数编码”

“单词符号的特征或特性”

单词符号的编码：

标识符：一般统归为一种常数：常按整型、实型、布尔型等分类 关键字：全体视为一种/一字一种 运算符：一符一种 界符：一符一种4

§3.1对于词法分析器的要求例：考虑下述C++代码段：while ( i >= j ) i - -; 经词法分析器处理后，它将被转换为如下的 单词符号序列：< while , - > <(,-> < id ,指向i的符号表项的指针> <>=,-> < id ,指向j的符号表项的指针> < ), - > < id ,指向i的符号表项的指针> < --, - > <;,->

§3.1对于词法分析器的要求二.接口设计1.词法分析器作为独立的一遍词法分析

字符流 (源程序)

单词序列 (输出在一个中间文件上)

2.词法分析器作为一个独立的子程序，但并不 一定作为独立的一遍语法分析器单词(至少一个) 调用(取下一个单词)

词法分析器

优点：使整个编 译程序的结构更 简洁、清晰和条 理化.6

§3.2 词法分析器的设计 一.输入和预处理 二.单词符号的识别 三.状态转换图及其实现

§3.2词法分析器的设计一. 输入、预处理1.预处理：剔掉空白符、跳格符、回车符、换行符、 注解部分等.

原因：编辑性字符除了出现在文字常数中之外，在别

处的任何出现都无意义. #注解部分不是程序的必要组成部分，它的作用 仅在于改善程序的易读性和易理解性.8

§3.2词法分析器的设计2. 预处理子程序： 每当词法分析器调用时，就处理出一串确定长 度(如120个字符)的输入字符，并将其装进词法 分析器所确定的扫描缓冲区中。

§3.2词法分析器的设计扫描缓冲区的两

个指示器：

一个指向当前正在识别的单词的开始位置(即新单词的首字符) 起点指示器 一个用于向当前搜索以寻找单词的终点 搜索指示器

起点指示器

搜索指示器10

图 _ 源程序输入缓冲区的对半互补结构

§3.2词法分析器的设计二. 单词符号的识别——超前搜索1.关键字的识别:---FORTRAN语言的需要超前搜索.

2.标识符的识别:在程序中标识符的出现都后跟着算符或界符. 3.常数的识别: 多数语言算术常数的表示大体相似,对它们的识 别也是很直接的;但对于某些语言的常数的识别 也需用超前搜索的方法;逻辑常数和用引号括起 来的字符串常数很容易识别. 4.算符和界符的识别: 应将那些由多个字符复合成的算符和界符 拼合成一个单词符号,因为这些字符串是 不可分的整体,若分划开来,便失去了原来 的意义.---需用超前搜索的方法11

§3.2词法分析器的设计三. 状态转换图及其实现1.状态转换图及其示例状态转换图: 有限方向图.结点: 代表状态, 用圆圈表示, 状态之间用弧连接. 箭弧上的标记(字符): 代表在射出结点(即始结点)状

态下可能出现的输入字符或字符类.

一张转换图只包含有限个状态(即有限个结点), 其中一 个为初态,而且实际上至少要有一个终态(用双圈表示).

§3.2词法分析器的设计例:0字母或数字

字母

1

其它

2

*

数字

0

数字

1

其它

2

*

例: (课本42页表3.1; 43页图3.3)

§3.2词法分析器的设计2. 状态转换图的实现实现方法: 用程序实现, 让每个状态结点对应一小段程序。 A、变量和过程说明 ① ch 字符变量，存放最新读进的源程序字符。 ② strToken 字符数组，存放构成单词符号的字符串。 ③ GetChar 子程序过程，将下一输入字符读到ch中，搜索指 示器前移一字符位置。

④ GetBC⑤ Concat

子程序过程，检查ch中的字符是否为空白。若是，则调用GetChar直至ch中进入一个非空白字符。 子程序过程，将ch中的字符连接到strToken之后.14

§3.2词法分析器的设计⑥ IsLetter和IsDigit 布尔函数过程，它们分别判断ch中的 字符是否为字母和数字。 ⑦ Reserve 整型函数过程，对strToken中的字符串查找 保留字表，若它是一个保留字则返回它的编码，否则 返回0值(假定0不是保留字的编码)。 ⑧ Retract 子程序过程，将搜索指示器回调一个字符位置， 将ch置为空白字符。 ⑨ InsertId 整型函数过程，将strToken中的标识符插入

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

§3.2词法分析器的设计B、示例小程序字母

j k l

i

数字

/

图中结点i所对应的程序段可表示为：

GetChar (); if ( IsLetter( ) ) {…状态j的对应程序段…;} else if ( IsDigit( ) ) {…状态k的对应程序段…;} else if ( ch= / ) {…状态l的对应程序段…;} else {…错误处理…;} 图中结点i所对应的程序段可表示为： GetChar (); while (IsLetter ( ) or IsDigit ( ) ) GetChar ( ); …状态j的对应程序段…16

字母或数字

i

其它

j

§3.2词法分析器的设计

C、示例大程序 课本43页图3.3;45--46页

§3.3 正规表达式与有限自动机一.单词符号的描述 1. 正规式与正规集 2. 正规文法 二.有限自动机 1.DFA 2.NFA 3. NFA与DFA的等价 4. DFA的化简 三.正规式与有限自动机的等价性 四.正规文法与有限自动机的等价性18

§3.3正规表达式与有限自动机一.单词符号的描述1. 正规式与正规集

(1) 递归定义 ﹑Ф都是∑上的正规式, 正规集-----{ }和{Ф} a∈∑,a-----正规式，正规集-----{a} U﹑V-----正规式，正规集-----L(U)和L(V), 那么(U|V),(U V)和(U)*也都是正规式， 正规集-----L(U)∪ L(V),L(U)L(V)和 (L(U))* 仅由有限次使用上述三步骤而得到的表达式才是∑上的 正规式，仅由这些正规式所表示的字集才是∑上正规集。19

本文来源：https://www.bwwdw.com/article/xidq.html