文档库

最新最全的文档下载
当前位置:文档库 > 编译原理与技术练习题汇总

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

练习 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:

(b) (c)

(a)

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

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

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

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

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

2.15 描述下列语言词法记号的正规表达式:

(1) 描述C浮点数的正规表达式。

(2) 描述Java表达式的正规表达式。

2.16 Pascal语言的注释允许两种不同的形式:花括弧对{...},以及括弧星号对(*...*)。

(1) 构造一个识别这两种注释形式的DFA;

(2) 用Lex的符号构造它的一个正规式。

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

练习 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

试检验下列符号串中哪些是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) 指出该文法的终结符号及非终结符号。

(2) 给出下列各句子的语法分析树:

①(a,a) ②(a,(a, a)) ③(a, ((a, a), (a, a)))

(3) 分别构造(b)中各句子的一个最左推导和最右推导。3.4 考虑文法G3.29[S]

S→aSbS | bSaS |ε

(1) 讨论句子abab的最左推导,说明该文法是二义性的。

(2) 对于句子abab构造两个相应的最右推导。

(3) 对于句子abab构造两棵相应的分析树。

(4) 此文法所产生的语言是什么?

3.5 文法G3.30[S]为:

S→ Ac | aB

A→ ab

B→ bc

写出L(G3.30)的全部元素。

3.6 试描述由下列文法G[S]所产生的语言。

(1) S→ 10S0 | aA A→bA | a

(2) S→ SS | 1A0 A→1A0 | ε

(3) S→ 1A | B0 A→1A | C B→B0 | C C→1C0 | ε

(4) S→ bAdc A→A S | a

(5) S→ aSS S→a

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

3.7 设已给文法G3.31=(V N,V T,P,S),其中:

V N = {S}

V T = {a1,a2,…,a n,∨,∧, ~, [,]}

