1、一、填空题|（每题4分，共20分）1. 乔母斯基定义的3型文法（线性文法）产生式形式 ABa|a,或AaB|a，A，BVn,a,bVt 。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）的最右推到并画
2、出语法树。（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为： （
3、6分）状态转换表：abFSSS,AS,AS,AS五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分） （2）将（1）所得的NFA确定化：（5分）ab01，301,32，32,31,32,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分）fi
4、rstfollowSa (# , )Ta ()T, )七. 已知文法G(S) :(1) S SiA | A(2) A A+B | B(3) B A* | （试构造非终止符的firstVT和lastVT集合。（10分）答：（10分）firstVTlastVTSi , + , * , ( i , + , * , (A+ , * , (+ , * , (B* , (* , (FollowS#Ba,b,#八.已知文法G(S) :(1) S B B(2) B a B(3) B b 的follow集合如表：试：（1）给出该文法的LR（0）项目集规范族划分； （2）填写相应的SLR（1）的分析表。（15分）
5、答：（1）LR（0）项目集规范族划分(8分)I0S .SS .BBB .aBB .b- I1- I2- I3- I4SBa bI1S S.I2S B.BB .aBB .b- I5- I3- I4Ba bI3B a.BB .aBB .b- I6- I3- I4Ba bI4B b.I5S BB.I6B aB. (2) SLR(1)分析表（7分）状态ActionGotoab#SB0S3S4121Acc2S3S453S3S464R3R3R35R16R2R2R2九设某语言的not-then-else 语句的语法形式为：S not E then S1 其语义解释为： 针对自上而下的语法分析器，(1) 分段
6、产生式；（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,AVn, V+。2.词法分析程序的输入是 字符串 ，其输出是 单词符号 。3 算符有限分析方法每次都是对 最左素短语 进行规约。型为 B aB. 的LR（0）项目被称为 规约 项目。4、写出x:=b*(d-e
7、)/(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分）（3）（4分） 短语：（a,(a,a)） ，a,(a
8、,a) ， (a,a) ， a,a , a 直接短语：a 句柄：a三证明文法 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分） （2）将（1）所得的NFA确定化：（5分）ab11,21,21,21,2 （5分）六. 已知文法G(S) :(1) S
9、 | a | (T)(2) T ST | S(3) T ,ST |试：求first和follow集合，构造改文法的LL（1）分析表。（10分）答：文法相应的first 和 follow 集合 （5分）firstfollowSa (# , )Ta ()T, )其LL（1）分析表如下：七. 已知文法G(S) :(1) S SiA | A(2) A A+B | B(3) B A* | （非终止符的firstVT和lastVT集合如下:firstVTlastVTSi , + , * , ( i , + , * , (A+ , * , (+ , * , (B* , (* , (试构造算符的优先关系表。（
10、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 其语义解释为：针对自上而下的语法分析器，(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
