编译原理试题A及答案

编译原理试题A、单项选择题(每题1分，共20分)代码生成器语法分析器1、哪个不是编译系统的组成部分A.词法分析器 B.代码生成器语法分析器C.设备管理程序D.设有表达式a*b-c，将其中a*b识别为表达式的编译阶段是什么(B)A.词法分析 B. 语法分析C.语义分析 D. 代码生成(A(A)语法图A.源语言 B.EBNFC.BNFD.设有文法G[S]:S-S1|S0|Sa|Sc|a|b|c，下列符号串中不是该文法的句子的是A.ab0B.aOcO1C .aaaD.bc10(A)5.文法G[S]:SfaAA—bBBfa|aS,贝UL(G)为(C)A.{(ab)na|n>1}B.{a(ba)n|n>1}C.{(aba)n|n>1}D.{(aba)n|n>0}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.19 B.20C .21 D.2310•自上而下语法分析的主要动作是A.j+=k;i++；},经过词法分析后可以识别的单词个数是 (B)A.19 B.20C .21 D.2310•自上而下语法分析的主要动作是A.移进B.推导C.规约D.匹配(B)11.下面不属于LL(1)分析器的组成部分是 (D)A.LL(1)总控程序B.LL(1) 分析表C.分析栈 D. 源程序串12.设有文法G[S]为S—AB|bC,Ar|b,Bf|aD,C—AD|b,D^aS|c贝UFOLLOW(A为A.{a,c,#} B.{c,#}C .{a,#} D.{#}(A)13.设有文法G[S]:S—Ap|Bq,A—a|cA,B—b|dB,贝UFIRST(Ap)为A.{p,q}B.{b,d}C .{a,c}D.其他14.自下而上语法分析的主要分析动作是 (D)A.推导B.规约C.匹配D.移进-规约15.算法优先分析中，可规约串是A.句柄B .活前缀 C .最左素短语 D(C).素短语设有文法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.在编译程序中与生成中间代码的目的无关的是19.在编译程序中与生成中间代码的目的无关的是(B)A•便于目标代码优化的组织B•便于存储空间C•便于目标代码的移植D.便于编译程序的移植A•便于目标代码优化的组织B•便于存储空间C•便于目标代码的移植D.便于编译程序的移植20•中间代码是介于源语言程序和什么之间的一种代码(D)A.源代码B. 机器语言C.汇编语言D.目标代码.简答(每题3分，共12分)什么是编译程序？编译程序是将源语言程序翻译为目标语言程序的程序。2•词法分析器的主要任务是什么？词法分析器的主要任务是逐步扫描和分解构成源程序的字符串， 识别出一个一个的单词符号。有限自动机有哪几部分组成？有限自动机是一个五元组，由非空的有限状态集、输入字母表、状态转换函数、唯一的起始状态和接受状态集组成。语法分析的基本任务是什么？在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单元。得分| 三、解答题(本大题共6小题，每小题4分，共24分)写正则式：所有小写字母a开头和结尾的串。*a(a|b|…|z)a构造有限自动机M使得：L(M)={anbn|n>1}。应是L(M)={anb]n,m>1}

给定文法G[S]:S—aAcB|BdS,4aScA|cAB|b,A—BaB|aBc|a,试检验aacbccb是不是其句子。不是其句子文法G[S]: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}把下列表达式变换成后缀表达式：（x:=x+3）*4xx3+:=4*把下列表达式变换成后缀表达式：(notAandB)or(CornotD)AnotBandCDnotoror四、求解题（本大题共5小题，每小题6,共30分）设文法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*(T-i),P,T*(T-i)+P短语T,i,T-i,（T-i）直接短语T,i,P素短语,T*(T-i),P,T*(T-i)+P句柄T对文法G[R]:R-R'I'T|T,T-TF|F,F-F*|C,C^(R)|a|b，消除文法左递归。R—TR,R1—'|'TR|£,T—FT,T1—FT|&,F—CF,F1—*F1|£,C-(R)|a|b给定程序：voidfun(intx,inty){x++;y++;}main(){intx=0;fun(x,x);printf(x);}调用函数fun时，若参数传递机制是1)按值传递，那么输出结果为多少？2 )按引用传递，那么输出结果为多少？3 )按值-结果传递，那么输出结果为多少？答：1)按值传递，输出02)按引用传递，输出23)按值-结果传递，输出1把下列表达式翻译成三地址代码：i:=(j+k)*(10+m)。t1:=j+kt2:=10+mi:=t1*t2已知文法G的EBNF表示为：Af[B,B-X]{A},Xf(a|b){a|b}，试用C语言写出其递归下降子程序A—[B，BfX]{A}，Xf(a|b){a|b} 即Af[BBfX]{A}Xf(a|b){a|b}可以先变换：BfX]{[B}A(){if(sym=='[‘){scaner();B();}elseerror();}B(){X();if(sym==']‘){scaner();while(sym=='[‘){scaner();B();}}elseerror();}X(){if(sym=='a‘){scanner();}elseif(sym== 'b‘){scanner();}elseerror();while(sym=='a‘orsym=='b‘)

{seanner();}{seanner();}五、综合题（本大题共2小题，每小题7分，共14分）1.将下列NFA确定化，并画出最小化的DFA输入a输入输入a输入b{0} {0,1}{1}{1}{0,1}{1}{0,1}{0,1}{1}{0}{1,2}f(1,a)=2f(2,a)=2f(1,b)=1f(2,b)=1{1,2}等价给定文法G[S]:S—