编译原理之词法分析

1、LI Wensheng, SCST, BUPT 第第3 3章章 词法分析词法分析基础知识：基础知识：PASCALPASCAL、C C语言、正规表达式语言、正规表达式 正规文法、有限自动机知识点：词法分析器的作用、地位知识点：词法分析器的作用、地位 记号、模式 词法分析器的状态转换图Wensheng Li BUPT 20082/78词法分析词法分析 简介简介3.1 3.1 词法分析程序与语法分析程序的关系词法分析程序与语法分析程序的关系3.2 3.2 词法分析程序的输入与输出词法分析程序的输入与输出3.3 3.3 记号的描述和识别记号的描述和识别3.4 3.4 词法分析程序的设计与实现词法分析程

2、序的设计与实现3.5 3.5 软件工具软件工具LEXLEX 小结小结Wensheng Li BUPT 20083/78简介简介n任务：把构成源程序的字符串转换成语义上关联的记号序列任务：把构成源程序的字符串转换成语义上关联的记号序列n编译程序是在单词的级别上来分析和翻译源程序，因此，词编译程序是在单词的级别上来分析和翻译源程序，因此，词法分析是编译的基础法分析是编译的基础n本章内容安排本章内容安排 讨论用手工方式设计并实现词法分析程序的方法和步骤讨论用手工方式设计并实现词法分析程序的方法和步骤词法分析程词法分析程序序的作用的作用词法分析程序的地位词法分析程序的地位源程序的输入与词法分析程源程序

3、的输入与词法分析程序序的输出的输出单词符号的描述及识别单词符号的描述及识别词法分析程词法分析程序序的设计与实现的设计与实现 词法分析程词法分析程序自动序自动生成工具生成工具LEXLEX简介简介Wensheng Li BUPT 20084/78词法分析程序的作用词法分析程序的作用n源程序由单词组成，单词是最小的语义单位源程序由单词组成，单词是最小的语义单位n词法分析程词法分析程序序的作用：的作用： 扫描源程序字符流扫描源程序字符流 按照源语言的词法规则识别出各类单词符号按照源语言的词法规则识别出各类单词符号 产生用于语法分析的记号序列产生用于语法分析的记号序列 词法检查词法检查 创建符号表创建符

4、号表 把识别出来的标识符插入符号表中把识别出来的标识符插入符号表中 与用户接口的一些任务：与用户接口的一些任务：跳过源程序中的注释和空白跳过源程序中的注释和空白把错误信息和源程序联系起来把错误信息和源程序联系起来Wensheng Li BUPT 20085/783.1 3.1 词法分析程序与语法分析程序的关系词法分析程序与语法分析程序的关系n词法分析程序与语法分析程序之间的三种关系词法分析程序与语法分析程序之间的三种关系词法分析程序作为独立的一遍词法分析程序作为独立的一遍词法分析程词法分析程序序作为语法分析程作为语法分析程序序的子程序的子程序词法分析程词法分析程序序与语法分析程与语法分析程序序

5、作为协同程序作为协同程序n分离词法分析程分离词法分析程序序的好处的好处n词法分析的一些难点词法分析的一些难点Wensheng Li BUPT 20086/78词法分析程序作为独立的一遍词法分析程序作为独立的一遍n输出放入一个中间文件输出放入一个中间文件 磁盘文件磁盘文件 内存文件内存文件字符串源程序字符串源程序字符字符词法分析程序词法分析程序记号记号记号流源程序记号流源程序Wensheng Li BUPT 20087/78词法分析程序作为语法分析程词法分析程序作为语法分析程序序的子程序的子程序n避免了中间文件避免了中间文件n省去了取送符号的工作省去了取送符号的工作n有利于提高编译程有利于提高编

6、译程序序的效率的效率语法语法分析器分析器词法词法分析器分析器取下一记号取下一记号字符串字符串源程序源程序字符字符记号记号符号表符号表Wensheng Li BUPT 20088/78词法分析程序与语法分析程词法分析程序与语法分析程序序作为协同程序作为协同程序n协同程序：协同程序： 如果两个或两个以上的程如果两个或两个以上的程序，它们之间交叉地执行，序，它们之间交叉地执行，这些程序称为协同程序。这些程序称为协同程序。词法分析程序与语法分析程词法分析程序与语法分析程序在同一遍中，以生产者和序在同一遍中，以生产者和消费者的关系同步运行。消费者的关系同步运行。P1P2唤醒唤醒P2唤醒唤醒P1唤醒唤醒P

