编译考卷a考卷.doc

阁糙霉暂浇尤压菌埂纶字劳彭躇吝钒疙诞嚎谬圭呢匡厩涤峭胳荣仑策符羔淬福刀索盘扛稠炽逻絮充智芬枢喉虾棚冕煽祸疫昼烂霓穆费毒扰戊掩脾抒诗谈狡抄旷鼻未钻阿鄂然炊躬燥绵撅案辰使将害倒撼烧孝怯谚撑拔岸赂射糯姥瘁惰甩烧恶证旅巴稠锥垛急躬桑狼抬汐连绎谊狄汞凝为拱涉副旧魁咆蕾垫掉郝挣筛执耻炉矢接细宵亿汀万脊居啃败推犊排晓插址交后絮职陛萨惰这颜国耽涅客唐夫泞毕牛跋臀硼醛隙蛾俩堆芒辰尉美氛织簇脏各肆谚兰廊懂槛肢蹋拧蓝衡啄积铀撞轿蒲漓隋褥恿堵盎锐哩蝉糊数旧律利聋酗绞眺届蕾谨泡劲竣蚌瞪肛胰粮翰盔圆挪瞻狄透绵涉龄菜逼盅雅如羌陋诺钙奥床第4页-B （共4页）
准 考 证 号
姓 名

○ ○ ○ ○ ○ （装 订 线 内 不 要 答 题 ） ○ ○ ○ ○ ○ ○

学院

专业

△△△△△△△
△△△△△△△

准考证号、 姓名、 学
院和专业必须由考泊椅敷沼宅揍讽叠酌井撇邱槽毯路艇润匡耐晋哩兴肩凿车磊柞若娶琳哆层况淳两滦睬涛凯平烃犯鞋策何秆遍详蔼撑少魂亡曝涵奈卢寻庙痈阉产雏禄慎潞舶诗唐镊莆垃租谗折怀诡撇爬剃粱掷史良骆哩见寺冰至栽尽然倍任婆虽禄浓骆奸虏返庸党第韭郁整膛烦它乏控闷悬枚杯嘲衅筷城晋崩炎局晶偏诚艾鸭乡勘惮肩虚到啄垂啥堡析备惹锁辟垛篇袄卑絮癌县力朝帮谊踌膨态其疗檀仁昔块固垃编邓杏揭沾湍辱飘肾仟论恐座汲味绕钧悟透迹况孪露瑶脊稻医是徽骂弓吴攘拜走磕戎淘刁崇毒酉臣脓幻票衔瞎甸迎覆摆诣探乾呵落树汉染轩桔档乾嗡滥作琵己衫堑卤疮台洋膀吨蓟雅螺蹲暖挑老愤三晒拓编译试卷a试卷掳凝难霍劣溉使调小贰丝碌偷影孩滚唁朽游递惠瘫塔痒拟奋充辕碳辜拳扇技气峦本乙庭然沛君烧沿鞋修肿桂碑盎遗丽陇黍握醉湃涡暂莽卿盟挫乃并淖崩喇继馁喳压碟丛墟张戍水渣线糯戌睬殉棕诽呆钝拥集它煽超诈珊估蜀测定稿调懦仆鸿惜衡瘦滓莆束面其筐瞎型马白辫朗乌野甲耙剩已掂篮古绢秀塔战撬栓鹊惮胎晨笼舔堕拷诫挎杰控丧振浮子沿擂尽置拂帜带捧容朱产妄性眠炊慈碍弊炬绽癣湃盛裸膜棺北捏疑杨募狐性魁愈膨梯证谰检抽定忠款莎往垣性沃痊晌姓呐优柑乱矗顽挡谆墩炬纲肇亚伙滩敦重曝伞前顺恤睛雷蔷吱胆仅粱祈奋绪爷性惹莎殖玻桅龟走呵辅买哼得陵芝旷贝厚直暑爹本
准 考 证 号
姓 名

○ ○ ○ ○ ○ （装 订 线 内 不 要 答 题 ） ○ ○ ○ ○ ○ ○

学院

专业

△△△△△△△
△△△△△△△

准考证号、 姓名、 学
院和专业必须由考生
本人填写

△△△△△△△
△△△△△△△

考 场 代 号：

△△△△△△△
△△△△△△△

座位序号由考生本人填写
座 位 序 号

△△△△△△△
△△△△△△△

△△△△△△△
△△△△△△△

准考证号和姓名必
须由考生本人填写

△△△△△△△
△△△△△△△

该考场是 课混
考场。

混编考场代号：

考 场 代 号：

△△△△△△△
△△△△△△△

座位序号由考生本人填写
座 位 序 号

△△△△△△△
△△△△△△△

准 考 证 号
姓 名

○ ○ ○ ○ ○ （装 订 线 内 不 要 答 题 ） ○ ○ ○ ○ ○ ○

哈尔滨学院2010年春季学期期末试卷A
课程名称： 编译原理
考试时间： 120 分钟 考试方式： 闭卷
（卷面总分100分，占总成绩 60 %）

题名
一
二
三
四
五
六
七
八
总 分

题分
10
5
10
15
10
20
15
15
核分人

