计算机编译原理练习题

《计算机编译原理练习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理练习题一一、选择题1.下列文法中，不是产生语言{abna∣n≥1}的文法。A．A→aBaB→b∣bBB．A→aBB→ba∣bBC．A→aBB→ba∣bBaD．A→aBB→bCC→bC∣a2.设有文法G[S]：S→aABA→bAc∣εB→bB∣Ae∣ε则经消去ε-产生式后与G等价的文法G1[S]为。A．S→aA∣aB∣aAB∣aA→bc∣bAcB→bB∣Ae∣b∣eB．S→aABA→bAcB→bB∣AeC．S→aA∣aBA→bcB→b∣eD．S→aA∣aB∣aA→bc∣bAcB→bB∣Ae∣b∣e3.下列文法中，是LL(1)文法。A．S→bBS′aS′→aBS′∣εA→S∣

2、aB→AcB．S→bS∣bA∣bA→aA∣aC．E→E+T∣TT→T*F∣FF→(E)∣iD．S→bBS′S′→aBS′∣εA→S∣aB→Ac4.下列文法中，是简单优先文法。A．E→E+T∣TT→T*F∣FF→(E)∣iB．S→A/A→aA∣AS∣/C．E→E+E∣E*E∣(E)∣iD．E→E1E1→E1+T1∣T1T1→TT→T*F∣FF→(E)∣i5.当扫视到数组说明进行语义处理时，必须把一个数组的如维数、各维的上、下界等记录下来。为了便于引用，通常是把上述内容存放于数组相应的之中。A．信息向量B．内情向量C．地址向量D．指针向6.设有文法G[S]：S→aS∣W∣UU→aV→

3、bV∣acW→aW则经化简后与G等价的文法G1[S]为。A．S→aS∣WV→bV∣acW→aWB．S→aS∣UU→aC．S→aS∣W∣UU→aW→aWD．S→aSV→bV∣ac7.下列文法中，是LL（1）文法。A．S→aS∣aAA→bA∣acB．S→AS∣bA→SA∣aC．E→E+E∣E*E∣(E)∣iD．S→aS∣bAA→bA∣ac8.所谓相容，是指在一个项目集中，不出现这样的情况，和归约项目并存，或多个归约项目并存。A．移进项目B．基本项目C．待约项目D．后继项目9.下列表示中，不是目前经常使用的中间语言的形式。A．逆波兰式B．四元式C．五元式D．树形表示10.如果从流程图的

4、首结点到流程图中某一结点n的所有通路都要经过结点d，我们就说结点d控制了结点n，或者把d称为n的必经结点，记作。A．dDFAnB．dDOMnC．dDAGnD．dDAMn二、证明题1、试证明文法S→aB∣bAA→aS∣bAA∣aB→aBB∣bS∣b为二义性文法。三、简答题对于如下文法，求各候选式的FIRST集和各非终结符号的FOLLOW集。S→ACAB

5、bA

6、εA→aAd

7、eB→bB

8、cC→cC

9、四、应用题1、对于如下的状态转换矩阵分别画出相应的状态转换图；（10分）(2)写出相应的3型文法。2、将如图所示的DFA最小化。五、应用题1、设有文法G[E]：E→E+T

10、TT→T*F

11、F

12、F→(E)

13、i其相应的算符优先矩阵如下图所示，试给出对符号串i*i+i进行算符优先分析的过程。(i*+)#(i*+)#2、试描述由文法：S→aAdA→aAd∣bBcB→bBc∣e所产生的语言。六、应用题1、设有文法G[S]：S→aABbA→Acd∣dB→Bce∣e(1)将其改写为LL(1)文法；(2)构造改写后文法的LL(1)分析表。2、已知文法G[S]：S→aABA→bA∣aB→cB∣b的LR(0)项目集及状态转换图如下图所示，(1)构造LR(0)分析表；(2)给出对输入符号串abacb的LR分析过程。七、简答题1、设有二维PASCAL数组A[1··10,1··20]，给出赋值

14、语句A[I,J]:=X+Y*Z的四元式序列。2、将逆波兰式：ABCD/-*EF*+改写为中缀式。八、简答题1、设有如下的三地址码（四元式）序列：A:=5I:=1J:=2L1:ifI≤JgotoL3X:=I*AL2:I:=I-JifI>JgotoL2J:=J+1I:=NgotoL1L3:X:=J*A试将它划分为基本块，并作控制流程图。2、设有如下的三地址码（四元式）序列：I:=1readL,ML1：ifI>10gotoL2A:=L*MB:=L*IC:=M*AD:=M+BI:=I+1gotoL1L2：halt对其中的循环进行循环不变运算外提的优化。编译原理练习题二一、选择题1.文法G

15、产生的的全体是该文法描述的语言。A．句型B.终结符集C.非终结符集D.句子2.设M为一DFA，并设s和t是M的两个不同状态。如果s和t，则称s和t等价。A．不可区分B．可划分C．可区分D．待区分3.下列说法中正确的是。A.所谓递归下降法，是指只能对具有左递归性的文法进行分析的一种语法分析方法。B.如果一个文法具有二义性，则它必然不是LL(1)文法。C.对于文法G，当进行自顶向下的语法分析时，不会出现回溯的主要条件是，对于G中的每个A∈VN，A产生式的所有不同候选式均能推导出以同一