Chapter03--词法分析

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

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

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

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

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

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

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

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

9、Li BUPT113.2 3.2 词法分析程序的输入与输出词法分析程序的输入与输出一、词法分析程一、词法分析程序序的实现方法的实现方法二、设置缓冲区的必要性二、设置缓冲区的必要性三、配对缓冲区三、配对缓冲区四、词法分析程四、词法分析程序序的输出的输出Wensheng Li BUPT12一、词法分析程序的实现方法一、词法分析程序的实现方法n利用词法分析程利用词法分析程序自动序自动生成器生成器u从基于正规表达式的规范说明自动生成词法分析程从基于正规表达式的规范说明自动生成词法分析程序序。u生成器提供用于源程序字符流读入和缓冲的若干子程序生成器提供用于源程序字符流读入和缓冲的若干子程序n利用传统的系

10、统程序设计语言来编写利用传统的系统程序设计语言来编写u利用该语言所具有的输入利用该语言所具有的输入/ /输出能力来处理读入操作输出能力来处理读入操作n利用汇编语言来编写利用汇编语言来编写u直接管理源程序字符流的读入直接管理源程序字符流的读入Wensheng Li BUPT13二、设置缓冲区的必要性二、设置缓冲区的必要性n超前搜索：为了得到某一个单词符号的确切性质，超前搜索：为了得到某一个单词符号的确切性质，需要超前扫描若干个字符。需要超前扫描若干个字符。例：有合法的例：有合法的FORTRANFORTRAN语句：语句： DO99K=1,10 DO99K=1,10 和和 DO99K=1.10DO9

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

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

13、的开始位置向前指针移到缓冲区的开始位置; ELSE 向前指针前移一个位置向前指针前移一个位置;Wensheng Li BUPT16每半区带有结束标记的缓冲器每半区带有结束标记的缓冲器开始指针开始指针向前指针向前指针 i f x = y t h eof e n j : = j + 2 ; eof eofn 基本方法的缺点：基本方法的缺点：更新向前指针时要做二次测试更新向前指针时要做二次测试n 改进：每半区带有结束标记的缓冲器改进：每半区带有结束标记的缓冲器更新向前指针时只要做一次测试更新向前指针时只要做一次测试Wensheng Li BUPT17测试指针的过程测试指针的过程(2)(2)向前指针前

14、移一个位置；向前指针前移一个位置；IF (向前指针指向向前指针指向 eof ) IF (向前指针在左半区的终点向前指针在左半区的终点) 读入字符串，填充右半区读入字符串，填充右半区; 向前指针前移一个位置向前指针前移一个位置; ELSE IF (向前指针在右半区的终点向前指针在右半区的终点) 读入字符串，填充左半区读入字符串，填充左半区; 向前指针指向缓冲区的开始位置向前指针指向缓冲区的开始位置; ; ELSE 终止词法分析终止词法分析;Wensheng Li BUPT18四、词法分析程序的输出四、词法分析程序的输出记号记号n记号、模式和单词记号、模式和单词u记号：是指某一类单词符号的种别编码

15、，如标识符的记号记号：是指某一类单词符号的种别编码，如标识符的记号为为id，数的记号为，数的记号为num等。等。u模式：是指某一类单词符号的构词规则，如标识符的模式模式：是指某一类单词符号的构词规则，如标识符的模式是是“由字母开头的字母数字串由字母开头的字母数字串”。u单词：是指某一类单词符号的一个特例，如单词：是指某一类单词符号的一个特例，如position是是标识符标识符。机内表示机内表示外部表示外部表示构词规则构词规则1.关键字关键字 记号的种类记号的种类2.标识符标识符 3.常数常数4.运算符运算符5.分界符分界符Wensheng Li BUPT19记号的属性记号的属性n词法分析程序在

16、识别出一个记号后，要把与之有关的信息作词法分析程序在识别出一个记号后，要把与之有关的信息作为它的属性保留下来。为它的属性保留下来。n记号影响语法分析的决策，属性影响记号的翻译。记号影响语法分析的决策，属性影响记号的翻译。n在词法分析阶段，对记号只能确定一种属性在词法分析阶段，对记号只能确定一种属性u标识符：单词在符号表中入口的指针标识符：单词在符号表中入口的指针u常数：它所表示的值常数：它所表示的值u关键字：（一符一种、或一类一种）关键字：（一符一种、或一类一种）u运算符：（一符一种、或一类一种）运算符：（一符一种、或一类一种）u分界符：分界符：（一（一符一种、或一类一种符一种、或一类一种）n

