编译原理期末试卷(含答案)

《编译原理期末试卷(含答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理试题计算机学院2001级班学号姓名题号一二三四五六七八九十十一十二总分满分126878812127668100得分一选择题（12分）【】1．词法分析器的输入是。A．符号串B．源程序C．语法单位D．目标程序【】2．两个有穷自动机等价是指它们的。A．状态数相等B．有向弧数相等C．所识别的语言相等D．状态数和有向弧数相等【】3．文法G：S→xSx

2、y所识别的语言是。A．xy*xB．(xyx)*C．xx*yxx*D．x*yx*【】4．设a,b,c为文法的终结符，且有优先关系aºb和bºc，则。A．必有aºcB．必有cºaC．必有bºaD．选项A、

3、B和C都不一定成立【】5．若状态k含有项目“A→α.”，且仅当输入符号a∈FOLLOW(A)时，才用规则“A→α”归约的语法分析方法是。A．ALR分析法B．LR(0)分析法C．LR(1)分析法D．SLR(1)分析法【】6．生成中间代码时所依据的是。A．语法规则B．词法规则C．语义规则D．等价变换规则【】7．表达式（┐a∨b）∧（c∨d）的逆波兰表示为。A．┐ab∨∧cd∨B．a┐b∨cd∨∧C．ab∨┐cd∨∧D．a┐b∨∧cd∨【】8．基本块。A．只有一个入口语句和一个出口语句B．有一个入口语句和多个出口语句C．有多个入口语句和一个出口语句D．

4、有多个入口语句和多个出口语句二判断题（6分。认为正确的填“T”，错的填“F”）【T】1．同心集的合并有可能产生“归约/归约”冲突。【T】2．一个文法所有句子的集合构成该文法定义的语言。【】3．非终结符可以有综合属性，但不能有继承属性。【T】4．逆波兰表示法表示表达式时无需使用括号。【】5．一个有穷自动机有且只有一个终态。【】6．若过程p第k次被调用，则p的DISPLAY表中就有k+1个元素。三填空题（8分）1．最常用的两类语法分析方法是自顶向下　　　和　　自低向上　分析法。2．对于文法G[E]：E→T

5、E+TT→F

6、T*FF→P↑F

7、PP→(E)

8、

9、i,句型T+T*F+i的直接短语为　　　，句柄为　　　。3．在LR(0)分析法中，若a,βÎV*且aÎ则称“A®a.”为　规约　　项目，称“S®a.aβ”为　　移进　项目。4．在PL/0的目标代码解释执行时，寄存器B总是指向当前执行过程活动记录的　起始地址　　，而寄存器T总是指向　栈顶　　。四（7分）有穷自动机M接受字母表S＝{0,1}上所有满足下述条件的串：串中至少包含两个连续的0或两个连续的1。请写出与M等价的正规式。五（8分）构造下列文法相应的有穷自动机。G[S]：S→aA

10、bQA→aA

11、bB

12、bB→bD

13、aQQ→aQ

14、bD

15、bD→bB

16、

17、aAE→aB

18、bFF→bD

19、aE

20、b六（8分）写一个文法，使其语言是：L＝{ambmanbn

21、m,n≥0}七（12分）已知文法G[A]：A→aAB

22、aB→Bb

23、d（1）构造与G[A]等价的LL(1)文法；（2）构造G’[A]的预测分析表。八（12分）考虑文法G[S]:S→AS

24、bA→SA

25、a（1）构造文法的可归前缀图（活前缀的DFA）；（2）判断文法是否是LR(0)文法，并说明理由。九（7分）将下面程序段翻译成四元式序列。while　A

26、以下程序段programmain;vara,b:integer;procedurep(x,y,z:integer);beginy:=y+1;z:=z+xend;begina:=2;b:=3;p(a+b,a,a);write(a)end.对于下列参数传递方式，分别写出执行程序后a的输出值。（1）传名；（2）传地址。十一（6分）有一语法制导翻译如下所示：S→bAb{print(”1”)}A→(B{print(”2”)}A→a{print(”3”)}B→Aa){print(”4”)}若对输入序列b(((aa)a)a)b进行自底向上分析，请写出输出序列。

27、34242421十二（8分）对PL/0语言扩充ELSE子句:<条件语句>::=IF<条件>THEN<语句>[ELSE<语句>]请在空缺处填空，完成条件语句的编译算法：switch(SYM){……caseIFSYM:GetSym();CONDITION(SymSetUnion(SymSetNew(THENSYM),FSYS),LEV,TX);if(SYM==THENSYM)GetSym();elseError(16);CX1=CX;GEN(JPC,0,0);STATEMENT(SymSetUnion(SymSetNew(ELSESYM),FSYS)

28、,LEV,TX);if(SYM!=ELSESYM)CODE[CX1].A=CX;else{CX2=CX;GEN(JMP,0,0);COD