《编译原理-第三章》由会员分享，可在线阅读，更多相关《编译原理-第三章（117页珍藏版）》请在金锄头文库上搜索。
1、编译原理 第三章 词法分析 王金伟 计算机与信息工程学院 天津师范大学 *1TJNU-COCIE-WJW 第三章 词法分析 n3.1 对于词法分析器的要求 n3.2 词法分析器的设计 n3.3 正规表达式与有限自动机 n3.4 词法分析器的自动产生（LEX） Date 2TJNU-COCIE-WJW n词法分析的任务 从左至右逐个字符的对源程序进行扫描，产生 一个个的单词符号，把作为字符串的源程序改 造成为由单词符号串组成的程序 n词法分析器：执行词法分析的程序 输入：源程序 输出：单词符号 n词法分析器的构造方法 手工方法：根据词法直接编程序(有限自动机) 自动方法：利用一些工具Lex Da
2、te 3TJNU-COCIE-WJW 3.1 对词法分析器的要求 源程序 词法分析器 单词符号 1.单词符号概念 指语言中具有独立意义的最小的语法符号 例例：C = A * 3.14 + 5 单词： C，A 变量 3.14, 5 常数 = ，*，+ 算符 一、词法分析器的功能和输出形式 Date 4TJNU-COCIE-WJW 2.单词的种类 （1）基本字（保留字，关键字） 由程序语言定义的具有固定意义的标识符。 用户不能用来表示变量名，函数名等标识符 例例：C语言中的“if” “else” “while” （2）标识符 用户使用的，用来表示各种名字，变量名，函 数名等 Date 5TJNU-
3、COCIE-WJW 2.单词的种类（续） （3）常数 整型、实型、逻辑、字符 例：1000，3.14，TRUE，“Abcd” （4）运算符 +、-、*、/ （5）界符 ， ； （） Date 6TJNU-COCIE-WJW 词法分析器输出的单词符号常常用二元式来表示： 二、单词的表示形式 Date 7TJNU-COCIE-WJW 1. 单词种别 通常用整数编码来表示 （1）关键字，运算符，界符 n一字一种编码（处理起来比较方便） n n 例例：if，else，(，+， （2）常数 n按类型分别给出编码 例例：整型，实型，布尔型， （3）标识符 n统归一种，只给一个编码 n n 例例：变量名，函
4、数名等都是一种编码 Date 8TJNU-COCIE-WJW 1. 单词种别（续） 注意注意： (1)若一个种别只包含一个单词符号（一种一字） ，对于该单词符号，种别编码就可以代表它自身 了。 例如例如：关键字，运算符，界符 (2)若一个种别包含有多个单词符号（一种多字） ，对于该种别的每个单词符号，除了给出种别编 码，还需给出单词符号的属性值 例如例如：整型常数，实型常数，布尔常数，标识符 Date 9TJNU-COCIE-WJW 2.单词符号的属性信息 单词符号的属性：指单词符号的特性或特征 单词符号的属性值：反映单词特性或特征的值 Date 10TJNU-COCIE-WJW 2.单词符号
5、的属性信息（续） 属性值的表示方法： （1）基本字，运算符，界符（一字一种） n只给其种别编码，不给出它的属性值 n n 例例：基本字while表示成： （2）常数 n表示成标准的二进制形式 n n 例例：1024表示成： （3）标识符 n用字符串编码或对应的符号表项地址 n n 例例：name表示成： 或 Date 11TJNU-COCIE-WJW 例例1 1：FORTRAN编译程序的词法分析器，在扫描输 入串： IF （5. EQ .M） GOTO 100 输出的单词如下： 单词符号 nIF n左括号 n整常数 n等号 n标识符 n右括号 nGOTO n标号 三、例子 Date 12TJN
6、U-COCIE-WJW 例例2 2：考虑下面C+的一段代码： while ( i = j) i-; 经词法分析器处理后，将被转换成如下单词符号序列： 单词符号 nwhile n( ni n= ，- nj n) ni n- n； Date 13TJNU-COCIE-WJW 3.2 词法分析器的设计 源程序 预处理 子程序 输入 缓冲区 扫描器 扫描缓冲区 输入 列表 单词符号 一、词法分析器的结构 Date 14TJNU-COCIE-WJW 1. 输入缓冲区、预处理子程序 （1）输入源程序文本，放入输入缓冲区中，词 法分析工作可在这个输入缓冲区中工作 （2）剔除无用的空白，跳格(TAB)，回车，
7、换 行等编辑性字符；若空白符号为单词符号的界 符，就将若干空白和并为1个 （3）剔除注释行，比如/*/ （4）如果是FORTRAN语言，区分标号区、续 行区和给出句末符 （5）源程序的出错列表打印 （6）将预处理好的子程序放到扫描缓冲区中 Date 15TJNU-COCIE-WJW 2.扫描缓冲区、扫描器 （1）扫描缓冲区 n设两个半区，可互补使用 n设两个指针 起点指针：指出正在识别单词起点位置 搜索指针：向前搜索以寻找单词终点 （2）扫描器：扫描缓冲区，直接进行单词的识别 前半区后半区 起点指针搜索指针 Date 16TJNU-COCIE-WJW 源程序 预处理 子程序 输入 缓冲区 扫描
8、器 扫描缓冲区 输入 列表 单词符号 二、词法分析器的工作过程 Date 17TJNU-COCIE-WJW 1. 超前搜索 (1)关键字的识别 前提：允许用户使用基本字（关键字） 例例：试分析下面FORTRAN的几个语句 （1） DO99K=1，10 （2） IF(S.EQ.M) GOTO 55 （3） DO99K=1.10 （4） IF(S)=55 超前扫描很多字符，直到扫描到可以肯定词性的 地方为止 PROGRAM SUM S=0 DO 99 I=1,100 S=S+I 99 CONTINUE END 三、单词符号的识别 Date 18TJNU-COCIE-WJW 1. 超前搜索法（续1）
9、 (2) 标识符的识别 一般是以字母开头后跟数字/字母的字符串，后边 一般都有算符和界符，比较好识别 (3)常数的识别 例例：对于FORTRAN 5.EQ.M（5=M） 5.E08 （5*108) 直到超前扫描到字母Q时才能 确定5的词性 3HABC（“ABC”） 3H是词头，代表长度为3的字 符串常数 Date 19TJNU-COCIE-WJW 1. 超前搜索法（续2） (4) 算符和界符的识别 应将那些由多个字符复合成的算符和界符拼成一 个单词符号 例例：+ - = Date 20TJNU-COCIE-WJW 2. 直接分析法 （1）基本思想 根据读来的第一个字符的种 类分别转到各种子程序
10、处理。这些子程序 功能就是识别以相应字符开头的各种单词 。 （2）方法 以FORTRAN语言为例，分成几种情况 以字母开头的 基本字、标识符、格式说明 符， nIF nWHILE Date 21TJNU-COCIE-WJW 2. 直接分析法（续1） 以小数点开头的 n.34.EQ. .TRUE. .FALSE. 等 以数字开头的 n常数、格式语句、重复说明 nWRITE(6,10) X,Y 10 FORMAT(2X, F10.4, F9.3) 以*开头的：* * 除此之外：都是一个基本字符表示一个单词 Date 22TJNU-COCIE-WJW 子 程 序 1 子 程 序 2 子 程 序 3
11、子 程 序 4 子 程 序 5 下一个语句 字符是否读来 该字符是什么 读 一 个 符 号 字母 数字 * 其他 出口 否 是 2. 直接分析法（续2） 分析流程图 Date 23TJNU-COCIE-WJW 3. 状态转换图法 (1)状态转换图：一张有限方向图 (2)状态转换图的功能 识别（接受）一定的符号串（单词） Date 24TJNU-COCIE-WJW 3. 状态转换图法（续1） (3)状态转换图的结构 结点：代表状态，用圆圈表示 箭弧：状态之间用箭弧连接 箭弧上的标记：代表在射出节点下可能出现 的字符或字符串 例例： 注意注意：一个完整的状态转换图有n个状态，其中 有一个初态，至少
12、要有一个终态(用双圆圈表示 ) Date 25TJNU-COCIE-WJW 3. 状态转换图法（续2） (4)举例 例例1 1：构造一个识别标识符的状态转换图 解： 其中“*”表示在该状态下多读进一个字符 识别：name1 Date 26TJNU-COCIE-WJW 3. 状态转换图法（续3） 例例2 2：构造一个识别整数的状态转换图，说说 识别256过程 解： Date 27TJNU-COCIE-WJW 3. 状态转换图法（续4） 例例3 3： 识别FORTRAN实型常数的状态转换图 解： 实数：小数形式：3.413.4 34. 指数形式：3E+05 即 3X105 Date 28TJNU-
13、COCIE-WJW 四、综合例子 用状态转换图法，构造一个识别某一个简单语 言（SL）的所有单词符号的词法分析器 Date 29TJNU-COCIE-WJW 单词单词 符号种别编码别编码助记记符号内码值码值 DIM IF DO STOP END 标识标识 符 常数（整型） = + * * , （ ） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 $DIM $IF $DO $STOP $END $ID $INT $ASSIGN $PLUS $STAR $POWER $COMMA $LPAR $RPAR - - - - - 内部字符串 标标准二进进制 - - - - - - -
14、 1、SL的单词符号及其内部表示（P42) Date 30TJNU-COCIE-WJW 2.为了讨论方便，对SL加三点限制 （1）所有基本字都规定为保留字（用户不能 用它们来定义标识符的，避免超前搜索 ） （2）对基本字只构造一个基本字表，不构造 其状态转换图（只要识别出是一个标识符 ，就去查基本字表看看是否是基本字） （3）对基本字，标识符和常数之间要留有间 隔符（避免超前搜索） Date 31TJNU-COCIE-WJW 3.构造能够识别SL单词 的状态转换图(P43) Date 32TJNU-COCIE-WJW 4. 状态转换图的程序实现 思路：为每个状态结点都编写一个子程序 首先，设以
15、下一些变量或过程 ch:字符变量,存放最新读进的源程序字符 strToken:字符数组,存放构成单词符号的字符串 GetChar:子程序过程,将下一输入字符读到ch中,搜索 指示器前移一字符位置 GetBC:子程序过程,检查ch中的字符是否为空白,若是, 则调用GetChar直至ch中进入一个非空白字符 Concat:子程序过程,将ch中的字符连接到strToken之 后.例如,假定strToken原来的值为“AB”,而ch中存放 着C,经调用Concat后,strToken的值就变为“ABC” Date 33TJNU-COCIE-WJW IsLetter和IsDigit:布尔函数过程,他们分
16、别判断 ch中的字符是否为字母和数字 Reserve:整型函数过程,对strToken中的字符串 查找保留字表,若它是一个保留字则返回它的编 码，否则返回0值（假定0不是保留字的编码） Retract:子程序过程,将搜索指示器回调一个字位 置，将ch置为空白字符 InsertId:整型函数过程,将strToken中的标识符 插入符号表,返回符号表指针。 InsertConst:整型函数过程,将strToken中的常 数插入到常数符号表,放回常数表针 Date 34TJNU-COCIE-WJW 然后，对每个状态编写一个对应的程序 (1)对于不含回路的状态结点，采用分叉法 例例： GetChar(); If(IsLetter() 状态j对应的程序段 Else if(IsDigit() 状态k对应的程序段 Else if(ch=/) 状态l对应的程序段 Else 错误处理 Date 35TJNU-COCIE-WJW