17、记号的属性是指记号的特征或特性，反映特征或特性的值是记号的属性是指记号的特征或特性，反映特征或特性的值是属性值属性值n一种一符则种别值可以认为是属性值，一种多符则需给出属一种一符则种别值可以认为是属性值，一种多符则需给出属性值性值Wensheng Li BUPT20total:=total+ratetotal:=total+rate* *4 4 的词法分析结果的词法分析结果Wensheng Li BUPT213.3 3.3 记号的描述和识别记号的描述和识别n识别单词是按照记号的模式进行的，一种记号的模识别单词是按照记号的模式进行的，一种记号的模式匹配一类单词的集合。式匹配一类单词的集合。u为设

18、计词法程序，对模式要给出规范、系统的描述。为设计词法程序，对模式要给出规范、系统的描述。n正规表达式和正规文法是描述模式的重要工具。正规表达式和正规文法是描述模式的重要工具。u二者具有同等表达能力二者具有同等表达能力u正规表达式：清晰、简洁正规表达式：清晰、简洁u正规文法：便于识别正规文法：便于识别 一、词法与正规文法一、词法与正规文法 二、记号的文法二、记号的文法 三、状态转换图与记号的识别三、状态转换图与记号的识别Wensheng Li BUPT22一、词法与正规文法一、词法与正规文法n把源语言的文法把源语言的文法G G分解为若干子文法：分解为若干子文法：G G0 0、 G G1 1、G

19、G2 2、G Gn n 正规文法正规文法 上下文无关文法上下文无关文法 语法语法 词法词法n词法：描述语言的标识符、常数、运算符和标点符词法：描述语言的标识符、常数、运算符和标点符号等记号的文法号等记号的文法n语法：借助于记号来描述语言的结构的文法语法：借助于记号来描述语言的结构的文法Wensheng Li BUPT23二、记号的文法二、记号的文法n标识符标识符n常数常数u整数整数u无符号数无符号数n运算符运算符n分界符分界符n关键字关键字Wensheng Li BUPT24标识符标识符n假设标识符假设标识符定义为定义为“由字母打头的、由字母或数字由字母打头的、由字母或数字组成的符号串组成的符

20、号串”n描述标识符集合的正规表达式：描述标识符集合的正规表达式：letter(letter|digit)*n表示标识符集合的正规定义式：表示标识符集合的正规定义式： letter A|B|Z|a|b|z digit 0|1|9 id letter(letter|digit)*Wensheng Li BUPT25把正规定义式转换为相应的正规文法把正规定义式转换为相应的正规文法 ( letter | digit )* = | ( letter | digit )+ = | ( letter | digit ) ( letter | digit )* = | letter ( letter | di

21、git )* | digit ( letter | digit )* = | (A|Z|a|z) ( letter | digit )* | (0|9)( letter | digit )* = | A ( letter | digit )* | | Z ( letter | digit )* | a ( letter | digit )* | | z ( letter | digit )* | 0 ( letter | digit )* | | 9 ( letter | digit )* Wensheng Li BUPT26标识符的正规文法标识符的正规文法 id A rid|Z rid|a

22、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 BUPT27常数常数整数整数n描述整数结构的正规表达式为：描述整数结构的正规表达式为： (digit)+n对此正规表达式进行等价变换：对此正规表达式进行等价变换： (digit)+ = digit(digit)* (digit)* = | digit(digit)*n整数的正规文法：整数的正规文法： digits digit re

23、mainder remainder | digit remainderWensheng Li BUPT28常数常数无符号数无符号数n无符号数的正规表达式为：无符号数的正规表达式为：(digit)+ (.(digit)+)? (E(+|-)?(digit)+)?n正规定义式为正规定义式为digit 0|1|9digits digit+optional_fraction (.digits)?optional_exponent (E(+|-)?digits)?num digits optional_fraction optional_exponentWensheng Li BUPT29把正规定义式转

