编译原理练习题

一、填空题（每空1分）

1．设G［S］是一个文法，我们把能由文法的 开始符号s 推导出来的符号串α称为G的一个句型。当句型α仅由 终结符号 组成时 (即α∈VT)，则将它称为G产生的句子。

2．从某一给定的状态q出发，仅经过若干条 标记为 ε 的矢线所能达到的状态所组成的集合称为ε-CLOSURE(q)。

3．设G=(VN,VT,P,S)是一文法，我们说G中的一个符号X∈VN∪VT是有用的，是指X至少出现在 一个句子 的推导过程中，否则，就说X是无用的。我们将不含形如A→A的产生式和不含无用符号及无用产生式的文法称为 已化简的文法 。

4．我们常采用形如 (class, value)的二元式作为一个单词的 内部表示 。其中,class是一个整数，用来指示该单词的 类别 ，value则是单词之值。

5．一个文法G[S]可表示成形如 （ VN ，VT ，P,S ） 的四元式。其中VN,VT,P均为非空的有限集，分别称为非终结符号集、终结符号集和产生式集， S∈VN为文法的开始符号。此外，将出现在各产生式左部和右部的一切符号所组成的集合称为 字汇表 ，记作V。显然，V=VN∪VT,VN∩VT=。

6．通常，可通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义，用 手工的方式 构造词法分析程序；另外一种途径是所谓词法分析程序的 自动生成 。

7．设G为一文法，A→α是G的一个产生式，如果α具有υAδ的形式，其中υ，δ不同时为ε，则称产生式A→α是 直接递归的 。若存在推导A称产生式A→α是 递归的 。

8．设M=(K,Σ,f,S0,Z)为一DFA，并设s和t是M的两个不同状态，我们说状态s,t为某一输入串w 所区分 ，是指从s,t中之一出发，当扫视完w之后到达M的终态，但从其中的另一个状态出发，当扫视完同一个w后而进入 非终态 。

9．把最右推导称为 规范推导 ，而把右句型称为 规范句型 。

10．如果从状态转换图的初态出发，分别沿着一切可能的路径到达 终态结点 ，并

*

A*，则

将每条路径各矢线上的 标记字符 依次连接起来，便得到状态转换图所能识别的全部字符串，这些字符串所组成的集合也就是该状态转换图所识别的语言。

二、选择题（每空2分）

