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

《编译原理与技术》练习题
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 开头和结尾的串。 (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 的同构来证明正规式的等价。
(1) 证明此文法生成={a, b}上的除了和ε的所有正规表达式。
(2) 试说明此文法是二义性的。
(3) 构造一个等价的无二义性文法，该文法给出*、连接和|等运算符号的优先级和结合规则。
3.18 给出产生下述语言的上下文无关文法： (1) { an bn am bm | n, m≥0}。 (2) { 1n 0m1m 0n | n, m≥0}。
(2) 给出下列各句子的语法分析树：
① (a,a) ② (a,(a, a)) ③ (a, ((a, a), (a, a)))
(3) 分别构造(b)中各句子的一个最左推导和最右推导。
3.4 考虑文法 G3.29[S] S→ aSbS | bSaS |ε (1) 讨论句子 abab 的最左推导，说明该文法是二义性的。
若 α1α2…αn β 则存在 V 上的符号串 β1,β2，…,βn，使 β=β1β2…βn，且有 ai βi (i=1,2,…,n)。
3.20 设 G=(VN,VT,P,S)为 CFG，α 和 β 都是 V 上的符号串，且 α β，试证明：
(1) 当 α 的首符号为终结符号时，β 的首符号也必为终结符号；
《编译原理与技术》练习题
7
(3) { cT | ∈{a, b}*}，其中T 是的逆。
(4) { w | w∈{a,b}+，且 w 中 a 的个数恰好比 b 多 1 }。
(4) { w | w∈{a,b}+，且|a|≤|b|≤2|a| }。
(5) { w | w 是不以 0 开始的奇数集 }。
3.19 设 G=(VN,VT,P,S)为 CFG，α1,α2,…,αn 为 V 上的符号串，试证明：
《编译原理与技术》练习题
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 形图示 意过程和结果。
3.15 证明下述文法 G3.35［〈表达式〉］是二义的：
〈表达式〉→ a | (〈表达式〉) |〈表达式〉〈运算符〉〈表达式〉
〈运算符〉→ + | - | * | /
3.16 下面的文法产生 a 的个数和 b 的个数相等的非空 a、b 串 S→ aB | bA B→ bS | aBB | b A→ aS | bAA | a
《编译原理与技术》练习题
4
练习 3
3.1 对于文法 G3.26[E] E→ T | E+T | E-T T→ F | T*F | T/F F→ (E) | i
证明(i+T)*i 是它的一个句型。
3.2 给定文法 G3.27[S] S→ aAcB | BdS B→ aScA | cAB | b A→ BaB | aBc | a
3.7 设已给文法 G3.31=(VN,VT,P,S)，其中： VN = {S} VT = {a1,a2,…,an,∨,∧, ~, [,]}
P = {S→ai| i=1,2,…,n}∪{S→ ~S, S→[ S∨S］, S → [ S∧S］}，
试指出此文法所产生的语言。
3.8 已知文法 G3.32=({A,B,C},{a,b,c},A,P)，其中 P 由以下产生式组成：
(2) 对于句子 abab 构造两个相应的最右推导。
(3) 对于句子 abab 构造两棵相应的分析树。
(4) 此文法所产生的语言是什么？
《编译原理与技术》练习题
5
3.5 文法 G3.30[S]为：
S→ Ac | aB A→ ab B→ bc
写出 L(G3.30)的全部元素。
3.6 试描述由下列文法 G[S]所产生的语言。
A abc Bb bB bC Cb aC aa
A aBbc Bc Cbcc aC aaB
问：此文法表式的语言是什么？
3.9 已知文法 G3.33 [P]:
P → aPQR |abR RQ → QR bQ → bb bR → bc cR → cc
证明 aaabbbccc 是该文法的一个句子。
3.10 构造一个文法，使其产生的语言是由算符+, *, (, ) 和运算对象 a 构成的算术表达式的集合。
给出相应的正规式和等价的正规文法。
3.23 给出下列文法 G[A]消除左递归后的等价文法： (1) A→ BaC | CbB B→ Ac | c C→ Bb | b (2) A → B a | A a | c B → B b |Ab | d (3) S→ SA | A A→ SB | B | (S) | ( ) B→ [S] | [ ] (4) S→ AS | b A→ SA | a (5) S→ (T) | a | ε T→ S | T, S
试检验下列符号串中哪些是 G3.27 [S]中的句子。 (1) aacb (2) aabacbadcd (3) aacbccb (4) aacabcbcccaacdca (5) aacabcbcccaacbca
3.3 考虑文法 G3.28[S] S→ (L) | a L→ L, S | S (1) 指出该文法的终结符号及非终结符号。
《编译原理与技术》练习题
8
练习 4
4.1 证明：含有左递归的文法不是 LL(1)文法。 4.2 对于文法 G4.11[S]
S → uBDz B → Bv | w D → EF E→y| F→x| (1) 计算文法 G4.11 各非终结符的 FIRST 集和 FOLLOW 集，以及各产生式的 SELLECT 集。 (2) 判断该文法是否是 LL(1)文法。 (3) 若不是 LL(1)文法，则修改此文法 , 使其成为能产生相同语言的 LL(1) 文法。 4.3 已知布尔表达式文法 G4.12[bexpr] bexpr→ bexpr or bterm | bterm bterm→ bterm and bfactor | bfactor bfactor→ not bfactor | (bexpr) | true | false 改写文法 G4.12 为扩充的巴克斯范式，并为每个非终结符构造递归下降分析子程序。 4.4 已知用 EBNF 表示的文法 G4.13[A] A→ [ B B→ X ] {A} X→ (a | b) {a | b} 试用类 C 或类 PASCAL 语言写出其递归下降子程序。 4.5 已知文法 G4.14[S] S→ (L) | a L→ L, S | S
URL → (label.)*label (1) 请将这个 URL 的扩展正规改写成只含字母表{A, B, 0, 1, _, .}上符号的正规式； (2) 构造出识别（1）更简化的 URL 串的有限自动机。 2.14 用某种高级语言实现 (1) 将正规式转换成 NFA 的算法； (2) 将 NFA 确定化的算法； (3) 将 DFA 最小化的算法。 2.15 描述下列语言词法记号的正规表达式： (1) 描述 C 浮点数的正规表达式。 (2) 描述 Java 表达式的正规表达式。 2.16 Pascal 语言的注释允许两种不同的形式：花括弧对{...}，以及括弧星号对(*...*)。 (1) 构造一个识别这两种注释形式的 DFA； (2) 用 Lex 的符号构造它的一个正规式。 2.17 写一个 Lex 输入源程序，它将产生一个把 C 语言程序中（注释除外）的保留字全部大写。
(2) 当 β 的首符号为非终结符号时，则 α 的首符号也必为非终结符号。
3.21 写出下列语言的 3 型文法： (a) {an | n≥0} (b) {anbm | n, m≥1} (c) {anbmck | n, m, k≥1}
3.22 已知文法 G3.37 [S]： S→ dAB A→ aA|a B→ ε |Bb
(1) S→ 10S0 | aA A→bA | a (2) S→ SS | 1A0 A→1A0 | ε (3) S→ 1A | B0 A→1A | C B→B0 | C (4) S→ bAdc A→AS | a (5) S→ aSS S→a
C→1C0 | ε
(6) A → 0B | 1C B → 1 | 1A | 0BB C → 0 | 0A | 1CC
《编译原理与技术》练习题
6
3.12 已知语言 L={anbbn| n≥1}, 写出产生语言 L 的文法。
3.13 写一文法，使其语言是偶正整数的集合。 要求：
(1) 允许 0 打头。 (2) 不允许 0 打头。
3.14 文法 G3.34 [S]为： S→ Ac|aB, A→ ab B→ bc
该文法是否为二义的？为什么？（提示：找一个句子，使之有两棵不同的分析树。）
a
S
A
b
D
F
C b 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)？
《编译原理与技术》练习题
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 的所有串。
2.12 分别将下列 NFA 确定化，并画出最小化的 DFA：
(a)
(b)
(c)
a
a,b
0
1
b
1
a
a
a,b
0a
b3
4
a
b 2b
B
b
a
a,b
其中非终结符 B 推出 b 比 a 的个数多 1 个的串，A 则反之。
(1) 证明该文法是二义的。
(2) 修改上述文法，不增加非终结符，使之成为非二义文法，并产生同样的语言。
3.17 考虑文法 G3.36[R] R→R '|' R | RR | R* | (R) | a | b
其中 R '|' R 表示 R 或 R；RR 表示 R 与 R 的连接；R*表示 R 的闭包。