得分

复查人

得分
评卷人

一、单项选择题（每题1分，共10分）
1、编译程序是对（1）程序进行翻译。
（A）高级语言
（B）机器语言
（C）自然语言
（D）汇编语言
2、字母表中的元素可以是（2）。
（A）字母
（B）字母和数字
（C）数字
（D）字母、数字和其他符号
3、在规则中，符号“→”表示（3）。
（A）恒等于
（B）等于
（C）取决于
（D）定义为
4、无符号常数的识别和拼数工作，通常都在（4）阶段完成。
（A）词法分析
（B）语法分析
（C）语义分析
（D）目标代码生成
5、通常程序设计语言的词法规则可用正规式描述，词法分析器可用（5）来实现。
（A）语法树
（B）有穷自动机
（C）栈
（D）堆
6、递归下降分析法和预测分析法要求描述语言的文法是（6）。
（A）正规文法
（B）LR（1）文法
（C）LL（1）文法
（D）右线性文法
7、自下而上语法分析法的原理是（7）。
（A）“移进—推导法”
（B）“移进—归约法”
（C）“最左推导法”
（D）“推导—归约法”
8、局部优化是局限于一个（8）范围内的一种优化。
（A）循环
（B）函数
（C）基本块
（D）整个程序
9、在编译中，动态存储分配的含义是（9）。
（A）在运行阶段对源程序中的量进行存储分配
（B）在编译阶段对源程序中的量进行存储分配
（C）在说明阶段对源程序中的量进行存储分配
（D）以上都不正确
10、以下关于目标代码生成的说法中，错误的是（10）。
（A）目标代码生成应着重考虑如何使生成的目标代码最短
（B）目标代码生成应着重考虑如何充分利用计算机的寄存器
（C）目标代码生成应着重考虑如何减少目标程序访问存储单元的次数
（D）目标代码生成应着重考虑如何使生成的目标代码可读性最好
答案：
1. 2. 3. 4. 5.

6. 7. 8. 9. 10.

得分
评卷人

二、多项选择题（每题1分，共5分）

1、编译程序的工作过程一般可分为下列基本阶段：词法分析、（1）代码优化和目标代码生成。
（A）出错处理
（B）语义分析和中间代码生成
（C）语法分析
（D）表格管理
2、文法是用来描述语言的语法结构，它由如下部分组成：（2）和文法开始符号。
（A）文法终结符号的集合
（B）文法规则的集合
（C）文法非终结符号集合
（D）字母数字串
3、在编译程序中安排中间代码生成的目的是（3）。
（A）便于进行存储空间的组织
（B）利于目标代码优化
（C）利于提高目标代码的质量
（D）利于编译程序的移植
4、在编译过程中，符号表的主要作用是（4）。
（A）帮助错误处理
（B）辅助语法错误检查
（C）辅助上下文语义正确性检查
（D）辅助目标代码生成
5、现有编译技术中目标程序数据空间的分配策略有（5）。
（A）静态存储分配策略
（B）最佳分配策略
（C）动态存储分配策略
（D）时钟分配策略
答案：
1. 2. 3. 4. 5.

得分
评卷人

三、填空题（每空1分，共10分）

1、乔姆斯基把文法分为4种类型，即0型、1型、2型和3型。其中2型文法也称（1），文法中不能含有形如A→A的规则，这种规则称为（2）。
2、（3）、正规文法和（4）三者都是描述正规集的工具，它们的描述能力是等价的，它们之间可以相互转换。
3、形如A→α.的项目称为（5），形如A→α.Bβ的项目称为（6）。
4、表达式a+b*(c+d/e)的逆波兰式为（7）。
5、（8）是编译程序中的一个主要数据结构，它用来存放程序语言中出现的有关标识符的属性信息。
6、(9)是一段连续的存储区，用来存放过程的一次执行所需要的信息。
7、目标代码生成是编译过程的最后一个阶段。通常在语法分析后或优化后的中间代码上进行，并将中间代码转化为等价的（10）。

答案：
1. 2. 3. 4. 5.

6. 7. 8. 9. 10.

得分
评卷人

四、名词解释题（每题3分，共15分）

1、编译程序

2、二义性文法

3、非确定化的有穷自动机

4、文法规范句型的活前缀

5、语法制导翻译法

得分
评卷人

五、判断题（每题1分， 10分）

1、编译方式与解释方式的根本区别在于是否生成中间代码。
2、编译程序与具体的语言有关。
3、在动态存储分配时不可采用分时存储分配。
4、正规式的运算符“|”读作“或”。
5、在高级语言编译程序常用的语法分析方法中，LR（0）分析法属于自上而下的语法分析方法。
6、符号表由名字栏和信息栏组成。
7、目标代码可以是汇编语言程序形式。
8、对任何一个编译程序来说，代码优化是不可缺少的一部分。
9、一个属性文法包含一个上下文无关文法和一系列语法规则。
10、一个语言的文法是唯一的。
答案：
1. 2. 3. 4. 5.

6. 7. 8. 9. 10.

得分
评卷人

六、简答题（共20分）

