answer.西北工业大学考试题纸B卷-编译原理20120619.final

诚信保证本人知晓我校考场规则和违纪处分条例的有关规定，保证遵守考场规则，诚实做人。 本人签字：编号：西北工业大学考试试题（ B卷）2011－2012学年第 二学期开课学院考试日期

计算机学院

课程编译原理考试时间2小时

学时64考试形式（闭）卷题 一

二

三 四

五 六 七

八 九

十

总分号得分考生班级 学 号 姓 名一、选择题（每小题 2分，共10分）1）对文法S→，B→b，A→，以下哪些结论是正确的（B）。①该语言可以用正规式(a**)描述②该文法对应的语言可由图灵机识别③不是该文法的有效句型④是语言的句子A、②④ B. ①②④ C.①③D. ①③④（2）语法分析的任务是：①分析单词的构成 ②分析单词流如何构成语句； ③分析语句如何构成程序；④分析程序的结构 （A）A、②③④ B 、①②③④ C 、②③ D 、①④3）给定数组A[1..10，1..20，1..30]，假定数组是按行存放的，且首地址为0（按字编址），则A[3，4，5]的地址为（A）A.1294

B.1043

C.1925

D.832（4）以下哪个结论是正确的（ C）。①常量传播可能产生无用变量 ②与的等价的最小在同构意义下唯一③可以用表示 ④中的垃圾收集属于栈式存储管理机制A、①② B 、②④ C、①②③ D 、②③注：1.命题纸上一般不留答题位置，试题请用小四、宋体打印且不出框。命题教师和审题教师姓名应在试卷存档时填写。共3页 第1页西北工业大学命题专用纸（5）对文法G[S]：文法S→，A→b，A→，B→，哪个结论是正确的（①该文法是正规文法 ②该文法定义的语言无限③中的句柄是 ④该文法不能用(1)方法分析A、① B 、③ C 、②③④ D 、②④二、判断题（每小题 2分，共10分）

D）（1）已知属性翻译文法：S→{("1");}S→y{("2");}W→{("3");}若输入串为

""，则分析过程将输出

23131

(

)（2）文法

E→

|

，T→T*，F→i

可用识别

(

)（3）使用分析法进行分析的前提条件是文法不含左递归产生式（ ）（4）对于文法S→，[1]项目[S→b·]对于活前缀有效（）（5）存在递归调用的语言不能采用静态存储管理方式分配存储空间（ ）三、（17分）对于以下状态矩阵a b0 1 21 3 42 1 23 44 3其中初始状态为状态0，终止状态为状态3、4（1）画出相应的状态转换图（4分）（2）对所得进行最小化（6分）（3）求解最小化对应的正规表达式（ 5分）四、（8分）用长度不超过4的某个句型的两个不同最左推导来说明下面的文法是二义的，并画出相应的语法树。S→A→五、（12分）给定文法：S→，A→，B→（1）给出该文法的每个候选式的集及每个非终结符的集（4分）()={}(b)={b}()={b}(c)={c}( )={ }（2）判断该文法是否为(1)文法,若是，请给出该文法的（1）分析表，若不是，请给出理由。（4分）答案：是，表略（3）给出识别的分析过程（4分）教 务 处 印 制共3页 第2页六、（18分，每小题6分）对于文法 S→，X→，X→b，Y→c，Y→（1）构造（1）状态机；（2）构造该文法的(1)分析表并判断该文法是否为 (1)文法；（3）给出用（1）分析表对输入串进行分析的步骤。七、（10分）以下二小题任选一题作答（1）给出语句 b<a a>b 的逆波兰表示；2）语言中的语句的形式为SE，其含义是重复地执行S，直到布尔表达式E的值为真时，退出循环。请给出此结构的属性翻译文法八、（15分）（1）考虑下面的三地址语句序列：L0:i0L1:i1i>mL2nn<<1n<kL1L2:k1k<=0L3L0L3:L4L4:8分）将代码分成基本块，并给出控制流图。如有不可达代码则删除（（2）用图对下面的程序进行