工学第三章词法分析

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

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

1.关键字（保留字）：while、class、for、do2.标识符：a、m_a3.常数：无符号数、布尔常数、字符串常数等4.运算符：+、-、*5.界限符：逗号，分号，括号和引号种类的划分是根据编译的目标和方便设定的单词常用的单词内部形式：1、按单词种类分类2、保留字和分界符采用一符一类3、标识符和常数的单词属性值为符号表入口指针（标识符、常数相关属性很多）（单词属性，单词值）属性字：词法分析程序的输出形式-----单词的内部形式单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数保留字分界符类别编码1234567单词值符号表入口指针整数值数值0或1内部字符串保留字或内部编码分界符或内部编码1、按单词种类分类2、保留字和分界符采用一符一类单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数BEGINENDFORDO………:+*,(类别编码123456789…….20212223…….单词值符号表入口指针整数值数值0或1内部字符串----…..-----3.2.2源程序的输入与预处理词法分析器工作的第一步是接受输入源程序。通常是把输入的源程序引导至一个输入缓冲区，并对输入串进行预处理，然后才交付扫描器进行处理。S.P.(字符串)词法分析程序输入缓冲区的处理？输入缓冲区的处理？显然，无论缓冲区设定为多大，都不能保证单词不会被它的边界打断，若有标识符TEST123，可能在缓冲区中成为：………….TES在这种情况下，即使读到缓冲区的最后一个字符，但仍不能找到该单词的右边界，这时，若从外存上再读一部分源程序进入缓冲区，则会将没有处理过的字符(TES)冲掉。两个半区互补使用为此，我们可将缓冲区分成相等的两个区域：扫描缓冲区一分为二，互补使用。搜索指针从单词起点开始搜索，如果遇到半区域的边界，但尚未到达单词的终点时，则可将后续的输入字符装入该缓冲区的另一半。单词起点

搜索指针IfFatendoffirsthalf{reloadsecondhalf;F++;}ElseifFatendofsecondhalf{ reloadfirsthalf;moveFtobeginningoffirsthalf}ElseF++;输入缓冲区两个半区互补功能的实现算法源程序的预处理为了减轻词法分析器实质性处理的负担，因此源程序从输入缓冲区进入词法分析器之前，要先对源程序进行预处理，预处理子程序一般完成的主要功能是：过滤掉源程序中的注释；剔除源程序中无用字符；进行宏替换；实现文件包含的嵌入和条件编译的嵌入等。具有两个缓冲区的词法分析器结构源程序L输入缓冲区X预处理子程序扫描缓冲区X1词法分析器源程序L的属性字流实现方案（编译程序中实现方式）：基本上有两种1.词法分析单独作为一遍2.词法分析程序作为单独的子程序S.P.(字符串)词法分析S.P.(符号串)语法分析第一遍第二遍单词串优点:结构清晰、各遍功能单一缺点：生成中间文件，效率低S.P.(字符串)词法分析程序语法分析程序取单词单词★词法分析程序的设计与实现词法规则正规表达式状态转换图（最小DFA）1.构造识别单词的状态转换图(1)对程序语言的单词按种类分别构造对应的状态转换图.(2)对各类转换图合并，构成一个能识别语言所有单词的状态转换图.2.编程实现状态转换图1.词法及其状态转换图例1假定语言X的字母表∑={A-Z,a-z,0-9,;,=}单词符号定义如下： 1、标识符：字母打头的字母数字串 2、无符号整数：无符号数字串 3、分界符：； 4、运算符：=标识符出口S1非字母数字字母字母、数字无符号整数出口S1非数字数字数字分界符出口S；运算符出口S=标识符无符号整数分界符S1非字母数字*字母字母、数字2非数字*数字数字；出口出错其他读字符返回S运算符==80;0134256eniL字母字母字母字母数字数字数字==；；0124563Line=80;1,‘Line’3,‘=’2,‘80’4,‘;’数字数字字母字母11==0003;;1输入输出2.状态转换图的实现——构造词法分析程序标识符无符号整数分界符运算符<1，标识符名字><2，整数值><3，“;”><4，“=”>例1假定语言X的字母表∑={A-Z,a-z,0-9,;,=}单词符号定义如下： 1、标识符：字母打头的字母数字串 2、无符号整数：无符号数字串 3、分界符：； 4、运算符：=标识符S1非字母数字字母字母、数字无符号整数S1非数字数字数字分界符出口S；运算符S=出口出口出口标识符出口S1非字母数字字母字母、数字If(ISLETTER){WHILE(ISLETTERORISDIGIT)DO{

当前字符放入一临时字符数组；

GETNEXTCHAR；//从缓冲区取下一字符};UNGETCH；//回退一字符OUTPUT(1，标识符名字)；}；=80;eniLLine=80;==;;无符号整数出口S1非数字数字数字If(ISDIGIT){WHILEISDIGITDO{

当前字符放入一临时字符数组；

GETNEXTCHAR；//从缓冲区取下一字符};UNGETCH；//回退一字符OUTPUT(2,整数)；};=80;eniLLine=80;==;;分界符出口S；If(CH==‘;’)OUTPUT(3,“;”)；If(CH==‘=’)OUTPUT(4,“=”)；运算符S=出口标识符无符号整数分界符S1字母字母、数字2数字数字；出口出错其他读字符返回S运算符=例1程序语言的词法分析程序GETNEXTCHAR()；SWITCH(CHCODE);{CASE1:{WHILE(ISLETTERORISDIGIT)DO{SAVE();//当前字符放入一临时字符数组；GETNEXTCHAR()；//从缓冲区取下一字符};UNGETCH；//回退一字符OUTPUT(1，标识符名字)；}；BREAK;CASE2:{WHILEISDIGITDO{SAVE();//当前字符放入一临时字符数组；GETNEXTCHAR；//从缓冲区取下一字符};UNGETCH；//回退一字符OUTPUT(2,整数)；};BREAK;CASE3:OUTPUT(3,“;”)；BREAK;CASE4:OUTPUT(4,“=”)；BREAK;DEFAULT:Error();};标识符无符号整数分界符S1字母字母、数字2数字数字；出口出错其他读字符返回S运算符=采用面向对象的方法设计词法分析器标识符无符号整数分界符S1字母字母、数字2数字数字；出口出错其他读字符返回S运算符=词法规则正规表达式状态转换图（最小DFA）合并状态转换图编程实现状态转换图合并状态转换图文法、正规表达式、有限自动机有限自动机(最小化？)3.3

词法分析程序的自动生成器—LEX（LEXICALAnalyzerGenerator）LEX是1972年在贝尔实验室的UNIX上首先实现FLEX是1984年GNU工程推出，是LEX的扩充，并兼容LEX原理：LEX源程序(lex.l)S.P.字符串LEX编译器词法分析程序L(lex.yy.c)S.P.单词字符串C编译器可执行L词法分析程序L(lex.yy.c)可执行L1.LEX源程序的结构一个LEX源程序具有如下形式:声明部分%%识别规则%%辅助函数各部分之间用%%隔开，同时%%在最左边.一、声明部分

D1R1

D2R2∶∶DnRn

其中：R1,R2，……，Rn为正则表达式。D1,D2，……，Dn为正则表达式名字

例：C++标识符letterA|B|¨¨¨|Z|_

digit0|1|¨¨¨|9

idletter(letter|digit)*二、识别规则：是一串如下形式的LEX语句：

模式{动作}P1{A1}P2{A2}∶∶Pm{Am}Pi：定义在Σ∪{D1,D2,¨¨Dn}上的正规表达式，也称模式。{Ai}：Ai为语句序列，它指出，在识别出模式为Pi的单词以后，词法分析器所应作的动作。其基本动作是返回单词的类别编码和其属性。三、辅助函数定义模式动作需要的函数在这三部分中一和三为可选项，但是二是必须的

一对特殊的符号%{和%}：出现在括号内的所有内容都被复制到文件中，它们不会被当作正则定义处理。下面是识别某语言单词符号的LEX源程序：例：LEX源程序AUXILIARYDEFINITIONS/*声明部分*/letter[A—z]digit[0—9]%%RECOGNIYIONRULES/*识别规则*/“BEGIN”“END”“FOR”{RETURN(1,─)}{RETURN(2,─)}{RETURN(3,─)}RETURN是LEX过程，该过程将单词传给语法分析程序RETURN（C，LEXVAL）其中C为单词类别编码LEXVAL：标识符：TOKEN（字符数组）整常数：DTB（数值转换函数，将TOKEN中的数字串转换二进制值）其他单词：无定义。“THEN”“ELSE”{