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

1、诚信保证本人知晓我校考场规则和违纪处分条例的有关规定，保证遵守考场规则，诚实做人。 本人签字： 编号： 西北工业大学考试试题（B卷）20112012学年第 二 学期开课学院 计算机学院 课程 编译原理 学时 64 考试日期 考试时间2小时 考试形式（闭）卷 题号一二三四五六七八九十总分得分考生班级学号姓名一、选择题（每小题2分，共10分）（1）对文法SAcB|A，Bb，AaA|a|e，以下哪些结论是正确的（ B ）。该语言可以用正规式(a*|a*cb)描述 该文法对应的语言可由图灵机识别 aaacB不是该文法的有效句型 aaaacb是语言的句子A、 B. C. D. （2）语法分析的任务是：分

2、析单词的构成 分析单词流如何构成语句；分析语句如何构成程序；分析程序的结构 （ A ）A、 B、 C、 D、（3）给定数组A1.10，1.20，1.30，假定数组是按行存放的，且首地址为0（按字编址），则A3，4，5的地址为（A ）A.1294 B. 1043 C. 1925 D.832（4）以下哪个结论是正确的（ C ）。 常量传播可能产生无用变量 与任何NFA的等价的最小DFA在同构意义下唯一NFA可以用BNF表示 Java中的垃圾收集属于栈式存储管理机制A、 B、 C、 D、注：1. 命题纸上一般不留答题位置，试题请用小四、宋体打印且不出框。2. 命题教师和审题教师姓名应在试卷存档时填写

3、。 共3页第1页西北工业大学命题专用纸（5）对文法GS：文法SaAbBe，Ab，AAb，BdA，哪个结论是正确的（ D ）该文法是正规文法 该文法定义的语言无限aAbdbe中的句柄是Ab 该文法不能用LL(1)方法分析A、 B、 C、 D、二、判断题（每小题2分，共10分）（1）已知属性翻译文法：SxxWprintf("1"); Syprintf("2");WSzprintf("3");若输入串为"xxxxyzz"，则分析过程将输出 23131 ( Ö )（2）文法EE+T | E-T，TT*F|T/F，

4、Fi可用DFA识别 (´) （3）使用LR分析法进行分析的前提条件是文法不含左递归产生式（´）（4）对于文法SaS|b，LR1项目Sb·,#对于活前缀aab有效（Ö）（5）存在递归调用的语言不能采用静态存储管理方式分配存储空间（Ö ）三、（17分）对于以下状态矩阵ab0121342123443其中初始状态为状态0，终止状态为状态3、4（1）画出相应的状态转换图（4分）（2）对所得DFA进行最小化（6分）（3）求解最小化DFA对应的正规表达式（5分）四、（8分） 用长度不超过4的某个句型的两个不同最左推导来说明下面的文法是二义的，并画出相应的语法

5、树。SAS|bASA|a五、（12分）给定文法： SAa，Ab|Bbc，Bc|e（1）给出该文法的每个候选式的Fisrt集及每个非终结符的Follow集（4分）First(Aa)=b,c,FIRST(b)=b,FIRST(Bbc)=b,FIRST(c)=c;FIRST(e)=e（2）判断该文法是否为LL(1)文法,若是，请给出该文法的LL（1）分析表，若不是，请给出理由。（4分） 答案：是，表略（3）给出识别cbca的分析过程（4分）教务处印制 共3页第2页六、（18分，每小题6分） 对于文法 SXY，XYb，Xb，Yc，Ye（1）构造LR（1）状态机；（2）构造该文法的LR(1)分析表并判断

6、该文法是否为LR(1)文法；（3）给出用LR（1）分析表对输入串cbc进行分析的步骤。七、（10分）以下二小题任选一题作答（1）给出语句 while b<a do if a>b then b:=a else a:=b 的逆波兰表示；（2）PASCAL语言中的REPEAT语句的形式为 repeat S until E，其含义是重复地执行S，直到布尔表达式E的值为真时，退出循环。请给出此结构的属性翻译文法八、（15分）（1）考虑下面的三地址语句序列：L0: i := 0L1: i := i+1if i>m goto L2n := n<<1if n<k goto L1L2: k := k-1if k<=0 goto L3goto L0L3: goto L4L4: halt将代码分成基本块，并给出控制流图。如有不可达代码则删除（8分）（2）用DAG图对下面的程序进行优化，假定所有的T打头的变量在本基本块外均不活跃（不再被使用）：（7分）1. T1: