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

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. 文法 G 产生的 的全体是该文法描述的语言。 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产生式的所有不同候选式均能推导出以同一终结符号开始的符号串。

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

4. 简单优先分析每次归约的是 。 A. 最左直接短语 B.直接短语 C.最左素短语 D.控制结点

5. 下列表示中， 是与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×

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

7．我们常采用形如 (class, value)的二元式作为一个单词的 。其中,class是一个整数，用来指示该单词的 ，value则是单词之值。 8．LL(1)分析表可用一个 表示，它的每一行与文法的一个非终结符号相关联，而其每一列则与文法的一个终结符号或 相关联。 9．若在一个文法G中，不含有形如 的产生式，其中A,B∈VN，则称G为算符文法。

10．将每一运算符都置于其 的表达式称为后缀表示，也称为逆波兰表示。

11．把流程图中具有如下性质的一组结点称为程序中的一个循环：(ⅰ) 在这组结点中，有惟一的 ，使得从循环外到循环内任何结点的所有通路，都必通过此结点；(ⅱ) 这一组结点是 。 12．设G［S］是一个文法，我们把能由文法的 推导出来的符号串α称为G的一个句型。当句型α仅由 组成时 (即α∈VT)，则将它称为G产生的句子。

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

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

15．在每一LR(0)项目［A→α·β］中放置一个 a ，使之成为

*

［A→α·β,a］的形式，我们将此种项目称为一个 。

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

1、消除文法: S→AbB∣A A→AB∣caB∣B B→Aa∣b 中的单产生式。 2、消除文法: S→ABb∣a A→aB∣caB∣ε B→aA∣b∣ε 中的ε-产生式。

3、试构造一文法，使其描述语言： L(G)={ abcd∣m,n≥1 }

三、应用题

1、设有文法G[S]： S→aBc∣bAB A→aAb∣b B→b∣ε

(1) 构造该文法的LL(1)分析表； (2) 分析符号串baabbb是否为该文法的句子。 2、将如图所示的具有ε动作的NFA确定化：

nmmn

3、将如图所示的NFA确定化：

四、简答题（

**

1、对正规式((a∣b)∣ab)b ，构造与其相应的状态转换图。

2、设有文法G[Z]： Z→ZAc∣Ba A→Ab∣a B→Bd∣c ，将其改写为LL(1)文法。

3、消除文法: S→aAc A→Bb∣a B→Ad∣c 的左递归性。

五、应用题

1、设有文法G′[E]： E→E1 E1→E1+T1|T1 T1→T T→T*F|F F→(E)|i 其相应的简单优先矩阵如下图所示，试给出对符号串i+i进行简单优先分析的过程。

E E1EE1T1TF+*()i T1 T F + * ( ) i = ·= >··> >··> = >···> > >···= < < < <·····= < <···= < < < < < <·······> > >···> > >··· 2、设有文法G[S]： S→ABAC A→aD B→b C→d D→c （1）构造此文法的LR(0)项目集及状态转换图；） （2）构造SLR(1)分析表。 3、设有文法G[S]： S→aAB A→bA∣a B→cB∣b

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