编译原理词法解析.pptx
1第一节 状态转换图一 单词分类及表示 编译中,把高级语言的单词分为五类:标识符,基本字,常数,运算符,界符 基本字,运算符,界符都是有限可枚举的;而标识符,常数可认为是无限的.简单起见,单词可表示为如下二元组:(单词分类号,单词自身值);或者为:(单词种别码,单词自身值);标识符,常数 各为一个种别码,而由于基本字,运算符,界符的有限性,可以设计为一字一个种别码.第1页/共42页2例如:单词 单词种别码分类号 标识符1 1常数 2 2if 3 3then4 3end90 3,91 4;92 4=151 5+152 5保留字界符运算符第2页/共42页3二 词法分析器的设计1 源程序的预处理子程序 源程序中,存在许多编辑用的符号,它们对程序逻辑功能无任何影响.例如:回车,换行,多余空白符,注释行等.在词法分析之前,首先要剔除掉这些符号,使得词法分析更为简单.源程序输入缓冲区预处理子程序扫描缓冲区2扫描缓冲区1 缓冲区分为两部分,每个长度为256字节,这样单词的总长度可达到256字节.预处理子程序把处理好的字符串轮流放入两个缓冲区中,供词法分析程序使用.第3页/共42页42 词法分析程序 词法分析程序又称为词法分析器或扫描器.可以单独为一个程序;也可以作为整个编译程序的一个子程序,当需要一个单词时,就调用词法分析子程序返回一个单词.这里,作为子程序介绍.词法分析器的结构:源程序输入缓冲区预处理子程序扫描缓冲区2扫描缓冲区1词法分析子程序调用返回一单词数据第4页/共42页53 词法规则的表示-状态转换图定义:状态转换图是一有向图,由有限个结点及有向边连接而成;每个结点称为状态;状态图有一个初态,多个终态;每条边上 有相应的字符.状态转换图用于表示单词结构,从状态转换图的初态到终态间,每条路径上字符的连接,就构成了该状态图的合法单词.例如:012初态终态字母字母数字其它*1标识符的状态图表示:星号表示单词尾部多跟一个字符,应该去掉.第5页/共42页6012初态终态数字数字其它*2整数的状态图表示:016初态终态数字数字其它*3实数的状态图表示:23456数字数字 数字E+或 数字E其它数字第6页/共42页74 单词的识别 状态图即可以表示单词规则,同时也可以用于识别单词.设有一字符串S=s1s2.sn,若状态图中存在一初态到终态的路径,且路径上字符的连接为:s1s2.sn,称 S 可被状态图识别.例如:S=var1012初态终态var1其它*保留字由于满足标识符定义,因此可以跟标识符用同样的状态图表示与识别,只需增加一个保留字表,当识别出一个标识符时,通过查保留字表来区别保留字及普通标识符.因此 var1 是一个合法的标识符.第7页/共42页85 一个简单示例 构造一个简单语言所有单词的状态转换图.该语言的单词种类如下表所示:单词符号 种别码 助记符 内码值 DIMIFDOSTOPEND标识符正常数=+*,()1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR(1,)(2,)(3,)(4,)(5,)(6,串值)(7,数值)(8,)(9,)(10,)(11,)(12,)(13,)(14,)第8页/共42页90 1 2初态终态字母字母数字其它*空白 3 4 终态数字数字非数字*5=6+7*9 8*非*10,11(12)13其它第9页/共42页106 状态转换图的程序实现 为便于程序实现,假设每个单词间都有界符或运算符或空格隔开,并引入下面的全局变量及子程序:1)CHAR 字符变量2)TOKEN 单词字符串3)GETCHAR 读一个字符到 CHAR 中4)GETBC 读一个非空白字符到CHAR 中5)CONCAT 把CHAR 中字符连接到TOKEN 之后6)LETTER 判断CHAR 中字符是否为字母7)DIGIT 判断CHAR 中字符是否为数字8)RESERVE 用TOKEN中的字符串查找保留字表,并返回保留 字种别码,若返回零,则非保留字9)RETRACT 把CHAR 中字符回送到缓冲区第10页/共42页11 下面分析状态图的结构特点.每个状态图都由三种结构构成:分支结构 循环结构 终结点1分支结构程序设计 i i2i1 inc1c2cnstate i:GETCHAR;CASE CHAR OF c1:CONCAT；state i1:.c2:CONCAT；state i2:.cn:CONCAT；state in:.ELSE ERROR END;第11页/共42页122循环结构程序设计 i j C其它state i:GETCHAR;WHILE CHAR=C DO CONCAT;GETCHAR;RETRACT；state j:.3终结点程序设计 一般对应一条返回语句:return(c,val);c 为种别码,val 为单词值.带*号的终结点,必须用RETRACT 退还多余字符 下面程序为简单示例语言的实现:第12页/共42页13TYPE WORDTYPE=RECORD C：INTEGER；VAL：CHAR；END；FUNCTION RETURN_WORD():WORDTYPE;STATE0:TOKEN:=;GETCHAR;GETBC;CASE CHAR OF A.Z:CONCAT;STATE1:GETCHAR;WHILE (LETTER OR DIGIT)DO CONCAT;GETCHAR;RETRACT；STATE2:C:=RESERVE;IF C=0 THEN RETURN($ID,TOKEN)ELSE RETURN(C,_)第13页/共42页14 0.9:CONCAT;STATE3:GETCHAR;WHILE (DIGIT)DO CONCAT;GETCHAR;RETRACT；STATE4:RETURN($INT,TOKEN);=:STATE5:RETURN($ASSIGN,_);+:STATE6:RETURN($PLUS,_);*:STATE7:GETCHAR;STATE9:IF CHAR=*THEN RETURN($POWER,_);STATE8:RETRACT;RETURN($STAR,_);,:STATE10:RETURN($COMMA,_);(:STATE11:RETURN($LPAR,_);):STATE12:RETURN($RPAR,_);ELSE STATE13:ERROR第14页/共42页 这节介绍词法规则的形式表示(正规式),从正规式向有限自动机的转化.正规式有限自动机词法分析器控制程序自动生成器转化合成第二节 正规式与有限自动机第15页/共42页16一 基本概念 定义 1 字与字集 假设:是一有穷字符集,它的每个元素称为一个字符;字-上的一个字,是由 中的字符所构成的一个有穷序列;空串-不包含任何元素的序列称为空串,记为;闭包*-上所有可能的字的全体;空字集-不含任何字的集合称为空字集;记为=;例如:=a,b 则 *=,a,b,aa,ab,ba,bb.注意:,三者间的关系定义 2 连接运算 设 U,V *则 UV=|U,V 一般 UVVU Vn =VV.V 称为 V 的 n 次积第16页/共42页17例如:设 U=a,aa,V=b 则UV=ab,aab VU=ba,baa定义 3 V的闭包 设 V 为字集,且 V0=令 V*=V0V1 V2.V+=V*-称V*为V的闭包 称V+为V的正则闭包 注意:*与 V*的区别.第17页/共42页18 二 正规式与正规集 *是一个无穷集,在程序语言中,我们只研究满足词法规则(正规式)的单词集(正规集).定义 1 正规式与正规集的递归定义:1),是 上的正规式,所表示的正规集为 ,;2)若 a,则 a 为正规式,所表示的正规集为 a;3)设U,V 为 上的正规式,所表示的正规集为 L(U),L(V);则 U|V为 上的正规式,所表示的正规集为 L(U)L(V);UV为 上的正规式,所表示的正规集为 L(U)L(V);V*为 上的正规式,所表示的正规集为 L(V)*;4)仅当有限次使用上述三步骤而定义的表达式,才是 上的正规式,而这些正规式所表示的字集才是上的正规集.第18页/共42页19示例:令=A.Z,0.9 则整数的正规式为:(0|1|2.|9)(0|1|2.|9)*所表示的正规集为所有整数;标识符的正规式为:(A|B|.Z)(A|B|.Z|0|1|.|9)*所表示的正规集为所有标识符定义 2 若两个正规式 U,V 所表示的正规集相同,即 L(V)=L(U),则称两个正规式等价,记为 U=V.正规式的运算:设 U V W 为正规式,则满足以下关系:1)U|V=V|U 2)U|(V|W)=(U|V)|W 3)U(VW)=(UV)W 4)U(V|W)=UV|UW (U|V)W=UW|VW 5)U=U=U第19页/共42页20三 确定有限自动机 一个确定有限自动机(DFA M)是一个五元式:DFA M=(S,f,s0,Z)其中 S 是一有限集,每个元素称为一个状态;是一个有穷字母表,每个元素为一字符;f 是一个单值映射函数,f(si,a)=sj(si,sj S,a);其含义为:在状态 si ,输入字符 a 时,将转换到下一状态sj.称sj为 si的后继状态.s0 S,是唯一的初态;Z S,是终态集.一个DFAM可用状态转换矩阵或状态图表示第20页/共42页21例如:DFAM=(0,1,2,3,a,b,f,0,3)其中f为:f(0,a)=1 f(1,a)=3 f(2,a)=1 f(3,a)=3 f(0,b)=2 f(1,b)=2 f(2,b)=3 f(3,b)=3状态转换矩阵可表示为:状态图可表示为:ab012132213333状态字 符013初态终态2abbaaabb第21页/共42页22四 非确定有限自动机 一个非确定有限自动机(NFA M)是一个五元式:NFA M=(S,f,S0,Z)其中 S 是一有限集,每个元素称为一个状态;是一个由穷字母表,每个元素为一字符;f 是一个多值映射函数,f(si,)=s i1,s i2,.s ik (si,si1,.,s ik S,*);其含义为:在状态 si ,输入字串 时,将转换到下一状态集:s i1,s i2,.s ik S0 S,是初态集;Z S,是终态集.一个NFAM也可用状态图表示,此时每条边用字串表示.第22页/共42页23例如:01初态终态2aabba,ba,ba,b终态DFAM 是 NFAM 的特例.定义:状态图中,从初态到终态任一路径上的字串连接,称为该状态图可识别的单词,可识别单词的全体记为:L(M).若L(M)=L(M),称M 与M等价.第23页/共42页24五 正规式与有限自动机的等价性 前面,介绍了正规式,DFAM,NFAM,下面讨论这三个概念间的关系.定理1:对任意正规式V,存在一个NFAM ,使得L(V)=L(NFAM);证明:(1)构造一个拓广转换图 显然,该转换图能识别的 单词集为:L(V)XYV第24页/共42页25(2)进行如下等价变换,直到转换图的每条边上的标志为上的 字符.ijV1V2ijV1kV2aijV1|V2iV1jV2bijV*ijkcV 等价变换后的转换图M 符合 NFAM的定义,显然有 L(V)=L(M).该定理说明,从正规式可逐步构造一个NFAM.第25页/共42页26定义:设 S 是一个状态集,_CLOSURE(S)定义如下:a)若 s S,则 s _CLOSURE(S);b)若 s S,则 从 s 出发经过任意条 边所能到达的状态 s 都属于 _CLOSURE(S).状态集_CLOSURE(S)称为 S 的_ 闭包.定理2:对任意NFAM,存在一个DFAM ,使得L(DFAM)=L(NFAM);证明:(1)对 NFAM 进行等价变换,使得变换后的转换图NFAM中 仅含边和 上的字符边;(2)用状态转换矩阵M 表示NFAM;第26页/共42页27其中,I0 为初态集的_ 闭包.Ii a=_ CLOSURE f(si 1,a)f(si 2,a)f(sik,a)si 1,si 2,.sik Ii(3)将M 中的状态集换名,si=Ii 得到一新的状态转换矩阵 M,M 满足 DFAM 的定义.Iabc.I0I1Ii Ii a Ii b Ii cInM第27页/共42页28证毕.推论:对任意正规式V,存在一个DFAM ,使得L(DFAM)=L(V).Sabc.s0s1si si a si b si csnM第28页/共42页29示例:设正规式为 (a|b)*(aa|bb)(a|b)*,求与之等价的DFAM.(1)由定理 1 的证明方法,可如下构造NFAMXY(a|b)*(aa|bb)(a|b)*等价变换得到:513264aaaabbbbNFAMXY(2)用状态转换矩阵M 表示NFAM;第29页/共42页30Iabx,5,1 5,1,3 5,1,45,1,3 5,1,3,2,6,y 5,1,45,1,4 5,1,3 5,1,4,2,6,y5,1,3,2,6,y 5,1,3,2,6,y 5,1,4,6,y5,1,4,2,6,y 5,1,3,6,y 5,1,4,2,6,y5,1,4,6,y 5,1,3,6,y 5,1,4,2,6,y5,1,3,6,y 5,1,3,2,6,y 5,1,4,6,yM(3)将M 中的状态集换名,si=Ii 得到一新的状态转换矩阵 M注意:M 与 M等价.第30页/共42页31Sabs0 s1 s2s1 s3 s2s2 s1 s4 s3 s3 s5 s4 s6 s4 s5 s6 s4 s6 s3 s5MM满足确定有限自动机的定义,状态图表示如下:s0s1s3s5s6s4abbs2aaaaaabbbbb第31页/共42页32 第三节 词法分析器的 自动生成原理及LEX语言正规式确定自动机状态转换矩阵词法分析器控制程序自动生成器转化合成一 自动生成原理第32页/共42页33二 LEX 语言 LEX 语言用正规式描述单词的词法规则,并通过LEX编译,自动生成词法扫描器.LEX语言源程序LEX编译词法分析器 LEX语言源程序由两部分组成:正规式辅助定义式识别规则第33页/共42页341 辅助定义式 辅助定义式是如下形式的 LEX 语句D1 R1D2 R2Dn Rn Ri为正规式,Di为简名.规定Ri中只能出现上的字符及之前已定义过的D1.Di-1.例如:Letter A|B|.|Z|a|b|.|zDigit 0|1|2.|9Iden Letter(Letter|Digit)*第34页/共42页352 识别规则Unsignedint Digit(Digit)*Sign +|-|signedint Sign Unsignedint P1 A1P2 A2Pm Am Pi为正规式,规定Pi中只能出现上的字符及D1.Dn;P1.Pm 代表了某种高级语言的所有词形.Ai为一段程序代码,指出当识别出满足规则Pi的单词时,扫描器应采取的动作.第35页/共42页363 LEX编译的工作原理 LEX编译对源程序进行处理,产生一个词法分析器.主要有三个步骤:1 对每条识别规则Pi,构造一个非确定有限自动机 Mi ,设一 初态X,用边连接每个Mi的初态,构成一个总的NFAM;M1 M2 Mm x P1 P2Pm NFAM第36页/共42页372根据定理 3,把 NFAM 确定化,得到一确定有限自动机 DFAM 的状态转换矩阵;3产生一个控制程序.输出如下所示的词法分析器:状态转换矩阵控制程序 控制程序用于扫描输入字符串,控制状态的转移;(对任何 转换矩阵,其控制程序是一样的)当识别出某词形Pi后,执行Ai.(返回种别码及值)词法分析器 第37页/共42页38 本章习题1)构造如下正规式相应的DFA 11(0|1)*1012)构造一个DFA,它接受=0,1上所有满足如下 条件的字符串:每个1后都有0直接根在后边;根 据DFA的状态图,编写一个识别程序.第38页/共42页39 课程设计1词法分析器设计 设计题目：手工设计c语言的词法分析器 （可以是c语言的子集）设计内容：处理c语言源程序，过滤掉无用符号，判断源程序中单词的合法性，并分解出正确的单词，以二元组形式存放在文件中。设计目的：了解高级语言单词的分类，了解状态图以及如何表示并识别单词规则，掌握状态图到识别程序的编程。结果要求：课程设计报告。完成日期：第十五周提交报告第39页/共42页40一、用正规式表达如下的单词规则：）偶数规则；）带符号（+，-）以及无符号整数的规则；）首字符为的标识符规则。4）S=0，1上的正规集S由倒数第二个字符为1的所有字符串组成，写出满足条件的串的正规式；二、设有正规式 11(0|10)(0|10)*111、求与正规式等价的NFAM；2、求与正规式等价的DFAM（用状态图表示）。第40页/共42页41第41页/共42页42感谢您的观看。第42页/共42页
