编译原理期末考试试卷答案

2018～2019学年第1学期期末考试试卷答案

《编译原理》（共4页）

（考试时间：年月日）

一、选择题（每题1分，共10分）

1．将编译程序分为若干“遍”是为了B 。

A．提高程序的执行效率

B．使程序结构更加清晰

C．利用有限的机器内存并提高机器的执行效率

D．利用有限的机器内存但降低了机器的执行效率

2．构造编译程序应掌握D

A．源程序B．目标语言

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

3．文法G描述的语言L(G)是指 A 。

A．L(G)={α|S=>+α,α∈V T*} B．L(G)={α|S=>*α,α∈V N*} C．L(G)={α|S=>*α,α∈(V T∪V N)*} D．L(G)={α|S=>+α,α∈(V T∪V N )*}

4．编译程序绝大多数时间花在 D 上。

A．出错处理B．此法分析C．目标代码生成D．管理表格5． D 不可能是目标代码。

A．汇编指令代码B．可重定位指令代码

C．绝对指令代码D．中间代码

6．设G为算符优先文法，G的任意终结符对a、b，有以下关系成立Ｃ。A．若f(a)>g(b)，则a>b B．若f(a)

C．a~b都不一定成立D．a~b都一定成立

7．词法分析器的输入是Ｂ。

A．单词符号串B．源程序

C．语法单位D．目标程序

8．文法G：S→xSx|y所识别的语言是Ｃ。

A．xys B．(xyx)* C．x n yx n(n≥0) D．x*yx*

9．编译程序是对Ｄ。

A．汇编程序的翻译B．高级语言程序的解释执行

C．机器语言的执行D．高级语言的翻译

10．文法G[S]的产生式是：S→aB B→Aa B→b；那么G[S]是( Ｂ) A．正则文法B．上下文无关文法C．二义性文法

二、简答题（每题5分，共20分）

1．何谓二义性文法？试举一例说明。

答：若文法G的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是二义性的。产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。

例子：给定文法G[]：

→*||a|b

考察句子ab*，它有两棵不同的推导树，如下所示：

a

*

b

*

a b

2．通过合并LR(1)文法中的同心状态得到的LALR(1)文法可能会产生哪些冲突？一定不会产生哪些冲突？为什么？

答：可能会产生归约-归约冲突，一定不会产生移进-归约冲突。

因为在对LR(1)合并同心集合时，有可能将原本没有冲突的同心集的项目集合并后造成一些归约项目向前搜索符集合的交集不是空，产生归约-归约冲突。但是由于文法本身已经是LR(1)文法，因此可知，在项目集中一定不存在移进-归约冲突，也就是移进项目要求输入的终结符和任意归约项目的向前搜索符集合的交集都是空集。这样，在将同心集合并之后，移进项目要求输入的终结符和归约项目的向前搜索符集合的交集也还是空集。

3．自顶向下的预测分析方法为什么不能分析具有左递归的文法？

答：在自顶向下的语法分析技术中，要解决的问题是根据当前输入符号判断将识别符号以及非终结符号替换成哪条规则的右部，若文法具有左递归，则在分析过程中，无法判断替换的规则，造成无穷递归求解过程。

4．设G=（V N，V T，P，）是上下文无关文法，产生式集合P中任意一个产生式应具有什么样的形式？若G是正则文法呢？

答：上下文无关文法的产生式形式为：

A→α，其中，A∈V N，α∈（V N∪V T）*

正则文法产生式形式为：

A→aB，或A→a（右线性文法）其中，A,B∈V N，a∈V T

A→Ba，或A→a（左线性文法）其中，A,B∈V N，a∈V T

三、推导题（共70分）

1．对于文法G[S]：

S→aAcB|Bd A→AaB|c B→bScA|b

（1）求句型aAaBcbbdcc和aAcbBdcc的句柄。

（2）写出句子acabcbbdcc的最左推导过程（15分）

2. 构造一个NFA，

(1) 接受字母表{a,b,d}上的正规式b*(ad|d)(b|ab)+描述的集合。(5分)

(2) 将(1)中的NFA转换为等价的DFA (5分)

(3) 将(2)中的DFA转换为最小状态DFA（写出步骤）(5分)

3. 给出如下程序段的三地址代码。（10分）

z := 3;

while( j< 10)

{

j := x +1;

x := x+1 ;

m: = x+1;

if( x <10)

y:= A[i] +m

else y:= A[i] -m

n := z + 10;

}

答：

z:=3

Label Ltest

t1:= j<10

fjump t1 Lend1

j := x +1

x := x+1

m: = x+1

t2:= x<10

fjump t2 Lfalse

y:= A[i] +m

jump Lend2

Label Lfalse

y:= A[i]-m

Lable Lend2

n := z + 10

jump Ltest

Label Lend1

4. 用自底向上的语法分析方法分析数学公式编排预处理器EQN中的文法G[E]：

E→E sub E sup E

E→E sub E

E→E sup E

E→{E}

E→c

对于上述二义性文法G[E]，给出如下规则

(1) E→E sub E sup E是特例产生式。

(2) sub和sup具有相同的优先级

(3) sub和sup的结合顺序都是右结合的。

给出上述文法的语法分析表。（30分）