第4部分词法分析课件.ppt

《第4部分词法分析课件.ppt》由会员分享，可在线阅读，更多相关《第4部分词法分析课件.ppt（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理编译原理第第4 4章章 词法分析词法分析词法分析程序的设计单词的描述工具有限自动机正规式和有穷自动机的等价性正规文法和有穷自动机间的转换词法分析程序的自动构造工具返回目录寇酣鄙炕绿胖荒靛帽泄传敬豁蔬喳瘁搏梢续陶导橇措踞喷鹃援泻害隙襄拘第4部分词法分析第4部分词法分析编译原理编译原理逐个读入逐个读入源程序字符并按照构词规则切分成一系列单词。4.1 4.1 词法分析程序的设计词法分析程序的设计词法分析（词法分析（lexical analysis）单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分

2、析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。今谋藤哉路殿泞诚聋蛋壤硒幻鸿滴锨鸳肮怀著鸯监褒凸旨享却印持勇井傈第4部分词法分析第4部分词法分析编译原理编译原理词法分析程序词法分析程序源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序Tokenget token.主要任务：读源程序，产生单词符号。滤掉空格，跳过注释、换行符。追踪换行标志，复制出错源程序。宏展开，其他任务：洛蕴帮阜妆届暴越绳叙它袖服躲稼轻坷富澈宫吃星营座手搪街晃猿虎市耘第4部分词法分析第4部分词法分析编译原理编译原理单词符号单词符号单词符号一般可分为下列五种：基本字基本字（关键字关键字

3、）：begin,end,if,while,var等。标识符标识符：各种名称，如常量名、变量名、过程名等。常数常数（量）：25,3.1415,TRUE,“ABC”等运算符运算符：如+-*/=等。界符界符：逗号，分号，括号等。容泪臆姑歪萎镀穴氨茬佣筋叉爵椎伦扇蟹思矗铰冗挟家敬滋帘媚回森毫垦第4部分词法分析第4部分词法分析编译原理编译原理输出表示输出表示（单词种别，单词自身的值单词种别，单词自身的值）。单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，保留字为3，运算符为4，界符为5。如：程序段 if i=5 then x=y；在经词法分析器扫描后输出的单词符号和它们的表示如下：共逆琴垮菠

4、烙揉镑鲤拈果邓丈诈数牺砖邻芍砧泻燎晰乌倾倘汹还拨邪式钵第4部分词法分析第4部分词法分析编译原理编译原理程序段 if i=5 then x=y -保留字if(3，if)-标识符i(1，指向i的符号表入口)-等号=(4，=)-常数5(2，5)-保留字then(3，then)-标识符x(1，指向x的符号表入口)-赋值号=(4，=)-标识符 y(1，指向y的符号表入口)-分号；(5，；)迅燥秀汤看积答秽稽烃穷当消滇怨惕锭偏榆请陌寇祥顿奠诽萝弧寸别牵镰第4部分词法分析第4部分词法分析编译原理编译原理词法分析工作独立的原因词法分析工作独立的原因：简化设计 改进编译效率 增加编译系统的可移植性 坚柄戈鲤兹腐

5、浚混态径夕馆苗径釜塞乖缸衬摊针制眷屡亩碾学胃燎绿脸润第4部分词法分析第4部分词法分析编译原理编译原理单词的描述工具单词的描述工具 文法G=（VN，VT，P，S），P中每一产生式的形式都为：AaBAaB或AaAa，其中AVN，BVN，aVT。几类单词的描述几类单词的描述标识符标识符：标识符l|l字母数字字母数字l|d|l字母数字|d 字母数字4.2 4.2 正则表达式和正规集正则表达式和正规集正规文法正规文法磺埔蛊火澡蛀配她士柠豪睹斜浦伍囱嘎得慷颈莉魔士屠匡美溪喧钩抬唁钞第4部分词法分析第4部分词法分析编译原理编译原理无符号整数无符号整数：无符号整数d|d无符号整数运算符运算符：运算符+|-|*

