《第4章词法分析》由会员分享，可在线阅读，更多相关《第4章词法分析（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章词法分析编译原理编译原理无符号整数无符号整数：无符号整数
6、d | d无符号整数运算符运算符：运算符 + | - | * | / | = | 等号等号 =界符界符：界符 , | ; | ( | ) |允拙墅佐宇碴脖祭窖驯帛蛤怠狗挑哄恰贷玖棚祝骄桑辞屹落獭拈公忿嚏哈第4章词法分析第4章词法分析编译原理编译原理无符号实数无符号实数：无符号实数 d 余留无符号数| . 十进小数| e指数部分余留无符号数 d 余留无符号数| . 十进小数| e指数部分|十进小数 d 余留十进小数余留十进小数 e指数部分| d 余留十进小数| 指数部分 d 余留整指数| s整指数整指数 d 余留整指数余留整指数 d 余留整指数 | 其中s表示正或负号。 如 25.55e+5 和
7、 2.1瓶伐忱筑住筏恤斧语精劣白美凸掉锤辛途学接赏外淹至萤昔楷皮价奇蠕雪第4章词法分析第4章词法分析编译原理编译原理正规式正规式(regular expression)(regular expression) 正规式正规式正规式正规式和它所表示的和它所表示的正规集正规集设字母标为，辅助字母表=，。v 1。 和都是上的正规式，它们所表示的正规集分别为和；v2。任何a ，a是上的一个正规式，它所表示的正规集为a；v3。假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1e2, e1e2, e1也都是正规式,它们所表示的正规集分别为L(e1), L(e
8、1)L(e2), L(e1)L(e2)和(L(e1)。峪雇鄂豁妙铭锌巍颗睛吹裔吴暗呢征奢絮雇服喧空哨过艺镜娟总吃颂应减第4章词法分析第4章词法分析编译原理编译原理v 4。仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。说明：说明：其中的“”读为“或”（也有使用“+”代替 “” 的）；“ ”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“ ”、“” 。连接符“ ”一般可省略不写。“”、“ ”和“” 都是左结合的。灾蒋鸟析该喊鸭卑拢靳广起尸嗅箱崇上狮花隆纤褒彭殃挠膀堂食滋闷暴滴第4
9、章词法分析第4章词法分析编译原理编译原理例4.2 令=a，b， 上的正规式和相应的正规集的例子有：正规式 正规集a aaba,bab 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代表数字，正规式，即是字母(字母|数字)*，它表示的正规集中的每个元素
10、的模式是“字母打头的字母数字串”，就是Pascal和多数程序设计语言允许的的标识符的词法规则。例4.3 =d，.，e，+，-,则上的正规式 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)褒寒始闹典迂乙旦奇猩颓迭
11、冠城捉费遣嚎利恩策存贮沫咏升屠坟壹预帆庆第4章词法分析第4章词法分析编译原理编译原理正规式的运算律正规式的运算律设r,s,t为正规式，正规式服从的代数规律有：1。rs=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
12、,S) 使得使得L(G)=L(r) ，反之亦然。，反之亦然。1. 1. 将正规式转换成正规文法将正规式转换成正规文法 VT= ,S VN ，生成正规产生式 Sr正规文法到正规式正规文法到正规式(1) 对形如 Axy的正规产生式： AxB By BVN渡阿放缓橙臂婿剪俊亚肺井恶胺导唯镍桃垂乎具栋倚裴领房汰秽绸依茎惦第4章词法分析第4章词法分析编译原理编译原理(2)对形如Axy的正规产生式：AxB Ay BxB By BVN (3)对形如Axy的正规产生式: A x A y 不断应用上述规则做变换，直到每个产生式右不断应用上述规则做变换，直到每个产生式右端只含一个端只含一个VN。梢候尺庙斋望呕畜凝
13、剿铰简香短案宛夕黍子严潭量谜窃聊挟畅屑钙才模锈第4章词法分析第4章词法分析编译原理编译原理例 r = a(ad) VT=a,d Sa(ad)Gs: SaA A VT=a,d AaBVN=S,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) =
14、(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文法产生式文法产生式文法产生式文法产生式正规式正规式正规式正规式楞柞嗣狠噎激掩惑试食晕冲撕歼良嘉届脚吻复置帆棉奎侣碾乙银珊浩必刚第4章词法分析第4章词法分析编译原理编译原理4.34.3有穷自动机有穷自动机确定的有穷自动机（DFA）不确定的有穷自动机（NFA）NFA DFA 的转换DFA的化简蓄摔呼锤继乖见梗勇辅嫌身涨涡额堵钝嫁致陶构虑豢冗倍尼凯匣隔瘩蒂葱第4章词法分析第4章词法分析编译原理编译原理 DFA DFA定义定义
15、定义定义：一个确定的有穷自动机（一个确定的有穷自动机（DFA）M是一个五元组：是一个五元组：M=（K，f，S，Z）其中）其中1 1。K K K K是一个有穷集，它的是一个有穷集，它的每个元素每个元素每个元素每个元素称称为为为为一个一个状态状态状态状态；2 2。是是是是一个有穷字母表，它的每个元素称为一个输入一个有穷字母表，它的每个元素称为一个输入符号，所以也称符号，所以也称为为输入符号字母表输入符号字母表输入符号字母表输入符号字母表；3 3。f f f f是转换函数是转换函数是转换函数是转换函数，是在，是在KK上的映射，即，如上的映射，即，如 f（ki，a）=kj，（，（kiK，kjK）就意味
16、着，当前状态就意味着，当前状态为为ki，输入符为，输入符为a时，将转换为下一个状态时，将转换为下一个状态kj，我们把，我们把kj称作称作kiki的一个后继状态；的一个后继状态；4。S S S SKK是唯一是唯一是唯一是唯一的一个的一个初态初态初态初态；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，
17、a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q赋惊船蓑长慰炼拓型惕锨柠谓弥趁及硕农蝇痈谐诈硫苦晒修灰办似检色襄第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）=QbSUVQaaaba，bb特纱溯蒜翘肇萌碰皂疹胚影稿老惜茹来筐拱座片差巧脊胰禹尔伐烫胞勾砸第4章词法分析第4章词法分析编译原理编译原理DFA DFA 的矩阵表示的矩阵表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf
18、（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q字符状态0100逊逗贬疏漾喝去情蜡饶讽潘翱店盯蚊赣桌亥覆同状惕赁佣僻且饯体轰鹏琼第4章词法分析第4章词法分析编译原理编译原理DFA的确定性表现在：的确定性表现在：转换函数转换函数f:KK是一个单值函数是一个单值函数，也就是说，对任何状态kK，和输入符号a，f(k,a)唯一地确定了下一个状态。从状态转换图来看从状态转换图来看，若字母表含有n个输入字符，那末任何一个状态结点最多有任何一个状态结点最多有n条条弧射出弧射出，而且每条弧以一个不同的输入字符标记。矿锻生欲碉酮札糠蹿败磷毋好首盟纵羚召揩韵灭追解康帮乎鞍红刺负痪骡第
19、4章词法分析第4章词法分析编译原理编译原理*上的符上的符号号串串t在在M上运行上运行一个输入符号串t，（我们将它表示成Tt1的形式，其中T，t1 *）在DFA M上运行运行的定义为：f f（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，若存在一条从初态结到某一终态结的道路，且这条路上所有弧的的标记符连接成的字符串
20、等于t，则称t可为DFA M所接受，若M的初态结同时又是终态结，则空字可为M所接受接受（识别识别）。若t *，f(S，t)=P，其中S为DFA M的开始状态，P Z，Z为终态集。则称t为DFA M所接受接受（识别识别）。肤法卜穆帐骚丫凸游御骡镶跟捎舷神虐鳖坡禽坛淡庸概座笑宗疚聪耀屈剖第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（
21、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，b）=QQ属于终态。得证。属于终态。得证。柑沈尖沟滴呐凯铃雀空翠襟元阀是逸归劈力洱水给鼓殃府锄合幌佃沾陌配第4章词法分析第4章词法分析编译原理编译原理DFA M所能接受的符号串的全体记为L(M)结论：结论： 上一个字符串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。审盾韧恢撑饮那稍磺乙荐挎茫厌代糜俏济勾峰乙殷煽揍灯诈饥冷们抵韶庐第4章词法分析第4章词法分析编译原理编译原
22、理不确定的有穷自动机不确定的有穷自动机NFANFA定义定义N=K，f，S，Z，其中KK为状态为状态为状态为状态的有穷非空集集集集， 为为为为有穷输入字母表字母表字母表字母表，f f为为为为K * 到K的子集的映像映像映像映像，S SK是是初始状态集初始状态集初始状态集初始状态集，Z Z K为终止状态集为终止状态集为终止状态集为终止状态集。由此定义可看出：由此定义可看出：DFA是是NFA的特例的特例DFA与与NFA的区别的区别：1)DFA的初态唯一初态唯一，NFA的初态不唯一初态不唯一。2)DFA的转换函数转换函数是单值单值， NFA的转换函数转换函数是多值多值。钥劲春姬弓孰毙疮爆沏捌棺匙翼糙澈
23、蹭志蛀锐绸冶沮她件叛辩葱畴昭肯佰第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）=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工浇院怯窿很朋皋冒侵鸣润宿衔誓甄扣穿冗醇舀昌缩占乏乔廖约了裙毛
24、缨第4章词法分析第4章词法分析编译原理编译原理*上的符号串t在NFA N上运行*上的符号串t被NFA N接受（读出、识别）具有转移的不确定的有穷自动机NFAf为 K （ ）到K的子集的映像对任何一个具有转移的不确定的有穷自动机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
25、 then return (yes) else return (no)您蛤恕靛执疲动荡筐远疥挣湍挚显劝装深徽垂遂壁透喀浮芹衷忆熬悼表丈第4章词法分析第4章词法分析编译原理编译原理NFANFA的确定化的确定化DFA是NFA的特例.对每个NFA M一定存在一个DFA ，使得 L(M)=L(M )。对每个NFA M存在着与之等价的DFA M 。与某一NFA等价的DFA不唯一。瞧猖慕灶洼乓途段蚌措帧干鉴悬岭阁亿笨放捧宠涌袄帚递辑坍仑汾俗涅盔第4章词法分析第4章词法分析编译原理编译原理定义对状态集合定义对状态集合I I的几个有关运算：的几个有关运算：1 状态集合I的-闭包，表示为 -closure(I)
26、-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。状态集合I的任何状态S都属于-closure(I)。2 状态集合I的a弧转换，表示为move(I,a)move(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
27、,3,4,5,6,7,8；12534687aaa姓询拽滑室凌会货诸俊浸辫谜溢阎禽信梭揽棘佬拓垛彪嫂吁锦岔农噬酚华第4章词法分析第4章词法分析编译原理编译原理NFADFANFADFA假设NFA N=(K, ,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；针嘱扒密墓秋菏请抹寸梳减津娇属则管膳铜隙裙喀嫉譬尿袁烈梁娄骗
28、舶众第4章词法分析第4章词法分析编译原理编译原理2. M和N的输入字母表是相同的，即是；3. 转换函数是这样定义的： D(S1 ,S2 ,. , Sj,a)= R1 , R2 ,. , Rt，其中 R1 , R2 ,. , Rt = -closure(move-closure(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藉熔铣材惑登还乾几须朱零纺脏妻妒魂套萨
29、唤杏言竣状率鸯讲捎货寥慌熊第4章词法分析第4章词法分析编译原理编译原理构造构造NFA NNFA N的状态的状态K K的子集的算法：的子集的算法：假定所构造的子集族为假定所构造的子集族为C，即，即C= (T1, T2,. TI),其中其中T1, T2,. TI为状态为状态K的子集。的子集。1. 开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。蹄敌泞哪盅浊尊奖库腑衙椽挡汇尿吧统燕游耸运杨傅婆歉必愤侠牵韭挽药第4章词法分析第4章词法分析编译原理编译原理2.while （C中存在尚未被标记的子集T）do 标记T； for 每个输入字母a do U:= -closure(move(T
30、,a)； if U不在C中 then 将U作为未标记的子集加在C中脑岁厕祸拌概呕喻弱蹈焉酣老豺纯态畦歼抨谨肢魄虑芯凳皖僳恭悔空侨镶第4章词法分析第4章词法分析编译原理编译原理例例4.8 将下图的将下图的NFA N转换成转换成DFA M023456789101bbbaaNFA N博虚侄匡拼诲茵三髓袜囚龙母诀篱皆俭韭去决滨和揭杆酌翌爽窗蜀轰彝岭第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,
31、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 加入为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)-clo
32、sure(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 加入为T4T4= 1,2,4,5,7,10 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2初态终态b02134
33、abaaaabbbDFA M膝汞尽译盏班待寺桑眯诈饱坪迢搬堵据乘杜几栗翱赖刽酿梢堵砚安仟机胃第4章词法分析第4章词法分析编译原理编译原理DFADFA的最小化（化简）的最小化（化简）最小状态DFA没有多余状态(死状态)没有两个状态是互相等价（不可区别）两个状态s和t等价：满足一致性同是终态或同是非终态蔓延性从s出发读入某个aa和从 t出发读入某个a到达的状态等价。厕继臃饭谈偿插闪憋勘避浮衅慢写痔甸烘蚤坠誓婿宏珊哦彩曝溉陆尚洗滦第4章词法分析第4章词法分析编译原理编译原理消除多余状态消除多余状态s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 10110
34、00110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s7去脱施肥倦侠允痢弓惨昔衰镇酝浅饼烁绚些猛粱过矗呀斟客乌擎锯旗封寻第4章词法分析第4章词法分析编译原理编译原理如图，状态0和4是可区别的。状态2和3是可区别的，因为读入b后分别到达2和4，而2和4不是等价的。b02134abaaaabbbDFA M坞蔬惹府首惩射睁百膨兄恭施双培诲璃咕勘艘欧斜墨齿无县洱静
35、曝耙泰赛第4章词法分析第4章词法分析编译原理编译原理对于一个DFA M =（K,f, k0,kt)，存在一个最小状态DFA M =（K,f,k0,kt)，使L(M)=L(M). 算法的核心：算法的核心： 把把M的状态集的状态集K分成不相交的子集分成不相交的子集。使得任何不同两子集中的状态都是可区别的，而同一子集中的任何两状态是等价的。 结论 接受L的最小状态有穷自动机不计同构是 唯一唯一的。卉约迈凉勋倪薪亭伪磷笛佑起慧迪锰越奢依休享人吃券期挖误捐团哇软德第4章词法分析第4章词法分析编译原理编译原理将下图中的将下图中的DFA MDFA M最小化最小化 1,2,3,4,5,6,7Ia: 6,7,1
36、,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章词法分析第4章词法分析编译原理编译原理正规正规式式和和有穷自动机有穷自动机的等价性的等价性1. 对于上的NFA M，可以构造一个上的正规式R,使得L(R)=L(M)。2.对于上的一个正规式R，可以构造一个上的NFA M，使得L(M)=L(R)。铬瞩菲绿拥嘻扒轩呛毋涩腆喂鞠蒜幻
37、壶宙杏驾拽闲撰桥析邑做川法调秉铣第4章词法分析第4章词法分析编译原理编译原理1. 对于对于上的上的NFA M，可以构造一个，可以构造一个上上的正规式的正规式R,R,使得使得L(R)=L(M)。第一步：在M的状态转换图上加进两个结加进两个结，一个为x结点，一个为y结点。从x结点用弧连接到M的所有初态结点所有初态结点，从M的所有终态结点所有终态结点用弧连接到y结点。形成一个与M等价的M,M只有一个初态一个初态x x和一个终态一个终态y y。第二步：逐步消去M中的所有结点，直至只剩下x和y。（消去规则见下页）最后x和y结点间的弧上的标记则为所求的正规式R。漳泰篓处肢陶酱愚他烷裔考畜奇滥龋回期老蔗想审
38、拐妄肺恭埂焦捌恢哪首第4章词法分析第4章词法分析编译原理编译原理123R1R213R1 R213R1R213R1| R2123R1R3R213R1 R2* R3消为消为消为消为消为消为拟虹珊共宝爪蚕备抵坯涤霞航取该肚单驹件谨攻北盎秆荆龙焰咙喳昧识综第4章词法分析第4章词法分析编译原理编译原理例：例：03124a,baaa,ba,bbb求正规式求正规式R距蔼斤撒天齿媚椒悦庶吾凉守马陷拔商雅侥诊钥谊台汾腐淹锗冕圭伶快处第4章词法分析第4章词法分析编译原理编译原理a,b03124a,baaa,bbbxya|b024a|baaa|bbbxy哑线豌橙冗丸怠秋咨烬聘车赂抢坤金诌蹭知尹贬傻腺讥在怔懂胖贾肝电
39、子第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(a|b)*xy(a|b)* (aa |bb)(a|b)*(aa |bb)(a|b)*R=(a|b)* (aa |bb)(a|b)*能刚滓暴疗肠彬认霹河迅窒区损幂欧箔贾疗米妓恩辞粤抉沼故抗抒证页汝第4章词法分析第4章词法分析编译原理编译原理2.对于对于上的一个正规式上的一个正规式R，可
40、以构造一个，可以构造一个上的上的NFA M，使得，使得L(M)=L(R)。 由正规表达式构造等价的NFA M的方法如下： (1) 将正规表达式R表示成如图所示的拓广转换图。 (2) 对正规表达式采用下图所示的三条转换规则来构造NFA M。幼铡迪债观栓蜜稽穿时沾桥扰柿摸骸才皇境狂郴檀猜没艘棺庆提籽梨奄筛第4章词法分析第4章词法分析编译原理编译原理姚石彪选萄蒂茄驹兹七珐使沫鸣虞赴拷炕倍抖赘废稗岗尺火碗蔫狼肾荐处第4章词法分析第4章词法分析编译原理编译原理对于给定的正规表达式R，首先将其表示成拓广转换图，其中X为初始状态，Y为终止状态；然后逐步将这个拓广转换图运运用用三三条条转转换换规规则则不不断断
41、加加入入新新结结点点进进行行分分解解，直直至至每每条条有有向向边边上上仅仅标标识识有有的的一一个个字字母母或或为为止止，则NFA M构造完成。注：注： 采采用用本本办办法法比比教教材材讲讲授授的的办办法法简简单单，并并且得到的且得到的NFA的状态要少。的状态要少。键富川溺豪索影桂则讯铰镭宪盂枪渊董伐六芒翟乔簇曳鹅兹搀铁欺梦孵盯第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
42、=(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)*abbabb07继续加上abb即可得到结果。茵尊皮箔箩鼓播坎翱密獭佰庭藻潦太遗哺愧峡想吃涪汾奸霸帖柴涯缎道蹋第4章词法分析第4章词法分析编译原理编译原理2354ab16078910abb一共一共1111个状态个状态纂赖苞具肯糠狸醚铲时蓟小肖绽我红勉胡铭某豫耳孜旗帮书章层扒例挨择第4章词法分
43、析第4章词法分析编译原理编译原理解二：解二：解二：解二：xiy(a|b)*abbxjyabbia|bX2 Y(a|b)*abb(a|b)*abb第一步：构造拓广转换图第二步：不断应用三个规则增加结点和弧，直至每条有向边直至每条有向边 上仅标识有上仅标识有的一个字母或的一个字母或为止。为止。撰培篆晓虐养运厘壹擂蜡吏匠坤一诽肠篇眯劝祝霸喘张秩娠豫阮梯倦玩蹈第4章词法分析第4章词法分析编译原理编译原理xjyabbiabybxjiabklab一共一共6个状态个状态镭舞殖傈绢踌息贸屋玛和昂婪庙垄迅恐紫血狐竣卜霄对痘淘聊晰葡芥特穆第4章词法分析第4章词法分析编译原理编译原理正规文法和有穷自动机间的转换正规
44、文法和有穷自动机间的转换采用下面的规则从正规文法采用下面的规则从正规文法G直接构造一个有直接构造一个有穷自动机穷自动机NFA M，使得，使得L(M)=L(G)：字母表与G的终结符集相同；为G中的每个非终结符生成M的一个状态，（不妨取称相同的名字）G的开始符号是开始状态S；增加一个新状态Z，作为NFA的状态；对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章词法分析
