编译原理练习题解答.docx

编译原理练习题解答.docx

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

编译原理练习题解答

一.名词解释：

1）前缀

答：

前缀——是指符号串任意首部。

2）可归前缀

答：

可归前缀——是指规范句型的一个前缀，这种前缀包含句柄且不含句柄之后的任何符号。

3）活前缀

答：

活前缀——规范句型的一个前缀，这种前缀不含句柄之后的任何符号。

或给定文法规范句型的可归前缀的任意首部。

4）简单短语

答：

简单短语——设G[Z]是给定文法,w=xuy∈V+，为该文法的句型,如果满足下面两个条件:

①Z

xUy；②U⇒u；

则称句型xuy中的子串u是句型xuy的简单短语。

5）扫描遍

答：

扫描遍——指编译程序对源程序或中间代码程序从头到尾扫描一次。

6）句柄

答：

句柄——给定句型中的最左简单短语就是句柄。

7）句型

答：

句型——设G是一个给定的文法，S是文法的开始符号，如果S

x（其中x∈V*）,则称x是文法的一个句型。

8）句子

答：

句子——设G是一个给定的文法，S是文法的开始符号，如果Sx（其中x∈VT*），则称x是文法的一个句子。

9）非终结符

答：

非终结符——出现在文法产生式的左部且能派生出符号或符号串的那些符号称为非终结符号。

10）终结符

答：

终结符——出现在文法产生式的右部且不能派生出符号或符号串的那些符号称为终结符号。

11）属性文法

答：

一个属性文法形式的定义为一个三元组AG，AG=（G，V，E）。

其中G为一个上下文无关文法；V为属性的有穷集；E为一组语义规则。

12）语法制导翻译

答：

语法制导翻译——语法制导翻译就是在语法分析的过程中，当进行推导或归约时同步完成附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。

13）后缀式

答：

后缀式——一种把运算量（操作数）写在前面，把算符写在后面（后缀）的表示法。

14）短语

答：

短语——设G[Z]是给定文法,w=xuy∈V+，为该文法的句型,如果满足下面两个条件:

①Z

xUy；②U

u；

则称句型xuy中的子串u是句型xuy的短语。

或：

句型语法树的全部子树的叶从左到右排列起来构成的符号串均是句型的短语。

15）基本块

答：

基本块——源程序或者中间代码程序中只有一个入口和一个出口的顺序执行的代码段。

16）语义规则

答：

对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。

17）语法分析

答：

语法分析——按文法的产生式识别输入的符号串是否为一个句子的分析过程。

18）四元式

答：

四元式——是一个带有四个域的记录结构，这四个域分别称为操作符域、左运算对象域、右运算对象域及运算结果域。

二．简答题：

1）什么是句子？

什么是语言?

解答：

句子——设G是一个给定的文法，S是文法的开始符号，如果Sx（其中x∈VT*），则称x是文法的一个句子。

语言——语言是句子的集合。

或——设G[S]是给定文法，则由文法G所定义的语言L（G）可描述为：

L（G）＝{x│S

x,x∈VT*}。

2）DFA与NFA有何区别?

解答:

DFA与NFA的区别表现为两个方面:

一是NFA可以有若干个开始状态，而DFA仅只有一个开始状态。

另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。

3）自顶向下的语法分析方法的基本思想是什么?

解答:

从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。

4）自底向上的语法分析方法的基本思想是什么?

解答:

从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。

5）一个上下文无关文法G包括哪四个组成部分？

解答:

一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。

6）在自底向上的语法分析方法中，分析的关键是什么？

解答:

关键是寻找句柄。

7）在自顶向下的语法分析方法中，分析的关键是什么？

解答:

关键是选择候选式。

8）编译程序中语法分析器接收以什么为单位的输入？

解答:

接收以单词为单位的输入。

9）若一个文法是递归的，则它所产生的语言的句子是可枚举的吗？

解答:

它所产生的语言的句子不是可枚举的，而是无穷多个。

10）编译程序生成的目标程序是不是一定是机器语言的程序？

解答:

不一定是机器语言的程序。

11）词法分析器是用于做什么的？

解答:

词法分析器是用于识别单词的。

12）“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法正确吗？

解答:

不正确。

13）把汇编语言程序翻译成机器可执行的目标程序的工作是由什么完成的？

解答:

由汇编器（汇编程序）完成的。