6、|/|=|等号等号=界符界符：界符,|;|(|)|适捅强鞘至牌蝎涛恋辐魂同撇党募结厦赖钦桅攻渴徘淡梅邵虐殷疼绕菲辙第4部分词法分析第4部分词法分析编译原理编译原理无符号实数无符号实数：无符号实数 d 余留无符号数|.十进小数|e指数部分余留无符号数 d 余留无符号数|.十进小数|e指数部分|十进小数 d 余留十进小数余留十进小数 e指数部分|d 余留十进小数|指数部分 d 余留整指数|s整指数整指数 d 余留整指数余留整指数 d 余留整指数|其中s表示正或负号。如 25.55e+5 和 2.1榜人讼贼庐硕炕飘猖毯抒囤糜您章茵翠玲相窿界蹬密律餐匠诉谆刷织柞脂第4部分词法分析第4部分词法分析编译原

7、理编译原理正规式正规式(regular expression)(regular expression)正规式正规式正规式正规式和它所表示的和它所表示的正规集正规集设字母标为，辅助字母表=，。v 1。和都是上的正规式，它们所表示的正规集分别为和；v2。任何a，a是上的一个正规式，它所表示的正规集为a；v3。假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1)。伙脆洋灸沏征崎雕钵铀斑端铜族袒澳希崔碾潜贷升台网萤橱残蹿肃浙迂屎第4

8、部分词法分析第4部分词法分析编译原理编译原理v 4。仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。说明：说明：其中的“”读为“或”（也有使用“+”代替“”的）；“”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“”、“”。连接符“”一般可省略不写。“”、“”和“”都是左结合的。讨匆释胶娩渐卑娃咖榆法技孕逐洋灰济划执呵雾亮鼎茄占柬蹋驰侯券南蕾第4部分词法分析第4部分词法分析编译原理编译原理例4.2 令=a，b，上的正规式和相应的正规集的例子有：正规式 正规集a aaba,bab

9、 ab(ab)(ab)aa,ab,ba,bba ,a,a,任意个a的串(ab),a,b,aa,ab 所有由a和b组成的串(ab)(aabb)(ab)上所有含有两个相继的a或两个相继的b组成的串理瓦迂顺贤幽牲凋蕴栽仆谢贿蝇全怨筐粤槛闪乾胺碘缀随攻求柄八看讨轻第4部分词法分析第4部分词法分析编译原理编译原理例 =l，d，r=l(l d)定义的正规集:l,ll,ld,ldd,，其中l代表字母，d代表数字，正规式，即是字母(字母|数字)*，它表示的正规集中的每个元素的模式是“字母打头的字母数字串”，就是Pascal和多数程序设计语言允许的的标识符的词法规则。例4.3 =d，.，e，+，-,则上的正规式