7、2唤醒唤醒P1Wensheng Li BUPT 20089/78分离词法分析程序的好处分离词法分析程序的好处n可以简化设计可以简化设计词法程词法程序序很容易识别并去除空格、注释，使语法分析程很容易识别并去除空格、注释，使语法分析程序序致力于语法分析，结构清晰，易于实现。致力于语法分析，结构清晰，易于实现。n可以改进编译程可以改进编译程序序的效率的效率利用专门的读字符和处理记号的技术构造更有效的词法分利用专门的读字符和处理记号的技术构造更有效的词法分析程析程序序。n可以加强编译程可以加强编译程序序的可移植性的可移植性在词法分析程在词法分析程序序中处理特殊的或非标准的符号。中处理特殊的或非标准的符

8、号。Wensheng Li BUPT 200810/78词法分析的一些难点词法分析的一些难点n位置对准位置对准FortranFortran要求某些结构出现在输入行的固定位置要求某些结构出现在输入行的固定位置n空白不作为分隔符空白不作为分隔符FortranFortran中空格是无意义的，可以随便加入中空格是无意义的，可以随便加入DO 5 I = 1.25 （赋值语句，（赋值语句，DO5I是标识符）是标识符）DO 5 I = 1,25 （循环语句，（循环语句，DO是关键字）是关键字）n关键字不保留关键字不保留PL/IPL/I语言的关键字不保留语言的关键字不保留IF THEN THEN THEN=E

9、LSE; ELSE ELSE=THENWensheng Li BUPT 200811/783.2 3.2 词法分析程序的输入与输出词法分析程序的输入与输出一、词法分析程一、词法分析程序序的实现方法的实现方法二、设置缓冲区的必要性二、设置缓冲区的必要性三、配对缓冲区三、配对缓冲区四、词法分析程四、词法分析程序序的输出的输出Wensheng Li BUPT 200812/78一、词法分析程序的实现方法一、词法分析程序的实现方法n利用词法分析程利用词法分析程序自动序自动生成器生成器从基于正规表达式的规范说明自动生成词法分析程从基于正规表达式的规范说明自动生成词法分析程序序。生成器提供用于源程序字符流

10、读入和缓冲的若干子程序生成器提供用于源程序字符流读入和缓冲的若干子程序n利用传统的系统程序设计语言来编写利用传统的系统程序设计语言来编写利用该语言所具有的输入利用该语言所具有的输入/ /输出能力来处理读入操作输出能力来处理读入操作n利用汇编语言来编写利用汇编语言来编写直接管理源程序字符流的读入直接管理源程序字符流的读入Wensheng Li BUPT 200813/78二、设置缓冲区的必要性二、设置缓冲区的必要性n超前搜索：为了得到某一个单词符号的确切性质，超前搜索：为了得到某一个单词符号的确切性质，需要超前扫描若干个字符。需要超前扫描若干个字符。例：有合法的例：有合法的FORTRANFORT

