搜索
第1页共7页华东交通大学2012—2013学年第二学期考试卷试卷编号：（A）卷编译原理（B）课程课程类别：必修课闭卷（√）、开卷()：考试日期：2013.06.08题号一二三四五六七八九十总分累分人签名题分102010101520105100得分考生注意事项：1、本试卷共7页，总分100分，考试时间120分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、是非判断题（在下列各题中，你认为正确的，请在题目前的括号内打“√”，错的打“×”。）（共10小题，每题1分，共计10分)（）1.编译程序与解释程序的主要不同之处在于：编译程序要生成目标代码，而解释程序不会目标代码。（）2.在编译程序的设计中，中间代码生成和优化功能并不是必须的。（）3.编译程序的实现与具体的机器有关，与具体的语言也是有关的。（）4.一个句型只对应唯一的一颗语法树。（）5.文法G产生的全体句型的集合就是该文法描述的语言。（）6.描述一个语言L的文法是唯一的。（）7.一个文法G是2型文法，则该文法一定是3型文法。（）8.一个递归文法G所描述的语言是一个无限集合。（）9.一个高级程序设计语言的词法可以用一个右线型文法来描述。（）10.在句型分析中，最左归约序列与最右推导序列是互逆序列。得分评阅人承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业班级学号学生签名：第2页共7页二、单项选择填空题（共10小题，每题2分，共计20分)1．在语法分析中，递归下降分析法属于分析方法。A．自顶向下；B．自底向上；C．自左向右；D．自右向左2．一个文法G[S]：S→a│aB，B→aS，该文法所描述的语言是。A．{ai│i≥0}；B．{a2i+1│i≥0}；C．{a2i│i≥0}；D．{a2i+1│i≥1}3．由于受到具体机器主存容量的限制，编译程序的几个不同阶段的工作往往被组合成遍，各阶段的往往是进行的。A．并行；B．顺序；C．穿插；D．成批4．文法G[S]:S→S+S|S-S|S*S|S/S|i，是。A.LL(1)文法B.算符优先文法C.非二义性文法D.二义性文法5．一个句型中的最左称为该句型的句柄。A．直接短语；B．短语；C．素短语；D．终结符号6．文法的二义性和语言的二义性是两个的概念。A．相同；B．不同；C．无法判定；D．在某种意义是相同的7．LL（K）文法二义性的。A．不一定都是；B．都是；C．都不是；D．中只有LL(1)文法不是8．在LR分析方法的分析栈中存放的状态是识别的DFA状态。A．句柄；B．项目；C．前綴；D．活前綴9．表达式a+b*（c–d）的逆波兰式表示形式是。A．abcd-*+；B．-*+abcd；C．cd-b*a+；D．ab+cd-*10．在LR文法中，的描述能力最强。A．LR(0)；B．LR(1)；C．SLR(1)；D．LALR(1)得分评阅人第3页共7页三、对文法G[S]:S→A│S+A│S–AA→B│A*BB→(S)│b写出句型A-b+(S)的短语、直接短语、句柄和素短语。（共10分）四、给定文法G[S]：S→(A)│a│bA→AcS│S请在下面的算符优先关系表中标记为“？”的栏目内填写出正确的优先关系（、或=）：（共10分）ab()c#ab？(？？？？？)c？？？？#=得分得分评阅人得分得分评阅人第4页共7页五、设计一个最小状态数的DFA，其输入字母表是{a，b}，它能接受以以ab结尾的所有由a和b组成的符号串。（15分）得分得分评阅人第5页共7页六、给定文法G[S]:(共20分)S→AaAb│BbBaA→εB→ε1.计算各非终结符号的Follow集；（6分）2.计算各产生式的SELECT集；（4分）3.证明该文法是LL(1)文法；（2分）4.证明该文法不是SLR(1)文法。（8分）得分评阅人第6页共7页七、把下列语句翻译成四元式(四元式的编号从100开始）。（10分)whileA∨B∧～C∨Ddoifabthenx:=m-kelsey:=m+k;得分评阅人第7页共7页八、综合应用题(共5分)有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放≥3分的硬币，便可以得到一块硬糖（注意：只给一块硬糖且不找钱）。（1）给出售货机售糖的正规表达式。（2）构造出识别上述正规表达式的自动机（FA）。得分评阅人