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

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

《编译原理与技术练习题汇总.docx》由会员分享，可在线阅读，更多相关《编译原理与技术练习题汇总.docx（35页珍藏版）》请在冰点文库上搜索。

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

练习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）（（e|0）1）*）*

（3）（a|b）*a（a|b|e）

（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|e）b*）*这三个正规式是等价的：

（1）仅用正规式的定义及其代数性质；

（2）从正规式构造的最小DFA的同构来证明正规式的等价。

2.11构造有限自动机M，使得

（1）L（M）={anbn|n³1}；

（2）L（M）={anbncn|n³1}；

（3）它能识别S＝{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）

2.13下面是URL的一个极其简化的扩展正规式的描述：

letter→[A-Za-z]

digit→[0-9]

letgit→letter|digit

letgit_hyphen→letgit|_

letgit_hyphen_string→letgit_hyphen|letgit_hyphenletgit_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.16Pascal语言的注释允许两种不同的形式：

花括弧对{...}，以及括弧星号对（*...*）。

（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|aAA→bA|a

（2）S→SS|1A0A→1A0|ε

（3）S→1A|B0A→1A|CB→B0|CC→1C0|ε

（4）S→bAdcA→AS|a

（5）S→aSSS→a

（6）A→0B|1CB→1|1A|0BBC→0|0A|1CC

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由以下产生式组成：

AabcAaBbc

BbbBBcCbcc

bCCbaCaaB

aCaa

问：

此文法表式的语言是什么？

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

P→aPQR|abR

RQ→QR

bQ→bb

bR→bc

cR→cc

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

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

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

该文法是否为二义的？

为什么？

（提示：

找一个句子，使之有两棵不同的分析树。

）

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）{anbnambm|n,m≥0}。

（2）{1n0m1m0n|n,m≥0}。

（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α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）当α的首符号为终结符号时，β的首符号也必为终结符号；

（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

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

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

（1）A→BaC|CbB

B→Ac|c

C→Bb|b

（2）A→Ba|Aa|c

B→Bb|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

练习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→bexprorbterm|bterm

bterm→btermandbfactor|bfactor

bfactor→notbfactor|（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根据下列优先关系矩阵计算其优先函数，并说明优先函数是否存在。

S

A

B

a

b

c

S

≯

A

≮

≮

≌

≮

≮

B

≌

a

≌

≮

≮

≯

b

≯

≯

≯

≯

≯

≌

c

≯

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|e

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→e

B→e

（1）证明它是LL

（1）文法，但不是SLR

（1）文法；

（2）证明所有LL

（1）文法都是LR

（1）文法。

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

（1）A→AA+|AA*|a

（2）S→AB

A→aBa|e

B→bAb|e

（3）S→D;B|B

D→d|e

B→B;a|a|e

（4）S→D;B|B

D→d|e

B→B;a|a|e

（5）S→（SR|a

R→.SR|）

（6）S→UTa|Tb

T→S|Sc|d

U→US|e

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

B→BandB|BorB|notB|（B）|true|false|b

是二义性文法。

（1）为句子bandbortrue构造两个不同的最右推导，以此说明该文法是二义的。

（2）为它写一个等价的非二义性文法。

（3）给出无二义性规则，构造出LR（0）分析表，并给出句子bandbortrue的分析过程。

练习6

6.1符号表的作用有哪些？

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

6.3符号表组织的数据结构有哪些种？

每种组织结构选取的主要依据是什么？

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

大多数语言规定，程序块结构的声明作用域使最近嵌套规则，请按照这个规则写出下列声明的作用域。

main（）

{/*开始块B0*/

inta=0;

intb=0;

{/*开始块B1*/

intb=1;

{/*开始块B2*/

inta=2;

……

}/*结束块B2*/

{/*开始块B3*/

intb=3;

……

}/*结束块B3*/

……

}/*结束块B1*/

}

6.5C语言中规定变量标识符可以定义为：

extern、erternstatic、auto、localstatic和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）值－结果调用方式；

programcopyout（input,output）;

vara:

integer;

procedureunsafe（varx:

integer）;

beginx:

=2;a:

=0end;

begin

a:

=1;unsafe（a）;writeln（a）

end

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

（1）按值调用方式；

（2）引用调用方式；

（3）值－结果调用方式；

（4）换名调用方式。

procedurep（x,y,z）;

begin

y:

=y+1;

z:

=z＋x;

endp;

begin

a:

=2;

b:

=3;

p（a+b,a,a）;

printa;

end;

7.7设计存储分配时要考虑哪些主要因素？

常见的存储分配策略有哪些？

简单说明在什么情况下使用哪种存储分配策略。

7.8C++语言中关于变量的存储类型符有4个：

auto、register、static和extern，请说明每个说明符所表示的存储方式。

7.9为下面FORTRAN程序的运行时环境构造出一个可能的组织结构，要保证对AVE的调用时存在的一个存储器指针（参考7.4节）。

REALA（SIZE）,AVE

INTEGERN,I

10READ*,N

IF（N.LE.0.OR.N.GT.SIZE）GOTO99

READ*,（A（I）,I=1,N）

PRINT*,‘AVE=‘,AVE（A,N）

GOTO10

99CONTINUE

END

REALFUNCTIONAVE（B,N）

INTEGERI,N

REALB（N）,SUM

SUM=0.0

DO20I=1,N

20SUM=SUM+B（I）

AVE=SUM/N

END

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

voidf（charc,chars[10],doubler）

{int*x;

inty[5];

......

}

（1）使用标准C参数传递约定，利用7.5.1所描述的活动记录结构判断以下的fp的偏移：

c，s[7]和y[2]（假设数据大小为：

整型＝2个字节，字符＝1个字节，双精度＝