编译原理试题及参考答案.doc
《编译原理试题及参考答案.doc》由会员分享,可在线阅读,更多相关《编译原理试题及参考答案.doc(16页珍藏版)》请在咨信网上搜索。
1、课程测试试题(04A卷)I、命题院(部): 数学与计算机科学学院 II、课程名称: 编译原理 III、测试学期:20062007 学年度第 1 学期IV、测试对象: 数计、国交 学院 计科 专业 2004 级 1、2、国交 班V、问卷页数(A4): 3 页VI、答卷页数(A4):4 页VII、考试方式: 闭卷 (开卷、闭卷或课程小论文,请填写清楚)VIII、问卷内容:(请老师在出题时安排紧凑,填空题象征性的留出一点空格,学生将所有的答案做在答题纸上的规定位置,并写清楚大题、小题的题号)一、填空题(共30分,30个空,每空1分)1、典型高级程序设计语言编译系统的工作过程一般分为六个阶段,即词法分
2、析、语法分析、语义分析、中间代码生成、 、目标代码生成。编译阶段的两种组合方式是 组合法和按遍组合法,这两种组合方式的主要参考因素都是 的特征。2、Chomsky将文法按其所表示语言的表达能力,由高往低分为四类:0型,1型,2型,3型文法。其中,2型文法也称 ,它的所有规则 都满足: , (VNVT) *且 ,仅当= 时例外。3、现代编译系统多采用 方法,即在语法分析过程中根据各个规则所相联的 或所对应的语义子程序进行翻译的办法。该方法使用 为工具来说明程序设计语言的语义。 4、构造与NFA M等价的正规文法G的方法如下:(1)对转换函数f(A,a)=B或f(A,)=B,改成形如 或 的产生式
3、;(2)对可识别终态Z,增加一个产生式: 。5、代码生成要考虑的主要问题:充分利用 的问题、选择 的问题、选择 的问题。6、设有穷自动机M=(K,S,f,S,Z),若当M为 时,满足z0f(S,)且z0Z,或当M为 时,满足f(S,)=PZ,则称符号串S*可被M所 。7、符号表中每一项对应一个多元组。符号表项的组织可分为 组织、 组织、 组织等。8、对于AN 定义A的后续符号集:FOLLOW(A)=a|S=*uA, aT,且a ,uT*,+;若 ,则#FOLLOW(A)。也可以定义为:FOLLOW(A)=a|S=*Aa,aT。若有 ,则规定#FOLLOW(A)。9、基本块的定义:一个基本块是指
4、程序中一个 执行的语句序列,其中只有一个入口和一个出口。入口是程序第一个语句或转移语句的目标语句,或转移语句的后继第一个语句。出口是程序 或转移语句。在基本块范围内的优化称为 。10、预测分析器由预测分析表、先进后出栈(用来存放分析过程的语法符号)和 三部分组成。其中预测分析表是一个二维矩阵,其形式为MA,a,其中AVN,aVT或#。若有产生式A,使得a ,则将A填入MA,a中。(书写时,通常省略规则左部,只填)。对所有 的MA,a标记为出错。二、简述题(共20分,4个小题,每小题5分)1、简述将NFA转换为最小化DFA的步骤。2、简述静态存储分配、栈式存储分配和堆式存储分配的特点和主要用途。
5、3、以表达式 a:=b*(-c)+b/(-d)为例,简述常用的三种中间代码表示形式。4、简述判别文法是否为LL(1)文法的步骤和将一个非LL(1)文法转换为LL(1)文法的方法。三、应用题(共50分)1、有文法GS:(12分)SaAS|aASbA|SS|ba(1)证明aabbaa是文法的一个句子。(3分)(2)构造句子aabbaa的语法树。(3分)(3)指出该句子的所有短语、直接短语和句柄。(6分)2、对文法GE:(15分)E#E# EE+T|TTT*F|F FPF|P P(E)|i(1)计算GE的FIRSTVT和LASTVT。(5分)(2)构造GE的算符优先关系表,并说明GE是否为算符优先文
6、法。(5分)(3)给出输入串w=i+i# 的算符优先分析过程。(5分)3、对以下基本块:(8分)A:=5 B:=R+rT0:=A+BT1:=2*AT2:=B+AT3:=A+AX1:=T1+T2X2:=T0*T3(1)画出基本块的DAG图。(3分)(2)根据DAG结点原来的构造顺序重写四元式。(2分)(3)假设基本块出口后只有X1,X2还被引用,试写出优化后的四元式序列。(3分)4、对文法GS: (15分)0)SS 1)S A 2)S B 3)A aAe 4)A a 5)B bBd 6)B b(1)试构造GS的LR(0)项目集规范族DFA。(4分) (2)试构造GS的SLR(1)分析表,并判断它
7、是否为SLR(1)文法。(4分)(3)试用SLR(1)方法分析输入串aae#。(4分)(4)GS是否为LR(0)、LR(1)和LALR(1)文法?为什么?(3分)课程测试试题(04B卷)I、命题院(部): 数学与计算机科学学院 II、课程名称: 编译原理 III、测试学期:20062007 学年度第 1 学期IV、测试对象: 数计、国交 学院 计科 专业 2004 级 1、2、国交 班V、问卷页数(A4): 3 页VI、答卷页数(A4):4 页VII、考试方式: 闭卷 (开卷、闭卷或课程小论文,请填写清楚)VIII、问卷内容:(请老师在出题时安排紧凑,填空题象征性的留出一点空格,学生将所有的答
8、案做在答题纸上的规定位置,并写清楚大题、小题的题号)一、填空题(共30分,30个空,每空1分)1、典型编译过程一般分为词法分析、语法分析、语义分析、 (并非所有的编译程序都包含此阶段)、代码优化、目标代码生成六个阶段,其中词法分析的任务是对构成源程序的字符串进行扫描和分解,识别出 (如标识符等)符号;为代码生成阶段收集类型信息,并进行类型审查和违背语言规范的报错处理是 的任务。2、文法是一些规则的有穷集合,它是以有穷规则集来刻划无穷 集合的工具。文法的四元组表示G =(VN,VT,P,S)中,元素VN,VT 分别是非空有限的 。且二者交集为;P为产生式/规则集,是文法的核心部分;S VN,是文
9、法的开始符号(或识别符) ,它是一个非终结符,至少要在一条规则中作为 出现。3、构造()项目集规范族的项目类型分为四种:形如A.a的 、形如 的待约项目、形如AB.的归约项目、形如S.的 。4、一个优先关系矩阵对应的优先函数 ;所表示优先关系唯一的矩阵不一定存在优先函数;当两个终结符对之间无优先关系时, 可以将相应元素置出错信息,而使用 却无法识别这种情况,不能准确指出出错位置。5、在编译程序中用符号表来存放语言中出现的有关 的语义特征属性信息。程序设计语言中通用的标识符属性主要有如下几种:符号名、符号的 、符号的存储类别、符号的 、符号变量的存储分配信息及数组的内情向量等其它属性。6、如果文
10、法G=( VN,VT,P,S)中不存在形如 ABC的产生式,其中B、C为非终结符,则称之为 。在此基础上,如果 a,bVT, ab,ab,ab 至 有一个成立,则称之为 。 7、 分为三类: 的机器语言代码; 的机器语言代码;汇编语言(宏汇编)。8、在程序流中,一个循环必须具有以下性质:1) ,即序列中任意两点都可达,若只有一个结点,则有一条返回本身的回边;2) ,即从序列外某结点,有一条有向边指向它,或它为图中首结点。9、LR分析步骤:1)置输入指针ip指向输入串的第一个符号;令S是栈顶状态, a 是 ip 所指向的符号;将#压入符号栈,将开始状态0压入状态栈;2)根据分析表重复执行如下过程
11、:如果actionS,a=Sj,则把 入符号栈,把 入状态栈,并使 ip 指向下一个输入符号;如果actionS,a=rj,则从栈顶弹出第j条规则右部串长|个符号,把 压入符号栈,将 压入状态栈,并输出规则 A;如果actionS,a=acc,则分析成功,否则报错。10、过程(函数)是结构化程序设计的主要手段。调用与被调用过程两者之间的信息主要通过 或参数来传递。参数分为 ,常用的参数传递方式有传地址、传值、传名等。二、简述题(共20分,4个小题,每小题5分)1、简述运行目标程序时所需空间的种类。2、简述算符优先分析算法的步骤和算符优先分析方法的优、缺点。3、简述代码优化的概念和分类,并列举出
12、四种以上常用的代码优化技术。 4、简述判别任意给定的一个上下文无关文法GS是否为LALR(1)文法的过程。三、应用题(共50分)1、有文法GE:(16分)E T + ETT T * FFF ( E )i(1)证明T+T*F+i是文法的一个句型。(3分)(2)构造型T+T*F+i的语法树。(3分)(3)指出该句型的所有短语、直接短语和句柄。(7分)(4)指出该句型的所有素短语和最左素短语。(3分)2、将下列条件语句翻译成四元式的中间代码形式:(6分)if ab or cf then s1 else s23、有正规文法GS: (12分)SaA|bB AbS|b BaS|a (1)构造对应的正规式R
13、,使得L(R)=L(G)。 (3分)(2)构造对应的NFA状态图,使得L(M)=L(R)。 (3分)(3)将所得NFA确定化为DFA。 (3分)(4)将所得DFA最小化。 (3分)4、对表达式文法GE: (16分)E E - TTT T FFF ( E )a(1)判断GE是否为LL(1)文法。若不是,改造为LL(1)文法。(8分)(2)构造预测分析表,并对输入串w=a-aa#进行预测分析。(8分)课程测试试题(03A卷)-以下为教师填写-I、命题院(部): 数学与计算机科学学院 II、课程名称: 编 译 原 理 III、测试学期:20052006学年度第1学期IV、测试对象: 数计 学院 计算
14、机科学技术 专业 2003 级 1、2、3 班V、问卷页数(A4): 4 页VI、答卷页数(A4): 6 页VII、考试方式: 闭卷 (开卷、闭卷或课程小论文,请填写清楚)VIII、问卷内容:(请老师在出题时安排紧凑,填空题象征性的留出一点空格,学生将所有的答案做在答题纸上的规定位置,并写清楚大题、小题的题号)一、填空 (30分)1、将编译过程的各阶段划分为前端或后端和将编译程序分遍的主要参考因素都是( )和( )的特征。2、( )是一种语法分析程序的自动构造工具,用它可以直接构造各种语言的语法分析器;而( )是一种词法分析程序的自动构造工具,用它可以直接构造各种语言的词法分析器。3、假设GS
15、是一个文法,如有Sx,则称x是该文法G的( );文法G产生的( )的全体称为该文法所描述的语言。4、所谓2型文法就是指( )文法,若用G =(VN,VT,P,S)表示它,则它要求G中的所有规则都满足:是( ),而属于(VN U VT)*。5、文法中形如UU的规则称为( )规则;由不可达的非终结符或不可终止的非终结符作为左部的规则称为( )规则。在实用文法中一般不允许含有这两类规则。6、在用五元组表示的确定的有穷自动机DFAM=(K,V,F,S,Z)中,元素V表示字母表;元素S表示唯一的初态,它是状态集K的一个元素;元素F表示( );元素Z表示终态集,它是状态集K的一个( )。7、语法分析方法分
16、为自上而下与自下而上两类,自上而下的分析方法方要有递归子程序分析法和( );而自下而上的分析方法主要有( )和LR分析方法。8、LR(0)项目集规范族中的项目可分为四类,它们是移进项目、( )、归约项目和接受项目。其中,接受项目是( )的一种特例。9、将非LL(1)文法转换为等价的LL(1)文法所采用的两种方法是( )和( )。但这两种方法并不能保证所有的非LL(1)文法都能转换为等价的LL(1)文法。10、通常局部优化是指基本块内的优化,所谓基本块是指程序中一顺序执行的语句序列,其中只有一个( )语句和一个( )语句。11、算符优先分析时,在句型N1a1N2ai-1NiaiNi+1ai+1a
17、jNj+1aj+1Nj+2中,寻找的最左素短语NiaiNi+1ai+1ajNj+1中的终结符应满足下优先关系:( )、( )、( )。12、在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息,这些信息集中反映了标识符的语义特征属性。符号表的功能可以归结为三个主要方面,即( )、作为上下文语义合法性检查的依据和作为( )的依据。13、根据优先关系矩阵计算优先函数可用迭代法或优先关系图法,但先关系图方法计算出来的优先函数不一定有效,当( )时,所得的优先函数无效,这时也说明该优先关系矩阵不存在优先函数。14、当一个过程调用其他过程时,调用过程和被调用过程之间的通信经由非局部变量或者经由
18、参数传递,常用的参数传递方式有( )、( )等。15、现代很多编译程序都采用( )翻译方法,它是指在语法分析过程中,随着分析的步步进展,根据每个规则所对应的语义子程序或语义动作进行翻译的办法。这种方法使用( )为工具来说明程序设计语言的语义。二、结合你所熟悉的一门高级语言的编译系统,简述典型编译程序在各个工作阶段的任务。(共7分)三、给定正规式R=(01|10) (01|10)* ,要求: (10分)1、 构造对应的正规文法G,使得L(G)=L(R)。 (4分)2、 构造对应的NFA M状态图,使得L(M)=L(R)。 (3分)3、将所得NFA M确定化为DFA。 (3分)四、现有文法GE:
19、(共10分)EE+T|E-T|TTT*F|T/F|FFi|(E) 1、 证明:E-F*(i)是文法的一个句型。(3分)2、 构造句型E-F*(i)的语法推导树。(2分)3、 指出该句型所有短语、直接短语和句柄。(5分)五、任意给定一个文法GS: (10分)1、 给出判断GS是否为LL(1)文法的步骤。(4分)2、 如果GS是LL(1)文法,怎样构造它的预测分析表?(3分)3、 怎样根据预测分析表对给定的某个输入串进行预测分析?(3分)六、现有文法GE:(共15分)E E;D|DDD(T)|HHa|(E) TT*E|E1、计算GE的FIRSTVT和LASTVT;(4分)2、构造GE的算符优先关系
20、表,并说明GE是否为算符优先文法;(5分)3、给出输入串(a*a)# 的算符优先分析过程,并据此说明算符优先分析方法的优点和缺点。(6分)七、现有文法GS: (共18分)0) S S1) S L = R2) S R3) L * R4) L i5) R L1、 构造GS的LR(0)项目集规范族DFA,并据此判断GS是否为LR(0) 文法或SLR(1)文法。(6分)2、 构造GS的LR(1)项目集规范族DFA,并据此判断GS是否为LR(1)文法或LALR(1)文法。(6分)3、 给出相应的LALR(1)分析表。(3分)4、 简述LR分析算法。(3分)课程测试试题(03B卷)-以下为教师填写-I、命
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 试题 参考答案
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。