10、 d d (.dd(.dd )(e(+)(e(+-)dd)dd )表示的是无符号数的集合，其中d为09的数字。欺诅碴毗兄炙轮地素榴玉恃悬津湃桑爬艘坛棍贩涪宰蒙茧努靛秀胀吱拎缕第4部分词法分析第4部分词法分析编译原理编译原理两个正规式两个正规式等价等价若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如：e1=(ab)，e2=ba又如：b(ab)=(ba)b(ab)=(ab)狰袁于游拘受蛇嵌明盆友屿劈贫汞醚享昌拭陪豫屋舶不益妊碘纳铂趋鞭撼第4部分词法分析第4部分词法分析编译原理编译原理正规式的运算律正规式的运算律设r,s,t为正规式，正规式服从的代数规律有：1。rs

11、=sr“或”服从交换律2。r(st)=(rs)t“或”的可结合律3。(rs)t=r(st)“连接”的可结合律4。r(st)=rsrt (st)r=srtr 分配律 5。r=r,r=r是“连接”的恒等元素6。rr=r r=rrr “或”的抽取律 爱杨勤偏筐绎头兔约疚泣咯驾赵馅矢兄慎几斯断祷燕隧慷扮艰嗓午涅耍借第4部分词法分析第4部分词法分析编译原理编译原理 对于对于 上的正规式上的正规式r,存在一个存在一个G=(VN,VT,P,S)使得使得L(G)=L(r)，反之亦然。，反之亦然。1.1.将正规式转换成正规文法将正规式转换成正规文法 VT=,S VN，生成正规产生式 Sr正规文法到正规式正规文法

12、到正规式(1)对形如 Axy的正规产生式：AxB By BVN焚北软鞭签姬勋痕肢墩泅栅肇吨顽钳睹撤尚钢仿洞轮奋敏滓议逗漱梗晌诊第4部分词法分析第4部分词法分析编译原理编译原理(2)对形如Axy的正规产生式：AxB Ay BxB By BVN (3)对形如Axy的正规产生式:A x A y 不断应用上述规则做变换，直到每个产生式右不断应用上述规则做变换，直到每个产生式右端只含一个端只含一个VN。挺渝氖推泞满笨候史斩芹捣翌贼临播店辊讶耿栋换睛睁思而党脯辙意篷著第4部分词法分析第4部分词法分析编译原理编译原理例 r=a(ad)VT=a,d Sa(ad)Gs:SaA A VT=a,d AaBVN=S,

13、A,B AdB BaB BdB BSaAA(ad)A(ad)BAB(ad)BB规则一规则二陌酝阿咨载糠玩锹坑诧危慌割禽翰这量碳叔任砸屎盔砒荔色扩参已撼晾峰第4部分词法分析第4部分词法分析编译原理编译原理2.2.将正规文法转换成正规式将正规文法转换成正规式将正规文法转换成正规式将正规文法转换成正规式 S=aAa例Gs:SaA AaA AdA Sa Aa Ad A=aAdA a d =(ad)A(ad)=(ad)(ad)S=a(ad)(ad)a =a(ad)(ad)=a(ad)R=a(ad)（1）AxB,ByA=xy（2）AxA y A=x y（3）Ax yA=x y文法产生式文法产生式文法产生式

14、文法产生式正规式正规式正规式正规式枢腥奔诉宰辗劲赘惠古彭焕旱腊氯敝谨蠕椽蝇伏凤额瘩摹噪措佛客俄乙感第4部分词法分析第4部分词法分析编译原理编译原理4.34.3有穷自动机有穷自动机确定的有穷自动机（DFA）不确定的有穷自动机（NFA）NFA DFA 的转换DFA的化简怕铀篮挡为分人渡粗伤母略丸捷炸哼吾豁者粮忆薄勤根煎探隅缀恿梯招灌第4部分词法分析第4部分词法分析编译原理编译原理 DFA DFA定义定义定义定义：一个确定的有穷自动机（一个确定的有穷自动机（DFA）M是一个五元组：是一个五元组：M=（K，f，S，Z）其中）其中1 1。K K K K是一个有穷集，它的是一个有穷集，它的每个元素每个元素

15、每个元素每个元素称称为为为为一个一个状态状态状态状态；2 2。是是是是一个有穷字母表，它的每个元素称为一个输入一个有穷字母表，它的每个元素称为一个输入符号，所以也称符号，所以也称为为输入符号字母表输入符号字母表输入符号字母表输入符号字母表；3 3。f f f f是转换函数是转换函数是转换函数是转换函数，是在，是在KK上的映射，即，如上的映射，即，如 f（ki，a）=kj，（，（kiK，kjK）就意味着，当前状态就意味着，当前状态为为ki，输入符为，输入符为a时，将转换为下一个状态时，将转换为下一个状态kj，我们把，我们把kj称作称作kiki的一个后继状态；的一个后继状态；4。S S S SKK

16、是唯一是唯一是唯一是唯一的一个的一个初态初态初态初态；5 5。Z Z Z Z K是是是是一个一个终态集终态集终态集终态集，终态也称，终态也称可接受状态可接受状态或或结束状结束状态态。乙哮读檬磁汝柑汁排酱菌希刷载朱剂妹掸屑消购废荡采恐凑钉货伍巩刘戮第4部分词法分析第4部分词法分析编译原理编译原理DFA 例：DFA M=（S,U,V,Q,a,b,f,S,Q）其中 f 定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q掣拣剪挤让知位酉障概绥肥哺激曹帕向吏拥葱候侦渤低隅给栓煽瞅惜苹伏第4部分词法分析第4部分词法分析编

17、译原理编译原理DFA DFA 的状态图表示的状态图表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bb衍减隐清库殿心框达稻临射供肖隶拯它稚臃弱锻掐枕你闽皱刁欧渍书氛焕第4部分词法分析第4部分词法分析编译原理编译原理DFA DFA 的矩阵表示的矩阵表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q字符状态0100伟碉历烛父耳陛稳偏埔炒鸯铃戮丘藤范龟梳挥诈聂拓防蟹抚伴拐嚼类眠荒第4部分词法分析第4部分词法分析编译

18、原理编译原理DFA的确定性表现在：的确定性表现在：转换函数转换函数f:KK是一个单值函数是一个单值函数，也就是说，对任何状态kK，和输入符号a，f(k,a)唯一地确定了下一个状态。从状态转换图来看从状态转换图来看，若字母表含有n个输入字符，那末任何一个状态结点最多有任何一个状态结点最多有n条条弧射出弧射出，而且每条弧以一个不同的输入字符标记。秩戏趁倍左睬捡译誉矾镰扎篇直圃镁该靳横锌瑚沾奠效熄性熟庙酿漱狂耸第4部分词法分析第4部分词法分析编译原理编译原理*上的符上的符号号串串t在在M上运行上运行一个输入符号串t，（我们将它表示成Tt1的形式，其中T，t1*）在DFA M上运行运行的定义为：f f

19、（Q Q，Tt1 Tt1）=f=f（f f（Q Q，T T），），t1t1）其中QK 扩充转换函数f，是K*K上的映射，且：f（Q，）=Q谆氛弱隘忿揖口稿效充眠瘩客杆懦姬挺磅步下讫芬橙昧氮蕴襟炭房董酥叁第4部分词法分析第4部分词法分析编译原理编译原理*上的符号串上的符号串 t t 被被 M M 接受接受对于*中的任何字符串t，若存在一条从初态结到某一终态结的道路，且这条路上所有弧的的标记符连接成的字符串等于t，则称t可为DFA M所接受，若M的初态结同时又是终态结，则空字可为M所接受接受（识别识别）。若t*，f(S，t)=P，其中S为DFA M的开始状态，P Z，Z为终态集。则称t为DFA M

20、所接受接受（识别识别）。旁雾例误孝渠塌筹努美赊乔纵晾慧被协颈心燥每糊犯夷褐的耳腕置彦徘浅第4部分词法分析第4部分词法分析编译原理编译原理例：证明例：证明t=baab被如下的被如下的DFA所接受。所接受。DFA M=（S,U,V,Q,a,b,f,S,Q）其中）其中 f 定义为：定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bb证明：证明：f（S，baab）=f（f（S，b），），aab）=f（V，aab）=f（f（V，a），），ab）=f（U，ab）=f（f（U，a），），b）=f（Q

21、，b）=QQ属于终态。得证。属于终态。得证。疥抢瓤室讳断伦锡最际伙婉踞嚏递她砍肪询晚聊钝檀奄撇淀喊搜卞昨撒哭第4部分词法分析第4部分词法分析编译原理编译原理DFA M所能接受的符号串的全体记为L(M)结论：结论：上一个字符串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。北椿捞娥迪蚌诗诞血氟尿痛眠憨俄酚孜怯痴藩苯淑蛾样丘逞淌当瘤湘乏示第4部分词法分析第4部分词法分析编译原理编译原理不确定的有穷自动机不确定的有穷自动机NFANFA定义定义N=K，f，S，Z，其中KK为状态为状态为状态为状态的有穷非空集集集集，为为为为有穷输入字母表字母表字母表字母表，f f为为为为K*到K的

22、子集的映像映像映像映像，S SK是是初始状态集初始状态集初始状态集初始状态集，Z Z K为终止状态集为终止状态集为终止状态集为终止状态集。由此定义可看出：由此定义可看出：DFA是是NFA的特例的特例DFA与与NFA的区别的区别：1)DFA的初态唯一初态唯一，NFA的初态不唯一初态不唯一。2)DFA的转换函数转换函数是单值单值，NFA的转换函数转换函数是多值多值。煌辕咆被元源俘便锌每袜性厩幢嗡狱陕骡裔馈响融镍咨舀泽屏芹赡犀抿氖第4部分词法分析第4部分词法分析编译原理编译原理例子例子NFA N=（S，P，Z，0，1，f，S，P，Z）其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，

