.
三．证明文法 G(S) ： S ? aSb | Sb | b 是二义的。（6分） 答：句子 aabbbb对应的两颗语法树为：
因此，文法是二义文法
四.给定正规文法G（S）：
(1) S ? aA
(2) A ? aB | bA （3）B ? aA | b 请构造与之等价的DFA。（6分） 答：对应的DFA为：（6分）
**
五. 构造识别正规语言(ab|a) 最小的DFA（要求写出求解过程）。（15分） 答：（1）对应的NFA （5分）
word范文
.
（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) :
word范文
.
(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 其语义解释为：
word范文
.
针对自上而下的语法分析器，
(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 ） }
word范文