第4讲-词法分析-III.ppt

《第4讲-词法分析-III.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理和技术本讲纲要DFA构建途径1：自然语言描述=>DFA途径2：正规式=>DFA途径3：正规式=>NFA=>DFA途径1:自然语言描述=>DFA构建识别能被5整除的二进制数的DFA练习题：构建识别下列描述DFA偶数个0，偶数个1的01串C语言的注释/*…*/作为课后思考题，课后可以把解题过程以及答案发到我的邮箱，会作为最终平时成绩的一个参考，本周5习题课时对这两个问题进行讨论本讲纲要DFA构建途径1：自然语言描述=>DFA途径2：正规式=>DFA途径3：正规式=>NFA=>DFA途径2:正则表达

2、式=>DFA顾名思义，就是从词法模式的正规式表示，直接得到能够识别相应模式的DFA示例1:关系运算符的识别正则式relop<

3、<=

4、=

5、<>

6、>

7、>=0开始1<2=return(relop,LE)3>return(relop,NE)4otherreturn(relop,LT)=5return(relop,LT)=7return(relop,GE)6>8otherreturn(relop,GT)示例2：Pascal标识符的识别正规式idletter(letter

8、digit)*9开始1011lett

9、erLetter或digitother2.2词法记号的描述与识别无符号数的转换图开始1912131415161718digitdigitdigitdigitdigitdigitother.E+/Edigitotherotherreturn(install_num())*numdigit+(.digit+)?(E(+

10、)?digit+)?2.2词法记号的描述与识别空白的转换图delimblank

11、tab

12、newlinewsdelim+2122开始delimother*delim20本讲纲要DF

13、A构建途径1：自然语言描述=>DFA途径2：正规式=>DFA途径3：正规式=>NFA=>DFA途径3：正规式=>NFA=>DFA先构造NFA，再将NFA转换为DFA三大步骤：1.NFA构建2.NFA->DFA的转化3.DFA化简正规式=>DFA?从正规式(a

14、b)*ab的自动机构造讲起状态0，1，2的含义并不太容易说明白12开始a0abbab从正规式到NFA按照正规式的构建规则，逐步从简单到复杂地讨论从正规式构建NFA的过程2.4从正规式到有限自动机首先构造识别和字母表中一个符号的NFAi开始识别

15、正规式的NFAafif开始识别正规式a的NFA2.4从正规式到有限自动机构造识别主算符为选择的正规式的NFAfi开始识别正规式s

16、t的NFAN(s)N(t)2.4从正规式到有限自动机构造识别主算符为连接的正规式的NFAiN(s)f开始识别正规式st的NFAN(t)2.4从正规式到有限自动机构造识别主算符为闭包的正规式的NFAN(s)f开始识别正规式s*的NFAi2.4从正规式到有限自动机对于加括号的正规式(s)，使用N(s)本身作为它的NFA。NFA构建实例下面来看一看正规式(a

17、b

18、)*ab的分解动作2.4从正规式到有限自动机19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a

19、bab(a

20、b)*ab的分解2.4从正规式到有限自动机19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a

21、bab(a

22、b)*ab的分解2.4从正规式到有限自动机19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a

23、bab(a

24、b)*ab的分解2.4从正规式到有限自动机19开始0ab

25、ab6782345r9r7r8r4r3r5r6*)(r2r1a

26、bab(a

27、b)*ab的分解2.4从正规式到有限自动机19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a

28、bab(a

29、b)*ab的分解2.4从正规式到有限自动机19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a

30、bab(a

31、b)*ab的分解2.4从正规式到有限自动机19开始0abab6782345r9r7r8r4r3r5r6*)

32、(r2r1a

33、bab(a

34、b)*ab的分解练习题为下列正规式构建NFA0(0

35、1)*0(0

36、1)*0(0

37、1)