编译原理试题A及答案

1、编译原理试题A、单项选择题(每题1分，共20 分)代码生成器 语法分析器1、哪个不是编译系统的组成部分 A.词法分析器B.C.设备管理程序 D.2. 设有表达式a*b-c，将其中a*b识别为表达式的编译阶段是什么(B )A.词法分析B.语法分析C.语义分析D.代码生成(A )语法图3. 下面不能用于对文法进行描述的是A.源语言B. EBNF C . BNF D.4. 设有文法GS: S-S1|S0|Sa|Sc|a|b|c ，下列符号串中不是该文法的句子的 是A. ab0 B. aOcO1C.aaa D. bc10(A )5.文法 GS:Sf aAA bBBf a|aS ,贝U L(G)为(C

2、)A. (ab) na|n 1B. a (ba)n|n 1C. (aba) n|n 1D. (aba)n|n 06.哪个不是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.20 C. 21D.2310自上而下语法分析的主要动作是A.移进 B. 推导 C .规约

3、D. 匹配(B )11.下面不属于LL(1)分析器的组成部分是(D )A. LL(1)总控程序 B. LL(1)分析表C.分析栈D.源程序串12.设有文法GS为S AB|bC, Ar |b , Bf |aD , C AD|b, DaS|c 贝U FOLLOW(A为A. a,c,#B.c,# C. a,#D.#(A )13.设有文法GS:S Ap|Bq, A a|cA , B b|dB,贝U FIRST(Ap)为A. p,q B. b,d C. a,c D.其他14.自下而上语法分析的主要分析动作是(D )A.推导 B. 规约 C .匹配 D. 移进-规约15.算法优先分析中，可规约串是A.句柄

4、 B.活前缀C.最左素短语D(C ).素短语16. 设有文法 G=S,a,S SaS| ,S,该文法是(B )A. LL(1)文法B.二义性文法C. SLR(1)文法D.算法优先文法17、 中间代码生成时所以据的是(C )A.语法规则 换规则B . 词法规则C .语义规则D.等价变18、给定文法 G: E E+T|T, T T*F|F , F i|(E)则L(G)中的一个句子i+i+(i*i)*i的逆波兰表示为(C)A. iii*i+ B . ii+iii*+C . ii+ii*i*+ D .其他19 .在编译程序中与生成中间代码的目的无关的是(B)A 便于目标代码优化 的组织B 便于存储空间

5、C 便于目标代码的移植D .便于编译程序的移植20中间代码是介于源语言程序和什么之间的一种代码(D)A.源代码 B.机器语言C.汇编语言 D.目标代码.简答(每题3分，共12 分)1. 什么是编译程序？编译程序是将源语言程序翻译为目标语言程序的程序。2词法分析器的主要任务是什么？词法分析器的主要任务是逐步扫描和分解构成源程序的字符串，识别出一个一个的单词符号。3. 有限自动机有哪几部分组成？有限自动机是一个五元组，由非空的有限状态集、输入字母表、状态转换函数、 唯一的起始状态和接受状态集组成。4. 语法分析的基本任务是什么？在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单元。

6、得分|三、解答题(本大题共6小题，每小题4分，共24分)1. 写正则式：所有小写字母a开头和结尾的串。*a(a|b| |z) a2. 构造有限自动机M使得：L(M)=a nbn|n 1。应是 L(M)=anbn,m 13. 给定文法 GS:S aAcB|BdS, 4aScA|cAB|b, A BaB|aBc|a ,试检验 aacbccb 是不是其句子。不是其句子4. 文法 GS:S Ac|aB, A ab, B be,写出 L(G)的全部元素L(G)=abc题目应该是写出文法的全部元素：开始符号：S；VT= a,b,c ;Vn=S,A,B；P= S Ac,S aB, A ab, B bc 5.

7、 把下列表达式变换成后缀表达式：（x:=x+3 ） *4xx3+:=4*6. 把下列表达式变换成后缀表达式：(not A and B) or (C or not D)A not B and C D n ot or or四、求解题（本大题共5小题，每小题6,共30分）1. 设文法 GE: E E+T|E-T|T , TT*F|T/F|F , FFT P|P, P (E)|i ，求 T*(T-i)+P的短语、直接短语、素短语和句柄。,T*(T-i), P,T*(T-i)+P短语 T,i, T-i ,（T-i） 直接短语T, i , P 素短语i句柄T2. 对文法 GR:R - R I T | T

8、, T- TF|F , F- F*|C , C (R)|a|b，消除文 法左递归。R TR,R1 | TR| , T FT,T1 FT| & , F CF, F 1*F1| , C-(R)|a|b3. 给定程序：void fun(int x,int y)x+;y+;main()int x=0;fun(x,x);printf(x);调用函数 fun 时，若参数传递机制是 1)按值传递，那么输出结果为多少？2)按引用传递，那么输出结果为多少？3)按值 - 结果传递，那么输出结果为多少？答： 1)按值传递，输出 02 )按引用传递，输出 23 )按值 - 结果传递，输出 14. 把下列表达式翻译成三

9、地址代码： i:=(j+k)*(10+m) 。t1:= j+kt2:=10+m i:=t1*t25. 已知文法G的EBNF表示为：A f B , B-XA , Xf (a|b)a|b，试用C语言写出其递归下降子程序A B，Bf XA，Xf (a|b)a|b即AfBBfXAXf(a|b)a|b可以先变换： BfX B A() if ( sym= ) scaner(); B(); else error();B() X();if(sym= ) scaner();while(sym= ) scaner();B(); else error();X()if(sym= a ) scanner();else if(sym=b ) scanner(); else error();while(sym= a or sym= b) sea nn er();五、综合题（本大题共2小题，每小题7分，共14分）1.将下列NFA确定化，并画出最小化的 DFA输入a 输入b00, 1 11 0,1 10, 1 0,1 10 1,2 f(1,a)=2 f(2,a)=2 f(1,b)=1 f(2,b)=11,2等价2. 给定文法 GS:S AS