24、换为正规文法把正规定义式转换为正规文法 ( digit )+ ( . ( digit )+ )? ( E( + | - )?( digit )+ )?=( digit )+ ( . ( digit )+ | ) ( E(+ |- | ) ( digit )+ | )=digit (digit)* ( . digit ( digit )*| ) ( E (+|-| ) digit ( digit )* | )num1 num1 表示无符号数的第一个数字之后的部分表示无符号数的第一个数字之后的部分num2 num2 表示小数点以后的部分表示小数点以后的部分num3 num3 表示小数点后第一个数字

25、以后的部分表示小数点后第一个数字以后的部分num4 num4 表示表示E E之后的部分之后的部分num5 num5 表示表示(digit)(digit)* *digits digits 表示表示(digit)(digit)+Wensheng Li BUPT30无符号数分析图无符号数分析图 digit (digit)* (. digit (digit)*|) (E (+|-|) digit (digit)* |)num3num2num1num4numnum digit num1num1 digit num1 | . num2 | E num4 | num2 digit num3num3 digi

26、t num3 | E num4 | num4 + digits | - digits | digit num5digits digit num5num5 digit num5 | digits digits 表示表示(digit(digit) )+num5 num5 表示表示(digit)(digit)* *Wensheng Li BUPT31无符号数的正规文法无符号数的正规文法 num digit num1 num1 digit num1 | . num2 | E num4 | num2 digit num3 num3 digit num3 | E num4 | num4 + digits

27、| - digits | digit num5 digits digit num5 num5 digit num5 | Wensheng Li BUPT32无符号数无符号数 4.6E-8 4.6E-8 的分析树的分析树numdigit num1. num2digit num3E num4- digitsdigit num5 468 Wensheng Li BUPT33运算符运算符n关系运算符的正规表达式为：关系运算符的正规表达式为： |= | = | | = | n正规定义式：正规定义式：relop |= | = | | = | n关系运算符的正规文法：关系运算符的正规文法：relop | e

28、qual | = | | equalgreater equal =Wensheng Li BUPT34三、状态转换图与记号的识别三、状态转换图与记号的识别n状态转换图状态转换图n利用状态转换图识别记号利用状态转换图识别记号n为线性文法构造相应的状态转换图为线性文法构造相应的状态转换图u状态集合的构成状态集合的构成u状态之间边的形成状态之间边的形成Wensheng Li BUPT35状态转换图状态转换图n状态转换图是一张有限的方向图状态转换图是一张有限的方向图u图中结点代表状态，用圆圈表示。图中结点代表状态，用圆圈表示。u状态之间用有向边连接。状态之间用有向边连接。u边上的标记代表在射出结状态下

29、，可能出现的输入符号或边上的标记代表在射出结状态下，可能出现的输入符号或字符类。字符类。123xyWensheng Li BUPT36标识符的状态转换图标识符的状态转换图n标识符的文法产生式：标识符的文法产生式：id letter ridrid | letter rid | digit ridn标识符的状态转换图标识符的状态转换图012letter/digitletterother*Wensheng Li BUPT37利用状态转换图识别记号利用状态转换图识别记号n语句语句 DO99K=1.10 DO99K=1.10 中中标识符标识符 DO99KDO99K 的识别过程的识别过程012letter

30、/digitletterother*状态状态 0读入读入D状态状态1读入读入O状态状态1读入读入9状态状态1读入读入K状态状态1读入读入=状态状态2读入读入9状态状态1Wensheng Li BUPT38为线性文法构造相应的状态转换图为线性文法构造相应的状态转换图n状态集合的构成状态集合的构成u对文法对文法G G的每一个非终结符号设置一个对应的状态的每一个非终结符号设置一个对应的状态u文法的开始符号对应的状态称为初态文法的开始符号对应的状态称为初态u增加一个新的状态，称为终态。增加一个新的状态，称为终态。n状态之间边的形成状态之间边的形成u对产生式对产生式A AaBaB，从，从A A状态到状态

