编译原理陈意云词法分析PPT学习教案

1、会计学1编译原理陈意云词法分析编译原理陈意云词法分析第1页/共72页法单元法单元n标准标识符也是预先确定了含义的标准标识符也是预先确定了含义的标识符，但程序可以重新声明它的标识符，但程序可以重新声明它的含义含义第2页/共72页第3页/共72页正确的记号正确的记号n错误修补错误修补进行增、删、替换和交换字符的尝进行增、删、替换和交换字符的尝试试第4页/共72页ns ，sss第5页/共72页, , , , , , , 1, , 9 L D, LD, L6, L*, L(L D )*, D+第6页/共72页规式规式(a) (b)*)| (c)可以写成可以写成ab*| c第7页/共72页( 00 |

2、11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：句子：01001101000010000010111001第8页/共72页第9页/共72页第10页/共72页第11页/共72页第12页/共72页 051624837return(relop, LE)return(relop, NE)return(relop, LT)return(relop, GE)return(relop, GT)return(relop, EQ)开始开始=*otherother第13页/共72页91011开始开始letterother*letter或或digitreturn(instal

3、lId( )第14页/共72页开始开始1912131415161718digitdigitdigitdigitdigitdigitother.E+/ Edigitotherotherreturn( installNum( ) )*第15页/共72页2122开始开始delimother*delim20第16页/共72页识别语言识别语言(a|b)*ab 的的NFA12开始开始a0abb第17页/共72页状状 态态 NFA的转换表的转换表识别语言识别语言(a|b)*ab 的的NFA12开始开始a0abb第18页/共72页12开始开始a0abb34 第19页/共72页1、状态集合、状态集合S2、输入字

4、母集合、输入字母集合 3、转换函数、转换函数move : S S，且可以是部分函数且可以是部分函数4、唯一的开始状态、唯一的开始状态 s05、接受状态接受状态集合集合F S12开始开始a0abbab识别语言识别语言(a|b)*ab 的的DFA第20页/共72页5个状态即可，分别代表已读部分的值个状态即可，分别代表已读部分的值除以除以5的余数的余数第21页/共72页0123开始开始4100101010110102 = 10101112 = 710第22页/共72页0000 3 211奇奇0奇奇1奇奇0偶偶1 1011开始开始偶偶0偶偶1偶偶0奇奇1第23页/共72页 12a开始开始 0abb00

5、, 1aba0, 2b未画完未画完第24页/共72页19开始开始 0ab ab6782345 第25页/共72页19开始开始 0ab ab6782345 状态状态 第26页/共72页19开始开始 0ab ab6782345 状态状态 A = 0, 1, 2, 4, 7 第27页/共72页19开始开始 0ab ab6782345 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 第28页/共72页19开始开始 0ab ab6782345 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 第29页/共72页19

6、开始开始 0ab ab6782345 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 第30页/共72页19开始开始 0ab ab6782345 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 第31页/共72页19开始开始 0ab ab6782345 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 第32页/共72页19开始开始 0

7、ab ab6782345 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 第33页/共72页19开始开始 0ab ab6782345 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 第34页/共72页19开始开始 0ab ab6782345 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7

8、, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 第35页/共72页19开始开始 0ab ab6782345 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 第36页/共72页19开始开始 0ab ab6782345 状态状态 BD开始开始aAabbabCba第37页/共72页19开始开始 0ab ab6782345 BD开始开始aAabbabCba12开始开始a0abbab识别语言识别语言(a|b)*ab 的的

9、自动机自动机第38页/共72页19开始开始 0ab ab6782345 BD开始开始aAabbabCba12开始开始a0abbab识别语言识别语言(a|b)*ab 的的自动机自动机子集构造法不一子集构造法不一定得到最简定得到最简DFA第39页/共72页BD开始开始aAabbaa, bCbaEbBD开始开始aAabbabCba第40页/共72页BD开始开始aAabbabCba第41页/共72页BD开始开始aAabbabCba12开始开始a0abbab第42页/共72页第43页/共72页i开始开始 识别正规式识别正规式 的的NFAafif开始开始识别正规式识别正规式a的的NFA第44页/共72页

10、fi开始开始识别正规式识别正规式s | t 的的NFAN (s)N (t) 第45页/共72页iN (s)f开始开始识别正规式识别正规式 st 的的NFAN (t)第46页/共72页N (s)f开始开始识别正规式识别正规式 s* 的的NFAi 第47页/共72页第48页/共72页19开始开始 0ab ab6782345 第49页/共72页19开始开始 0ab ab6782345 第50页/共72页19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解第51页/共72页19开始开始 0 ab678ab2345 r9r7r8r4r

11、3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解第52页/共72页 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解第53页/共72页19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解第54页/共72页19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解第55页/共72页19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解第56页/共72页19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解第57页/共72页 (a|b)*ab的两个的两个NFA的比较的比较 12开始开始a 0abb手工构造手工构造:算法构造算法构造:19开始开始 0ab ab6782345 第58页/共72页第59页/共72页Lex编译器编译器Lex源程序源程序lex.llex.yy.cC编译器编译器lex.yy.ca.outa.out输入流输入流记号序列记号序列第60页/共72页第61页/共72页第62页/共72页第63页/共72页