编译原理期末试题（8套含答案+大题集）(12)

答：

构造相应的正规式：(0|1)*1(0|1) (3分) NFA: (2分)

1 1

? ? ? ? 1 0 1 2 3 4

第38页共6页

0 0 确定化：(3分) I I0 I1 {0,1,2} {1,2} {1,2,3} {1,2,4} {1,2,3,4} {1,2} {1,2} {1,2,4} {1,2} {1,2,4} {1,2,3} {1,2,3} {1,2,3,4} {1,2,3} {1,2,3,4}

0

1 0 1 0 0 0 1 2 3 4

0 1 1 1

三、写一个文法使其语言为L(G)={ anbmambn | m,n≥1}。(6分)

答：文法G(S):

S ? aSb | B B ? bBa | ba

四、对于文法G(E): (8分)

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

1. 写出句型(T*F+i)的最右推导并画出语法树。

2. 写出上述句型的短语，直接短语、句柄和素短语。 答： 1. (4分)

E?T?F?(E) ?(E+T) ?(E+F)

E T F ?(E+i) ?(T+i) ?(T*F+i)

2. (4分)

短语：(T*F+i), T*F+i, T*F, i 直接短语：T*F, i 句柄：T*F 素短语：T*F, i

第39页共6页

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

五、设文法G(S)：(12分)

S?SiA|AA?A?B|B B?)A*|(1．构造各非终结符的FIRSTVT和LASTVT集合； 2．构造优先关系表和优先函数。(12分) 答：(6分)

FIRSTVT(S)={ i，+，)，( } FIRSTVT(A)={ +，)，( } FIRSTVT(B)={ )，( }

LASTVT(S)={ i，+，*，( } LASTVT(A)={ +，*，( } LASTVT(B)={ *，( }

优先关系表: (3分) i + ( ) i > < < < + > > < < ( > > ) < < < * > > 优先函数: (3分) i + ( ) f 2 6 6 1 g 1 4 6 6 六、设某语言的do-while语句的语法形式为 (9分) S ? do S(1) While E

其语义解释为：

针对自下而上的语法分析器，按如下要求构造该语句的翻译模式： (1) 写出适合语法制导翻译的产生式；

E的代码 假

S(1)的代码 真

* > > > * 6 1 第40页共6页