《编译原理》练习题

《编译原理》练习题

《编译原理》练习题⼀

⼀、填空题（每空1分）1．设G ［S ］是⼀个⽂法，我们把能由⽂法的 （1） 推导出来的符号串α称为G 的⼀个句型。当句型α仅由 （2） 组成时 (即α∈V T *

)，则将它称为G 产⽣的句⼦。

2．从某⼀给定的状态q 出发，仅经过若⼲条 (3) 的⽮线所能达到的状态所组成的集合称为ε-CLOSURE(q)。

3．设G=(V N ,V T ,P,S)是⼀⽂法，我们说G 中的⼀个符号X ∈V N ∪V T 是有⽤的，是指X ⾄少出现在 （4） 的推导过程中，否则，就说X 是⽆⽤的。我们将不含形如A→A 的产⽣式和不含⽆⽤符号及⽆⽤产⽣式的⽂法称为 （5） 。4．我们常采⽤形如 (class, value)的⼆元式作为⼀个单词的 (6) 。其中,class 是⼀个整数，⽤来指⽰该单词的 (7) ，value 则是单词之值。5．⼀个⽂法G[S]可表⽰成形如 （8） 的四元式。其中V N ,V T ,P 均为⾮空的有限集，分别称为⾮终结符号集、终结符号集和产⽣式集， S ∈V N 为⽂法的开始符号。此外，将出现在各产⽣式左部和右部的⼀切符号所组成的集合称为 （9） ，记作V 。显然，V=V N ∪V T ,V N ∩V T =?。6．通常，可通过两种途径来构造词法分析程序。其⼀是根据对语⾔中各类单词的某种描述或定义，⽤ (10) 构造词法分析程序；另外⼀种途径是所谓词法分析程序的 (11) 。7．设G 为⼀⽂法，A→α是G 的⼀个产⽣式，如果α具有υA δ的形式，其中υ，δ不同时为ε，则称产⽣式A→α是 （12） 。若存在推导δ

υαA A *

，则

称产⽣式A→α是 （13） 。8．设M=(K,Σ,f,S 0,Z)为⼀DFA ，并设s 和t 是M 的两个不同状态，我们说状态s,t 为某⼀输⼊串w (14) ，是指从s,t 中之⼀出发，当扫视完w 之后到达M 的终态，但从其中的另⼀个状态出发，当扫视完同⼀个w 后⽽进⼊ (15) 。9．把最右推导称为 （16） ，⽽把右句型称为 （17） 。

10．如果从状态转换图的初态出发，分别沿着⼀切可能的路径到达 (18) ，并

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

⼆、选择题（每空2分）1. 下列⽂法中，不是产⽣语⾔ {ab n a∣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∣AeC．S→aA∣aB A→bc B→b∣e

D．S→aA∣aB∣a A→bc∣bAc B→bB∣Ae∣b∣e

3. ⽂法 G 产⽣的的全体是该⽂法描述的语⾔。

A ．句型 B. 终结符集 C. ⾮终结符集 D. 句⼦

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

A．不可区分 B．可划分 C．可区分 D．待区分

5. 设有⽂法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

6. 若⽂法 G 定义的语⾔是⽆限集，则⽂法G必然是。

A．前后⽂⽆关的 B．递归的 C．⼆义性的 D．⽆⼆义性的

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

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

B ．⼀个状态转换图是由⼀组⽮线连接的有限个结点所组成的⽆回路有向图。

C ．所谓⼀个DFA M 状态数的最⼩化，是指构造⼀个与之等价的DFA M ′，使它们有相同的接受集。

D ．对于有同⼀接受集的FA ，与之等价的DFA 在同构意义下是唯⼀的。 8. 下列⽂法中， 不是产⽣语⾔}1{12≥+n a n 的⽂法。A ．A →aBa

B →a ∣aBa B ．A →aB B →aa ∣Baa

C ．A →aAA A →a

D ．A →aBB B →a ∣aBB

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

A ．左线性⽂法

B ．形如（Class ，Value ）的⼆元式

C ．正规式

D ．正规⽂法

三、证明题1．试证明⽂法

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

2． 试证明⽂法: S →a AB A →aA ∣a B →aB ∣b 为⼆义性⽂法。 （10分）

四、简答题1．试构造⼀⽂法，使其描述如下语⾔： （15分）L(G)={ a n b m c m d n

∣m,n ≥1 }

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

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

3．对正规式((a∣b) *∣ab*)b ，构造与其相应的状态转换图。（15分）

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→B ab∣cC B→bS∣b C→Da D→Cb∣CDa 8．对正规式(a∣ab)*ab*，构造与其相应的状态转换图。（15分）

9．试构造⼀正规⽂法，使其描述如下语⾔：（10分）

L(G)={ ab m cb n a∣m≥1, n≥0 }

10．试描述由下列⽂法所产⽣的语⾔。（15分）

S→aAbB A→A ab∣ε B→aA∣aC C→cC∣d 五、应⽤题

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

(1) 分别画出相应的状态转换图；（10分）

(2) 写出相应的3型⽂法。（10分）

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

4．将如图所⽰的DFA最⼩化。（20分）

5．将如图所⽰的DFA最⼩化。（25分）

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

(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∈V N，则称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、各维的上、下界l k和u k的数据结构称为数组的 (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∈V N，A产⽣式的所有不同候选式均能推导出以同⼀终结符号开始的符号串。D. 对任意⾮LL(1)⽂法⽽⾔，通过消除左递归和反复提取左因⼦，都能将其改造为LL(1)⽂法。

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

A. 最左直接短语

B.直接短语

C.最左素短语

D.控制结点

6. 下列表⽰中，是与f×(e+(a×d+c)/d)相应的逆波兰式。