、填空题| (每题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) ET | E+T TF | F*F 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分)IS(3) (4 分)短语： (T*F+i ), T*F+i , T*F , i直接短语：T*F , i句柄：T*F三.证明文法G(S) : S SaS | 是二义的。(6分) 答：句子aaa对应的两颗语法树为：S a S 因此，文法是二义文法四.给定正规文法G( S):(1) SSa | Ab |bASa请构造与之等价的DFA ( 6分) 答：对应的NFA为：(6分)状态转换表:abFSSS,AS,AS,AS五构造识别正规语言b*a(bb*a)*b* 最小的DFA(要求写出求解过程)。(15分) 答：(1)对应的NFA(5分)ab01 , 301,32 , 32,31,32,3（5 分）六.已知文法 G(S):(1) S A | a | (T) T T,S | S试：(1)消除文法的左递归；(4分)(2) 构造相应的first 和follow 集合。(6分) 答：(1)消除文法的左递归后文法 G( S)为：(1) SA | a | (T) TST |S(4 分) T ,ST | &(2) (6分)firstfollowSa A (# ,)Ta a ()T, &)七.已知文法 G(S): S SiA | A AA+B|B(3) BA* |(试构造非终止符的firstVT和lastVT集合。(10分)答：(10分)firstVTlastVTSi , + , * , ( i , + , *,(A+ , * ,(+ , * ,(B* ,(* ,(八.已知文法G(S):(1) SB BFollowBa BS#BbBa,b,#的 follow集合如表：试：(1)给出该文法的LR( 0)项目集规范族划分;(2)填写相应的SLR( 1)的分析表。(15分)答：(1) LR (0)项目集规范族划分(8分)SBaIbI11SS.12I 2B ,I 3SB.B -I 5b I 3Ba.B -B.aB -B.aB -B.b -B.b -BaIbI丨4Bb.I 5S BB.I 6B aB.(2) SLR(1)分析表(7分)状态ActionGoto01234aS3bS4AccS3S3R3S4S4R3R3R16R2R2R2九.设某语言的not-then-else 语句的语法形式为：S not E then S其语义解释为：(2) 写出每个产生式对应的语义动作。(7分) 答：(1)分段产生式(3分)及语义动作(7分)not E then Backpatch( $2.FC ，nxq );$.cha in = $2.Tc Backpatch( $2.chain ，nxq ) (1) R一、填空题| (每题4分，共20分1. 乔母斯基定义的2型文法(上下文无关文法)产生式形式 A B ,A Vn, B V+。2. 词法分析程序的输入是 字符串，其输出是 单词符号o3算符有限分析方法每次都是对最左素短语 进行规约。型为B aB.的LR( 0)项目被称为规约 项目。4、 写出 x:=b*(d-e)/(c-d)+e的逆波兰式 _xbde-*cd-/e+:=_。5、 常用的两种动态存贮分配办法是栈式存储分配和堆式存储 分配。二. 已知文法G(S):(1) S A | a | (T) 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分s/l(I )/lT ， SI /l (T )1 /l(3) (4 分)短语：(a,(a,a) ), a,(a,a), (a,a), a,a , a直接短语：a句柄：a三. 证明文法 G(S) : S aSb | Sb | b 是二义的。(6分) 答：句子aabbbb对应的两颗语法树为：Sb因此，文法是二义文法四. 给定正规文法G( S):(1) S aA A aB | bA(3) B aA | b请构造与之等价的DFA( 6分) 答：对应的DFA为：(6分)ab五构造识别正规语言（ab*|a） *最小的DFA（要求写出求解过程）。（15分） 答：（1）对应的NFA （ 5分）（5 分）（2）将（1）所得的NFA确定化：（5分）ab11,21,21,21,2六.已知文法G（S）: S A | a | （T）T ST |S（3）T ,ST | &试：求first和follow集合，构造改文法的LL （1）分析表。（10 分）答：文法相应的first 和follow 集合 （5分）firstfollowSa A (# ,)Ta a ()T, )其LL (1)分析表如下:ab(sA (T)TTf STT十 ST，SVrT，_ ET f STf七.已知文法G(S): S SiA | A AA+B|B(3) BA* | (非终止符的firstVT 和lastVT集合如下:firstVTlastVTSi , + , * , ( i , + , *,(A+ , * ,(+ , * ,(B* ,(* ,(试构造算符的优先关系表。(10分)答：i+()*I()八已知文法 G(S):(1) S a | aAb | b | bBa A1A0| &(3) B1B0 | &求：该文法的LR (0)项目集规范族。(15分)答：1/ S -a-S-bSb BaBIBO教育之通病是教用脑的人不用手，不教用手的人用脑，所以一无所能。教育革命的对策是手脑联盟，结果是手与脑的力量都可以大到不可思议。九.设某语言的DO-while语句的语法形式为:S do S i while E其语义解释为：*S的代码|E的代码二VE FCE,TC针对自上而下的语法分析器，(1) 分段产生式；(3分)(2) 写出每个产生式对应的语义动作。(7分) 答：(1)分段产生式(3分)G(S) : (1)Rdo(2) UR Si while(3) SU E(2)产生式对应的语义动作(7分)(1) Rdo $.loop = nxq (2) U R S 1 while $.loop = $1.loop (3) S U E backpatch ($2.FC, $1.loop )；Backpatch( $2.TC ， nxq )单纯的课本内容，并不能满足学生的需要，通过补充，达到内容的完善