文档介绍：第一章****题一 1. 解释名词:源语言、目标语言、翻译器、编译器和解释器。答: 源语言:被翻译器翻译的语言,用于书写源程序的语言。目标语言:被翻译器翻译之后得到的语言,用于书写目标程序的语言。翻译器:能够完成从一种语言到另一种语言的变换的软件。编译器:一种特殊的翻译器,要求目标语言比源语言低级。解释器: 解释器是不同于编译器的另一种语言处理器。解释器不像编译器那样通过翻译来生成目标程序,而是直接执行源程序所指定的运算。第二章词法分析作业: 假设∑={0,1} ,求 1. 写出包含 010 的所有串的正规式 2. 写出不包含 010 的所有串的正规式答: 1.( 0|1 ) *( 010 )( 0|1 ) * 2.( 10 *1) *|(( 11|00 ) * |0111 *0) *. 2.( 0|1 ) * 010 ( 0|1 ) *解:(1) RE 的分解树如下: r 17r 16 r 11*r 15 r 14 ()| r 12 r 13 01 r 100 r9r81 r7r60 r5*r4r3 ()| r1 r201(2 )由分解树及基本的 Thompson 构造算法逐步构造等价的 NFA 过程如下: 2 3 0 Start r1:4 5 1 Start r2:1 24 35 01???? r3、 r4: 6 Start 01 24 35? 01?? 6????? r5: 7 Start 7’8 0 Start r6:01 24 35? 01?? 6?? 7??? 0 r7: 8 Start 8’9 1 Start r8:01 24 35? 01?? 6?? 7??? 8 01 r9: 9 Start 9’ 10 0 Start r10 :01 24 35? 01?? 6?? 7??? 8 01 r11:9 100 Start 12 13 0 r12 : Start 14 15 1 r13 : Start 11 12 14 13 15 Start 01?? 16?? r14 、 r15 : 10’ Start 11 12 14 13 15? 01?? 16?? 17??? r16 :01 24 35? 01?? 6?? 7??? 8 0 91 100 11 12 14??? r17: (3 )由子集法构造等价的 DFA 过程如下: 01 ABC BBD CBC DEC EFG FFG GHI HFG IFIA closure ??}7,4,2,1,0{ })0 ({_?B closure A???}8,7,6,4,3,2,1{ })8,3 ({_ 0? Start C closure A???}7,6,5,4,2,1{ })5 ({_ 1?B closure B???}8,7,6,4,3,2,1{ })8,3 ({_ 0?D closure B???}9,7,6,5,4,2,1{ })9,5 ({_ 1?B closure C??})8,3 ({_ 0?C closure C??})5 ({_ 1? E B closure closure closure D???????}17 ,14 ,12 , 11,10 ,8,7,6,4,3,2,1{}17 ,14 ,12 , 11,10 { })10 ({_ })8,3 ({_ })10 ,8,3 ({_ 0???C closure D??})5 ({_ 1? F B closure closure closure E???????}17 ,16 ,14 ,13 ,12 , 11,8,7,6,4,3,2,1{}17 ,16 ,14 ,13 ,12 , 11{ })13 ({_ })8,3 ({_ })13 ,8,3 ({_ 0??? G D closure closure closure E???????}17 ,16 ,15 ,14 ,12 , 11,9,7,6,5,4,2,1{}17 ,16 ,15 ,14 ,12 , 11{ })15 ({_ })9,5 ({_ })15 ,9,5 ({_ 1???F closure F??})13 ,8,3 ({_ 0?G closure F???}17 ,16 ,15 ,14 ,12 , 11,9,7,6,5,4,2,1{ })15 ,9,5 ({_ 1?H E closure E closure closure closure G?????????}17 ,16 ,14 ,13 ,12 , 11,10 ,8,7,6,4,3,2,1{}17 ,16 ,14 ,13 ,12 , 11{ })13 ({_ })13 ({_ })10 ,8,3 ({_ })13 ,10 ,8,3 ({_ 0????IC closure C closure G??