编译原理试题汇总

《编译原理试题汇总》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、选择题（每个选择题2分，共20分）1．文法G产生的⑴的全体是该文法描述的语言。A．句型B.终结符集C.非终结符集D.句子2．若文法G定义的语言是无限集，则文法必然是⑵：A．递归的B前后文无关的C二义性的D无二义性的3．Chomsky定义的四种形式语言文法中，0型文法又称为⑶文法；1型文法又称为⑷文法；2型语言可由⑸识别。A．短语结构文法B前后文无关文法C前后文有关文法D正规文法E图灵机F有限自动机G下推自动机4．一个文法所描述的语言是⑹；描述一个语言的文法是⑺。A．唯一的B不唯一的C可能唯一，好可能不唯一5．数组的内情向量中肯定不含有数组的⑻的信息A

2、．维数B.类型C.维上下界D.各维的界差6．在下述的编译方法中，自底向上的方法有⑼，自顶向下的分析方法有⑽。①简单优先分析②算符优先分析③递归下降分析④预测分析技术⑤LR（K）分析⑥SLR（k）分析⑦LL（k）分析⑧LALR（K）分析A.③④⑦B.③④⑧C.①②⑧D.③④⑤⑥⑦E.①②⑤⑥⑦F.①②⑤⑥⑧二、简答题（每小题5分，共20分）1．LL（1）分析法对文法有哪些要求？2．常见的存储分配策略有几种？它们都适合于什么性质的语言？3．常见循环优化都有哪些项目？4．什么是活动记录？它主要由哪些内容构成？五、（12分）已给文法G[S]：S→SaP

3、Sf

4、P

5、P→qbP

6、q将G[S]改造成LL（1）文法，并给出LL（1）分析表。七、（8分）将下面的条件语句表示成逆波兰式和四元式序列：ifa>bthenx:=a+b*celsex:=b-a;八、（8分）给定基本块：A:=3*5B:=E+FC:=A+12D:=E+FA:=D+12C:=C+1E:=E+F假定出基本块后，只有A、C、E是活跃的，给出用DAG图完成优化后的代码序列。参考答案：一、⑴D⑵A⑶A⑷C⑸G.⑹A⑺B⑻A⑼F⑽A二、1．对于G中的每个产生式A→γ1

7、γ2

8、…

9、γm，其各候选式均应满足：（1）不同的候选式不能推出以同一终结符号打头的符号串，即FI

10、RST(γi)∩FIRST(γj)=φ（1≤i，j≤m；i≠j）（2）若有γjε，则其余候选式γi所能推出的符号串不能以FOLLOW(A)中的终结符号开始，即有FIRST(γi)∩FOLLOW(A)=φ（i≤1,2,…,m；i≠j）五、改造后的文法：S→PS'S'→aPS'

11、fS'

12、eP→qP'P'→bP

13、e各候选式的FIRST集，各非终结符的FOLLOW集为产生式FIRST集FOLLOW集S→PS'{q}{#}S'→aPS'→fS'→e{a}{f}{e}{#}P→qP'{q}{a,f,#}P'→bP→e{b}{e}{a,f,#}LL(1)分析表为七、（

14、1）逆波兰式：,其中，BLE表示汪或等于时的转向指令；[…]表示标号。（2）四元式：(1)(j>,a,b,(3))(2)(j,,,(7))(3)(*,b,c,T1)(4)(+,a,T1,T2)(5)(:=,T2,,x)(6)(j,,,(9))(7)(-,b,a,T3)(8)(:=,T3,,x)(9)(……)八、化简后的的四元式序列为A:=D+12E:=E+FC:=28二、填空题(每题2分，共20分)1、从功能上说，程序语言的语句大体可分为_______语句和______语句两大类。2、扫描器的任务是从________中识别出一个个_______。3、所谓

15、最右推导是指：_______。4、语法分析最常用的两类方法是________和_________分析法。5、一个上下文无关文法所含四个组成部分是_______________。6、所谓语法制导翻译方法是_____________________。7、符号表中的信息栏中登记了每个名字的有关的性质，如_________等等。8、一个过程相应的DISPLAY表的内容为________。9、常用的两种动态存贮分配办法是_____动态分配和_____动态分配。10、产生式是用于定义_____的一种书写规则。四、简述题(每题4分，共24分)1、考虑下面程序　　………

16、…　　Vara：integer；　　ProcedureS(X)；　　　VarX：integer；　　　Begin　　　　a：＝a＋1；　　　　X：＝a＋X　　　End；　　Begin　　　　a：＝5；　　　　S(a)；　　　　Print(a)　　End．试问：若参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？3、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。4、已知文法G(S)　　S→a

17、∧

18、(T)　　T→T，S

19、S　　写出句子((a，a)，a)的规范归约过程及每一步的句柄。五、计算题(共41分)1、写一个文法，使其语言

20、是奇数集，且每个奇数不以0开头。(5分)2、设文法G(S)：　　S→(L)

21、aS