11、RAN语句：语句： DO99K=1,10 DO99K=1,10 和和 DO99K=1.10DO99K=1.10 为了区别这两个语句，必须超前扫描到等号后的第一个为了区别这两个语句，必须超前扫描到等号后的第一个分界符处分界符处。例：例：PascalPascal语言中：语言中：、:=:=、（、（* *例：例：C C语言中：语言中：=、/ /* *、/、+n 方便实现读字符和退字符操作，提高词法分析器方便实现读字符和退字符操作，提高词法分析器的效率的效率Wensheng Li BUPT 200814/78三、配对缓冲区三、配对缓冲区n原因：不论缓冲器多大都不能保证单词不被它的边原因：不论缓冲器多大都

12、不能保证单词不被它的边界打断界打断n把一个缓冲器分为相同的两半，每半各含把一个缓冲器分为相同的两半，每半各含N N个字符，个字符，一般一般N=1KBN=1KB或或4KB4KB。n基本方法基本方法开始指针开始指针 向前指针向前指针 i f x = y t h e n j : = j + 2 ; eof Wensheng Li BUPT 200815/78测试指针的过程测试指针的过程(1)(1)IF (向前指针在左半区的终点向前指针在左半区的终点) 读入字符串，填充右半区读入字符串，填充右半区;向前指针前移一个位置向前指针前移一个位置;ELSE IF (向前指针在右半区的终点向前指针在右半区的终点

13、) 读入字符串，填充左半区读入字符串，填充左半区; 向前指针移到缓冲区的开始位置向前指针移到缓冲区的开始位置; ELSE 向前指针前移一个位置向前指针前移一个位置;Wensheng Li BUPT 200816/78每半区带有结束标记的缓冲器每半区带有结束标记的缓冲器开始指针开始指针向前指针向前指针 i f x = y t h eof e n j : = j + 2 ; eof eofn 基本方法的缺点：基本方法的缺点：更新向前指针时要做二次测试更新向前指针时要做二次测试n 改进：每半区带有结束标记的缓冲器改进：每半区带有结束标记的缓冲器更新向前指针时只要做一次测试更新向前指针时只要做一次测试

14、Wensheng Li BUPT 200817/78测试指针的过程测试指针的过程(2)(2)向前指针前移一个位置；向前指针前移一个位置；IF (向前指针指向向前指针指向 eof ) IF (向前指针在左半区的终点向前指针在左半区的终点) 读入字符串，填充右半区读入字符串，填充右半区; 向前指针前移一个位置向前指针前移一个位置; ELSE IF (向前指针在右半区的终点向前指针在右半区的终点) 读入字符串，填充左半区读入字符串，填充左半区; 向前指针指向缓冲区的开始位置向前指针指向缓冲区的开始位置; ; ELSE 终止词法分析终止词法分析;Wensheng Li BUPT 200818/78四、

15、词法分析程序的输出四、词法分析程序的输出记号记号n记号、模式和单词记号、模式和单词 记号：是指某一类单词符号的种别编码，如标识符的记号记号：是指某一类单词符号的种别编码，如标识符的记号为为id，数的记号为，数的记号为num等。等。 模式：是指某一类单词符号的构词规则，如标识符的模式模式：是指某一类单词符号的构词规则，如标识符的模式是是“由字母开头的字母数字串由字母开头的字母数字串”。 单词：是指某一类单词符号的一个特例，如单词：是指某一类单词符号的一个特例，如position是是标识符。标识符。机内表示机内表示外部表示外部表示构词规则构词规则1.关键字关键字 记号的种类记号的种类2.标识符标识

16、符 3.常数常数4.运算符运算符5.分界符分界符Wensheng Li BUPT 200819/78记号的属性记号的属性n词法分析程序在识别出一个记号后，要把与之有关的信息作词法分析程序在识别出一个记号后，要把与之有关的信息作为它的属性保留下来。为它的属性保留下来。n记号影响语法分析的决策，属性影响记号的翻译。记号影响语法分析的决策，属性影响记号的翻译。n在词法分析阶段，对记号只能确定一种属性在词法分析阶段，对记号只能确定一种属性关键字：一字一种或全体一种，前一种方法较好关键字：一字一种或全体一种，前一种方法较好标识符：一般统归一种，也可分为若干种标识符：一般统归一种，也可分为若干种常数：一般

17、统归一种，也可按类型分种常数：一般统归一种，也可按类型分种运算符：一符一种或一类一种运算符：一符一种或一类一种分界符：一般用一符一种分界符：一般用一符一种n记号的属性是指记号的特征或特性，反映特征或特性的值是记号的属性是指记号的特征或特性，反映特征或特性的值是属性值属性值n一种一符则种别值可以认为是属性值，一种多符则需给出属一种一符则种别值可以认为是属性值，一种多符则需给出属性值性值Wensheng Li BUPT 200820/78total:=total+ratetotal:=total+rate* *4 4 的词法分析结果的词法分析结果Wensheng Li BUPT 200821/78

18、3.3 3.3 记号的描述和识别记号的描述和识别n识别单词是按照记号的模式进行的，一种记号的模识别单词是按照记号的模式进行的，一种记号的模式匹配一类单词的集合。式匹配一类单词的集合。为设计词法程序，对模式要给出规范、系统的描述。为设计词法程序，对模式要给出规范、系统的描述。n正规表达式和正规文法是描述模式的重要工具。正规表达式和正规文法是描述模式的重要工具。二者具有同等表达能力二者具有同等表达能力正规表达式：清晰、简洁正规表达式：清晰、简洁正规文法：便于识别正规文法：便于识别 一、词法与正规文法一、词法与正规文法 二、记号的文法二、记号的文法 三、状态转换图与记号的识别三、状态转换图与记号的识

19、别Wensheng Li BUPT 200822/78一、词法与正规文法一、词法与正规文法n把源语言的文法把源语言的文法G G分解为若干子文法：分解为若干子文法：G G0 0、 G G1 1、G G2 2、G Gn n 正规文法正规文法 上下文无关文法上下文无关文法 语法语法 词法词法n词法：描述语言的标识符、常数、运算符和标点符词法：描述语言的标识符、常数、运算符和标点符号等记号的文法号等记号的文法n语法：借助于记号来描述语言的结构的文法语法：借助于记号来描述语言的结构的文法文法？文法？Wensheng Li BUPT 200823/78二、记号的文法二、记号的文法n标识符标识符n常数常数整

20、数整数无符号数无符号数n运算符运算符n分界符分界符n关键字关键字Wensheng Li BUPT 200824/78标识符标识符n标识符定义为标识符定义为“由字母打头的、由字母或数字组成由字母打头的、由字母或数字组成的符号串的符号串”n描述标识符集合的正规表达式：描述标识符集合的正规表达式：letter(letter|digit)*n表示标识符集合的正规定义式：表示标识符集合的正规定义式： letter A|B|Z|a|b|z digit 0|1|9 id letter(letter|digit)*正规表达式？正规表达式？Wensheng Li BUPT 200825/78把正规定义式转换为相

21、应的正规文法把正规定义式转换为相应的正规文法 ( letter | digit )* = | ( letter | digit )+ = | ( letter | digit ) ( letter | digit )* = | letter ( letter | digit )* | digit ( letter | digit )* = | (A|Z|a|z) ( letter | digit )* | (0|9)( letter | digit )* = | A ( letter | digit )* | | Z ( letter | digit )* | a ( letter | dig

22、it )* | | z ( letter | digit )* | 0 ( letter | digit )* | | 9 ( letter | digit )* Wensheng Li BUPT 200826/78标识符的正规文法标识符的正规文法 id A rid|Z rid|a rid|z ridrid |A rid|B rid|Z rid |a rid|b rid|z rid |0 rid|1 rid|9 ridn一般写作：一般写作： id letter ridrid | letter rid | digit ridWensheng Li BUPT 200827/78常数常数整数整数n描

23、述整数结构的正规表达式为：描述整数结构的正规表达式为： (digit)+n对此正规表达式进行等价变换：对此正规表达式进行等价变换： (digit)+ = digit(digit)* (digit)* = | digit(digit)*n整数的正规文法：整数的正规文法： digits digit remainder remainder | digit remainder Wensheng Li BUPT 200828/78常数常数无符号数无符号数n无符号数的正规表达式为：无符号数的正规表达式为：(digit)+ (.(digit)+)? (E(+|-)?(digit)+)?n正规定义式为正规定义

24、式为digit 0|1|9digits digit+optional_fraction (.digits)?optional_exponent (E(+|-)?digits)?num digits optional_fraction optional_exponentWensheng Li BUPT 200829/78把正规定义式转换为正规文法把正规定义式转换为正规文法 ( digit )+ ( . ( digit )+ )? ( E( + | - )?( digit )+ )?=( digit )+ ( . ( digit )+ | ) ( E(+ |- | ) ( digit )+ | )

25、=digit (digit)* ( . digit ( digit )*| ) ( E (+|-| ) digit ( digit )* | )num1 num1 表示无符号数的第一个数字之后的部分表示无符号数的第一个数字之后的部分num2 num2 表示小数点以后的部分表示小数点以后的部分num3 num3 表示小数点后第一个数字以后的部分表示小数点后第一个数字以后的部分num4 num4 表示表示E E之后的部分之后的部分num5 num5 表示表示(digit)(digit)* *digits digits 表示表示(digit)(digit)+Wensheng Li BUPT 2008

26、30/78无符号数分析图无符号数分析图 digit (digit)* (. digit (digit)*|) (E (+|-|) digit (digit)* |)num3num2num1num4numnum digit num1num1 digit num1 | . num2 | E num4 | num2 digit num3num3 digit num3 | E num4 | num4 + digits | - digits | digit num5digits digit num5num5 digit num5 | Wensheng Li BUPT 200831/78无符号数的正规文法

27、无符号数的正规文法 num digit num1 num1 digit num1 | . num2 | E num4 | num2 digit num3 num3 digit num3 | E num4 | num4 + digits | - digits | digit num5 digits digit num5 num5 digit num5 | Wensheng Li BUPT 200832/78无符号数无符号数 4.6E-8 4.6E-8 的分析树的分析树numdigit num1. num2digit num3E num4- digitsdigit num5 468 Wenshen

28、g Li BUPT 200833/78运算符运算符n关系运算符的正规表达式为：关系运算符的正规表达式为： |= | = | | = | n正规定义式：正规定义式：relop |= | = | | = | n关系运算符的正规文法：关系运算符的正规文法：relop | equal | = | | equalgreater equal =Wensheng Li BUPT 200834/78三、状态转换图与记号的识别三、状态转换图与记号的识别n状态转换图状态转换图n利用状态转换图识别记号利用状态转换图识别记号n为线性文法构造相应的状态转换图为线性文法构造相应的状态转换图状态集合的构成状态集合的构成状态

29、之间边的形成状态之间边的形成Wensheng Li BUPT 200835/78状态转换图状态转换图n状态转换图是一张有限的方向图状态转换图是一张有限的方向图图中结点代表状态，用圆圈表示。图中结点代表状态，用圆圈表示。状态之间用有向边连接。状态之间用有向边连接。边上的标记代表在射出结状态下，可能出现的输入符号或边上的标记代表在射出结状态下，可能出现的输入符号或字符类。字符类。123xyWensheng Li BUPT 200836/78标识符的状态转换图标识符的状态转换图n标识符的文法产生式：标识符的文法产生式：id letter ridrid | letter rid | digit rid

30、n标识符的状态转换图标识符的状态转换图012letter/digitletterother*Wensheng Li BUPT 200837/78利用状态转换图识别记号利用状态转换图识别记号n语句语句 DO99K=1.10 DO99K=1.10 中中标识符标识符 DO99KDO99K 的识别过程：的识别过程：012letter/digitletterother*状态状态 0读入读入D状态状态1读入读入O状态状态1读入读入9状态状态1读入读入K状态状态1读入读入=状态状态2读入读入9状态状态1Wensheng Li BUPT 200838/78为线性文法构造相应的状态转换图为线性文法构造相应的状态

31、转换图n状态集合的构成状态集合的构成对文法对文法G G的每一个非终结符号设置一个对应的状态的每一个非终结符号设置一个对应的状态文法的开始符号对应的状态称为初态文法的开始符号对应的状态称为初态增加一个新的状态，称为终态。增加一个新的状态，称为终态。n状态之间边的形成状态之间边的形成对产生式对产生式A AaBaB，从，从A A状态到状态到B B状态画一条标记为状态画一条标记为a a的边的边对产生式对产生式A Aa a，从，从A A状态到终态画一条标记为状态到终态画一条标记为a a的边的边对产生式对产生式A A，从，从A A状态到终态画一条标记为状态到终态画一条标记为 的边的边Wensheng Li

32、 BUPT 200839/78无符号数的右线性文法的状态转换图无符号数的右线性文法的状态转换图numnum1num2num3num4num5digits024digit1digit3digit6digitother7digitEE5+/-digitdigit*other.other num digit num1 num1 digit num1 | . num2 | E num4 | num2 digit num3 num3 digit num3 | E num4 | num4 + digits | - digits | digit num5 digits digit num5 num5 dig

33、it num5 | Wensheng Li BUPT 200840/783.4 3.4 词法分析程序的设计与实现词法分析程序的设计与实现步骤：步骤：1.1. 给出描述该语言各种单词符号的词法规则给出描述该语言各种单词符号的词法规则2.2. 画出状态转换图画出状态转换图3.3. 根据状态转换图构造词法分析器根据状态转换图构造词法分析器一、文法及状态转换图一、文法及状态转换图1. 1. 语言说明语言说明2. 2. 记号的正规文法记号的正规文法3. 3. 状态转换图状态转换图二、词法分析程二、词法分析程序序的构造的构造三、词法分析程三、词法分析程序序的实现的实现1. 1. 输出形式输出形式2. 2.

34、 设计全局变量和过程设计全局变量和过程3. 3. 编制词法分析程编制词法分析程序序Wensheng Li BUPT 200841/78一、文法及状态转换图一、文法及状态转换图n语言说明语言说明标识符标识符：以字母开头的、后跟字母或数字组成的符号串。：以字母开头的、后跟字母或数字组成的符号串。保留字保留字：标识符的子集。：标识符的子集。无符号数无符号数：同：同PASCAL语言中的无符号数。语言中的无符号数。关系运算符关系运算符：、=、=、=、。标点符号标点符号：+、-、*、/、(、)、:、 、；等。、；等。赋值号赋值号： :=注释标记注释标记：以：以/*开始，以开始，以*/结束。结束。单词符号间

