西北工业大学考试题纸a卷-编译原理0618.final.doc

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date西北工业大学考试题纸A卷-编译原理20120618.final成绩诚信保证本人知晓我校考场规则和违纪处分条例的有关规定，保证遵守考场规则，诚实做人。 本人签字： 编号： 西北工业大学考试试题（A卷）20112012学年第 二 学期开课学院 计算机学院 课程 编译原理 学时 64 考试日期 考试时间2小时 考试形式（闭）卷 题号一二三四五六七八九十总分得分考生班级学号姓名一、选择题（每小题2分，共10分）（1）以下哪些结论是正确的（ ）。 任意DFA最小化后可得到同构意义下唯一的DFA 正规文法可由LR(1)文法识别 LALR(1)和LR(0)文法具有相同的分析表 LL(1)文法可用正则表达式表示A、 B. C. D.（2）关于LR(0)、SLR(1)和LR(1)，以下哪些选项是正确的 ( )LR(1)和SLR(1)的状态机相同 SLR(1)使用了Follow集合判定句柄LR(1)是基于最左推导的 LALR(1)比 LR(0)识别能力更强A、 B、 C、 D、（3）对以下属性翻译文法采用LR分析，句子badc打印出来的结果是什么 ( ) SAaA printf(“a”); AdB printf(“d”); Ab printf(“b”); Bc printf(“c”); A、bcda B、abcd C、dbca D、cadb（4）以下哪个结论是正确的（ ）。 C+的new是栈式内存管理操作 简单优先分析属于自顶向下分析 SàaBc，BàEf，EàD | g包含无用产生式 C语言支持引用调用方式A、 B、 C、 D、注：1. 命题纸上一般不留答题位置，试题请用小四、宋体打印且不出框。2. 命题教师和审题教师姓名应在试卷存档时填写。 共3页第1页西北工业大学命题专用纸（5）给定文法GS：SbS | cc | Ad，AeA | e，下面符号串中是该文法句子的有（ ） cc bcbce bed eeedA、 B、 C、 D、二、判断题（每小题2分，共10分）（1）文法GE：EE+T|E-T|T TT*F|T/F|F中，Follow(T)=*，/，# ( ).（2）文法SaAbBe，Ab，AAb，BdA，简单优先关系b<d和d>b都成立( ) （3）正规式(a*b*)*=(a|b)*（ ）（4）活动记录只在动态存储管理中使用 （ ）（5）(a+b)*c-d/e的逆波兰表示是ab+c*de-/（ ）三、（10分）对文法EE+E | E-E | E*E | E/E | (E) | i（1）判断该文法是否是二义性文法，并给出原因（3分）（2）给出i* (i+i)的最左推导，并判定该句子的最左推导是否唯一（4分）（3）画出上述推导对应的语法树（3分）四、（18分） 给定以下NFA：（1）将该NFA转换为DFA（6分）（2）对所得DFA进行最小化（6分）（3）给出上述NFA的正规表达式（6分）五、（12分）对于文法文法GS：SaS|Db|DBDa，Bb, Dc|e；（1）给出各产生式右部的First集和各非终结符的Follow集合（6分）（2）判定GS是否是LL（1）文法，若不是，说明理由，若是，请给出其LL（1）分析表（6分）六、（18分，每小题6分） 对于以下文法：ACaBe | B，BC，Cb（1）证明该文法不是SLR(1)文法（6分）（2）构造LR(1)的DFA和分析表（8分）（3）利用LR(1)分析表，利用下表给出babe的分析过程（4分）教务处印制 共3页第2页步骤栈内容余留符号串下一步动作10#bade2七、（12分，每小题6分）（1）将以下程序翻译成等价的四元式表示：while(a>5 ) if(c>5) a=b*6;else a=b*(e-c);（2）请将下面的属性翻译文法中的语义动作补全：Condition®if Expr then ;$.chain=$2.FC;Statement®Condition Statement$.Chain= :八、（10分）对于以下控制流图，给出其控制节点树，并找出其中的所有循环教务处印制 共3页第3页-