《编译原理作业题整理》由会员分享，可在线阅读，更多相关《编译原理作业题整理（5页珍藏版）》请在装配图网上搜索。
1、编译原理作业题整理 第一章 习题一 1 解释名词：语言、目的语言、翻译器、编译器和解释器。 答：语言：被翻译器翻译的语言，用于书写程序的语言。 目的语言：被翻译器翻译之后得到的语言，用于书写目的程序的语言。 翻译器：可以完成从一种语言到另一种语言的变换的软件。 编译器：一种特殊的翻译器，要求目的语言比语言低级。 解释器：解释器是不同于编译器的另一种语言处理器。解释器不像编译器那样通过翻译来生成目的程序，而是直接执行程序所指定的运算。 第二章 词法分析p 作业： 假设=0,1，求 1. 写出包含010的所有串的正规式 2. 写出不包含010的所有串的正规式 答： 1. 0|1*0100|1* 2
2、.10*1*|11|00*|0111*0* . 2. 0|1*0100|1* 解：1RE的分解树如下： r17 r16 r11 r9 r7 r5 r6 0 r8 1 r10 0 ( r15 r14 * ) r13 1 r12 0 | r4 ( r3 ) r2 1 * r1 0 | 2由分解树及根本的Thompson构造算法逐步构造等价的NFA过程如下： Start 0 r1： 2 3 r2： Start 4 1 5 2 0 3 ? r3、r4: Start 1 ? 6 ? 4 1 5 ? ? ? r5: Start 0 2 0 3 ? 6 ? 1 ? 7 ? 4 1 5 ? ? Start 7
3、 r6： 0 8 ? ? r7: Start 0 2 0 3 ? 6 ? 1 ? 7 0 8 ? 4 1 5 ? ? Start 8 r8： 1 9 ? ? r9: Start 0 2 0 3 ? 6 ? 1 ? 7 0 8 1 9 ? 4 1 5 ? ? Start 0 r10： 9 10 ? ? r11: Start 0 2 0 3 ? 6 ? 1 ? 7 0 8 1 9 0 10 ? 4 1 5 ? ? Start r12： 0 12 13 Start r13： 1 14 15 0 ? r14、r15： Start 11 12 13 ? 16 ? 1 14 15 ? ? 0 ? r16：
4、 Start 10 12 13 ? 16 ? 11 ? 17 ? 1 14 15 ? ? ? r17: ? Start 0 2 0 3 ? 6 ? ? 7 0 8 1 9 12? 1 0 10 ? 11 ? 4 1 5 ? ? 14? 3由子集法构造等价的DFA过程如下： A B C D E F G H I 0 B B B E F F H F F 1 C D C C G G I G I ?_closure(0)?0,1,2,4,7?A A0-_closure(3,8)?1,2,3,4,6,7,8?B A1-_closure(5)?1,2,4,5,6,7?C B0-_closure(3,8)?1
5、,2,3,4,6,7,8?B B1-_closure(5,9)?1,2,4,5,6,7,9?D C0-_closure(3,8)?B C1-_closure(5)?C D0-_closure(3,8,10)-_closure(3,8)-_closure(10)?B?10,11,12,14,17?1,2,3,4,6,7,8,10 D1-_closure(5)?C E0-_closure(3,8,13)-_closure(3,8)-_closure(13)?B?11,12,13,14,16,17?1,2,3,4,6,7,8 E1-_closure(5,9,15)-_closure(5,9)-_cl
6、osure(15)?D?11,12,14,15,16,17?1,2,4,5,6,7,9 F0-_closure(3,8,13)?F F1-_closure(5,9,15)?1,2,4,5,6,7,9,11,12,14,15,16,17?G G0-_closure(3,8,10,13)-_closure(3,8,10)-_closure(13)?E-_closure(13)?E?11,12,13,14,16,17?1,2,3,4,6,7,8,10,11,12,13,14,16,17?HG1-_closure(5,15)?C-_closure(15)?C?11,12,14,15,16,17?1,2,4,5,6,7,11,12,14,15,16,17?I第 5 页 共 5 页
编译原理作业题整理
