.

三．证明文法 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范文