计算机编译原理练习题

编译原理练习题一

一、选择题

n

1. 下列文法中, 不是产生语言 {aba∣n≥1} 的文法。

A.A→aBa B→b∣bB B.A→aB B→ba∣bB C.A→aB B→ba∣bBa D.A→aB B→bC C→bC∣a 2. 设有文法G[S]:S→aAB A→bAc∣ε B→bB∣Ae∣ε

则经消去ε-产生式后与G等价的文法G1[S]为 。 A.S→aA∣aB∣aAB∣a A→bc∣bAc B→bB∣Ae∣b∣e B.S→aAB A→bAc B→bB∣Ae C.S→aA∣aB A→bc B→b∣e

D.S→aA∣aB∣a A→bc∣bAc B→bB∣Ae∣b∣e 3. 下列文法中, 是LL(1)文法。

A.S→bBS′a S′→aBS′∣ε A→S∣a B→Ac B.S→bS∣bA∣b A→aA∣a C.E→E+T∣T T→T*F∣F F→(E)∣i

D.S→bBS′ S′→aBS′∣ε A→S∣a B→Ac 4. 下列文法中, 是简单优先文法。

A.E→E+T∣T T→T*F∣F F→(E)∣i B.S→A/ A→aA∣AS∣/ C.E→E+E∣E*E∣(E)∣i

D.E→E1 E1→E1+T1∣T1 T1→T T→T*F∣F F→(E)∣i

5. 当扫视到数组说明进行语义处理时,必须把一个数组的如维数、各维的上、下界等记录下来。为了便于引用,通常是把上述内容存放于数组相应的 之中。 A.信息向量 B.内情向量 C.地址向量 D.指针向 6. 设有文法G[S]: S→aS∣W∣U U→a V→bV∣ac W→aW

则经化简后与G等价的文法G1[S]为 。 A.S→aS∣W V→bV∣ac W→aW B.S→aS∣U U→a

C.S→aS∣W∣U U→a W→aW D.S→aS V→bV∣ac

7. 下列文法中, 是LL(1)文法。

A.S→aS∣aA A→bA∣ac B.S→AS∣b A→SA∣a

C.E→E+E∣E*E∣(E)∣i

D.S→aS∣bA A→bA∣ac

8. 所谓相容,是指在一个项目集中,不出现这样的情况, 和归约项目并存,或多个归约项目并存。

A.移进项目 B.基本项目 C.待约项目 D.后继项目 9. 下列表示中, 不是目前经常使用的中间语言的形式。

A.逆波兰式 B.四元式 C.五元式 D.树形表示

10. 如果从流程图的首结点到流程图中某一结点n的所有通路都要经过结点d,我们就说结点d控制了结点n,或者把d称为n的必经结点,记作 。 A.d DFA n B.d DOM n C.d DAG n D.d DAM n 二、证明题

1、试证明文法 S→aB∣bA A→aS∣bAA∣a B→aBB∣bS∣b 为二义性文法。

三、简答题

对于如下文法,求各候选式的FIRST集和各非终结符号的FOLLOW集。

S→ACAB|bA|ε A→aAd|e B→bB|c C→cC|

四、应用题

1、对于如下的状态转换矩阵

分别画出相应的状态转换图;(10分) (2) 写出相应的3型文法。 2、将如图所示的DFA最小化。

五、应用题

1、设有文法G[E]: E→E+T|T T→T*F|F F→(E)|i

其相应的算符优先矩阵如下图所示,试给出对符号串i*i+i进行算符优先分析的过程。

( i * + ) # 2、

试描述由文法:S→aAd A→aAd∣bBc B→bBc∣e 所产生的语言。 六、应用题

1、设有文法G[S]: S→aABb A→Acd∣d B→Bce∣e (1) 将其改写为LL(1)文法; (2) 构造改写后文法的LL(1)分析表。

2、已知文法G[S]:S→aAB A→bA∣a B→cB∣b 的LR(0)项目集及状态转换图如下图所示,

(1) 构造LR(0)分析表; (2) 给出对输入符号串abacb的LR分析过程。

( < ○ < ○< ○ < ○i < ○ < ○< ○ < ○* < ○> ○> ○< ○> ○< ○+ < ○> ○> ○> ○> ○< ○) = ○> ○> ○> ○> ○ # > ○> ○> ○> ○ I0: S’→·SS→·aABaI2: S→a·ABaA→·bAA→·abI4: A→b·AA→·bAA→·aaI5: A→a·SI1: S’→S ·AI3: S→aA·BB→·cBB→·bbBcI6: S→aAB·cI7: B→c·BB→·cBbB→·bBbAI8: B→b·I9: A→bA·I10: B→cB·

七、简答题

1、设有二维PASCAL数组A[1··10, 1··20],给出赋值语句 A[I,J]:=X+Y*Z 的四元式序列。

2、将逆波兰式: ABCD/-*EF*+ 改写为中缀式。 八、简答题

1、设有如下的三地址码(四元式)序列:

A:=5 I:=1 J:=2

L1 : if I≤J goto L3 X:=I*A

L2 : I:=I-J

if I>J goto L2 J:=J+1 I:=N goto L1

L3: X:=J*A

试将它划分为基本块,并作控制流程图。

联系客服:779662525#qq.com(#替换为@)