31、到B B状态画一条标记为状态画一条标记为a a的边的边u对产生式对产生式A Aa a，从，从A A状态到终态画一条标记为状态到终态画一条标记为a a的边的边u对产生式对产生式A A，从，从A A状态到终态画一条标记为状态到终态画一条标记为 的边的边Wensheng Li BUPT39无符号数的右线性文法的状态转换图无符号数的右线性文法的状态转换图numnum1num2num3num4num5digits024digit1digit3digit6digitother7digitEE5+/-digitdigit*other.other num digit num1 num1 digit num1

32、| . num2 | E num4 | num2 digit num3 num3 digit num3 | E num4 | num4 + digits | - digits | digit num5 digits digit num5 num5 digit num5 | Wensheng Li BUPT403.4 3.4 词法分析程序的设计与实现词法分析程序的设计与实现步骤：步骤：1.1.给出描述该语言各种单词符号的词法规则给出描述该语言各种单词符号的词法规则2.2.画出状态转换图画出状态转换图3.3.根据状态转换图构造词法分析器根据状态转换图构造词法分析器一一、文法及状态转换图、文法及状态

33、转换图1. 1. 语言说明语言说明2. 2. 记号的正规文法记号的正规文法3. 3. 状态转换图状态转换图二、词法分析程二、词法分析程序序的构造的构造三、词法分析程三、词法分析程序序的实现的实现1. 1. 输出形式输出形式2. 2. 设计全局变量和过程设计全局变量和过程3. 3. 编制词法分析程编制词法分析程序序Wensheng Li BUPT41一、文法及状态转换图一、文法及状态转换图n语言说明语言说明标识符标识符：以字母开头的、后跟字母或数字组成的符号串。：以字母开头的、后跟字母或数字组成的符号串。保留字保留字：标识符的子集。：标识符的子集。无符号数无符号数：同：同PASCAL语言中的无符

34、号数。语言中的无符号数。关系运算符关系运算符：、=、=、=、。算术运算符算术运算符：+、-、*、/。标点符号标点符号：(、)、:、 、；等。、；等。赋值号赋值号： :=注释标记注释标记：以：以/*开始，以开始，以*/结束。结束。单词符号间的分隔符单词符号间的分隔符：空格：空格Wensheng Li BUPT42记号的正规文法记号的正规文法n标识符的文法标识符的文法 id letter ridrid | letter rid | digit ridn无符号整数的文法无符号整数的文法 digits digit remainderremainder | digit remainderWensheng

35、 Li BUPT43n无符号数的文法无符号数的文法 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 | n关系运算符的文法关系运算符的文法 relop |equal | = |equalgreater equal =记号的正规文法记号的正规文法( (续续1)1)Wensheng Li BUPT44n赋值号的文法赋值号

36、的文法assign_op :equal equal =n算术运算符及标点符号算术运算符及标点符号的文法的文法single + | - | * | / | ( | ) | : | | ;n注释头符号的文法注释头符号的文法note / star star *记号的正规文法记号的正规文法( (续续2)2)Wensheng Li BUPT45状状态态转转换换图图读去注释状态读去注释状态错误处理状态错误处理状态digitEother *35digit2digit4digit7digitdigit.E6+/-digit other * other *0letter1letter / digitother

37、*8other *9=other *=：10=other *+ / - / * / ( / ) / ; / /11*other *1213other转入口转入口出口出口入口入口 Wensheng Li BUPT识别识别注释的注释的DFADFA46Wensheng Li BUPT47二、词法分析程序的构造二、词法分析程序的构造n把把语义语义动作添加动作添加到状态转换图中，使每一个状态都对应一小段程序，就到状态转换图中，使每一个状态都对应一小段程序，就可以构造出相应的词法分析可以构造出相应的词法分析程序程序。n如果某一状态有若干条射出边，则如果某一状态有若干条射出边，则程序段：读程序段：读一个一个

38、字符，根据字符，根据读到的字读到的字符，选择标记与之匹配的边到达下一个状态，即程序控制转去执行下一符，选择标记与之匹配的边到达下一个状态，即程序控制转去执行下一个状态对应的语句序列。个状态对应的语句序列。n在状态在状态0 0，首先要读进一个字符。若读入的字符是一个空格（包括首先要读进一个字符。若读入的字符是一个空格（包括blankblank、tabtab、enterenter）就跳过它，继续读字符，直到读进一个非空字符为止。接）就跳过它，继续读字符，直到读进一个非空字符为止。接下来的工作就是根据所读进的非空字符转相应的程序段进行下来的工作就是根据所读进的非空字符转相应的程序段进行处理处理。n在

