《编译原理与技术》练习题 1
练习 1
1.1 为什么高级程序语言需要编译程序? 1.2 解释下列术语:
源程序,目标程序,翻译程序,编译程序,解释程序 1.3 简单叙述编译程序的主要工作过程。
1.4 编译程序的典型体系结构包括哪些构件,主要关系如何,请用辅助图示意。 1.5 编译程序的开发有哪些途径?了解你熟悉的高级编程语言编译程序的开发方式。 1.6 运用编译技术的软件开发和维护工具有许多类,简单叙述每一类的主要用途。 1.7 了解一个真实编译系统的组成和基本功能。 1.8 简单说明学习编译程序的意义和作用。
1.9 如果机器H上有两个编译:一个把语言A翻译成语言B,另一个把B翻译成C,那么可以把第一个编译的输出作为第二个编译的输入,结果在同一类机器上得到从A到C的编译。请用T形图示意过程和结果。
《编译原理与技术》练习题 2
练习 2
2.1 词法分析器的主要任务是什么? 2.2 下列各种语言的输入字母表是什么?
(1) C (2) Pascal (3) Java (4) C#
2.3 可以把词法分析器写成一个独立运行的程序,也可以把它写成一个子程序,请比较各自的优劣。 2.4 用高级语言编写一个对C#或Java程序的预处理程序,它的作用是每次调用时都把下一个完整的句子送到扫描缓冲区,去掉注释和无用的空格、制表符、回车、换行。 2.5 用高级语言实现图2.5所示的Pascal语言数的状态转换图。 2.6 用高级语言编程实现图2.6所示的小语言的词法扫描器。 2.7 用自然语言描述下列正规式所表示的语言: (1) 0(0|1)*0
(2) ((?|0)1)*)* (3) (a|b)*a(a|b|?) (4) (A|B|...|Z)(a|b|...|z)* (5) (aa|b)*(a|bb)*
(6) (0|1|...|9|A|B|C|D|E)+(t|T) 2.8 为下列语言写正规式
(1) 所有以小写字母a开头和结尾的串。 (3) 所有表示偶数的串。 (4) 所有不以0开始的数字串。 (5) 能被5整除的10进制数的集合。 (6) 没有出现重复数字的全体数字串。 (1) (a|b)*a(a|b) (2) (a||b)*a(a|b) * (3) ab((ba|ab)*(bb|aa))*ab (4) 00|(0|1)*|11 (5) 1(0|1)*01
(6) 1(1010*|1(010)*1*0
2.10 请分别使用下面的技术证明(a|b)*,(a*|b*)*以及((a|?)b*)*这三个正规式是等价的: (1) 仅用正规式的定义及其代数性质;
(2) 从正规式构造的最小DFA的同构来证明正规式的等价。
(2) 所有以小写字母a开头或者结尾(或同时满足这两个条件)的串。
2.9 试构造下列正规式的NFA,并且确定化,然后最小化。
《编译原理与技术》练习题 3
2.11 构造有限自动机M,使得
(1) L(M) = {anbn | n ? 1}; (2) L(M) = {anbncn | n ? 1};
(3) 它能识别?={0, 1}上0和1的个数都是偶数的串;
(4) 它能识别字母表{0, 1}上的串,但是串不含两个连续的0和两个连续的1;
(5) 它能接受形如?dd*,?d*E和?dd的实数,其中d={0,1,2,3,4,5,6,7,8,9}。 (6) 它能识别{a, b}上不含子串aba的所有串。
(c)
b a 4 S A D B 2.12 分别将下列NFA确定化,并画出最小化的DFA: (a) (b)
a 0 a,b 1 0 a a 1 a b b 3 a,b a a