编译原理期末考试习题及答案

（2）将（1）所得的NFA确定化：（5分） a b {1} {1,2} Φ {1,2} {1,2} {1,2} （5分）

六. 已知文法 G(S) :

(1) S ? ^ | a | (T) (2) T ? ST’ | S (3) T’ ? ,ST’ |ε

试：求first和follow集合，构造改文法的LL（1）分析表。（10分） 答：文法相应的first 和 follow 集合 （5分） first follow S a ^ ( # , ) T a ^ ( ) T’ , ε ) 其LL（1）分析表如下：

七. 已知文法 G(S) :

6

(1) S ? SiA | A (2) A ? A+B | B (3) B ? A* | （

非终止符的firstVT和lastVT集合如下: firstVT lastVT S i , + , * , ( i , + , * , ( A + , * , ( + , * , ( B * , ( * , ( 试构造算符的优先关系表。（10分） 答： i + ( ) * I > < < < + > > < < > ( > > > ) < < < * > > > 八已知文法 G(S) :

(1) S ? a | aAb | b | bBa (2) A ? 1A0 | ε (3) B ? 1B0 | ε

求 ：该文法的LR（0）项目集规范族。（15分） 答：

九．设某语言的DO-while 语句的语法形式为： S ? do S1 while E 其语义解释为：

7

针对自上而下的语法分析器，

(1) 分段产生式；（3分）

(2) 写出每个产生式对应的语义动作。（7分） 答：（1）分段产生式（3分） G(S) : (1) R ? do

(2) U ? R S1 while (3) S ? U E

(2) 产生式对应的语义动作(7分)

(1) R ? do { $$.loop = nxq }

(2) U ? R S1 while { $$.loop = $1.loop }

(3) S ? U E { backpatch（$2.FC ， $1.loop ）； Backpatch（$2.TC ， nxq ） }

8