39、标识符状态，识别并组合出一个标识符之后，还必须加入一些动作，在标识符状态，识别并组合出一个标识符之后，还必须加入一些动作，如查关键字表，以确定识别出的单词符号是关键字还是用户自定义标识如查关键字表，以确定识别出的单词符号是关键字还是用户自定义标识符，并输出相应的记号符，并输出相应的记号。n在在“ ”状态，若读进的下一个字符是状态，若读进的下一个字符是“= =”，则输出关系运算符，则输出关系运算符“= ”，则输出关系运算符，则输出关系运算符“”；否则输出关系；否则输出关系运算符运算符“ ”。Wensheng Li BUPT48开始开始读字符读字符空白？空白？YNToken := 字母？字母？Y

40、组合标识符组合标识符 R查保留字表查保留字表保留字？保留字？YN输出保留字输出保留字输出标识符输出标识符N数字？数字？Y组数组数 R输出无符号数输出无符号数N ？ YN读字符读字符 = ？Y输出输出 ？Y输出输出 N R输出输出 ？ Y读字符读字符 =？ Y输出输出 =N R输出输出 ：？：？Y读字符读字符 =? Y输出赋值号输出赋值号 :=:=N R输出冒号：输出冒号：N / ? 读字符读字符 * ?读去注释读去注释N R输出斜杠输出斜杠 / /NYY转入口转入口N 标点符号？标点符号？Y输出标点符号输出标点符号N错误处理错误处理出口出口说明：说明： R 为一过程，其功能是向前指针回退一个字

41、符；为一过程，其功能是向前指针回退一个字符； Token 为字符数组，用于存放单词符号为字符数组，用于存放单词符号 ?Wensheng Li BUPT49三、词法分析程序的实现三、词法分析程序的实现n输出形式输出形式n设计全局变量和过程设计全局变量和过程n编制词法分析程编制词法分析程序序Wensheng Li BUPT50输出形式输出形式n利用翻译表，将识别出的单词的记号以二元式的利用翻译表，将识别出的单词的记号以二元式的形式加以输出形式加以输出n二元式的形式：二元式的形式： n翻译翻译表：表：Wensheng Li BUPT51翻翻译译表表Wensheng Li BUPT52 (1) (1)

42、statestate：整型变量，当前状态指示。：整型变量，当前状态指示。 (2) (2)C C：字符变量，存放当前读入的字符。：字符变量，存放当前读入的字符。 (3) (3)tokentoken：字符数组，存放当前正在识别的单词字符串。：字符数组，存放当前正在识别的单词字符串。 (4) (4)bufferbuffer：字符数组，输入缓冲区。：字符数组，输入缓冲区。 (5) (5)forwardforward：字符指针，向前指针。：字符指针，向前指针。 (6) (6)lexemebeginlexemebegin：字符指针，：字符指针，指向指向bufferbuffer中中当前单词的开始位置。当前单

43、词的开始位置。 ( (7)7)get_charget_char：过程，每调用一次，根据：过程，每调用一次，根据forwardforward的指示从的指示从bufferbuffer中中 读读一个字符，并把它放入变量一个字符，并把它放入变量C C中，然后，移动中，然后，移动forwardforward，使，使之之 指向指向下一个字符。下一个字符。 ( (8)8)get_nbcget_nbc：过程：过程，检查，检查C C中的字符是否为空格，中的字符是否为空格，若是若是，则反复，则反复调调 用用过程过程get_charget_char，直到，直到C C中进入一个非空字符为止。中进入一个非空字符为止。

44、( (9)9)catcat：过程，把：过程，把C C中的字符连接在中的字符连接在tokentoken中的字符串后面。中的字符串后面。(10)(10)iskeyiskey：整型变量，值为：整型变量，值为-1-1，表示识别出的单词是用户，表示识别出的单词是用户自定义自定义 标识符标识符，否则，表示识别出的单词是关键字，其值为关键字，否则，表示识别出的单词是关键字，其值为关键字的的 记号。记号。设计全局变量和设计全局变量和过程过程Wensheng Li BUPT53(11)(11)letterletter：布尔函数，判断：布尔函数，判断C C中的字符是否为字母中的字符是否为字母， 若是若是则返回则返

