.
一、填空题|（每题4分，共20分）
1. 乔母斯基定义的3型文法（线性文法）产生式形式 A?Ba|a,或A?aB|a，A，B∈Vn,
a,b∈Vt 。
2.语法分析程序的输入是 单词符号，其输出是 语法单位 。
3 型为 B ? .aB 的LR（0）项目被称为 移进 项目，型为 B ? a.B 的LR（0）
项目被称为 待约 项目，
4.在属性文法中文法符号的两种属性分别为 继承属性 和 综合属性 。 5、运行时存贮管理方案有 静态存储分配、动态存储分配 和 堆式存储分配 和方案。
二.已知文法 G(S)
(1) E ? T | E+T (2) T ? F | F*F (3) F ? （E）| i
（1）写出句型（T*F+i）的最右推到并画出语法树。（4分） （2）写出上述句型的短语，直接短语和句柄。（4分）
答：（1）最右推到（2分）
E ==> T ==> F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i)
(2) 语法树（2分）
（3）（4分）
短语： （T*F+i） ，T*F+i ，T*F ， i
直接短语：T*F ， i 句柄：T*F
三. 证明文法 G(S) ： S ? SaS |ε 是二义的。（6分） 答：句子 aaa对应的两颗语法树为：
;..
.
因此，文法是二义文法
四.给定正规文法G（S）：
(1) S ? Sa | Ab |b (2) A ? Sa
请构造与之等价的DFA。（6分） 答：对应的NFA为： （6分）
状态转换表： a b {F} Φ {S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA（要求写出求解过程）。（15分） 答：（1）对应的NFA（5分）
（2）将（1）所得的NFA确定化：（5分） a b {0} {1，3} {0} {1,3} Φ {2，3} {2,3} {1,3} {2,3} （5分）
六. 已知文法 G(S) :
(1) S ? ^ | a | (T) (2) T ? T,S | S 试：（1）消除文法的左递归；（4分）
（2）构造相应的first 和 follow 集合。（6分） 答：（1）消除文法的左递归后文法 G’（S）为：
(1) S ? ^ | a | (T)
;..
.
(2) T ? ST’ | S
(3) T’ ? ,ST’ |ε （4分）
（2）（6分） first follow S a ^ ( # , ) T a ^ ( ) T’ , ε ) 七. 已知文法 G(S) :
(1) S ? SiA | A (2) A ? A+B | B (3) B ? A* | （
试构造非终止符的firstVT和lastVT集合。（10分） 答：（10分） firstVT lastVT S i , + , * , ( i , + , * , ( A + , * , ( + , * , ( B * , ( * , ( 八.已知文法 G(S) :
Follow (1) S ? B B
S # (2) B ? a B
B a,b,# (3) B ? b
的follow集合如表：
试：（1）给出该文法的LR（0）项目集规范族划分； （2）填写相应的SLR（1）的分析表。（15分） 答：（1）LR（0）项目集规范族划分(8分) I0 I2 I3
S B B S’? .S ---? I1 I1 S ? B.B ---? I5 B ? a.B ---? I6
a a S ? .BB ---B ? I2 --? I --? I3 S’? S. B ? .aB B ? .aB 3
a b b B ? .aB --? I3 B ? .b --? I4 B ? .b --? I4 b B ? .b --? I4
I4 I5 I6
B ? b. S ? BB. B ? aB.
(2) SLR(1)分析表（7分） 状态 Action Goto a b # S B 0 S3 S4 1 2 1 Acc 2 S3 S4 5 3 S3 S4 6 4 R3 R3 R3 5 R1 ;..
. 6 R2 R2 R2 九．设某语言的not-then-else 语句的语法形式为：S ? not E then S1 其语义解释为：
针对自上而下的语法分析器，
(1) 分段产生式；（3分）
(2) 写出每个产生式对应的语义动作。（7分） 答：（1）分段产生式（3分）及语义动作(7分)
(1) R ? not E then { Backpatch（$2.FC ，nxq ）;
$$.chain = $2.Tc }
(2) S ? R S1 { Backpatch（$2.chain ， nxq ）}
一、填空题|（每题4分，共20分）
1. 乔母斯基定义的2型文法（上下文无关文法）产生式形式 A?β,A∈Vn, β∈V+。 2.词法分析程序的输入是 字符串 ，其输出是 单词符号 。
3 算符有限分析方法每次都是对 最左素短语 进行规约。型为 B ? aB. 的LR（0）项
目被称为 规约 项目。
4、写出x:=b*(d-e)/(c-d)+e的逆波兰式__xbde-*cd-/e+:=__。
5、常用的两种动态存贮分配办法是__栈式存储 分配 和 堆式存储__分配。
二．已知文法 G(S) :
(1) S ? ^ | a | (T) (2) T ? T,S | S 试：（1）写出句型（a,(a,a))的最左推到并画出语法树。（4分） （2）写出上述句子的短语，直接短语和句柄。（4分） 答：（1）最左推到（2分）
S ==> （T） ==> （T,S）==> (S,S) ==> (a,S) ==> (a,(T)) ==> (a,(T,S)) ==> (a,（S,S)) ==> (a,（a,S)) ==> (a,（a,a))
(2) 语法树（2分）
;..