专业 班级 学号 学生签名:
试卷编号: ( A )卷
编译原理(B) 课程 课程类别:必修课 闭卷(√)、开卷( ) : 考试日期:2013.06.08 题号 一 二 三 四 五 六 七 八 九 十 总分 累分人 100 签名 题分 10 20 10 10 15 20 10 5 得分 考生注意事项:1、本试卷共 7 页,总分 100 分,考试时间 120 分钟。
2、考试结束后,考生不得将试卷、答题纸和草稿纸带出考场。
一、是非判断题(在下列各题中,你认为正确的,请在题目前的括号内打“√”,错的打“×”。)(共10小题,每题1分,共计10分)
( )1. 编译程序与解释程序的主要不同之处在于:编译程序
要生成目标代码,而解释程序不会目标代码。
得分 评阅人 ( )2. 在编译程序的设计中,中间代码生成和优化功能并不是必须的。 ( )3. 编译程序的实现与具体的机器有关,与具体的语言也是有关的。 ( )4. 一个句型只对应唯一的一颗语法树。
( )5. 文法G产生的全体句型的集合就是该文法描述的语言。 ( )6. 描述一个语言L的文法是唯一的。
( )7.一个文法G是2型文法,则该文法一定是3型文法。 ( )8. 一个递归文法G所描述的语言是一个无限集合。
( )9. 一个高级程序设计语言的词法可以用一个右线型文法来描述。 ( )10. 在句型分析中,最左归约序列与最右推导序列是互逆序列。
第 1 页 共 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)
第 2 页 共 7 页
三、对文法 G[S] :
S→A│S+A │S–A A→B│A*B B→(S)│b 写出句型A-b+(S) 的短语、直接短语、句柄和 素短语。(共10分)
得分 评阅人
四、给定文法G[S]:S→(A)│a│b A→AcS│S 得分请在下面的算符优先关系表中标记为“?”的栏目 内填写出正确的优先关系(<、> 或 =):(共10分)
a b ( ) c a > > b > ? ( ? ? ? ? ? ) > > c ? ? ? ? > # < < < 评阅人 # > > > = 第 3 页 共 7 页
五、设计一个最小状态数的DFA,其输入字母表
是{a,b},它能接受以以ab结尾的所有由a和 b组成的符号串。(15分)
得分 评阅人 第 4 页 共 7 页
六、给定文法G[S]: (共 20 分)
S→AaAb│BbBa A→ε B→ε 1. 计算各非终结符号的Follow集;(6分) 2. 计算各产生式的SELECT集;(4分) 3. 证明该文法是LL(1)文法;(2分) 4. 证明该文法不是SLR(1)文法。(8分)
得分 评阅人
第 5 页 共 7 页
七、 把下列语句翻译成四元式 (四元式的编号从100开始)。(10分)
while A∨B∧~C∨D do
得分 评阅人 if a > b then x := m - k else y := m + k;
第 6 页 共 7 页
八、综合应用题 (共 5 分)
得分 评阅人 有一台自动售货机,接收1分和2分硬币,出售3分钱一 块的硬糖。顾客每次向机器中投放≥3分的硬币,便可以得到 一块硬糖(注意:只给一块硬糖且不找钱)。 (1)给出售货机售糖的正规表达式。
(2)构造出识别上述正规表达式的自动机(FA)。
第 7 页 共 7 页
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