45、回truetrue，否则返回，否则返回falsefalse。(12)(12)digitdigit：布尔函数，判断：布尔函数，判断C C中的字符是否为数字中的字符是否为数字， 若是若是则返回则返回truetrue，否则返回，否则返回falsefalse。(13)(13)retractretract：过程，向前指针：过程，向前指针forwardforward后退一个后退一个字符。字符。(14)(14)reservereserve：函数，根据：函数，根据tokentoken中的单词查关键字表中的单词查关键字表， 若若tokentoken中的单词是关键字，则返回值该关键字的记号中的单词是关键字，则返回

46、值该关键字的记号， 否则否则，返回值，返回值“-1-1”。(15)(15)SToISToI：过程，将：过程，将tokentoken中的字符串转换成整数。中的字符串转换成整数。(16)(16)SToFSToF：过程，将：过程，将tokentoken中的字符串转换成浮点数中的字符串转换成浮点数。(17)(17)DTBDTB：过程，它将：过程，它将tokentoken中的数字串转换成二进制的数值表示。中的数字串转换成二进制的数值表示。(18)(18)table_inserttable_insert：函数，将识别出来：函数，将识别出来的标识符的标识符（即（即tokentoken中的中的单单 词词）插入

47、符号表，返回该单词在符号表中的位置指针。）插入符号表，返回该单词在符号表中的位置指针。(19)(19)errorerror：过程，对发现的错误进行相应的处理。：过程，对发现的错误进行相应的处理。(20)(20)returnreturn：过程，将识别出来的单词的记号返回给调用程序。：过程，将识别出来的单词的记号返回给调用程序。设计全局变量和过程（设计全局变量和过程（续）续）Wensheng Li BUPT54编制词法分析程序（编制词法分析程序（方法一方法一）token=;get_char();get_nbc();SWITCH (C) CASE a.z: WHILE (letter() | dig

48、it() cat(); get_char(); retract(); iskey=reserve(); / 查关键字表查关键字表 IF iskey=-1 / 识别出的是用户自定义标识符识别出的是用户自定义标识符 identry=table_insert(); / 返回该标识符在符号表的入口指针返回该标识符在符号表的入口指针 return(ID, identry); ; ELSE return (iskey,-); / 识别出的是关键字识别出的是关键字 BREAK;Wensheng Li BUPT55CASE 0.9: WHILE (digit()|.|E|+|-) cat(); get_cha

49、r(); 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 retract; return(relop, GT); BREAK;编制词法分析器（续）编制词法分析器（续）Wensheng Li BUPT56CASE : : get_char(); IF (C=) ret

50、urn(assign-op, -); retract(); return(:, -); BREAK;CASE + : return(+, -); BREAK;CASE - : return(-, -); BREAK;CASE ( : return(, -); BREAK;CASE ) : return(), -); BREAK;CASE ; : return(;, -); BREAK;编制词法分析器（续）编制词法分析器（续）Wensheng Li BUPT57编编制制词词法法分分析析程程序序 ( (方方法法二二) )读去注释状态读去注释状态错误处理状态错误处理状态digitEother *35

51、digit2digit4digit7digitdigit.E6+/-digit other * other *0letter1letter / digitother *8other *9=other *=：10=other *+ / - / * / ( / ) / ; / /11*other *1213other转入口转入口出口出口入口入口 Wensheng Li BUPT58词法分析词法分析程序（类程序（类C C语言描述）语言描述）state=0;DO SWITCH ( state ) CASE 0: / 初始状态初始状态 token= ; get_char() ; get_nbc(); S

52、WITCH ( C ) CASE a： CASE b： CASE z：state=1; break; /设置标识符状态设置标识符状态 CASE 0： CASE 1： CASE 9：state=2; break; /设置常数状态设置常数状态 CASE ：state=8; break; /设置设置：state=9; break; /设置设置状态状态 CASE :：state=10; break; /设置设置：状态状态 CASE /：state=11; break; /设置设置/状态状态 CASE =：state=0; return(relop, EQ); break; /返回返回=的记号的记号 C