14）图示运行时存储空间的划分（分为哪几个区）。

解答:

一般分为静态区和动态区：

程序代码区、静态数据区、栈区和堆区

15）词法分析的主要任务是什么？

解答:

词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫描，依次把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度统一的属性字并输出。

16）常用的中间语言种类有哪几种？

解答:

常用的中间语言种类有逆波兰表示、三元式、四元式和树形表示。

17）文法G所描述的语言是什么的集合？

解答:

是由文法的开始符号推出的所有终结符串的集合。

或说是句子的集合。

18）乔姆斯基把文法分为四种类型，即0型、1型、2型、3型。

其中2型文法叫什么？

解答:

2型文法叫上下文无关文法。

19）编译程序是一种解释程序吗？

还是什么程序？

解答:

编译程序是一种翻译程序。

20）按逻辑上划分，编译程序第二步工作是什么？

解答:

编译程序第二步工作是语法分析。

21）源程序是用高级语言编写的，目标程序是机器语言程序或汇编语言程序，则其翻译程序称为什么？

解答:

其翻译程序称为编译程序。

22）编译方式与解释方式的根本区别为什么？

解答:

编译方式与解释方式的根本区别在于是否生成目标代码。

23）常见的动态存贮分配策略有哪两种？

解答:

常见的两种动态存贮分配策略是栈式动态分配策略和堆式动态分配策略。

24）常用的参数传递方式有哪三种？

解答:

常见的参数传递方式有传地址、传值和传名三种方式。

25）语法分析的任务是什么？

解答:

语法分析的任务是识别给定的终结符串是否为给定文法的句子。

26）局部优化是局限于一个什么范围内的一种优化？

解答:

是局限于一个基本块范围内的一种优化。

27）文法等价的定义是什么？

解答:

设G1和G2是给定的文法，如果有L（G1）=L（G2），则称G1与G2等价。

28）在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是什么集合？

解答:

均是终结符集。

29）通常一个编译程序中应包括哪七个部分？

解答:

通常一个编译程序中应包含词法分析，语法分析，语义分析与中间代码生成，代码优化，目标代码生成以及表格处理和出错处理等七个部分。

32）如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分为哪三个阶段？

解答:

源程序的执行分为三个阶段:

编译阶段，汇编阶段和运行阶段。

33）翻译程序是这样一种程序，它能够将用什么转换成与其等价的用乙语言书写的程序？

解答:

能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程序。

34）说明下面文法G[S]是二义性文法：

S→SaS|SbS|cSd|eS|f

解答:

fafbf是文法G[S]的一个句子，并且有两个不同的最右推导。

（1）S=>SaS=>SaSbS=>SaSbf=>Safbf=>fafbf

（2）S=>SbS=>Sbf=>SaSbf=>Safbf=>fafbf

因此说明此文法有二义性。

35）在属性文法中，综合属性与继承属性是如何传递信息的？

解答:

综合属性用于自下而上传递信息，继承属性用于自上而下传递信息。

36）代码优化的主要目标是什么？

解答:

代码优化的主要目标是如何提高目标程序的运行速度和如何减少目标程序运行时所需的空间。

37）写一个文法，使其语言是无符号二进制实数（不含指数）。

解答:

文法G（N）：

　　　　　　N→L.L|L

　　　　　　L→LB|B

　　　　　　B→0|1

三．应用题

1）消除下列文法G[A]的左递归。

E→E-T∣T

T→T/F∣F

F→（E）∣i

解答：

消除文法G[E]的左递归后得到：

E→TE′

E’→-TE′∣ε

T→FT′

T’→/FT′∣ε

F→（E）∣i

2）消除下列文法G[A]的左递归。

A→AaB∣B

B→BbC∣C

C→eD∣D

D→（A）∣d

解答：

消除文法G[A]的左递归后得到：

A→BAˊ

Aˊ→aBAˊ∣ε

B→CBˊ

Bˊ→bcBˊ∣ε

C→eD∣D

D→（A）∣d

3）给定下列自动机：

把此自动机转换为确定自动机DFA。

解答：

有状态矩阵如图：

从而可得DFA如图：

4）正规式（a|b）*a（a|b）构造一个等价的有限自动机。

解答：

四．设计题

（1）给定文法G[S′]及相应翻译方案为：

a.按chomsky分类法，文法G属于哪一型文法？

b.符号串ri,i,i是不是该文法的一个句型，请证实。