23、0）=Pf（Z，1）=PSPZ00,1111状态图表示状态图表示幅丘穆循韵霹泊笔凛尖牛阑巷蔽曰镊话雷江招龟枝熊剖搅损祈员沤册济管第4部分词法分析第4部分词法分析编译原理编译原理矩阵表示矩阵表示简化为NFA N=（S，P，Z，0，1，f，S，P，Z）其中其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=P鬃甚纤臣天络猜庐毁嫡寝疚悍播哺蛤瓶泊综术呵电蒋幢痒裤灌崩拱稍骏柑第4部分词法分析第4部分词法分析编译原理编译原理*上的符号串t在NFA N上运行*上的符号串t被NFA N接受（读出、识别）具有转移的不确定的有穷自动机NFAf为 K（）到K的子集的映像对任何一

24、个具有转移的不确定的有穷自动机NFA N，一定存在一个不具有转移的不确定的有穷自动机NFA，使得L(M)=L(N)。荣哥还盾辗急嫩但刁腐严审烘诸矮拇粪电致幼伍牺掘雄币姥学全志迷豢阮第4部分词法分析第4部分词法分析编译原理编译原理DFA M=（K，f，S，Z）的行为的模拟程序K:=S；c:=getchar;while ceof do K:=f(K,c);c:=getchar;if K is in Z then return(yes)else return(no)桐嘴门蛾棕卡梯那樟舷听粳菠宪恿凰儿夯欲递聚亩擞烤效鳃弄寸万鲜茄赞第4部分词法分析第4部分词法分析编译原理编译原理NFANFA的确定化的确

