江南大学《编译原理》试卷参考 答案(2010A)

1、 江南大学考20092010第二学期编译原理期末考试试卷 （A）使用专业、班级 学号 姓名 题数一二三四五六七总分得分 一、选择填空每空1分，共计20分1编译程序将源程序加工成目标程序是 C 之间的转换。A词法 B语法 C语义 D规则2开发一个编译程序应掌握 D 。A源语言 B目标语言 C编译技术 D以上三项都是 3词法分析器的输出结果是 B 。A单词自身 B单词的机内符C单词的词义信息 D单词的词法信息 4称有限自动机A1和A2等价是指 D 。AA1和A2都是定义在一个字母表上的有限自动机BA1和A2状态数和有向边数相等CA1和A2状态数或有向边数相等DA1和A2所能识别的字符串集合相同5同

2、正则表达式(a | b)+等价的正则表达式是 B 。 A(a | b) * B(a | b) (a | b) *C(a b)* (a b) D(a | b)| (a | b)*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句柄考试形

3、式开卷（ ）、闭卷（），在选项上打（）（1）开课教研室 命题教师 命题时间 试卷专用纸 10一个文法G是LL(1)文法的充要条件是对每一个非终结符A的任意两个不同产生式A | ，有 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)，该文法是

4、 D 。ALL(1)文法 BLR(0)文法C简单优先文法 D二义性文法14LR分析器核心部分是一张分析表，该表由 D 组成。AACTION表 BGOTO表 CLL(1)分析表 DACTION表和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下面逆波兰式（

5、后缀式）中，能正确表示算术表达式a+b+c+d的是 D 。Aabcd+ Babc+d+Cab+cd+ Dab+c+d+ 20属于标识符“种属”属性信息的描述是 B 。A整型 B变量 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

6、= T+y*x -z= F+y*x -z= x+y*x -z (2) 试构造句型(E+T)-(T+F)的语法树xFTyxFT * FEE TFzE + T (3) 基于上述语法树给出该句型的短语、简单短语和句柄。短语：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

7、| | 9试构造描述C语言标识符集的正则表达式。 (L | _ ) (L | D | _ )*S1BCA00D11102设有如下DFA试构造与之等价的3型文法。 G：S 1A A 0B | B 1B | 0C C 0D D 1B | 0C | 江南大学考 a,bX3设有如下NFA：试完成下列（右侧）NFA到DFA状态表的构造，将该NFA确定化为DFAIaIb-SASASASXZ+XZXZXYZ+XYZXZXYZbYbbaASaZba,b 四、自上而下语法分析类型题每题5分，共计15分；1对文法GS：S BA A abB | B Acd | dc | eb（1）求如下每条产生式的SELECT集合

8、。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 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)文法，试完成

9、下列LL(1)分析表的构造。 VTVN a b cd e #SSBASBASBASBA AAabBAA BBAcdBdcBeb #acc 五、自下而上语法分析类型题每题10分，共计20分；1设有文法GS：S Aa | bAA cd | cAd (1) 完成下列优先关系矩阵的构造 SA a bcd#S A a b c d# (2) 基于上述优先关系矩阵，按下面要求回答上述文法GS是否为简单优先文法并说明其原因 该文法GS（ 是 ）简单优先文法； 原因是：优先关系矩阵不存在两个以上关系的元素。江南大学考2. 设有如下文法GS:SEFEaE | ab FFb | ba (1) 完成下列LR(0)项目

10、集规范族(可归前缀图)的构造I8:EabbaI0:SEFEaEEabI1:EaEEabEaEEabaI2:EaEEEI3:SEFFFbFbaI4: FbabaI5: FbaFI7:FFbI6:SEFFFbb(2) 基于该LR(0)可归前缀图，按下面要求回答上述文法GS是否为LR(0)文法并说明其原因。 该文法GS( 不是 )LR(0)文法 原因是：项目集规范族(可归前缀图)中项目集I6存在“移入归约”项目冲突。试卷专用纸六、代码生成类题每题5分，共计15分；1设有一语法制导翻译算法如下：SE print “E” EE+T print “+” ET print “T” TT*F print “*

11、” 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的四元式序列，且求其真、假链 四