江南大学《编译原理》试卷参考答案(2010A)Word格式文档下载.doc

1、6前后文无关文法G：S S | 所产生的语言是 D 。A m n （m，n0） B m n （m，n1）C m m （m0） D n n（n1） 7由文法的开始符出发通过若干步（包括0步）推导产生的文法符号序列是 B 。A语言 B句型 C句子 D句柄8最左简单子树的叶结点，自左至右排列组成句型的 C 。A短语 B简单短语 C句柄 D素短语9简单优先分析法每次都是对 D 进行归约。A短语 B简单短语C素短语 D句柄考试形式开卷（ ）、闭卷（），在选项上打（）（1）开课教研室 命题教师 命题时间 试卷专用纸 10一个文法G是LL（1）文法的充要条件是对每一个非终结符A的任意两个不同产生式A | ，

2、有 C 。AFIRST（）FIRST（）=BFIRST（）FOLLOW（A）=CSELECT（A）SELECT（A）=DSELECT（A）SELECT（A）11一个文法G，若 C ，则称它是LL（1）文法。AG中不含左递归BG无二义性CG的LL（1）分析表不含多重定义DG中产生式不含左公因子 12若a为终结符，则A a为 A 项目。A移入 B待约 C归约 D接受13设有文法G=（S，a， SSaS | ，S），该文法是 D 。ALL（1）文法 BLR（0）文法C简单优先文法 D二义性文法14LR分析器核心部分是一张分析表，该表由 D 组成。AACTION表 BGOTO表 CLL（1）分析表 D

3、ACTION表和GOTO表15可归前缀是指 C 。A规范句型的前缀 B活前缀 C含有句柄的活前缀 D句柄16编译程序的语法分析器必须输出的信息是 A 。A语法错误信息 B语法规则信息 C语法分析过程 D语句序列 17下列错误属于静态语义错误的是 C 。A括弧不配对 B出现非法字符C类型不相容 D溢出 18在语法制导翻译中不采用拉链回填技术的语句是 B 。A转向语句 B赋值语句C条件语句 D循环语句 19下面逆波兰式（后缀式）中，能正确表示算术表达式a+b+c+d的是 D 。Aabcd+ Babc+d+Cab+cd+ Dab+c+d+ 20属于标识符“种属”属性信息的描述是 B 。A整型 B变量

4、 C地址 D指针使用学期 总张数 教研室主任审核签字 江南大学考 二、文法和语言类型题1小题10分，2小题5分，共计15分1设有文法GS：E E+T | E-T | TT T*F | T/F | FF x | y | z | （E） （1） 给出对于句子x+y*x-z的最右推导过程E = E-T= E -F= E -z= E+T -z= E+ T*F -z = E+T*x -z= E+F*x -z= E+y*x -z= T+y*x -z= F+y*x -z= x+y*x -z（2） 试构造句型（E+T）-（T+F）的语法树xFTyT * FEE TzE + T （3） 基于上述语法树给出该句型

5、的短语、简单短语和句柄。短语：x+y*x-z、x+y*x、y*x、x（1）、y、x（2）、z简单短语：x（1）、y、x（2）、z句柄：x（1）试卷 专用纸2试构造文法G，L（G）=a2m b2n+1 | m1，n0。 G： S A BA aaA | aaB bbB | b 三、词法分析类题每小题5分，共计15分1令：L = A | B | | Z | a | b | | zD = 0 | 1 | 2 | 3 | | 9试构造描述C语言标识符集的正则表达式。 （L | _ ） （L | D | _ ）*S1BCAD2设有如下DFA试构造与之等价的3型文法。 G：S 1A A 0B | B 1B

6、| 0C C 0D D 1B | 0C | a,bX3设有如下NFA：试完成下列（右侧）NFA到DFA状态表的构造，将该NFA确定化为DFAIaIb-SASXZ+XZXYZ+XYZbYaZa,b 四、自上而下语法分析类型题每题5分，共计15分；1对文法GS：S BA A abB | B Acd | dc | eb（1）求如下每条产生式的SELECT集合。SELECT（ S BA ） = a , c , d ,e SELECT（ A abB ） = a SELECT（ A ） = c , # SELECT（ B Acd ） = a , c SELECT（ B dc ） = d SELECT（ B

7、 eb ） = e （2）证明这个文法是否为LL（1）文法。 由于SELECT（ A abB ） SELECT（ A ）= a c , # =SELECT（BAcd）SELECT（ B dc）SELECT（ B eb）= a , c d e = 满足LL（1）文法条件，所以该文法是LL（1）文法。 = （3）无论GS是否LL（1）文法，试完成下列LL（1）分析表的构造。 VTVN a b cd e #SBA AAabBA BBAcdBdcBebacc 五、自下而上语法分析类型题每题10分，共计20分；S Aa | bAA cd | cAd （1） 完成下列优先关系矩阵的构造 Sc# （2） 基

8、于上述优先关系矩阵，按下面要求回答上述文法GS是否为简单优先文法并说明其原因 该文法GS（ 是 ）简单优先文法；原因是：优先关系矩阵不存在两个以上关系的元素。2. 设有如下文法GS:SEFEaE | ab FFb | ba （1） 完成下列LR（0）项目集规范族（可归前缀图）的构造I8:EabI0:SEFEaEabI1:EaI2:EaEI3:SEFFbbaI4: FbI5: FbaI7:FFbI6:SEFFF（2） 基于该LR（0）可归前缀图，按下面要求回答上述文法GS是否为LR（0）文法并说明其原因。该文法GS（ 不是 ）LR（0）文法项目集规范族（可归前缀图）中项目集I6存在“移入归约”项

9、目冲突。六、代码生成类题每题5分，共计15分；1设有一语法制导翻译算法如下：SE print “E” EE+T print “+” ET print “T” TT*F print “*” TF print “F” Fid print “id”若输入序列为a+b*c，且采用自底向上的分析方法，则给出输出序列。输出序列：aFTbF*+E2试给出表达式w=x+y-z*（a+b）*c规范和简易的四元式序列。规范的四元式序列 简易的四元式序列1（+, x, y, T1） T1:= x+y2（+, a, b, T2） T2:= a+b3（*, z, T2, T3） T3:= z*T24（*, T3, c, T4） T4:= T3* c5（-, T1, T4, T5） T5:= T1-T4 6（:=, T5 , _ , w） w:= T53是给出布尔表达式ab and cd or ef or gh的四元式序列，且求其真、假链 四元式序列（序号从100开始） 真、假链 100：if ab goto 102 真链= 106, 104, 102 101：goto 104 102：if cd goto （0） 假链= 107 103：goto 104104：if ef goto （102）105：goto 106106：d goto （104）107：goto （0） 9