1. 下列文法中， C 不是产生语言 {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 。 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. 文法 G 产生的 D 的全体是该文法描述的语言。

A ．句型 B. 终结符集 C. 非终结符集 D. 句子

4. 设M为一确定有限自动机，并设s 和t是M的两个不同状态。如果s和t A ，则称s和t等价。

A．不可区分 B．可划分 C．可区分 D．待区分 5. 设有文法G[S]：

S→aS∣W∣U U→a V→bV∣ac W→aW

则经化简后与G等价的文法G1[S]为 B 。

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

6. 若文法 G 定义的语言是无限集，则文法G必然是 B 。

A．前后文无关的 B．递归的 C．二义性的 D．无二义性的

n

7. 下列说法中正确的是 A 。

A．一个确定的有限自动机实际上是相应的状态转换图的一种形式描述。

B．一个状态转换图是由一组矢线连接的有限个结点所组成的无回路有向图。 C．所谓一个DFA M状态数的最小化，是指构造一个与之等价的DFA M′，使它们有相同的接受集。

D．对于有同一接受集的FA，与之等价的DFA在同构意义下是唯一的。 8. 下列文法中， C 不是产生语言{a2n1n1} 的文法。

A．A→aBa B→a∣aBa B．A→aB B→aa∣Baa C．A→aAA A→a D．A→aBB B→a∣aBB

9. 如下的表示形式中，不能表示程序语言中单词结构的是 B 。

A．左线性文法 B．形如（Class，Value）的二元式 C．正规式 D．正规文法

三、证明题

1．试证明文法

S→aB∣bA A→aS∣bAA∣a B→aBB∣bS∣b 为二义性文法。 （10分）

2． 试证明文法: S→aAB A→aA∣a B→aB∣b 为二义性文法。 四、简答题

1．试构造一文法，使其描述如下语言： （15分）

L(G)={ anbmcmdn

∣m,n≥1 }

2．消除下列文法中的单产生式。 （10分）

S→AbB∣A A→AB∣caB∣B B→Aa∣b

3．对正规式((a∣b) *

∣ab*

)b ，构造与其相应的状态转换图。 （15分）

10分） （4．消除下列文法中的ε-产生式。 （10分）

S→ABb∣a A→aB∣caB∣ε B→aA∣b∣ε

5．试描述由下列文法所产生的语言。 （10分）

S→aAd A→aAd∣bBc B→bBc∣e

6． 消除下列文法中的单产生式。 （10分）

S→aFbM∣F F→M∣abc M→abF∣c

7．化简下列文法： （10分）

S→Bab∣cC B→bS∣b C→Da D8． 对正规式(a∣ab)*

ab*

，构造与其相应的状态转换图。9．试构造一正规文法，使其描述如下语言： （10分）L(G)={ abm

cbna∣m≥1, n≥0 }

10．试描述由下列文法所产生的语言。 （15分）

S→aAbB A→Aab∣ε B→aA∣aC C五、应用题

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

(1) 分别画出相应的状态转换图；（10分） (2) 写出相应的3型文法。 （10分） 2． 将如图所示的NFA确定化。 （20分）

→Cb∣CDa

15分） →cC∣d （

3． 将如图所示的具有ε动作的NFA确定化。 （20分）

4． 将如图所示的DFA最小化。 （20分）

5．将如图所示的DFA最小化。 （25分）

6．对于如下的状态转换矩阵

a b cAC B EB D C DD B E CE D初态: S 终态: D (1) 画出相应的状态转换图；（10分） (2) 写出相应的3型文法。 （10分） 7．设有如下正规文法G[S]：

S→aA∣aB A→bB∣b B→bB∣bC C→bC∣a

（1）构造与文法G[S]相应的状态转换图； （10分） （2）将所得的NFA确定化。 （15分） 8．将如图所示的NFA确定化。 （15分）

《编译原理》练习题二

一、填空题（每空1分，共10分）

1．所谓递归下降法，是指对文法的每一非终结符号，都根据相应产生式各候选式的结构，为其编写一个 (1) ，用来识别该非终结符号所表示的 (2) 。

2．在每一LR(0)项目［A→α·β］中放置一个 (3) a，使之成为［A→α·β,a］的形式，我们将此种项目称为一个 (4) 。

3．所谓 (5) ，就是对文法中的 (6) 都附加一个语义动作或语义子程序，且在语法分析过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应的 (7) 外，还要执行相应的语义动作或调用相应的语义子程序。

4．LL(1)分析表可用一个 (8) 表示，它的每一行与文法的一个非终结符号相关联，而其每一列则与文法的一个终结符号或 (9) 相关联。

5．若在一个文法G中，不含有形如 (10) 的产生式，其中A,B∈VN，则称G为算符文法。

6．将每一运算符都置于其 (11) 的表达式称为后缀表示，也称为逆波兰表示。 7．把流程图中具有如下性质的一组结点称为程序中的一个循环：(ⅰ) 在这组结点中，有惟一的 (12) ，使得从循环外到循环内任何结点的所有通路，都必通过此结点；(ⅱ) 这一组结点是 (13) 。

8．语法分析的基本任务是：根据语言的语法规则 (即根据描述该语言的前后文无关文法)，分析源程序的 (14) ，即分析如何由这些单词组成各种语法范畴，并在分析过程中，对源程序进行 (15) 。

9．所谓句型的素短语，是指一个句型中具有这样性质的短语：短语中至少含有一个 (16) ，且除它自身外，不再包含其它的 (17) 。

10．一个文法符号X的 (18) 我们称之为语义属性或简称为属性，用形如X.ATTR的记号来表示文法符号X的相关语义属性。

11．表示流程图中各结点间控制关系的一种直观而有效的方法是用树形结构，称之为 (19) 。

12．目前，已存在许多语法分析方面的方法。但就产生语法树的方向而言，可大致把它们分为 (20) 和 (21) 两大类。

13．将形如A→αX·β的项目称为A→α·Xβ的 (22) 。

14．记录和一个数组有关的信息，如维数n、各维的上、下界lk和uk的数据结构称为数组的 (23) 。

15．基本块是程序中具有下述性质的 (24) ：它有惟一的入口和惟一的出口，它们分别是块中的第1个操作和最末一个操作，且块中的各个操作按顺序执行，不出现 (25) 。

16．若一文法G的任何两个符号之间 (26) 一种优先关系，且任意两个不同的产生式均无 (27) ，则称G为简单优先文法。

17．把在数据区给变量分配的存储单元地址称为 (28) ，而把在目标程序运行时存放在相应单元中的值称为 (29) 。

18．如果从流程图的首结点到流程图中某一结点n的所有通路都要经过结点d，我们就说结点d控制了结点n，或者把d称为n的 (30) ，记作 (31) 。

二、选择题（每空2分）

1. 下列文法中， 是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 2. 下列文法中， 是简单优先文法。

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 3. 当扫视到数组说明进行语义处理时，必须把一个数组的如维数、各维的上、下界等记录下来。为了便于引用，通常是把上述内容存放于数组相应的 之中。

A．信息向量 B．内情向量 C．地址向量 D．指针向量 4. 下列说法中正确的是 。

A. 所谓递归下降法，是指只能对具有左递归性的文法进行分析的一种语法分析方法。 B. 如果一个文法具有二义性，则它必然不是LL(1)文法。

C. 对于文法G，当进行自顶向下的语法分析时，不会出现回溯的主要条件是，对于G中的每个A∈VN，A产生式的所有不同候选式均能推导出以同一终结符号开始的符号串。

D. 对任意非LL(1)文法而言，通过消除左递归和反复提取左因子，都能将其改造为LL(1)文法。

5. 简单优先分析每次归约的是 。

A. 最左直接短语 B.直接短语 C.最左素短语 D.控制结点 6. 下列表示中， 是与f×(e+(a×d+c)/d)相应的逆波兰式。

A．fead×c+d/+× B．f×e+a×d+c/d C．fad×+c/d+e× D．ad×c+d/e+f× 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 11. 下列说法中错误的是 。

A. 任何LL(1)文法都是无二义性的。 B. 左递归文法必然不是LL(1)文法。

C. 对于任意一个前后文无关文法G，都能为其构造一个无多重定义的预测分析表。 D. 如果文法是左递归的，则自顶向下的分析过程将不能正常地进行。 12. 如下的语法分析方法中， 要求文法中不含-产生式。

A．预测分析法 B．LR（1）分析法 C．递归下降分析法 D．算符优先分析法

13. 如下四元式中正确的是 。

A．（jnz， ， ，p） B．（j，A1，A2，p） C．（j<，A1，A2，p） D．（j，A1 ， ，p）

14. 如下的语法分析方法中， 属于自顶向下的语法分析方法。

A．LR（1）分析法 B．算符优先分析法 C．简单优先分析法 D．LL（1）分析法 15. 下列四元式中， 是变址取数四元式的形式。

A．（ =[ ]，X，0，T1[T] ） B．（ =[ ]，T1[T]，0，X ） C．（ [ ]=，T1[T]，X，0 ） D．（ [ ]=，X，0，T1[T] ） 16. 对基本块进行分析的一种有效数据结构是 。

A．DAG B．DOM C．DFA D．DAM

三、简答题

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

2．设有如下的三地址码（四元式）序列：

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

试将它划分为基本块，并作控制流程图。 （10分）

3． 消除下列文法的左递归性。 （10分）

S→aAc A→Bb∣a B→Ad∣c

4． 将下列中缀式改写为逆波兰式。 （10分）

A+B*(C-D)/(E+F)

5．将下列语句翻译成四元式序列。 （10分）

IF a6． 将下列语句翻译成四元式序列。 （10分）

while A0 do C:=C+B*D

7．设有文法G[Z]：

Z→ZAc∣Ba A→Ab∣a B→Bd∣c

将其改写为LL(1)文法。 （15分）

8．对于如下的程序，试对其中的循环进行削弱运算强度的优化。10分） （

(1) I:=1(2) read L,M(3) A:=L*MB1(4) if I>10 gotoB4(5) B:=M*I (6) C:=A*I(7) write C(8) I:=I+1(9) gotoB2B2B3(10) haltB4 9．对于如下文法，求各候选式的FIRST集和各非终结符号的FOLLOW集。 （共15分）

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

10．将下面的逆波兰式改写为中缀式。 （8分） ABCD/-*EF*+

11．设有如下的三地址码（四元式）序列：

I:=1

read L,M L1 ： if I>10 goto L2

A:=L*M B:=L*I C:=M*A D:=M+B I:=I+1 goto L1 L2 ： halt

(1) 将它划分为基本块，并作控制流程图； （6分）

(2) 对其中的循环进行循环不变运算外提的优化。 （6分）

12．将下列语句翻译成四元式序列。 （10分）

IF ad THEN b:=c+d*3 ELSE a:=a-c/d

13．将下列语句翻译成四元式序列。 （10分）

IF aELSE WHILE a<=d DO BEGIN a=a-2； d:=d+1 END

14．将下列逆波兰式改写为中缀式。 （10分）

AB+C*DEF*-/

15． 将下列语句翻译成四元式序列。 （10分）

while A<5∨B>0 do X:=A+B*C

16．对于如下的程序，试对其中的循环进行削弱运算强度的优化。（10分）

(1) I:=5(2) read J,K(3) A:=J*KB1(4) B:=J*I (5) C:=A*I(6) write B,C(7) I:=I+1(8) if I<30 gotoB2B2(9) haltB3

17．设有二维PASCAL数组A[1··10, 1··20, 1··30]，将下列语句翻译成四元式序列。（10分）

X := A[I+1,J*2,I] * B+C

18．对于如下的基本块，若变量G，L，M在基本块出口之后被引用： A:=B*C D:=5 E:=C/D F:=2*D G:=C/D H:=B*C L:=H*E M:=L

(1) 构造相应的DAG； （5分） (2) 重建经优化后的四元式序列。 （5分）

四、应用题

1．设有文法G[S]： S→aABb A→Acd∣d B→Bce∣e

(1) 将其改写为LL(1)文法； （10分） (2) 构造改写后文法的LL(1)分析表。 （10分）

2．设有文法G[E]：

E→E+T|T T→T*F|F F→(E)|i

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

( i * ( ＜ ○ ＜ ○i ＜ ○ ＜ ○* ＜ ○＞ ○＞ ○+ ＜ ○＞ ○＞ ○) ＝ ○＞ ○＞ ○# ＞ ○＞ ○+ ) # ＜ ○ ＜ ○＜ ○ ＜ ○＜ ○＞ ○＜ ○＞ ○＞ ○＜ ○＞ ○＞ ○ ＞ ○＞ ○ 文法G[E]的算符优先矩阵

3．设有文法G[S]： S→aAB A→bA∣a B→cB∣b

（1）构造此文法的LR(0)项目集及状态转换图； （15分） （2）构造LR(0)分析表。 （10分）

4．对于如图所示的控制流程图：

(1) 求出各个结点的必经结点集； （5分）

(2) 求出各个回边，并找出流程图的全部循环。 （5分）

1234657 5． 设有文法G[S]： S→aBc∣bAB A→aAb∣b B→b∣ε

(1) 构造该文法的LL(1)分析表； （10分）

(2) 分析符号串baabbb是否为该文法的句子。（15分）

6．设有文法G′[E]：

E→E1 E1→E1+T1|T1 T1→T T→T*F|F F→(E)|i

其相应的简单优先矩阵如下图所示，试给出对符号串i+i进行简单优先分析的过程。（20分）

E E1EE1T1TF+*()i

T1 T F + * ( ) i = ·= >··> >··> = >···> > >···= < < < <·····= < <···= < < < < < <·······> > >···> > >··· 7．对于如下的基本块，若变量G,M在基本块出口之后被引用： A:=B+C D:=3 E:=6 F:=D*E G:=B+C H:=A+D L:=H*F M:=L

(1) 构造相应的DAG； （5分） (2) 重建经优化后的四元式序列。 （5分）

8．设有文法G[S]：

S→ABAC A→aD B→b C→d D→c

（1）构造此文法的LR(0)项目集及状态转换图； （15分） （2）构造SLR(1)分析表。 （10分）

9．已知文法G[S]：

S→aAB A→bA∣a B→cB∣b

的LR(0)项目集及状态转换图如下：

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) 构造LR(0)分析表； （10分）

(2) 给出对输入符号串abacb的LR分析过程。 （15分）

10． 消除下列文法的左递归性。 （15分） Z→AaB A→Bb∣a B→Zd∣c

11．设有文法G′[E]：

E→E1 E1→E1+T1|T1 T1→T T→T*F|F F→(E)|i

其相应的简单优先矩阵如图所示，试给出对符号串i*i进行简单优先分析的过程。（20分）

E E1EE1T1TF+*()i

T1 T F + * ( ) i = ·= >··> >··> = >···> > >···= < < < <·····= < <···= < < < < < <·······> > >···> > >··· 12．对于如图所示的控制流程图： （共10分）

(1) 求出各个结点的必经结点集；

(2) 求出各个回边，并找出流程图的全部循环。

12345678 13．设有文法G[S]：

S→aAbDa∣d A→BSD∣b B→cD∣ε D→Sa∣c

(1) 构造该文法的LL(1)分析表； （10分）

(2) 分析符号串adcbdaa是否为该文法的句子。 （15分）

14．设有文法G[S]：

S→aA A→AbB∣B B→cB∣d

构造此文法的LR(0)项目集及状态转换图。 （15分）

15．对于如下的程序： （共10分）

I:=5

read J,K

L: A:=J*K

B:=J*I

Write B I:=I+1

if I<30 goto L halt

（1）划分基本块；

（2）试对其中的循环进行外提不变运算的优化。

16．设有文法G[Z]：

Z→ZbB∣Aa A→Ad∣b B→Bc∣d

（1）将其改写为LL(1)文法G′[Z]； （10分） （2）构造文法G′[Z]的LL(1)分析表。 （10分）

17．设有文法G[S]：

S→aABc A→Aab∣ε B→aA∣a

（1）构造此文法的LR(0)项目集及状态转换图； （15分） （2）构造SLR(1)分析表。 （10分）

18．对于如下的基本块，若变量G,M在基本块出口之后被引用： A:=15 C:=A*B

D:=6 E:=A-D F:=B+E G:=A*B H:=G*F

L:=C*F

M:=L

(1) 构造相应的DAG； （5分） (2) 重建经优化后的四元式序列。 （5分）

19．消除下列文法的左递归性: （共15分） Z→ABa A→ZbB∣a B→Bc∣d

20．设有文法G[E]：

E→E+T|T T→T*F|F F→(E)|i

其相应的算符优先矩阵如图所示，试给出对符号串(i+i)*i进行算符优先分析的过程。 （20分）

( i * + ) # ( ＜ ○ ＜ ○＜ ○ ＜ ○i ＜ ○ ＜ ○＜ ○ ＜ ○* ＜ ○＞ ○＞ ○＜ ○＞ ○＜ ○+ ＜ ○＞ ○＞ ○＞ ○＞ ○＜ ○) ＝ ○＞ ○＞ ○＞ ○＞ ○ # ＞ ○＞ ○＞ ○＞ ○ 文法G[E]的算符优先矩阵

21． 设有文法G[Z]：

Z→aBaA A→bBBaA∣ε B→dC C→cC∣ε

构造该文法的LL(1)分析表。 （15分）

22．设有文法G[Z]： Z→ZbB∣Aa A→Ad∣b B→Bc∣d

相应的LR(0)项目集及状态转换图如图所示：

(1) 构造SLR(1)分析表； （10分）

(2) 给出对输入符号串babdc的LR分析过程。 （15分）