35、的分隔符单词符号间的分隔符：空格：空格Wensheng Li BUPT 200842/78记号的正规文法记号的正规文法n标识符的文法标识符的文法 id letter ridrid | letter rid | digit ridn无符号整数的文法无符号整数的文法 digits digit remainderremainder | digit remainderWensheng Li BUPT 200843/78n无符号数的文法无符号数的文法 num digit num1 num1 digit num1 | . num2 | E num4 | num2 digit num3 num3 digit

36、 num3 | E num4 | num4 + digits | - digits |digit num5 digits digit num5 num5 digit num5 | n关系运算符的文法关系运算符的文法relop |equal | = |equalgreater equal =记号的正规文法记号的正规文法( (续续) )Wensheng Li BUPT 200844/78n赋值号的文法赋值号的文法assign_op :equal equal =n标点符号的文法标点符号的文法single + | - | * | / | ( | ) | : | | ;n注释头符号的文法注释头符号的文法

37、note / starstar *记号的正规文法记号的正规文法( (续续) )Wensheng Li BUPT 200845/78状状态态转转换换图图读去注释状态读去注释状态错误处理状态错误处理状态digitEother *35digit2digit4digit7digitdigit.E6+/-digit other * other *0letter1letter / digitother *8other *9=other *=：10=other *+ / - / * / ( / ) / ; / /11*other *1213other转入口转入口出口出口入口入口 Wensheng Li BU