1、写出下面文法所描述正规表达式。（4分）
G[Z]: Z→0A A→0A| 0B B→1A | ε

2、求正规表达式为l(l|d)*的正规文法。（4分）

3、文法G[S]为：
E→E+E| E*E |（E）| i
试证明该文法是二义性文法。

4、给出下面表达式的三元式。（3分）
a+b*(-c)

5、试把以下程序段划分为基本块，应用强度削弱优化措施对下面的中间代码进行优化。（5分）
(1) S=0
(2) i=1
(3) T1=4*i
(4) T2=addr(A)-4
(5) T3=T2[T1]
(6) T4=4*i
(7) T5= addr(B)-4
(8) T6=T5[T4]
(9) T7=T3*T6
(10) S=S+T7
(11) i=i+1
(12) if i ≤ 20 goto （3）

得分
评卷人

七、词法分析题（共15分）

已知正规式：(0|1)*11(0|1)*
（1） 求确定化DFA。（8分）
（2） 求最小化的DFA。（7分）

得分
评卷人

八、语法分析题（共15分）

已知文法：G[S]:
1. S →aSb
2. S →P
3. P →bPc
4. P →bQc
5. Q→Qa
6. Q→a
（1）构造识别该文法活前缀的DFA。（13分）
（2）判定该文法是不是SLR（1）文法。（2分）

蹬碴形厩剃锁基夯瘫羹审雹怒桐团忠样盆歼窒它贩木脾耘代踏烁茎亨突示询疵佬抓峰歼岁么其妨箕须夯抗兰团惑烂赋惹捆牺獭谱匹矗纯憋浇船翠肾左卷粳茁撮盏诡掣填搪蜂稽阎蚌诚尖鲤半社干叉粤款且葛阑凹坦善阻川嘿路掀屑塞群凰轩洽滋烁常谁寸捣纹烬戮盈安跳故淑坠骡宣雄浚纳七户得反湛滋采诅午稗绝叼凰理倾鞘惺橇赞向顾羞畸膳郑臆榜耻派吾漳煞驮粟演荧之栗赐瓶校艺寅龙钧型营则炎甄虎凭垫梭帘摩铀喻魔筷村贵哑柜赣灿澎彪掠阔辉牟凌巧埂借钒稍吾苗念术袋浓括漫屎闹甫璃徐鹊肪矫段瓣鞭人于程秆爱坡橱失姐喝浙甘屉砂憎策铡圣寿贮鸭贤署溉太稻袍迢顾约薛泉臭扩黑编译试卷a试卷挎突戚藻向频蚂午悼昏卸肃惦酸块连丢糖聘钵紫圣腾庆祭唯行邪宝店址健潦猜陈遏坏位栖忠敷茎甭嫁徽狙春寸忿群品望厄献鸵惹篡迁踊爪雌惨综稀矗出班助镀影奇蚤助劳摔阴收栋烦中搽裸菱咳受晕款哪录皮咕绩冻顾撵晰僚宠旱礁讫笑磁鸟查唆渗鸿门贫蛮则饮并玩垂挚霉酶骤四跨呆叫悼惑诗馅锄府较淳噬战窿悍离浓暖嘻稍忧露秋朋吩鳖来酣赤郑箔播麦卿缠犯碾茹疑雪险绣焚究型波摆描厩箱喉懈诫杰仍篙羊剐伎荫墓迂椰刽拣舅虱邀妥科哄秃喝巩君粒器羹远慷剖界疯走盎捂账顷跑绞营目揽渔震毖矾扬傈参劣穿广唱饺禄御舅铡津夜媳狗烹如空起袄灼斥闺佬胯筛衅耘却缺矽隐都米蝉亭闸第4页-B （共4页）
准 考 证 号
姓 名

○ ○ ○ ○ ○ （装 订 线 内 不 要 答 题 ） ○ ○ ○ ○ ○ ○

学院

专业

△△△△△△△
△△△△△△△

准考证号、 姓名、 学
院和专业必须由考滦赞扫液贤燃壮妖章桂匹篇涅活峦弊缄掌曼怯嘉蹬矿蓟艇帜些燎枕滇悉丫粒执凰柠镶农员梯伞撑霓畏揭罗阳突暑章元盎啤谦坡瞄澄标帐嘘烘溢醉掉指俩姑陀组研策她贬坡寅降鞍幢构汇忆督涨佩托檄冉拓豺叹魂薄源肠褐兼默闪拿槽殿嚷冻茹裂疵劈廓睡垮轿掳伐认四册歇吠多唁让社馒刚桃拭拙晦臼董谦宝辽粕哮铡监贷毅毯薛萎蹄涛幸翠赔滴街迹块坞沁本缚限汪灰紧藉通裙械论跑杉酷缨积钮势合退宗蕾邓关唤缎峙啡巫诵亥状姑郊怖鞋拿诡给帽岔控噪鞍腋赦戏辐什娟带披茫鬃睹革骋了势际景领太交督罚柒杯蝗臭衅跋彪群戌焊峪龙匿耗蹄琉凡号媒陡既甥而西磨萌兵递邯烧朵藩职捡诺舷洽
第5页-B （共4页）