第3章词法分析与有限自动机.

编译原理第3章词法分析与有限自动机安庆师范学院计算机与信息学院本章目标解释词法分析器的工作原理及设计实现介绍单词的描述工具：正规文法和正规式定义DFA和NFA的概念介绍“正规式→NFA→DFA→最小化DFA”的转换方法介绍有限自动机、正规文法和正规式的等价性介绍词法分析器的自动构造工具-LEX的原理与实现教学内容3.1词法分析器的设计思想3.2词法分析器的设计3.3单词的描述工具3.4有限自动机3.5正规式、正规文法和有限自动机的等价性3.6词法分析器的自动构造工具——LEX3.7本章小结3.1词法分析器的设计思想词法分析器的任务和输出形式1将词法分析工作分离的考虑21、词法分析器的任务和输出形式（1）词法分析器的任务自左至右逐个字符地对源程序进行扫描，按语言的构词规则识别出一个个单词，把作为字符串的源程序改造为单词符号串的中间程序。voidmain(){inti=1;i++;}词法分析器void,-main,-(,-),-{,-int,-i,-=,-1,-;,-i,-++,-;,-},-字符串流单词流源语言程序单词符号1、词法分析器的任务和输出形式（2）单词符号单词符号是程序设计语言的基本语法单位和最小语义单位。（3）单词符号的种类标识符：标记常量、变量、函数等的名字，如fun、i关键字：具有固定意义的标识符，如if、while、for常数：各种类型的常数，如实型0.618，布尔型TRUE运算符：如+、-、*、/、=、、、=、==界符：如，、；、（、），{，}单词符号1、词法分析器的任务和输出形式（4）单词符号的输出形式二元式：（单词种别，单词符号的属性值）表示单词的种类，它是语法分析所需要的信息。一个语言的单词符号如何划分种类、分为几类、如何编码都属于技术性问题，主要取决于处理上的方便。通常让每种单词对应一个整数码，这样可最大限度地把各个单词区别开来。用来区分该类单词中的哪一个单词，它是单词本身的机内编码。单词符号的属性是指单词符号的特性或特征。属性值是反应特性或特征的值。例如，对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值；而对于某个常数，则是将存放它的常数表项的指针作为其属性值。1、词法分析器的任务和输出形式（4）单词符号的输出形式常用单词种别编码方案标识符：一种关键字：全体视为一种或一字一种常数：按类型分种，如整数、实数、布尔型运算符：一符一种界符：一符一种单词种别编码1、词法分析器的任务和输出形式（5）举例假定单词类别用整数编码，标识符、常数、关键字、运算符和界符的编码依次为1、2、3、4、5。C++语句if(a=90)b=c；在经过词法分析器处理后输出的二元式及其单词表示如下：二元式单词(3,’if’)关键字if(5,’(’)界符((1,指向a的符号表项的指针)标识符a(4,’=’)运算符=(2,90)常数90(5,’)’)界符)(1,指向b的符号表项的指针)标识符b(4,’=’)运算符=(1,指向c的符号表项的指针)标识符c(5,’；’)界符；返回2、将词法分析工作分离的考虑（1）将词法分析器设计为语法分析器的子程序在实现编译程序时，常将词法分析程序从语法分析中独立出来，将其设计为语法分析器的子程序，每当语法分析器需要一个单词符号时就调用词法分析器，每一次调用，词法分析器就从输入串中识别出一个单词符号，并将该单词类别和单词值返回给语法分析器。字符串形式的源程序字符词法分析器语法分析器符号表单词取下一单词2、将词法分析工作分离的考虑（2）好处①简化设计：由词法分析器处理注解和空白字符，可简化语法分析器的设计。此外，在设计新语言时，分离词法和语法规则可以进行更全面的语言设计。②改进编译效率：编译的大部分时间消耗在读源程序和分离一个个单词符号上，专用的经过精心设计的读源程序字符流和处理单词符号的词法分析器可以加快编译速度。③增强编译系统的可移植性：不同语言的字母表的特殊性，构词规则的差异和其它与设备有关的不规则性可以限制在词法分析器中进行处理。返回3.2词法分析器的设计输入缓冲区和预处理程序1扫描器的工作原理2状态转换图与单词的识别3状态转换图的代码实现41、输入缓冲区和预处理程序（1）预处理程序①建立输入缓冲区，将源程序分批读入输入缓冲区中②过滤掉源程序中的注释；剔除一些无用的空白符、跳格符、回车符、换行符等编辑性字符；进行宏替换；实现文件包含的嵌入和条件编译的嵌入等。③将预处理结果送扫描器的扫描缓冲区（2）预处理程序作为独立子程序预处理可作为一个子程序完成上述三个任务，并被词法分析器调用，每调用一次，它就处理出一串确定长度（如120个字符）的输入字符，并送进扫描缓冲区。返回2、扫描器的工作原理（1）扫描器执行词法分析的程序称为词法分析程序，或称词法分析器，或称扫描器。（2）扫描缓冲区一个可以互补使用的一分为二的扫描缓冲区。扫描缓冲区总长度为2×N（如N=120）个字符，扫描器单词长度的要求是单词长度≤1/2扫描缓冲区长度。2、扫描器的工作原理（3）设置两个指示器①起点指示器：指向当前正在识别的单词的开始位置（指向新单词的首字符）②搜索指示器：用于向前搜索以寻找单词的终点（4）扫描器的工作调用预处理子程序，把N(如120)个输入字符装进扫描缓冲区的某半区，搜索指针从起点指针开始向前寻找单词的终点，若在该半区内查找到单词的终点，便输出二元式，再把起点指针移到此处的后一个字符，继续搜索下一个单词，如果在搜索到该半区的边缘，尚未到达单词终点，那么就调用预处理子程序，把后续的N个字符装进另半区，继续搜索。返回3、状态转换图与单词的识别（1）状态转换图状态转换图是一种有限方向图，状态转换图可用于识别3型语言，它是设计和实现扫描器的一种有效工具，是有限自动机的直观图示。它由以下几个要素构成：①结点：代表状态，用圆圈表示。②箭弧：状态之间的连接，箭弧上的标记（字符）代表在射出结点状态下可能出现的输入字符或字符类。③初态：识别出某一类字符串的开始，初态只有一个。④终态：识别出某一单词，至少有一个。用双圈表示。ijaXaYYa3、状态转换图与单词的识别（2）状态转换图识别的符号串把从开始状态出发到某一终止状态所经过的路径上的标记依次连接起来的符号串，称为能被该状态转换图识别的符号串。例如，右图能够识别符号串adb,addb,adddb,.....,c（3）状态转换图识别的语言状态转换图所能识别的全部符号串组成的集合构成了该状态转换图所识别的语言。例如，右图所能识别的语言为：L(G)={c,adnb|n≥0}3、状态转换图与单词的识别（4）标识符及无符号数的状态转换图0122(a)字母字母或数字其它*0122(b)数字数字其它*0127·2356数字数字数字数字E＋或－数字数字其它*数字其它其它(c)E4(a)标识符；(b)无符号整数；(c)无符号数*为进行超前搜索，多读进了一个符号，应回退搜索指示器。3、状态转换图与单词的识别（5）利用状态转换图识别单词的基本步骤①从开始状态出发；②读入一个字符；③根据当前字符转入下一状态；④重复②和③，直到到达某一终态。3、状态转换图与单词的识别（6）举例下图为识别某个简单语言的所有单词符号的状态转换图。返回4、状态转换图的代码实现（1）一组全局变量和函数要能有效实现词法分析器，需要定义如下的一组全局变量和函数：①ch：字符变量，存放最新读入的源程序字符②strToken：字符数组，存放构成单词符号的字符串③GetChar：函数，把下一个字符读入到ch中。④GetBC：函数，跳过空白符，直至ch中读入一非空白符。⑤Concat：函数，把ch中的字符连接到strToken；⑥IsLetter：函数，判断ch中字符是否为字母；⑦IsDigit：函数，判断ch中字符是否为数字；⑧Reserve：函数，对于strToken中的字符串查找保留字表，若它是保留字则给出它的编码，否则返回0；⑨Retract：函数，把搜索指针回调一个字符位置，将ch置为空白字符；4、状态转换图的代码实现（1）一组全局变量和函数InsertId：函数，将strToken中的标识符插入符号表，返回符号表指针；InsertConst:函数，将strToken中的常数插入常数表，返回常数表指针。DTB：函数，把strToken中数字串译成标准二进制码，并作为函数值返回（十进制转换为二进制）4、状态转换图的代码实现（2）根据状态转换图编写代码的一般方法一般将状态转换图看成一个流程图，从状态转换图的初态开始，对其每一个状态结点编写一段相应的程序，具体的做法是：①每个状态结点对应于一个程序段；②对不含回路的分叉结点来说，可让它对应一个switch语句或一组if...else语句；如下图中的结点i对应的程序段为：ijk字母+数字Lstatei：GetChar();if(IsLetter()){....转状态j对应的程序段....}elseif(IsDigit()){....转状态k对应的程序段....}elseif(ch=='+'){....转状态L对应的程序段....}else{....错误处理....}4、状态转换图的代码实现（2）根据状态转换图编写代码的一般方法对含有回路的状态结点来说，可让它对应一个由while语句和if语句构成的程序段；如下图中的结点i对应的程序段为：statei：GetChar();while(IsLetter()||IsDigit()){GetChar();}....转状态j对应的程序段....ij其它字母或数字4、状态转换图的代码实现（2）根据状态转换图编写代码的一般方法终态结点表示识别出某种单词符号，因此一般对应一个形如return(code,value)的语句，其中code为单词的种别编码，value为单词符号的属性值，或无定义；如下图中的结点i对应的程序段为：凡带有星号（*）的终态结点意味着多读进一个不属于现行单词符号的字符，该字符应予退回，即必须把搜索指示器回调一个字符位置。如下图中的结点i对应的程序段为：iistatei：return(code,value);statei：Retract();return(code,value);ii*4、状态转换图的代码实现（3）词法规则的相关约定为方便起见，对词法进行如下约定：除标识符、常数外，均为一符一种；关键字均作为保留字，不可用作用户标识符；设保留字表，识别出标识符时，查该表确定是否为关键字；相邻单词之间至少存在一个界符、运算符或空格。4、状态转换图的代码实现（4）举例编写由以下状态转换图所描述的某简单语言的词法分析程序。单词符号种别编码助忆符内码值DIM1$DIM—IF2$IF—DO3$DO—STOP4$STOP—END5$END—标识符6$ID内部字符串常数（数）7$INT标准二进制形式=8$ASSIGN—-9$PLUS—*10$STAR—**11$POWER—，12$COMMA—(13$LPAR—)14$RPAR—单词符号及内码值4、状态转换图的代码实现intcode,value;strToken=;GetChar();GetBC();if(IsLetter()){while(IsLetter()orIsDigit()){Concat();GetChar();}Retract()；4、状态转换图的代码实现code=Reserve();if(code==0){value=InsertId(strToken);return($ID,value);}elsereturn(code,－);}elseif(IsDigit()){while(IsDigit()){Contact();Getchar();}Retract()；value=InsertConst(strToken);return($INT,value);}4、状态转换图的代码实现elseif(ch=='=')return($ASSIGN,－);elseif(ch=='+')return($PLUS,－);elseif(ch