38、PT 200846/78二、词法分析程序的构造二、词法分析程序的构造根据上述状态转换图，再加上相应的语义动作，根据上述状态转换图，再加上相应的语义动作，就可以构造出的词法分析程就可以构造出的词法分析程序序的算法框图。的算法框图。Wensheng Li BUPT 200847/78开始开始读字符读字符空白？空白？YNToken := 字母？字母？Y 组合标识符组合标识符 R查保留字表查保留字表保留字？保留字？YN输出保留字输出保留字输出标识符输出标识符N数字？数字？Y组数组数 R输出无符号数输出无符号数N ？ YN读字符读字符 = ？Y输出输出 ？Y输出输出 N R输出输出 ？ Y读字符读字符

39、=？ Y输出输出 =N R输出输出 ：？：？Y读字符读字符 =? Y输出赋值号输出赋值号 :=:=N R输出冒号：输出冒号：N / ? 读字符读字符 * ?读去注释读去注释N R输出斜杠输出斜杠 / /NYY转入口转入口N 标点符号？标点符号？Y输出标点符号输出标点符号N错误处理错误处理出口出口说明：说明： R 为一过程，其功能是向前指针回退一个字符；为一过程，其功能是向前指针回退一个字符； Token 为字符数组，用于存放单词符号为字符数组，用于存放单词符号 Wensheng Li BUPT 200848/78三、词法分析程序的实现三、词法分析程序的实现n输出形式输出形式n设计全局变量和过程

