资源描述：
《编译原理试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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可能唯一，
2、好可能不唯一5．数组的内情向量中肯定不含有数组的⑻的信息A．维数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．什么是活动记录？它主要由哪些内容构成？三、（8分）化简文法G[S
3、]：S→ASe
4、BCaD
5、aD
6、ACA→Cb
7、DBSC→bC
8、dB→AcD→aD四、（12分）设Lí{a,b,c}*是满足下述条件的符号串构成的语言：(1)若出现a，则其后至少紧跟两个c；(2)若出现b，其后至少紧跟一个c。试构造识别L的最小化的DFA，并给出描述L的正规表达式。五、（12分）已给文法G[S]：S→SaP
9、Sf
10、PP→qbP
11、q将G[S]改造成LL（1）文法，并给出LL（1）分析表。六、（12分）给定文法G[S]：S→Aa
12、dAb
13、Bb
14、dBaA→cB→c构造文法G[S]的LR（1）分析表。七、（8分）将下面的条件语句表示成逆波兰式和四元式序列：ifa>bthenx:=
15、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
16、γ2
17、…
18、γm，其各候选式均应满足：（1）不同的候选式不能推出以同一终结符号打头的符号串，即FIRST(γi)∩FIRST(γj)=φ（1≤i，j≤m；i≠j）（2）若有γjε，则其余候选式γi所能推出的符号串不能以FOLLOW(A)中的终结符号开始，即有FIRST(γi)∩F
19、OLLOW(A)=φ（i≤1,2,…,m；i≠j）2．有三种分配存储空间的方式：（1）静态分配若在编译阶段就能确定源程序中各个数据实体的存储空间大小，则可以采用较简单的静态存储管理。适合静态管理的语言应具备条件：数组上下界是常数、过程调用不允许递归、不允许动态建立数据实体。（2）栈式分配适用于允许递归调用的程序设计语言；（3）堆式分配对于允许程序在运行时为变量动态申请和释放存储空间的语言，采用堆式分配是最有效的解决方案。3．不变运算外提；运算强度削弱；消除归纳变量；下标变量地址计算优化。4．一个过程的一次执行所需信息的管理，是通过称为活动记录的连续存储块来实现的。活动记录的主要内容有：
20、（1）临时变量域存放目标程序临时变量的值；（2）局部数据域存放过程本次执行时的局部数据、简单变量及数组内情向量等；（3）机器状态域保存在调用过程前有关机器状态的信息，包括各寄存器的当前值及返回地址等；（4）存取链为访问其它活动记录中所存放的非局部数据所提供的链地址；（5）控制链指向主调过程的活动记录；（6）实参存放主调过程为被调用过程所提供的实参信息；（6）返回值为主调过程存放被调过程的返回值三、化简后：S→ASe
21、ACA→CbC→bC
22、d四、DFA如图所示。相应的正规式为(c
23、acc
24、bc)*。五、改造后的文法：S→PS'S'→aPS'
25、fS'
26、eP→qP'P'→bP
27、e各候选式的F
28、IRST集，各非终结符的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)分析表为六、分析表如下图所示七、（1）逆波兰式：,其中，BLE表示汪或等于时的转向指令；[…]表示标号。（2）四元式：(1)(j>,a,b,(3))(2)(j,,,(7))(3)(*,b,c,T1)(4)(+,a,T1,T2
