编译原理和技术练习题汇总.doc

《编译原理与技术》练习题 PAGE 23 练习 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.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开头和结尾的串。 (2) 所有以小写字母a开头或者结尾（或同时满足这两个条件）的串。 (3) 所有表示偶数的串。 (4) 所有不以0开始的数字串。 (5) 能被5整除的10进制数的集合。 (6) 没有出现重复数字的全体数字串。 2.9 试构造下列正规式的NFA，并且确定化，然后最小化。 (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.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的所有串。 2.12 分别将下列NFA确定化，并画出最小化的DFA： (a) a a 1 0 a,b b (b) a a 4 0 a,b a 1 2 3 a b b b a (c) ? ? a b F A a,b B C D ? b b a S E ? ? 2.13 下面是URL的一个极其简化的扩展正规式的描述： letter → [A-Za-z] digit → [0-9] letgit → letter| digit letgit_hyphen → letgit | _ letgit_hyphen_string → letgit_hyphen | letgit_hyphen letgit_hyphen_string label → letter (letgit_hyphen_string? letgit)？ URL → (label.)*label (1) 请将这个URL的扩展正规改写成只含字母表{A, B, 0, 1, _, .}上符号的正规式； (2) 构造出识别（1）更简化的URL串的有限自动机。 2.14 用某种高级语言实现 (1) 将正规式转换成NFA的算法； (2