[工学]第三章-词法分析new.ppt

《[工学]第三章-词法分析new.ppt》由会员分享，可在线阅读，更多相关《[工学]第三章-词法分析new.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、7/2/20222词法：描述语言的单词符号的文法。 语言的单词符号单词符号种类很多，因此需要用不同的词法不同的词法来描述他们。 例如描述某一语言标识符的文法也称为词法。3.1 词法分析与词法分析程序词法分析与词法分析程序思考：词法是哪类文法？正规文法7/2/20223词法分析的任务：词法分析的任务：对输入的字符串形式的源程序按顺序进行扫描，根据源程序的词法规则识别具有独立意义的单词（符号），并产生与其等价的属性字流作为输出。 词法分析程序定义词法分析程序定义：编译程序中完成词法分析任务的程序段，又称词法分析器词法分析器或扫描器（扫描器（scannerscanner）。）。 7/2/20224词

2、法分析程序的功能词法分析程序的功能识别出单词（内部表示）；词法分析器（scanner）源程序属性字流L1While ( i != j ) do if (ij) ii-j ;/求求i,j的差值的差值词法分析器词法分析器while， (，i，!=，j， )， do， if， (，i，j, )， i, = , i, - , j,;7/2/202263.2 词法分析程序设计与实现词法分析程序设计与实现 词法分析程序的输入与输出 源程序的输入与预处理 单词的识别 词法分析程序与词法分析程序的接口 词法分析器的设计与实现7/2/20227单词是语言中具有单词是语言中具有独立意义独立意义的的最小语法单位最小

3、语法单位. .单词的种类单词的种类 1. 关键字（保留字）：while、class、for、do 2. 标识符：a、m_a 3. 常数：无符号数、布尔常数、字符串常数等 4. 运算符：+、-、* 5. 界限符：逗号，分号，括号和引号种类的划分是根据编译的目标和方便设定的种类的划分是根据编译的目标和方便设定的单词7/2/20228常用的单词内部形式：常用的单词内部形式：1 1、按单词种类分类、按单词种类分类2 2、保留字和分界符采用一符一类、保留字和分界符采用一符一类3 3、标识符和常数的单词属性值为符号表入口指针、标识符和常数的单词属性值为符号表入口指针 （标识符、常数相关属性很多）（标识符、

