编译原理试题A及答案

编译原理试题A

阳4

一、单项选择题(每题1分，共20分)

1、哪个不是编译系统的组成局部1C)

A.词法分析器B.代码生成器

C.设备管理程序D.语法分析器

2.设有表达式a*b-c,将其中a*b识别为表达式的编译阶段

是什么

(B)

A.词法分析B.语法分析

C.语义分析D.代码生成

3.下面不能用于对文法进展描述的是(A)

A.源语言B.EBNFC.BNFD.语法图

4.设有文法G[S]:S->Sl|SO|Sa|Sc|a|b|c,以下符号串中

不是该文法的句子的是

(A)

A.abOB.aOcOlC.aaaD.bclO

5.文法G[S]:

S-aA

A-bB

Bf4|aS,那么L(G)为(C)

A.{(ab)na|n^l}B.{d(bd)n|n^l}

C.{(aba)n|n1}D.{(aba)"|n^O}

6.哪个不是DFA的构成成分(B)

A.有穷字母表B.初始状态集合

C.终止状态集合D.有限状态集合

7.词法分析器的输入是

(B)

A.单词符号串B.源程序C.语法单位D.目标程序

8.在词法分析阶段不能识别的是(C)

A.标识符B.运算符C.四元式D.常数

9.设有一段C语言程序

while(i&&++j)

c=2.19;

j+=k;

i++；

),经过词法分析后可以识别的单词个数是

(B)

A.19B.20C.21D.23

10.自上而下语法分析的主要动作是

(B)

A.移进B.推导C.规约D.匹配

11.下面不属于LL⑴分析器的组成局部是

⑴)

A.LL(1)总控程序B.LL(1)分析表

C.分析栈D.源程序串

12.设有文法G[S]为

S->AB|bC,A-£|b,B一£IaD,C->AD|b,D-*aS|c

那么FOLLOW(A)为(A)

A.{a,c,#}B.{c,#}C.{a,#}D.{#}

13.设有文法G[S]:

S->Ap|Bq,A-a|cA,B-b|dB,那么FIRST(Ap)为(C)

A.{p,q}B.{b,d}C.{a,c}D.其他

14.自下而上语法分析的主要分析动作是⑴)

A.推导B.规约C.匹配D.移进-规约

15.算法优先分析中，可规约串是［C)

A.句柄B.活前缀C.最左素短语

D.素短语

16.设有文法G={{S},{a},{S-SaSl£},S},该文法是(B)

A.LL(1)文法B.二义性文法

C.SLR(1)文法D.算法优先文法

17、中间代码生成时所以据的是(C)

A.语法规则B.词法规则C.语义规则

D.等价变换规则

18、给定文法G:E-E+T|T,TT*F|F,Ff|(E)

那么L(G)中的一个句子i+i+(i*i)*i的逆波兰表示为©

A.iii*i++B.ii+iii**+C.ii+ii*i*+D.其他

19.在编译程序中及生成中间代码的目的无关的是(B)

A.便于目标代码优

化B.便于存储空间的组织

C.便于目标代码的移植D.便于

编译程序的移植

20.中间代码是介于源语言程序和什么之间的一种代码⑴）

A.源代码B.机器语言C.汇编语言D.目标代码

殂4

二.简答（每题3分，共12分）

1.什么是编译程序？

编译程序是将源语言程序翻译为目标语言程序的程序。

2.词法分析器的主要任务是什么？

词法分析器的主要任务是逐步扫描和分解构成源程序的字

符串，识别出一个一个的单词符号。

3.有限自动机有哪几局部组成？

有限自动机是一个五元组，由非空的有限状态集、输入字母

表、状态转换函数、唯一的起始状态和承受状态集组成。

4.语法分析的根本任务是什么？

在词法分析的根底上，根据语言的语法规则把单词符号串

分解成各类语法单元。

坦三、解答题（本大题共6小题，每题4分，共24分）

L写正则式：所有小写字母a开头和结尾的串。

a(ab|•••|z)*a

nn

2.构造有限自动机M,使得：L(M)={ab|n^l}o

应是L(M)={arb\n,ni21}

3.给定文法G[S]:S-aAcB|BdS,B->aScA|cAB|b,A一

BaB|aBc|a,试检验aacbccb是不是其句子。

不是其句子

4.文法G[S]:SfAc|aB,A-*ab,B->bc,写出L(G)的全部元

素。

L(G)={abc}

题目应该是写出文法的全部元素：开场符号：S；V尸

{a,b,c);VN={S,A,B};P={S->Ac,S->aB,A->ab,B->bc}

5.把以下表达式变换成后缀表达式：(x:=x+3)*4

xx3+:=4*

6.把以下表达式变换成后缀表达式：(notAandB)or(C

ornotD)

AnotBandCDnotoror

阳H国题(本大题共5小题，每题6,共30分)

1.设文法G[E]:E->E+T|E-T|T,T->T*F|T/F|F,F->FtP|P,

P-(E)|i,求T*(T-i)+P的短语、直接短语、素短语和句柄。

短语T,i,T-i,(T-i),T*(T-i),P,T*(T-i)+P

直接短语T,i,P

素短语i

句柄T

2.对文法G[R]:RfR'I'T|T,T->TF|F,F->F*|C,C->

(R)|a|b,消除文法左递归。

RTR；R—「TR11e,T-FT1,T-FT11e,F-CF1,F^^F11

£,C-(R)|a|b

3.给定程序：

voidfun(intx,inty)

x++;y++;

main()

intx=0;

fun(x,x);

printf(x);

调用函数fun时，假设参数传递机制是1）按值传递，那么

输出结果为多少?

2)按引用传递，那么输出结果为多少？

3)按值-结果传递，那么输出结果为多

少？

答：1)按值传递，输出0

2)按引用传递，输出2

3)按值-结果传递，输出1

4.把以下表达式翻译成二地址代码：i:=(j+k)*(10+m)c

tl:=j+k

t2:=10+m

i:=tl*t2

5.文法G的EBNF表示为：

A-[B,B->X]{A},X->(a|b){a|b},试用C语言写出其递

归下降子程序。

A-[B,B->X]{A},X-(a|b){a|b}即

A-[B

B-X]{A}

Xf(a|b){a|b}

可以先变换：B-X]{[B}

AO

{if(sym='['){scaner();B();}

elseerror();

B()

{X();

if(sym==,]9{scaner();

while(sym==,[')

{scaner();B();}

}elseerror();

x()

{if(sym==,a'){scanner();}

elseif(sym-,b9{scanner();}elseerror();

while(sym==,aorsym==,b')

scanner();}

阳4题（本大题共2小题，每题7分，共14分）

1.将以下NFA确定化，并画出最小化的DFA。

输入a输入b

{0}(0,1)⑴

{1}{0,1}{1}

(0,1}{0,1}⑴

{0}{1,2}f(l,a)=2f(2,a)=2f(l,b)=lf(2,b)=l

{1,2}等价

始4

2.给定文法G