40、设计全局变量和过程n编制词法分析程编制词法分析程序序Wensheng Li BUPT 200849/78输出形式输出形式n利用翻译表，将识别出的单词的记号以二元式的利用翻译表，将识别出的单词的记号以二元式的形式加以输出形式加以输出n二元式的形式：二元式的形式： Wensheng Li BUPT 200850/78正规表达式正规表达式记号记号属性属性ifififif- -thenthenthenthen- -elseelseelseelse- -idididid符号表入口指针符号表入口指针numnumnumnum常数表入口指针常数表入口指针 reloprelopLTLT=reloprelopLE

41、LE= =reloprelopEQEQreloprelopNENE reloprelopGTGT=reloprelopGEGE:=:=assign-opassign-op- -+ + +- - - - -* * *- -/ / /- -( ( (- -) ) )- - - -; ; ;- -: : :- -Wensheng Li BUPT 200851/78设计全局变量和过程设计全局变量和过程n转换图中的每一状态，分别用一段程序实现。转换图中的每一状态，分别用一段程序实现。n如果某一状态有若干条射出边，则程序：如果某一状态有若干条射出边，则程序：读一个字符读一个字符根据读到的字符，选择标记与之

42、匹配的边到达下一个根据读到的字符，选择标记与之匹配的边到达下一个状态，即程序控制转去执行下一个状态对应的语句序状态，即程序控制转去执行下一个状态对应的语句序列。列。Wensheng Li BUPT 200852/78(1) (1) C：字符变量，存放当前读进的字符。：字符变量，存放当前读进的字符。(2) (2) iskey：整型变量：整型变量(3) (3) token：字符数组，存放单词的字符串。：字符数组，存放单词的字符串。(4) (4) lexemebegin：字符指针，指向输入缓冲区中当前单：字符指针，指向输入缓冲区中当前单词的开始位置。词的开始位置。(5) (5) forward：字符

43、指针，向前扫描指针。：字符指针，向前扫描指针。(6) (6) buffer：字符数组，输入缓冲区。：字符数组，输入缓冲区。(7) (7) get_char：读字符过程，每调用一次，读进一个字符，：读字符过程，每调用一次，读进一个字符，并把它放入并把它放入charchar中，且向前指针中，且向前指针forwardforward指向下一个字符。指向下一个字符。(8) (8) get_nbc：过程，每次调用时，检查：过程，每次调用时，检查charchar中是否为空字中是否为空字符，若是，则反复调用该过程，直到符，若是，则反复调用该过程，直到charchar进入一个非空进入一个非空字符为止。字符为止。

44、设计全局变量和过程（续）设计全局变量和过程（续）Wensheng Li BUPT 200853/78(9) (9) cat：过程，每次调用把当前：过程，每次调用把当前charchar中的字符与中的字符与tokentoken中的中的字符串连接起来。字符串连接起来。(10) (10) letter和和digit：布尔函数，分别判断：布尔函数，分别判断charchar中的字符是中的字符是否为字母或数字，若是则返回否为字母或数字，若是则返回truetrue，否则返回，否则返回falsefalse。(11) (11) retract：过程，向前扫描指针：过程，向前扫描指针forwardforward后退