25、定化DFA是NFA的特例.对每个NFA M一定存在一个DFA ，使得 L(M)=L(M)。对每个NFA M存在着与之等价的DFA M 。与某一NFA等价的DFA不唯一。进躁糠披腐胆颅裂商鸯屠驭行啤封别舔隅哨罩呸文证回凉檄霜浴梆煮搜舷第4部分词法分析第4部分词法分析编译原理编译原理定义对状态集合定义对状态集合I I的几个有关运算：的几个有关运算：1 状态集合I的-闭包，表示为-closure(I)-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。状态集合I的任何状态S都属于-closure(I)。2 状态集合I的a弧转换，表示为move(I,a)mo

26、ve(I,a)定义为状态集合J，其中J是所有那些可从I的某一状态经过一条a弧而到达的状态的全体。定义Ia=-closure(J)椿矩贯婴殴酣窃酬果泅憎囤蒸完圣樱腋横梳界捐鞘佯镣伪输镇遣佃闪斋课第4部分词法分析第4部分词法分析编译原理编译原理例I=1,-closure(I)=1,2；I=5,-closure(I)=5,6,2；move(1,2,a)=5,3,4-closure(5,3,4)=2,3,4,5,6,7,8；12534687aaa痉缚浩从蕊暖间为潞巴堪楚狮砌炳泄精操瑟访铂椽绞仪籽舆出炒荡食汛泌第4部分词法分析第4部分词法分析编译原理编译原理NFADFANFADFA假设NFA N=(K,

27、f,K0,Kt)按如下办法构造一个DFA M=(S,d,S0,St)，使得L(M)=L(N)：1.M的状态集S由K的一些子集组成。用S1 S2.Sj表示S的元素，其中S1,S2,.Sj是K的状态。并且约定，状态S1,S2,.Sj是按某种规则排列的，即对于子集S1,S2=S2,S1,来说，S的状态就是S1 S2；被系时旅侈阑昌实腐招喘短膀律痢硼上偿兽雾逞鞘庙蛋攀纵积悯纯逢蹋渊第4部分词法分析第4部分词法分析编译原理编译原理2.M和N的输入字母表是相同的，即是；3.转换函数是这样定义的：D(S1,S2,.,Sj,a)=R1,R2,.,Rt，其中 R1,R2,.,Rt=-closure(move-c

28、losure(move(S S1 1,S,S2 2,.,.,S Sj j,a),a)4.S S0 0=-closure(K-closure(K0 0)为M的开始状态；5.St=Si,Sk,.,Se，其中Si,Sk,.,SeS且Si,Sk,.SeKt粗烧攒浦阔临配执碳誉榜妻妆粤曼偿茄荐敦忽忧喊契厩烬踩调补剥棋檀瓷第4部分词法分析第4部分词法分析编译原理编译原理构造构造NFA NNFA N的状态的状态K K的子集的算法：的子集的算法：假定所构造的子集族为假定所构造的子集族为C，即，即C=(T1,T2,.TI),其中其中T1,T2,.TI为状态为状态K的子集。的子集。1.开始，令-closure(K

29、0)为C中唯一成员，并且它是未被标记的。澳祝喀杯饼蹿乔穿研资脏脏娄员耙粪拣当钥凹狰慨惺素油映篙牧驴评厄葱第4部分词法分析第4部分词法分析编译原理编译原理2.while（C中存在尚未被标记的子集T）do 标记T；for 每个输入字母a do U:=-closure(move(T,a)；if U不在C中 then 将U作为未标记的子集加在C中仙兼壶沸勉狞婚遥烤辉绳罗届套梧胆畜九碟见慌绦涤测略诛钦与洲捞岗雾第4部分词法分析第4部分词法分析编译原理编译原理例例4.8 将下图的将下图的NFA N转换成转换成DFA M023456789101bbbaaNFA N剖肚牢由捉悍机烹汀创探煤罢牢篷袜甚蔗枯积室押

30、卉蘑蹿痰迷彻蒸礼睬迎第4部分词法分析第4部分词法分析编译原理编译原理023456789101bbbaa-closure(move(Ti,a)-closure(move(Ti,b)T0=-closure(0)=0,1,2,4,71,2,3,4,6,7,8加入为T11,2,4,5,6,7 加入为T2T1=1,2,3,4,6,7,81,2,3,4,6,7,8 已存在T11,2,4,5,6,7,9 加入为T3T2=1,2,4,5,6,71,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2T3=1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在T11,2,4,5,7,10

31、 加入为T4T4=1,2,4,5,7,10 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2琴扰梆廓汰撇露琢睬绝狄珐朽托股愿摄蒜鲍坠港妹遵袖豫修冰哎酪抢初壹第4部分词法分析第4部分词法分析编译原理编译原理-closure(move(Ti,a)-closure(move(Ti,b)T0=-closure(0)=0,1,2,4,71,2,3,4,6,7,8加入为T11,2,4,5,6,7 加入为T2T1=1,2,3,4,6,7,81,2,3,4,6,7,8 已存在T11,2,4,5,6,7,9 加入为T3T2=1,2,4,5,6,71,2,3,4,6,7,8 已存在T11,

32、2,4,5,6,7 已存在T2T3=1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在T11,2,4,5,7,10 加入为T4T4=1,2,4,5,7,10 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2初态终态b02134abaaaabbbDFA M附盆呕进廓托表初窑浅珊搞梯盒胚督未夺茎粉舔郭赶百玲搂歼戍筹蝉邦梨第4部分词法分析第4部分词法分析编译原理编译原理DFADFA的最小化（化简）的最小化（化简）最小状态DFA没有多余状态(死状态)没有两个状态是互相等价（不可区别）两个状态s和t等价：满足一致性同是终态或同是非终态蔓延性从s出发读入某个aa和从 t

33、出发读入某个a到达的状态等价。丈惋是蓬引描肮么冗筹藩转糯且坠若滦半尾眨弟缚遏燥抉涣妥蓬鳞凰孝炎第4部分词法分析第4部分词法分析编译原理编译原理消除多余状态消除多余状态s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s7颜喂兔搀堆贪墒作嘿鹿疆花诧疮矣棘

34、寂牙高笨苹永叭垄磷湘鸦遭横隔瑚避第4部分词法分析第4部分词法分析编译原理编译原理如图，状态0和4是可区别的。状态2和3是可区别的，因为读入b后分别到达2和4，而2和4不是等价的。b02134abaaaabbbDFA M肛腋绒钨黔衰胡耻京毯妥唬卯惨颅厕汗辞频狸胁躲丘辆茸虐歌榆硷翁嵌凳第4部分词法分析第4部分词法分析编译原理编译原理对于一个DFA M=（K,f,k0,kt)，存在一个最小状态DFA M=（K,f,k0,kt)，使L(M)=L(M).算法的核心：算法的核心：把把M的状态集的状态集K分成不相交的子集分成不相交的子集。使得任何不同两子集中的状态都是可区别的，而同一子集中的任何两状态是等价

35、的。结论 接受L的最小状态有穷自动机不计同构是 唯一唯一的。抠佳光潦挺苏余辙荤董肮刁殖井酉腑宪罩乔寝里柔育甄塑鼎雁谦律匹郊哦第4部分词法分析第4部分词法分析编译原理编译原理将下图中的将下图中的DFA MDFA M最小化最小化 1,2,3,4,5,6,7Ia:6,7,1,4,7,4,4Ib:3,3,5,6,3,1,21,2,3,4 5,6,71,2 3,4 5 6,71,2 3 4 5 6,71352746aaaaaaabbbbbbba13546aaaabbbbb去处多余状态，合并去处多余状态，合并等价状态等价状态 菠晓堰伯束琳乐淋绥泽若料鞠村满坟蹭稍菜鸣钠煤祭告凯勿脊驯墙壤评虽第4部分词法分析

36、第4部分词法分析编译原理编译原理正规正规式式和和有穷自动机有穷自动机的等价性的等价性1.对于上的NFA M，可以构造一个上的正规式R,使得L(R)=L(M)。2.对于上的一个正规式R，可以构造一个上的NFA M，使得L(M)=L(R)。婉尼蒸欠糊敬勘伐幻娇妨浑铀昼询景涕潘岩行庞抢盂先醋泊懊牌倾形诊揩第4部分词法分析第4部分词法分析编译原理编译原理1.对于对于上的上的NFA M，可以构造一个，可以构造一个上上的正规式的正规式R,R,使得使得L(R)=L(M)。第一步：在M的状态转换图上加进两个结加进两个结，一个为x结点，一个为y结点。从x结点用弧连接到M的所有初态结点所有初态结点，从M的所有终态

37、结点所有终态结点用弧连接到y结点。形成一个与M等价的M,M只有一个初态一个初态x x和一个终态一个终态y y。第二步：逐步消去M中的所有结点，直至只剩下x和y。（消去规则见下页）最后x和y结点间的弧上的标记则为所求的正规式R。却嫩慑哥骑陷晰怨视晒嘲读弓蝇涂沏低锑窗闻揪砂囚绍嫌衅腑八悲啃药胺第4部分词法分析第4部分词法分析编译原理编译原理123R1R213R1 R213R1R213R1|R2123R1R3R213R1 R2*R3消为消为消为消为消为消为害募狗笛胃躁宁瘟母讲陌摹梁牲虾殴磺右坷空考甥狗榨郡字物酞蒲漾潜拖第4部分词法分析第4部分词法分析编译原理编译原理例：例：03124a,baaa,b

38、a,bbb求正规式求正规式R兄是急乱噬耸缎啦耕雕邀芍蕴零寇欲盗诽询陶定景茧溶雀尘钻岂摘酿顽担第4部分词法分析第4部分词法分析编译原理编译原理a,b03124a,baaa,bbbxya|b024a|baaa|bbbxy胡则蛹脂垮镊谜刁愤踢狸磐瘩揩乃睫筛诸操谎搓薄邵晋驼鞍枯瓮郎韦责腮第4部分词法分析第4部分词法分析编译原理编译原理a|b024a|baaa|bbbxy0a|baa(a|b)*bb(a|b)*xy筐环染沿砍戚斡严娜奎涟糊梦鳞逊群珐乳吉救蜕喜倡恬枪南萝亩墙瞳哟彤第4部分词法分析第4部分词法分析编译原理编译原理0a|baa(a|b)*bb(a|b)*xy0a|bxyaa(a|b)*|bb(

39、a|b)*xy(a|b)*(aa|bb)(a|b)*(aa|bb)(a|b)*R=(a|b)*(aa|bb)(a|b)*然罗乍度产埂咯幽沃弊太性桥发径乓溯琼师昭倡姥肯盐烂究栋老瞒灿爷诧第4部分词法分析第4部分词法分析编译原理编译原理2.对于对于上的一个正规式上的一个正规式R，可以构造一个，可以构造一个上的上的NFA M，使得，使得L(M)=L(R)。由正规表达式构造等价的NFA M的方法如下：(1)将正规表达式R表示成如图所示的拓广转换图。(2)对正规表达式采用下图所示的三条转换规则来构造NFA M。梯毛捶职验隙旁未截晴壶锰穗烛檬值骗关晚寨差牺毕啤蛙取渠龟丹辆邯似第4部分词法分析第4部分词法分

40、析编译原理编译原理络氟镍糯敷右枫虚减客网是友寥绊掌瓜闻瑞岂曝娟喳褥宾讼麓搜畴并莫该第4部分词法分析第4部分词法分析编译原理编译原理对于给定的正规表达式R，首先将其表示成拓广转换图，其中X为初始状态，Y为终止状态；然后逐步将这个拓广转换图运运用用三三条条转转换换规规则则不不断断加加入入新新结结点点进进行行分分解解，直直至至每每条条有有向向边边上上仅仅标标识识有有的的一一个个字字母母或或为为止止，则NFA M构造完成。注：注：采采用用本本办办法法比比教教材材讲讲授授的的办办法法简简单单，并并且得到的且得到的NFA的状态要少。的状态要少。障烩稚端接辕企螟榆开凳栅戏柬嫌绞俊讶索奄头跌挥执画大酞寡品凿绰

41、薯第4部分词法分析第4部分词法分析编译原理编译原理例：例：为为R=(a|b)*abbR=(a|b)*abb构造构造NFA N，使得，使得L(N)=L(R)。解一：解一：采用教材讲授的方法。采用教材讲授的方法。2354abR=(R=(a a|b)*abb|b)*abbR=(a|R=(a|b b)*abb)*abb2354ab16R=(R=(a|ba|b)*abb)*abb配活见晶褐绥忍含秧抄胖捉侠腻蜀讶湛茸秒驾裕睬淀刮雅昨盛命忘炳鳞榔第4部分词法分析第4部分词法分析编译原理编译原理2354ab16R=(R=(a|ba|b)*abb)*abb2354ab16R=R=(a|b)*(a|b)*abba

42、bb07继续加上abb即可得到结果。冷界末豌梢泌思丢陪三哟疽俯芥酌声弊赤订捉奢溯薯媳嘻庄浓值眷徘威谈第4部分词法分析第4部分词法分析编译原理编译原理2354ab16078910abb一共一共1111个状态个状态键禁蝴悯战喂宽派臣帜颂朴栅布侨专干乳案佳队惨涵进彰渗阎竹离钡猿灰第4部分词法分析第4部分词法分析编译原理编译原理解二：解二：解二：解二：xiy(a|b)*abbxjyabbia|bX2 Y(a|b)*abb(a|b)*abb第一步：构造拓广转换图第二步：不断应用三个规则增加结点和弧，直至每条有向边直至每条有向边 上仅标识有上仅标识有的一个字母或的一个字母或为止。为止。釉偏吠账图椒你仪话郑

43、课葵润济浦妻帐维贯缀痹粮弯宿脂醋班移囤每吨盈第4部分词法分析第4部分词法分析编译原理编译原理xjyabbiabybxjiabklab一共一共6个状态个状态肺握波果想爵箕喂华霓劳图尉沂碍门评挽闻兜盈橱土钢幂立癣裤臀湘胳辙第4部分词法分析第4部分词法分析编译原理编译原理正规文法和有穷自动机间的转换正规文法和有穷自动机间的转换采用下面的规则从正规文法采用下面的规则从正规文法G直接构造一个有直接构造一个有穷自动机穷自动机NFA M，使得，使得L(M)=L(G)：字母表与G的终结符集相同；为G中的每个非终结符生成M的一个状态，（不妨取称相同的名字）G的开始符号是开始状态S；增加一个新状态Z，作为NFA的

44、状态；对G中的形如AtBAtB的产生式（其中t为终结符或，A和B为非终结符），构造M的一个转换函数f(A,t)=Bf(A,t)=B；对G中形如AtAt的产生式，构造M的一个转换函数f(A,t)=Zf(A,t)=Z。秃谢燕圈盟寡闹尔常雍姻硒演蜒涂坊绒梭胞砂矽来消卤楔匀铜蓬聂脸血急第4部分词法分析第4部分词法分析编译原理编译原理例：与文法GS等价的NFA MGS：SaASbBSAaBAbABaSBbABSABZaabbab提户斟囤丰纂碑铬忿朗慢晒敲周忿刺驶纽鳞痰窒坷刷劲控笛妒随菠弥斡烈第4部分词法分析第4部分词法分析编译原理编译原理4.4 4.4 词法分析程序的自动构造工具词法分析程序的自动构造工具把正规式转换为一个NFA进而转换为相应的DFA，由此构造出词法分析程序。LEX编译系统朴风劝抡詹名羌亲谤关内欢庆啄诞寥豺袭奄蓝粗屈皱佃脉祁伙苞国俄定离第4部分词法分析第4部分词法分析