53、ASE +：state=0; return(+, ); break; /返回返回+的记号的记号 CASE ：state=0; return( , ); break; /返回返回-的记号的记号 CASE *：state=0; return(*, ); break; /返回返回*的记号的记号 CASE (：state=0; return(, ); break; /返回返回（的记号的记号 CASE )：state=0; return() , ); break; /返回返回）的记号的记号 CASE ;：state=0; return(; , ); break; /返回返回；的记号的记号 CASE ：s

54、tate=0; return(, ); break; /返回返回的记号的记号 default: state=13; break; /设置错误状态设置错误状态 ; break;Wensheng Li BUPT59词法分析程序词法分析程序( (续续1)1) CASE 1: / 标识符状态标识符状态 cat(); get_char(); IF ( letter() | digit() ) state=1; ELSE retract(); state=0; iskey=reserve(); / 查关键字表查关键字表 IF ( iskey!=-1 ) return (iskey， ); / 识别出的是关

55、键字识别出的是关键字 ELSE / 识别出的是用户自定义标识符识别出的是用户自定义标识符 identry=table_insert(); / 返回该标识符在符号表的入口指针返回该标识符在符号表的入口指针 return(ID, identry); ; ; break; Wensheng Li BUPT60词法分析词法分析程序程序（续（续2 2） CASE 2: / 常数状态常数状态 cat(); get_char(); SWITCH ( C ) CASE 0: CASE 1: CASE 9: state=2; break; CASE . : state=3; break; CASE E: sta

56、te=5; break; DEFAULT: / 识别出整常数识别出整常数 retract(); state=0; return(NUM, SToI(token); / 返回整数返回整数 break; ; break;Wensheng Li BUPT3.5 3.5 软件工具软件工具 LEXLEXn词法分析程序自动生成词法分析程序自动生成工具工具一、一、LEXLEX使用流程使用流程二、二、LEXLEX源程序结构源程序结构三、三、LEXLEX工作原理工作原理61Wensheng Li BUPT62一一、LEXLEX使用流程使用流程Lex.yy.oLex.yy.o可以和其它程序的目标代码连接可以和其它

57、程序的目标代码连接a.outa.out是可执行的目标程序，可以作为独立运行的词法分析器是可执行的目标程序，可以作为独立运行的词法分析器Wensheng Li BUPT63二、二、LEXLEX源程序结构源程序结构一个一个LEXLEX源程序由三部分组成：源程序由三部分组成：1. 1. 说明部分说明部分2. 2. 翻译规则翻译规则3. 3. 辅助过程辅助过程 说明部分说明部分 % % 翻译规则翻译规则 % % 辅助辅助过程过程Wensheng Li BUPT641.1.说明部分说明部分n包括包括：变量的声明、符号常量的声明、正规：变量的声明、符号常量的声明、正规定义定义n正规正规定义中的名字可在翻译

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

59、ude # #include y.tab.hinclude y.tab.h typedef typedef char char * * YYSTYPE; YYSTYPE; char char * * yylval; yylval;%Wensheng Li BUPT652.2.翻译规则翻译规则n形式：形式：P1 P1 动作动作1 1 P2 P2 动作动作2 2 Pn Pn 动作动作n n nPi Pi 是一个正规表达式，描述一种记号的模式。是一个正规表达式，描述一种记号的模式。n动作动作i i 是是C C语言的程序语句，表示当一个串匹配模式语言的程序语句，表示当一个串匹配模式PiPi时，词法分析

60、器应执行的动作。时，词法分析器应执行的动作。Wensheng Li BUPTP Pi i书写中可能书写中可能用用到到的的规则规则(1) (1) 转义字符转义字符： - ? . - ? . * * + | ( ) $ / % + | ( ) $ / % u具有具有特殊含义，不能用来匹配自身。如果需要匹配的话，可以通过引特殊含义，不能用来匹配自身。如果需要匹配的话，可以通过引号号()()或者转义符号或者转义符号()()来指示。比如：来指示。比如：C C+和和C+ C+ 都可以匹配都可以匹配C+C+。(2) (2) 通配符通配符：. .可以可以匹配任何一个匹配任何一个字符字符。u如：如：a.ca.c