45、一个字符。后退一个字符。(12) (12) reserve：函数，查保留字表，若此函数的返回值为：函数，查保留字表，若此函数的返回值为0 0，则表示则表示tokentoken中的字符串是标识符，否则为保留字。中的字符串是标识符，否则为保留字。(13) (13) DTB：十：十/ /二进制的转换过程，它将二进制的转换过程，它将tokentoken中的数字串转中的数字串转换成二进制的数值表示。换成二进制的数值表示。(14) (14) table_insert：过程，将标识符插入符号表。：过程，将标识符插入符号表。(15) (15) error：错误处理函数。：错误处理函数。(16) (16) re

46、turn：返回过程，收集并携带必要的信息返回调用程：返回过程，收集并携带必要的信息返回调用程序。序。设计全局变量和过程（续）设计全局变量和过程（续）Wensheng Li BUPT 200854/78编制词法分析程序（编制词法分析程序（方法一方法一）token=;get_char;get_nbc;SWITCH (C) CASE a.z: WHILE (letter | digit) cat; get_char; retract; iskey=reserve; IF iskey=0 table_insert; return(ID, 指向该标识符在符号表的入口指针指向该标识符在符号表的入口指针);

47、 ; ELSE return (关键字的记号，关键字的记号，-); BREAK;Wensheng Li BUPT 200855/78CASE 0.9: WHILE (digit|.|E|+|-) cat; get_char; retract; return(num, DTB(token); BREAK;CASE ) return(relop, NE); ELSE retract; return(relop, LT); BREAK;CASE = : return(relop, EQ); BREAK;CASE : get_char; IF (C=) return(relop, GE); ELSE

48、retract; return(relop, GT); BREAK;编制词法分析器（续）编制词法分析器（续）Wensheng Li BUPT 200856/78CASE : : get_char; IF (C=) return(assign-op, -); retract; return(:, -); BREAK;CASE + : return(+, -); BREAK;CASE - : return(-, -); BREAK;CASE ( : return(, -); BREAK;CASE ) : return(), -); BREAK;CASE ; : return(;, -); BREA

49、K;编制词法分析器（续）编制词法分析器（续）Wensheng Li BUPT 200857/78CASE / : get_char; IF (C=*) loop_1: get_char; WHILE (!*) get_char; get_char; IF (C=/) BREAK; GOTO loop_1; ; ELSE retract; return(/,-); BREAK; / end of case /DEFAULT: error(); /end of switch编制词法分析器（续）编制词法分析器（续）Wensheng Li BUPT 200858/78编制词法分析器（方法二）编制词法分

50、析器（方法二）token=;B=1; state=0;WHILE (B) get_char; get_nbc; SWITCH (state) CASE 0: SWITCH (C) CASEa.z: cat; stata=1; BREAK; CASE0.9: cat; state=2; BREAK; CASE :state=8; BREAK; CASE + : return(+, -); BREAK; CASE 1: SWITCH (C) CASE a.z: cat; state=1; BREAK; CASE 0.9: cat; state=1; BREAK; DEFAULT: /*处理标识符和

51、关键字程序处理标识符和关键字程序*/;B=0; BREAK; CASE 2: Wensheng Li BUPT 200859/783.5 3.5 软件工具软件工具LEXLEXn使用使用LEXLEX的流程的流程: :LEXLEX源程序源程序lex.llex.lLEXLEX编译器编译器Lex.yy.cLex.yy.clex.yy.clex.yy.cC C编译器编译器Lex.yy.oLex.yy.o 或或a.outa.out字符流源程序字符流源程序a.outa.out记号序列记号序列Lex.yy.oLex.yy.o可以和其它程序的目标代码连接可以和其它程序的目标代码连接a.outa.out是可执行的

52、目标程序，可以作为独立运行的词法分析是可执行的目标程序，可以作为独立运行的词法分析器器Wensheng Li BUPT 200860/78说明部分说明部分%翻译规则翻译规则%辅助过程辅助过程主要内容主要内容一、一、LEXLEX源程序源程序1. 1. 说明部分说明部分2. 2. 翻译规则翻译规则3. 3. 辅助过程辅助过程二、二、LEXLEX的工作原理的工作原理1. LEX1. LEX的工作过程的工作过程2. 2. 处理二义性问题的两条规则处理二义性问题的两条规则3. LEX3. LEX工作过程举例工作过程举例Wensheng Li BUPT 200861/78一、一、LEXLEX源程序源程序1

