资源描述：
《第三章词法分析及有穷自动机ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、编译原理第三章词法分析及有穷自动机主要内容●词法分析程序的设计过程。●描述单词的文法：正规文法和正规式及它们之间的转换。●单词识别机制（有穷自动机）。●正规式，正规文法和有穷自动机三者之间相互转换。§1.词法分析程序的任务一、词法分析程序的任务及处理方式1.词法分析程序的任务主要任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。词法分析程序（扫描程序）：执行词法分析的程序。2.词法分析程序的处理方式词法分析程序与语法分析程序接口方式有两种：第一种方式：将词法分析作为单独一遍扫描
2、，即在语法分析之前，实现源程序的词法分析工作。其输出（单词串）形成一个中间文件（内部形式的源程序表），然后移交给语法分析程序。第二种方式：将词法分析程序编写成一个子程序，每当语法分析程序需要读一个新单词时，便去调用它。注：后一种方式比较好。因为不需要在内存中构造和保存中间文件。二、词法分析程序的I/O1.输入字符串表示的源程序2.输出单词符号序列或单词符号。1)程序语言的单词符号单词：指语言中具有独立意义的最小语法单位。语言中的单词符号：一般可归结为五种：保留字（基本字）：如if,for,and等――个
3、数确定标识符：表示常量、变量、类型、过程等名称――个数不确定常数：如34，-0.37等――个数不确定运算符：如+，-，*，/，<等――个数确定界线符：如逗号，分号，括号等――个数确定注：·保留字，运算符，界线符可列表，供词法分析程序查询；·标识符和常数可用正规文法或正规式描述，供词法分析程序识别。2)输出的单词形式二元组：（单词的种别码，单词自身值）1o单词的种别码：表示单词的种类分类的原则：处理简单分类的方法：使每一个单词对应一个整数码分类的目的：最大限度地区别各个单词单词地分类法有多种：一种一类一字
4、一类或一符一类具体：保留字：一字一种。如：if1then2。。。标识符：统归一种。常数：整数，实数，布尔统为一种或按类型分整数11实数12布尔13或全体一种+29:=17=21-14<>18>=22*15<19>23/16<=20…运算符：+，-，*，/，>，<等统为一种；或一符一种：2o单词自身值（可有可无）单词自身值是单词的机内代码或者单词在表格中的地址码。如：标识符：自身的字符串（1，’a’）常数：自身的二进制数（11，’100’的二进制数）例：一种一类的单词输出形式设保留字、标识符、常数、运算符
5、、分界符的种别码分别为1，2，3，4，5；将ifa>1thenb:=10表示为一种一类的单词输出形式。ifa>1thenb:=10＝>词法分析器=>(1,’if’)(字符串表示的源程序)(2,’a’),(4,’>’)(3,’1’的二进制数)(1,’then’)(2,’b’)(4,’:=’)(3,’10’的二进制数)例：采用一字一类或一符一类地分类技术，则保留字单词自身值可无，但事先构造一个保留字单词对照表，其值可在词表中查到。ifa>1thenb:=10＝>词法分析器=>(1,◎)字符串表示的源程序(1
6、0,‘a’)(23,◎)(3,’1’的二进制数)(2,◎)(10,’b’)(17,◎)(11,’10’的二进制数)上面符号◎表示要查保留词表表2.1保留字单词表单词类别码单词类别码...............If1+29Then2-14else3*15....../16............>23for19:=17...§2.词法分析程序的设计过程一、词法分析程序的设计过程设计过程：词法分析程序设计过程：①把有的单词（如：标识符和常数）用正规文法或正规式描述；②将正规文法或正规式转换成等价的状态转换
7、图（最小化的DFA图）；③根据状态转换图设计词法分析程序（状态转换图可视为词法分析程序的框图）。转换规则分裂法子集法状态转换图（DFA图）二、用状态转换图设计词法分析程序1.词法分析程序的预处理词法分析程序在识别单词前，需要对输入到缓冲区的源程序进行预处理。预处理：删去无用的空格，跳格，回车和换行等编辑性字符；删去注释部分每次对一串定长（如120个字符）的输入字符进行预处理，并装入一个指定的扫描缓冲区中。扫描缓冲区是一个一分为二的区域，每一个区域可容纳120个字符，且相互交替使用。搜索指针从单词起点开始
8、搜索，如果遇到半区的边界但尚未达到单词的终点时，则可将后续的120个输入字符装进缓冲区的另一半中。2.状态转换图状态转换图是为了识别正规文法或正规式而专门设计的有向图。他是有穷自动机的非形式化表示。状态转换图的组成：1o有限个状态结点状态结点代表正规文法的非终结符（用单圈表示）；开始状态结点：用双箭头指示；终止状态结点：用双圈表示。2o弧线→弧上的标记x指明在射出弧的结点状态下可能出现的输入字符或字符类,即终结符。(→表示机器的识别方向).