4、常数相关属性很多） （单词属性（单词属性 ， 单词值）单词值）属性字：词法分析程序的输出形式词法分析程序的输出形式-单词的内部形式单词的内部形式7/2/20229单词名称单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数保留字分界符类别编码类别编码1234567单词值单词值符号表入口指针整数值数值0 或 1内部字符串保留字或内部编码分界符或内部编码1 1、按单词种类分类、按单词种类分类7/2/2022102 2、保留字和分界符采用一符一类、保留字和分界符采用一符一类单词名称单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数BEGINENDFORDO:+*,(类别编码类别编码

5、123456789.20212223.单词值单词值符号表入口指针整数值数值0 或 1内部字符串-.-7/2/2022113.2.2 源程序的输入与预处理 词法分析器工作的第一步是接受输入源程序。通常是把输入的源程序引导至一个输入缓冲区，并对输入串进行预处理，然后才交付扫描器进行处理。S.P.(字符串)词法分词法分析程序析程序输入缓冲区的处理？输入缓冲区的处理？显然，无论缓冲区设定为多大，都不能保证单词不会被它的边界打断，若有标识符TEST123，可能在缓冲区中成为：.TES在这种情况下，即使读到缓冲区的最后一个字符，但仍不能找到该单词的右边界，这时，若从外存上再读一部分源程序进入缓冲区，则会将

6、没有处理过的字符(TES)冲掉。两个半区互补使用为此，我们可将缓冲区分成相等的两个区域：7/2/202213扫描缓冲区扫描缓冲区 一分为二，互补使用。 搜索指针从单词起点开始搜索，如果遇到半区域的边界，但尚未到达单词的终点时，则可将后续的输入字符装入该缓冲区的另一半。单词起点 搜索指针If F at end of first half reload second half; F+;Else if F at end of second halfreload first half; move F to beginning of first halfElse F+;输入缓冲区两个半区互补功能的实现算

7、法输入缓冲区两个半区互补功能的实现算法7/2/202215源程序的预处理 为了减轻词法分析器实质性处理的负担，因此源程序从输入缓冲区进入词法分析器之前，要先对源程序进行预处理，预处理子程序一般完成的主要功能是：过滤掉源程序中的注释； 剔除源程序中无用字符； 进行宏替换； 实现文件包含的嵌入和条件编译的嵌入等。7/2/202216具有两个缓冲区的词法分析器结构源程序L输入缓冲区X预处理子程序扫描缓冲区X1词法分析器源程序L的属性字流7/2/202217实现方案（编译程序中实现方式）：实现方案（编译程序中实现方式）：基本上有两种1.词法分析单独作为一遍2.词法分析程序作为单独的子程序S.P.(字符

8、串)词法分析词法分析S.P.(符号串)语法分析语法分析第一遍第一遍第二遍第二遍单词串单词串优点优点: 结构清晰、各遍功能单一结构清晰、各遍功能单一缺点：生成中间文件，效率低缺点：生成中间文件，效率低S.P.(字符串)词法分词法分析程序析程序语法分语法分析程序析程序取单词取单词单词单词7/2/202218 词法分析程序的设计与实现词法分析程序的设计与实现词法规则词法规则 正规表达式正规表达式状态转换图（最小状态转换图（最小DFA）1.构造识别单词的状态转换图(1)对程序语言的单词按种类分别构造对应的状态转换图.(2)对各类转换图合并，构成一个能识别语言所有单词的状态转换图.2.编程实现状态转换图

9、7/2/2022191. 词法及其状态转换图词法及其状态转换图例例1 假定语言假定语言X的字母表的字母表=A-Z,a-z,0-9,;,=单词符号定义如下：单词符号定义如下： 1 1、标识符：、标识符：字母打头的字母数字串字母打头的字母数字串 2 2、无符号整数：、无符号整数：无符号数字串无符号数字串 3 3、分界符：、分界符： ； 4 4、运算符：、运算符： = =7/2/202220标识符出口出口S1非字母数字字母字母、数字无符号整数出口出口S1非数字数字数字分界符出口出口S；运算符出口出口S=7/2/202221标识符无符号整数分界符S1非字母数字*字母字母、数字2非数字*数字数字；出口出

10、口出错出错其他读字符读字符返回返回S运算符=7/2/202222= 80;0134256eniL字母字母字母字母字母字母数字数字数字数字数字数字= =；0124563L ine= 80; 1, Line 3 , = 2 , 80 4 , ; 数字数字数字数字字母字母1 1= =0 0 03; ;1输入输出7/2/2022232. 状态转换图的实现状态转换图的实现构造词法分析程序构造词法分析程序标识符无符号整数分界符运算符例例1 假定语言假定语言X的字母表的字母表=A-Z,a-z,0-9,;,=单词符号定义如下：单词符号定义如下： 1 1、标识符：、标识符：字母打头的字母数字串字母打头的字母数字

11、串 2 2、无符号整数：、无符号整数：无符号数字串无符号数字串 3 3、分界符：、分界符： ； 4 4、运算符：、运算符： = =标识符S1非字母数字字母字母、数字无符号整数S1非数字数字数字分界符出口出口S；运算符S=出口出口出口出口出口出口标识符出口出口S1非字母数字字母字母、数字If (ISLETTER) WHILE (ISLETTER OR ISDIGIT) DO 当前字符放入一临时字符数组；当前字符放入一临时字符数组； GETNEXTCHAR ；/从缓冲区取下一字符 ; UNGETCH；/回退一字符 OUTPUT(1，标识符名字)；= 80;eniL L ine= 80;= =; ;

12、无符号整数出口出口S1非数字数字数字If (ISDIGIT) WHILE ISDIGIT DO 当前字符放入一临时字符数组；当前字符放入一临时字符数组； GETNEXTCHAR ；/从缓冲区取下一字符 ; UNGETCH；/回退一字符 OUTPUT (2, 整数)；;= 80;eniL L ine= 80;= =; ;7/2/202227分界符出口出口S；If (CH=;) OUTPUT ( 3 , “;” )；If (CH=) OUTPUT ( 4 , “=” )；运算符S=出口出口7/2/202228标识符无符号整数分界符S1字母字母、数字2数字数字；出口出口出出错错其他读字符读字符返回返

13、回S运算符=例例1程序语言的词法分析程序程序语言的词法分析程序GETNEXTCHAR( ) ； SWITCH(CHCODE);CASE 1: WHILE (ISLETTER OR ISDIGIT) DO SAVE( ); / 当前字符放入一临时字符数组； GETNEXTCHAR( ) ；/从缓冲区取下一字符 ; UNGETCH；/回退一字符 OUTPUT(1，标识符名字)； ；BREAK;CASE 2: WHILE ISDIGIT DO SAVE( ); / 当前字符放入一临时字符数组； GETNEXTCHAR ；/从缓冲区取下一字符 ; UNGETCH；/回退一字符 OUTPUT (2, 整

14、数)； ; BREAK; 7/2/202230 CASE 3 : OUTPUT ( 3 , “;” )； BREAK; CASE 4 : OUTPUT ( 4 , “=”)； BREAK;DEFAULT: Error();标识符无符号整数分界符S1字母字母、数字2数字数字；出口出口出出错错其他读字符读字符返回返回S运算符=7/2/202231采用采用面向对象面向对象的方法设计词法分析器的方法设计词法分析器标识符无符号整数分界符S1字母字母、数字2数字数字；出口出口出出错错其他读字符读字符返回返回S运算符=7/2/202232词法规则词法规则 正规表达式正规表达式状态转换图（最小状态转换图（最小

15、DFA）合并状态转换图合并状态转换图编程编程实现状态转换图实现状态转换图合并状态转换图合并状态转换图文法、正规表达式、有限自动机有限自动机(最小化？)7/2/2022333.3 词法分析程序的自动生成器词法分析程序的自动生成器LEX（LEXICAL Analyzer Generator）LEX是1972年在贝尔实验室的UNIX上首先实现FLEX是1984年GNU工程推出，是LEX的扩充，并兼容LEX原理：LEX源程序(lex.l)S.P.字符串LEX编译器词法分析程序L (lex.yy.c)S.P.单词字符串C编译器可执行La.out词法分析程序L (lex.yy.c)可执行La.out7/2

16、/2022341. LEX源程序的结构源程序的结构一个LEX源程序具有如下形式:声明部分声明部分%识别规则识别规则%辅助函数辅助函数各部分之间用%隔开，同时%在最左边.7/2/202235一、声明部分一、声明部分 D1 R1 D2 R2 Dn Rn 其中： R1,R2，Rn 为正则表达式。 D1,D2，Dn 为正则表达式名字 7/2/202236例：C+标识符 letter A|B|Z|_ digit 0|1| |9 id letter(letter|digit)*7/2/202237二、识别规则：是一串如下形式的二、识别规则：是一串如下形式的LEX语句：语句： 模式模式 动作动作 P1 A1

17、 P2 A2 Pm AmPi ：定义在D1,D2,Dn上的正规表达式，也称模式。Ai：Ai为语句序列，它指出，在识别出模式为Pi的单词以 后，词法分析器所应作的动作。 其基本动作是返回单词的类别编码和其属性。7/2/202238三、辅助函数三、辅助函数 定义模式动作需要的函数定义模式动作需要的函数在这三部分中一和三为可选项，但是二是必须的在这三部分中一和三为可选项，但是二是必须的 一对特殊的符号%和% ： 出现在括号内的所有内容都被复制到文件lex.yy.c中，它们 不会被当作正则定义处理。7/2/202239下面是识别某语言单词符号的LEX源程序：例：LEX 源程序 AUXILIARY DE

18、FINITIONS /*声明部分*/ letter Az digit 09 % RECOGNIYION RULES /*识别规则*/“BEGIN” “END” “FOR” RETURN(1,) RETURN(2,) RETURN(3,) RETURN是LEX过程，该过程将单词传给语法分析程序 RETURN（C，LEXVAL） 其中C为单词类别编码 LEXVAL： 标识符：TOKEN（字符数组） 整常数：DTB（数值转换函数，将TOKEN 中的数字串转换二进制值） 其他单词：无定义。7/2/202240“THEN” “ELSE ” letter(letter | digit)*digit(dig

19、it)*RETURN(6,) RETURN(7,) RETURN(8,TOKEN) RETURN(9,DTB） “DO” “IF” RETURN(4,) RETURN(5,) “:” “+” “*” RETURN(10,) RETURN(11,) RETURN(12,) 7/2/202241“,” “:=” “=” RETURN(13,) RETURN(14,) RETURN(15,) RETURN(16,) RETURN(17,) “（” “）” 7/2/2022422. LEX的实现的实现 LEX的功能是根据LEX源程序构造一个词法分析程序，该词法分析器实质上是一个有限自动机。LEX算法X

20、算法Y算法ZLEXLEX源程序源程序正规表达式动作（C代码）DFADFA状态转移矩阵状态转移矩阵7/2/202243LEX生成的词法分析程序有两部分组成:词法分析程序状态转换矩阵(DFA)控制执行程序LEX的功能是根据LEX源程序生成状态转换矩阵和控制程序算法X算法Y算法ZLEXLEXLEX源程序源程序正规表达式动作（C代码）DFADFA状态转移矩阵状态转移矩阵算法X算法Y算法Z7/2/202244LEX的处理过程： 扫描每条识别规则Pi构造一相应的非确定有穷自动机Mi将各条规则的有穷自动机Mi合并成一个新的NFA M确定化 NFADFA生成该DFA的状态转换矩阵和控制执行程序0P1startM1P2M2P3M3