P = {S→a i| 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由以下产生式组成:

A→abc A→aBbc

Bb →bB Bc →Cbcc

bC →Cb aC →aaB

aC →aa

问:此文法表式的语言是什么?

3.9 已知文法G3.33 [P]:

P → aPQR |abR

RQ → QR

bQ → bb

bR → bc

cR → cc

证明aaabbbccc 是该文法的一个句子。

3.10 构造一个文法,使其产生的语言是由算符+, *, (, ) 和运算对象a构成的算术表达式的集合。

3.12 已知语言L={a n bb n| n≥1}, 写出产生语言L的文法。

3.13 写一文法,使其语言是偶正整数的集合。要求:

(1) 允许0打头。(2) 不允许0打头。

3.14 文法G3.34 [S]为:

S→ Ac|aB, A→ ab

B→ bc

该文法是否为二义的?为什么?(提示:找一个句子,使之有两棵不同的分析树。)

3.15 证明下述文法G3.35[〈表达式〉]是二义的:

〈表达式〉→ a | (〈表达式〉) |〈表达式〉〈运算符〉〈表达式〉

〈运算符〉→+ | - | * | /

3.16 下面的文法产生a的个数和b的个数相等的非空a、b串

S→ aB | bA

B→ bS | aBB | b

A→ aS | bAA | a

其中非终结符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的闭包。

(1) 证明此文法生成∑={a, b}上的除了?和ε的所有正规表达式。

(2) 试说明此文法是二义性的。

(3) 构造一个等价的无二义性文法,该文法给出*、连接和|等运算符号的优先级和结合规则。

3.18 给出产生下述语言的上下文无关文法:

(1) { a n b n a m b m | n, m≥0}。

(2) { 1n 0m1m 0n | n, m≥0}。

(3) { ωcωT | ω∈{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=(V N,V T,P,S)为CFG,α1,α2,…,αn为V上的符号串,试证明:

若α1α2…αnβ 则存在V上的符号串β1,β2,…,βn,使β=β1β2…βn,且有a iβi(i=1,2,…,n)。

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

3.20 设G=(V N,V T,P,S)为CFG,α和β都是V上的符号串,且αβ,试证明:

(1) 当α的首符号为终结符号时,β的首符号也必为终结符号;

(2) 当β的首符号为非终结符号时,则α的首符号也必为非终结符号。

3.21 写出下列语言的3型文法:

(a) {a n| n≥0}

(b) {a n b m | n, m≥1}

(c) {a n b m c k | n, m, k≥1}

3.22 已知文法G3.37 [S]:

S→ dAB

A→ aA|a

B→ε |Bb

给出相应的正规式和等价的正规文法。

3.23 给出下列文法G[A]消除左递归后的等价文法:

(1) A→ BaC | CbB

B→ Ac | c

C→ Bb | b

(2) A→ B a | A a | c

B → B b | A b | 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

练习 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

(1) 消除文法G4.14的左递归,并为每个非终结符构造不带回溯的递归子程序。

(2) 经改写后的文法是否是LL(1)文法?给出它的预测分析表。

(3) 给出输入串(a, a)$ 的分析过程,并说明该符号串是否为文法G4.14的句子。

4.6 对于文法G4.15[R]

R → R ' | ' T | T

T → TF | F

F → F* | C

C → (R) | a | b

(1) 消除文法的左递归。

(2) 计算文法G4.15各非终结符的FIRST集和FOLLOW集。

(3) 构造LL(1)分析表。

4.7 已知文法G4.16[A]

A→ aABe | a

B→ Bb | d

(1) 判断该文法是否为LL(1) 文法。

(2) 写出输入串aade$ 的分析过程。

练习 5

5.1 设文法G5.10[E]为

E → E+T | E-T | T

T → T*F | T/F | F

F → F↑P | P

P → (E) | i

求以下句型的短语、直接短语、素短语、句柄和最左素短语:

(1)E-T/F+i

(2)E+F/T-P↑i

(3)T*(T-i)+P

(4)(i+i)/i-i

5.2 根据下列优先关系矩阵计算其优先函数,并说明优先函数是否存在。

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

5.3 对于文法G5.11[S]

S → (R) | a | b

R → T

T → S; T | S

(1)计算G5.11 [S]的FIRSTTV和LASTTV;

(2)构造G5.11 [S]的优先关系表,并说明G5.11 [S]是否为算符优先文法;(3)计算G5.11 [S]的优先函数。

5.4 对于文法G5.12 [S]

S → S;G | G

G → G(T) | H

H → a | (S)

T → T+S | S

(1)构造G5.12 [S]的算符优先关系表,并判断G5.12 [S]是否为算符优先文法;

(2)给出句型a(T+S);H;S的短语、直接短语、句柄、素短语和最左素短语;

(3)分别给出(a+a)和a;(a+a)的分析过程,并说明它们是否为G5.12 [S]的句子;

(4)给出(3)中输入串的最右推导,分别说明它们是否为G5.12 [S]的句子;

(5)从(3)和(4)说明算符优先分析的优缺点。

5.5 对于文法G5.13[P]

P → LAd | cd

L → c

A→ aP | P | a

请证明它不存在优先函数。

5.6 给定文法G5.14 [S]

S →AS | b

A→ SA | a

(1)构造它的LR(0)的项集;

(2)构造识别该文法所有活前缀的DFA;

(3)这个文法是SLR(1)吗?若是,构造出它的SLR(1)分析表。

5.7 给定文法G5.15[S]

S →AS |

A→ aA | b

(1)构造它的LR(1)文法;

(2)构造识别该文法所有活前缀的DFA;

(3)构造出它的SR(1)分析表;

(4)给出字符串abab$的分析过程。

5.8 若有定义二进制数的文法G5.16[D]

D → L . L | L

L → LB | B

B → 0 | 1

(1)通过构造该文法的无冲突的分析表来说明它是哪类LR文法;

(2)给出输入串101.010的分析过程。

5.9 给定文法G5.17[S]

S → L = R| R

L → *R | id

R → L

(1)构造它的LR(0)的项集;

(2)构造它的LR(0)项集规范族;

(3)构造识别该文法所有活前缀的DFA;

(4)该文法是SLR(1)、LR(1)以及LALAR(1)?构造相应的分析表。

5.10 对于文法G5.18[S]

S → A

A→ Ab | bBa

B → aAc | aAb | a

(1)证明它是SLR(1)文法,但不是LR(0)文法;

(2)证明所有SLR(1)文法都是LR(1)文法。

5.11 证明文法G5.19[M]

M → N

N → Qa | bQc | dc | bda

Q → D

是LALR(1)文法,但不是SLR(1)文法。

5.12 证明文法G5.20[S]

S → aAa | aBb | bAb | bBa

A→ c

B → c

是LR(1)文法,但不是LALR(1)文法。

5.13 对于文法G5.21[S]

S → AaAb | BbBa

A→ε

B →ε

(1)证明它是LL(1)文法,但不是SLR(1)文法;

(2)证明所有LL(1)文法都是LR(1)文法。

5.14 对于下列各个文法,判断它是哪类最简单的LR文法,并构造相应的分析表。

(1)A→ AA + | AA* | a

(2)S → AB

A→ aBa | ε

B → bAb | ε

(3)S → D; B | B

D → d | ε

B → B; a | a| ε

(4)S → D; B | B

D → d | ε

B → B; a | a| ε

(5)S → (SR | a

R → . SR | )

(6)S → UTa | Tb

T → S | Sc | d

U → US | e

5.15 命题演算的文法G5.22[B]

B → B and B | B or B | not B | (B) | true | false | b

是二义性文法。

(1)为句子b and b or true构造两个不同的最右推导,以此说明该文法是二义的。(2)为它写一个等价的非二义性文法。

(3)给出无二义性规则,构造出LR(0)分析表,并给出句子b and b or true的分析过程。

练习 6

6.1 符号表的作用有哪些?

6.2 符号表的表项通常包括哪些属性,主要描述的内容是什么?

6.3 符号表组织的数据结构有哪些种?每种组织结构选取的主要依据是什么?

6.4 程序块是程序语言的主要构造元素,它允许以嵌套的方式确定局部声明。大多数语言规定,程序

块结构的声明作用域使最近嵌套规则,请按照这个规则写出下列声明的作用域。

main()

{ /* 开始块B0 */

int a = 0;

int b =0;

{ /* 开始块B1 */

int b = 1;

{ /* 开始块B2 */

int a = 2;

……

} /* 结束块B2 */

{ /* 开始块B3 */

int b = 3;

……

} /* 结束块B3*/

……

} /* 结束块B1*/

}

6.5 C语言中规定变量标识符可以定义为:extern、ertern static、auto、local static和register,请对这

5种变量分别说明其作用域。

6.6 设散列表为HT[13],哈希函数定义为hash(key)=key%13(整数除法取余运算),用链地址法解决

冲突对下列关键码12,23,45,57,20,3,31,15,56,78造表。

练习 7

7.1 请考虑过程和活动记录的联系和区别。

7.2 请解释下列概念:

生存期,过程的活动,活动树,活动记录。

7.3 有哪些常见的参数传输方式,请分析和比较它们各自的特点。

7.4 对你熟悉的高级程序语言(如C、Pascal、C++、Java或C#),了解它们的参数传输机制。

7.5 执行下面Pascal程序的输出a结果分别是什么,如果参数的传递机制是:

(1)引用调用方式;

(2)值-结果调用方式;

program copyout (input, output);

var a: integer;

procedure unsafe (var x: integer);

begin x := 2; a := 0 end;

begin

a := 1; unsafe (a); writeln (a)

end

7.6 执行下面程序时打印的a分别是什么,若参数的传递机制是:

(1)按值调用方式;

(2)引用调用方式;

(3)值-结果调用方式;

(4)换名调用方式。

procedure p(x, y, z);

begin

y := y +1;

z := z+x;

end p;

begin

a := 2;

b := 3;

p(a+b, a, a);

print a;

end;

7.7 设计存储分配时要考虑哪些主要因素?常见的存储分配策略有哪些?简单说明在什么情况下使

用哪种存储分配策略。

7.8 C++语言中关于变量的存储类型符有4个:auto、register、static和extern,请说明每个说明符所

表示的存储方式。

7.9 为下面FORTRAN程序的运行时环境构造出一个可能的组织结构,要保证对A VE的调用时存在

的一个存储器指针(参考7.4节)。

REAL A(SIZE), A VE

INTEGER N, I

10 READ *, N

IF (N .LE. 0 .OR. N .GT. SIZE) GOTO 99

READ *, (A(I), I=1, N)

PRINT *, ‘A VE = ‘, A VE(A, N)

GOTO 10

99 CONTINUE

END

REAL FUNCTION A VE (B, N)

INTEGER I, N

REAL B(N), SUM

SUM = 0.0

DO 20 I=1, N

20 SUM = SUM+B(I)

A VE = SUM/N

END

7.10考虑C语言中的下列过程:

void f ( char c, char s[10], double r)

{ int * x;

int y [5];

......

}

(1)使用标准C参数传递约定,利用7.5.1所描述的活动记录结构判断以下的fp的偏移:c,s[7]和y[2](假设数据大小为:整型=2个字节,字符=1个字节,双精度=8个字节,地址=4个字节)(2)假设所有的参数都是按值传递(包括数组),重做(1);

(3)假设所有的参数都是引用传递(包括数组),重做(1)。

7.11为下面C程序的运行时环境构造出一个可能的组织结构(参考7.5.1节)。

(1) 在进入函数f中的块A之后;

(2) 在进入函数g中的块B之后。

int a[10];

char *s = ‘hello’;

int f ( int i, int b[] )

{ int j = 1;

A: { int i = j;

char c = b[i];

......

}

return 0;

}

void g (char *s)

{ char c = s[0];

B: { int a[5]; ...... }

}

main ()

{ int x = 1;

x = f (x, a);

g (s);

return 0;

}

7.12 使用访问链(参考7.5.2节)分别画出下面Pascal程序执行到

(1)第1次调用r之后的运行时栈的内容;

(2)第2次调用r之后的运行时栈的内容;

program pascal1;

procedure p;

var x: integer;

procedure q;

procedure r;

begin

x := 2;

......

if ... then p;

end; { r }

begin

r;

end; { q }

begin

q;

end; { p }

begin { pascal1 }

p;

end.

7.13 使用显示表display重做练习7.12。

7.14 对下面的Pascal程序,分别画出程序执行到点(1)和(2)时刻的运行时栈的内容。

program pascal2 (input, output);

var i: integer; d: integer;

procedure a ( k: real );

var p: char;

procedure b;

var c: char;

begin

...(1)...

end: {b}

procedure c;

var t: real;

begin

...(2)...

end: {c}

begin

......

b;

c;

......

end; {a}

begin { pascal2 }

......

a (d);

......

end.

7.15 使用显示表display重做练习7.14。

7.16 实现栈式动态存储管理的一个问题是,如何分配空闲块。请考虑有几种空闲块的分配策略,并比

较每个策略的优缺点。

7.17 了解面向对象语言(如面向对象Pascal、C++、C#、Java)是如何实现垃圾搜集任务的。

7.18 存储紧缩有时也称为“单空间复制”,以区别双空间复制,请指出两者的相同之处和差异。

7.19 为以下的C++类画出对象的存储器框架和虚拟函数表(参考7.6.3节):

class A

{ public:

int a;

virtual void f();

virtual void g();

};

class B: public A

{ public:

int b;

virtual void f();

void h();

};

class C: public B

{ public:

int c;

virtual void g(); }