53、.1.说明部分说明部分n包括：包括：变量说明变量说明标识符常量说明标识符常量说明正规定义正规定义n正规定义中的名字可在翻译规则中用作正规表达式正规定义中的名字可在翻译规则中用作正规表达式的成分的成分nC C语言的说明必须用分界符语言的说明必须用分界符“ % ”% ”和和“ % ”% ”括起括起来。来。出现在括号中的任何东西都直接抄写到词法分析器出现在括号中的任何东西都直接抄写到词法分析器Lex.yy.cLex.yy.c中，不作为正规定义和翻译规则的一部分。在第中，不作为正规定义和翻译规则的一部分。在第三节中的辅助过程也按同样方式处理三节中的辅助过程也按同样方式处理Wensheng Li BUP

54、T 200862/78一、一、LEXLEX源程序源程序2.2.翻译规则翻译规则n形式：形式：P1 P1 动作动作1 1 P2 P2 动作动作2 2 PnPn 动作动作n n nPi Pi 是一个正规表达式，描述一种记号的模式。是一个正规表达式，描述一种记号的模式。n动作动作i i 是是C C语言的程序语句，表示当一个串匹配模式语言的程序语句，表示当一个串匹配模式PiPi时，词法分析器应执行的动作。时，词法分析器应执行的动作。Wensheng Li BUPT 200863/78一、一、LEXLEX源程序源程序3.3.辅助过程辅助过程n对翻译规则的补充对翻译规则的补充n翻译规则部分中某些动作需要调

55、用的过程，如果不翻译规则部分中某些动作需要调用的过程，如果不是是C C语言的库函数，则要在此给出具体的定义。语言的库函数，则要在此给出具体的定义。n这些过程也可以存入另外的程序文件中，单独编译，这些过程也可以存入另外的程序文件中，单独编译，然后和词法分析器连接装配在一起。然后和词法分析器连接装配在一起。Wensheng Li BUPT 200864/78LEXLEX源程序举例源程序举例nLEXLEX生成的词法分析器的执行：最长匹配原则生成的词法分析器的执行：最长匹配原则n传递单词的属性，是把属性值赋给全程变量传递单词的属性，是把属性值赋给全程变量yylvalyylvaln正规定义式：正规定义式

56、：if ifthen thenelse elserelop | = | = | | | =id letter(letter|digit)*num digit+(.digit+)?(E(+|-)?digit+)?Wensheng Li BUPT 200865/78相应的相应的LEXLEX规格说明规格说明 /* 说明部分说明部分 */%#include /* C语言描述的标识符常量的定义，如语言描述的标识符常量的定义，如 LT、LE、EQ、NE、GT、GE、IF、THEN、ELSE、ID、NUMBER、RELOP */extern yylval;% /* 正规定义式正规定义式 */delim tn

57、ws delim+letter A-Za-zdigit 0-9id letter(letter|digit)* num digit+(.digit+)?(E+-?digit+)?%Wensheng Li BUPT 200866/78/* 规则部分规则部分 */ws /* 没有动作，也不返回没有动作，也不返回 */if return(IF); then return(THEN); else return(ELSE); id yylval=install_id(); return(ID); num yylval=install_num(); return(NUMBER); “” yylval=LT

58、; return(RELOP); “=” yylval=LE; return(RELOP); “=” yylval=EQ; return(RELOP); “” yylval=NE; return(RELOP); “” yylval=GT; return(RELOP); “=” yylval=GE; return(RELOP); %相应的相应的LEXLEX规格说明（续）规格说明（续）如果没有如果没有return语句，则，处理完整个输入之后才会返回！语句，则，处理完整个输入之后才会返回！Wensheng Li BUPT 200867/78/* 辅助过程辅助过程 */int install_id()

59、 /* 把单词插入符号表并返回该单词在符号表中的位置把单词插入符号表并返回该单词在符号表中的位置 yytext指向该单词的第一个字符指向该单词的第一个字符 yyleng给出它的长度给出它的长度 */int install_num() /* 类似于上面的过程，但单词是常数类似于上面的过程，但单词是常数 */相应的相应的LEXLEX规格说明（续）规格说明（续）Wensheng Li BUPT 200868/78LEXLEX解决冲突的方式解决冲突的方式1.1. 根据规则定义的先后次序根据规则定义的先后次序解决了例子中关键字和标识符的冲突解决了例子中关键字和标识符的冲突2.2. 最长匹配原则最长匹配原则解决了例子中诸如解决了例子中诸如 “ “” ” 和和 “ “=” =” 的冲突的冲突?Wensheng Li BUPT 200869/78二、二、LEXLEX的工作原理的工作原