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

练习 1

1.1 为什么高级程序语言需要编译程序？

1.2 解释下列术语：

源程序，目标程序，翻译程序，编译程序，解释程序

1.3 简单叙述编译程序的主要工作过程。

1.4 编译程序的典型体系结构包括哪些构件，主要关系如何，请用辅助图示意。

1.5 编译程序的开发有哪些途径？了解你熟悉的高级编程语言编译程序的开发方式。

1.6 运用编译技术的软件开发和维护工具有许多类，简单叙述每一类的主要用途。

1.7 了解一个真实编译系统的组成和基本功能。

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 所示的小语言的词法扫描器。

(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)

(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：

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) 将 NFA 确定化的算法；

(3) 将 DFA 最小化的算法。

2.17 写一个 Lex 输入源程序，它将产生一个把 C 语言程序中（注释除外）的保留字全部大写。

B→ aScA | cAB | b

A→ BaB | aBc | a

(1) aacb

(2) aabacbadcd

(3) aacbccb

(4) aacabcbcccaacdca

(5) aacabcbcccaacbca

S→ (L) | a

S→ aSbS | bSaS |ε

S→ Ac | aB

A→ ab

B→ bc

(6) A → 0B | 1C B → 1 | 1A | 0BB C → 0 | 0A | 1CC

V

V

,a

,…,a

P = {S→a