c.若是句型，写出该句型的所有短语、简单短语，以及句柄。

d.构造识别该文法的活前缀的DFA。

e.判断该文法是LR（0）还是SLR

（1），并构造其相应的语法分析表。

f.对于ri,i,i这个输入符号串，经该翻译方案翻译后的输出是什么？

解答：

a．文法G属于2型（上下文无关）文法。

b．符号串ri,i,i是该文法的一个句型。

证：

S'⇒S⇒rD⇒rD，i⇒rD，i，i⇒ri，i，i，得证。

或证：

构造语法树见图4，可知符号串ri,i,i是该文法的一个句型。

c．句型ri,i,i的短语有：

①ri,i,i；②i,i,i；③i,i；④第一个i

简单短语有：

第一个i

句柄有：

第一个i

d．求得文法G的识别全部活前缀的DFA见图3：

e．∵在项目集I4中存在冲突项目，∴文法G不是LR（0）文法。

FOLLOW（S'）={#}

FOLLOW（S）={#}

FOLLOW（D）={，,#}

而由于{，}∩FOLLOW（S）={，}∩{#}=Φ，所以文法G是SLR

（1）文法。

求得文法G的SLR

（1）分析表见表1：

f．可以先求得该句子的语法树（见图4），然后通过剪枝的方式进行归约，

最后归约到文法的开始符号，在归约的过程中同步产生输出符号串dccba。

即对于ri,i,i这个输入符号串，该翻译方案的输出是：

dccba

（2）给定文法:

（1）S→bTc

（2）S→a

（3）T→R

（4）R→R/S

（5）R→S

a）符号串ba/ac是不是该文法的一个句子，请证实。

b）若是句子，写出该句子的所有短语、简单短语和句柄。

c）为该文法设计翻译方案，使句型bR/bTc/bSc/ac经该翻译方案翻译后,输出下列串：

0342031320

解答：

a）符号串ba/ac是该文法的一个句子。

∵S⇒bTc⇒bRc⇒bR/Sc⇒bS/Sc⇒ba/Sc⇒ba/ac，

∴得证。

或：

给出符号串ba/ac的语法树如右图，则判定

符号串ba/ac是该文法的一个句子。

b）给出句型ba/ac的语法树如右图：

则可求得句型adbb的短语有：

ba/ac,a/a,第1个a,第2个a

简单短语有：

第1个a,第2个a

句柄有：

第1个a

c）给出句型bR/bTc/bSc/ac的语法树如右图：

按照归约过程，则给定文法的相应翻译方案为：

（1）S→bTc{print（“0”）}

（2）S→a{print（“1”）}

（3）T→R{print（“2”）}

（4）R→R/S{print（“3”）}

（5）R→S{print（“4”）}

（3）设有基本块：

t1:

=3*A

t2:

=2*C

t3:

=t1+t2

t4:

=t3+5

t5:

=2*C

t6:

=3*A

t7:

=t6+t5

E:

=t7-1

F:

=t4-E

a）画出DAG图；

b）假设基本块出口时只有E，F还被引用，请写出优化后的三地址代码序列。

解答：

a）构造DAG：

见右图。

b）优化后的三地址代码序列为：

t1:

=3*A

t2:

=2*C

t3:

=t1+t2

t4:

=t3+5

E:

=t3-1

F:

=t4-E

五．转换题：

给定下列中缀式（运算符优先级按常规理解），分别写出等价的逆波兰式和四元式。

1）a≤b∧a＞0∨b＜0

解答：

逆波兰式为：

ab≤a0＞∧b0＜∨

写出等价的四元式表示

1.（≤,a,b,T1）

2.（＞,a,0,T2）

3.（∧,T1,T2,T3）

4.（＜,b,0,T4）

5.（∨,T3,T4,T5）

2）―a＋b≤0∨a＜0∧（a―b）>2

解答：

逆波兰式为：

a―b＋0≤a0＜ab―2＞∧∨；

四元式为：

1.（,a,,T1）

2.（＋,T1,b,T2）

3.（≤,T2,0,T3）

4.（＜,a,0,T4）

5.（―,a,b,T5）

6.（＞,T5,2,T6）

7.（∧,T4,T6,T7）

8.（∨,T3,T7,T8）

《编译原理》习题

（一）——词法分析

一、是非题（请在括号内，正确的划√，错误的划×）

1．编译程序是对高级语言程序的解释执行。

（）

2．一个有限状态自动机中，有且仅有一个唯一的终态。

（）

3．两个正规集相等的必要条件是他们对应的正规式等价。

（）

4.对任何正规表达式e，都存在一个DFA　M，满足L（M）＝L（e）。

二、选择题

1．词法分析器的输出结果是_____。

　A．（）记号　　　　　　B．（）相应条目在符号表中的位置

　C．（）记号和属性二元组　　D．（）属性值

2．正规式M1和M2等价是指_____。

A．（）M1和M2的状态数相等 　　      B．（）M1和M2的有向边条数相等

　C．（）M1和M2所识别的语言集相等　　D．（）M1和M2状态数和有向边条数相等

3.编译过程可分为（），（），（），（），（）和（）六个阶段。

4．语言是

A．句子的集合B．产生式的集合

C．符号串的集合D．句型的集合

5．编译程序前三个阶段完成的工作是

A．词法分析、语法分析和代码优化

B．代码生成、代码优化和词法分析

C．词法分析、语法分析、语义分析和中间代码生成

D．词法分析、语法分析和代码优化

6．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即

A．字符B．单词C．句子D．句型

7．构造编译程序应掌握______。

A．（）源程序   　　　B．（）目标语言   

  C．（）编译方法    D．（）以上三项都是

8．词法分析的任务是

A．识别单词B．分析句子的含义

C．识别句子D．生成目标代码

三、填空题

1．计算机执行用高级语言编写的程序主要有两种途径：

和。

6.扫描器的任务是从（）中识别出一个个（）。

17.一张转换图只包含有限个状态,其中有一个被认为是（）态;而且实际上至少要有一个（）态。

1．编译程序首先要识别出源程序中每个（），然后再分析每个（）并翻译其意义。

3．通常把编译过程分为分析前端与综合后端两大阶段。

词法、语法和语义分析是对源程序的（），中间代码生成、代码优化与目标代码的生成则是对源程序的（）。

5．对编译程序而言，输入数据是（），输出结果是（）。

6.若二个正规式所表示的相同，则认为二者是等价的。

四、名词解释题：

1．词法分析

2.扫描器

4解释器

五、简答题

（一）、描述由正规式b*（abb*）*（a|ε）定义的语言，并画出接受该语言的最简DFA。

答：

（二）、描述由正规式b*a（bb*a）*b*定义的语言，并画出接受该语言的最简DFA。

答：

（三）.一字母表Σ={a,b}，试写出Σ上所有以a为首的字组成的正规集相对应的正规式。

答：

（四）.令Σ={a,b}，则正规式a*b|b*a表示的正规集是什么？

答：

（五）、构造下列正规式相应的DFA（用状态转换图表示）

（1）0（0|1）*1

（2）0*10*10*10*1

（3）letter（letter|digit）*

答：

（1）

（2）

（3）

（六）．设有非确定的有自限动机NFAM=（{A，B，C}，{0，1}，δ，{A}，{C}），其中：

δ（A，0）={C}δ（A，1）={A，B}δ（B，1）={C}δ（C，1）={C}。

请画出状态转换距阵和状态转换图。

解：

（七）．编译程序和高级语言有什么区别?

（八）．编译程序的工作分为那几个阶段?

（九）、有穷自动机M接受字母表∑＝{0,1}上所有满足下述条件的串：

每个1都有0直接跟在右边。

构造一个最小的DFAM及和M等价的正规式。

（十）、证明正规式（ab）*a与正规式a（ba）*等价（用构造他们的最小的DFA方法）。

【答案：

】

（十一）、设∑={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。

（8分）

答：

构造相应的正规式：

（3分）

NFA:

（2分）

确定化：

（3分）

（十二）、处于/*和*/之间的串构成注解，注解中间没有*/。

画出接受这种注解的DFA的状态转换图。

（十三）设有字母表{a，b}上的正规式R=（ab|a）*。

构造NFA，确定化，化简

解：

（1）

（2）将

（1）所得的非确定有限自动机确定化

a

b

-+013

123

+123

123

13

+13

123

（3）对

（2）得到的DFA化简，合并状态：

（十四）、给定文法G[S]：

S→aA|bQ；A→aA|bB|b；B→bD|aQ；Q→aQ|bD|b；D→bB|aA；E→aB|bF

F→bD|aE|b

构造相应的最小的DFA。