编译原理习题及答案(整理后).doc
《编译原理习题及答案(整理后).doc》由会员分享,可在线阅读,更多相关《编译原理习题及答案(整理后).doc(28页珍藏版)》请在咨信网上搜索。
1、_第一章1、将编译程序分成若干个“遍”是为了 。 b使程序的结构更加清晰 2、构造编译程序应掌握 。 a源程序b目标语言 c编译方法 3、变量应当 。 c既持有左值又持有右值 4、编译程序绝大多数时间花在 上。 d管理表格5、 不可能是目标代码。d中间代码6、使用 可以定义一个程序的意义。 a语义规则 7、词法分析器的输入是 。 b源程序 8、中间代码生成时所遵循的是- 。 c语义规则 9、编译程序是对 。 d高级语言的翻译10、语法分析应遵循 。 c构词规则 二、多项选择题1、编译程序各阶段的工作都涉及到 。b表格管理c出错处理 2、编译程序工作时,通常有 阶段。 a词法分析b语法分析c中间
2、代码生成 e目标代码生成三、填空题 1、解释程序和编译程序的区别在 于是否生成目标程序 。2、编译过程通常可分为5个阶段,分别是 词法分析 、语法分析中间代码生成 、代码优化和目标代码生成。3、编译程序工作过程中,第一段输入是 源程序 ,最后阶段的输出为 标代码生成程序。4、编译程序是指将 源程序 程序翻译成 目标语言 程序的程序。 一、单项选择题1、文法G:SxSx|y所识别的语言是 。a. xyxb. (xyx)*c. xnyxn(n0)d. x*yx*2、文法G描述的语言L(G)是指 。a. L(G)=|S , VT*b. L(G)=|S, VT*c. L(G)=|S,(VTVN*)d.
3、 L(G)=|S, (VTVN*)3、有限状态自动机能识别 。a. 上下文无关文法b. 上下文有关文法c.正规文法d. 短语文法4、设G为算符优先文法,G的任意终结符对a、b有以下关系成立 。a. 若f(a)g(b),则abb.若f(a)g(b),则a0c. anbmcmdn|n,m0d. anbncmdm|n,m0e. anbncndn|n05、自下而上的语法分析中,应从 开始分析。a. 句型b. 句子c. 以单词为单位的程序d. 文法的开始符e. 句柄6、对正规文法描述的语言,以下 有能力描述它。a.0型文法b.1型文法 c.上下文无关文法 d.右线性文法 e.左线性文法 三、填空题1、文
4、法中的终结符和非终结符的交集是 。词法分析器交给语法分析器的文法符号一定是 ,它一定只出现在产生式的 部。2、最左推导是指每次都对句型中的 非终结符进行扩展。3、在语法分析中,最常见的两种方法一定是 分析法,另一是 分析法。4、采用 语法分析时,必须消除文法的左递归。5、 树代表推导过程, 树代表归约过程。6、自下而上分析法采用 、归约、错误处理、 等四种操作。 7、Chomsky把文法分为 种类型,编译器构造中采用 和 文法,它们分别产生 和 语言,并分别用 和 自动机识别所产生的语言。四、判断题1、文法 SaS|bR|描述的语言是(a|bc)* ( ) RcS2、在自下而上的语法分析中,语
5、法树与分析树一定相同。 ( )3、二义文法不是上下文无关文法。 ( )4、语法分析时必须先消除文法中的左递归。( )5、规范归约和规范推导是互逆的两个过程。( )6、一个文法所有句型的集合形成该文法所能接受的语言。( )五、简答题1、句柄2、素短语3、语法树4、归约5、推导六、问答题1、给出上下文无关文法的定义。2、文法GS: SaSPQ|abQ QPPQ bPbb bQbc cQcc(1)它是Chomsky哪一型文法?(2)它生成的语言是什么?3、按指定类型,给出语言的文法。L=aibj|ji1的上下文无关文法。4、有文法G:SaAcB|BdAAaB|cBbScA|b(1)试求句型aAaBc
6、bbdcc和aAcbBdcc的句柄;(2)写出句子acabcbbdcc的最左推导过程。5、对于文法GS: S(L)|aS|a LL, S|S(1)画出句型(S,(a)的语法树。(2)写出上述句型的所有短语、直接短语、句柄和素短语。6、考虑文法GT:TT*F|FFFP|PP(T)|i证明T*P(T*F)是该文法的一个句型,并指出直接短语和句柄。单选解答 1、选c。2、选a。3、选c。4、虽然a与b没有优先关系,但构造优先函数后,a与b就一定存在优先关系了。所以,由f(a)g)(b)或f(a)g(b)并不能判定原来的a与b之间是否存在优先关系:故选c。EE + FE + T PT iP #+#图2
7、-8-1 句型P+T+I的语法及优先关系5、如果文法G无二义性,则最左推导是先生长右边的枝叶:对于d,如果有两个不同的是了左推导,则必然有二义性。故选a。6、选c。7、由图2-8-1的语法树和优先关系可以看出应选b。8、规范推导是最左推导,故选d。9、由TT,和T( 得FIRSTVT(T)=(,,); 由TS得FIRSTVT(S)FIRSTVT(T),而FIRSTVT(S)=b,(;即 FIRSTVT(T)=b,(,,; 因此选c。 10、d 11、c 12、b 13、b 14、b多选解答 1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e填空解答
8、1、空集 终结符 右 2、最左 3、自上而上 自下而上 4、自上而上 5、语法 分析 6、移进 接受 7、4 2 型 3型 上下文无关语言 正规语言 下推自动机 有限判断解答 1、对 2、错 3、错 4、错 5、错 6、错 简答解答 1、句柄:一个句型的最左直接短语称为该句型的句柄。2、素短语:至少含有一个终结符的素短语,并且除它自身之外不再含任何更小的素短语。3、语法树:满足下面4个条件的树称之为文法GS的一棵语法树。每一终结均有一标记,此标记为VNVT中的一个符号;树的根结点以文法GS的开始符S标记;若一结点至少有一个直接后继,则此结点上的标记为VN中的一个符号;若一个以A为标记的结点有K
9、个直接后继,且按从左至右的顺序,这些结点的标记分别为X1,X2,XK,则AX1,X2,XK,必然是G的一个产生式。4、归约:我们称直接归约出A,仅当A 是一个产生式,且、(VNVT)*。归约过程就是从输入串开始,反复用产生式右部的符号替换成产生式左部符号,直至文法开始符。5、推导:我们称A直接推出,即A,仅当A 是一个产生式,且、(VNVT)*。如果12n,则我们称这个序列是从1至2的一个推导。若存在一个从1n的推导,则称1可推导出n。推导是归约的逆过程。 问答1解答一个上下文无关文法G是一个四元式(VT,VN,S, P),其中:VT是一个非空有限集,它的每个元素称为终结符号;VN是一个非空有
10、限集,它的每个元素称为非终结符号,VTVN=;S是一个非终结符号,称为开始符号;P是一个产生式集合(有限),每个产生式的形式是P,其中,PVN,(VTVN)*。开始符号S至少必须在某个产生式的左部出现一次。 2解答 (1)由于产生式左部存在终结符号,且所有产生式左部符号的长度均小于等于产生式右部的符号长度,所以文法GS是Chomsky1型文法,即上下文有关文法。(2)按产生式出现的顺序规定优先级由高到低(否则无法推出句子),我们可以得到: SabQabc SaSPQaabQPQaabPQQaabbQQaabbcQaabbcc SaSPQaaSPQPQaaabQPQPQaaabPQQPQaaab
11、PQPQQaaaPPQQQaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc 于是得到文法GS生成的语言L=anbncn|n13【解答】(1)由L=aibj|ji1知,所求该语言对应的上下文无关文法首先应有SaSb型产生式,以保证b的个数不少于a的个数;其次,还需有SSb或SbS型的产生式,用以保证b的个数多于a的个数;也即所求上下文无关文法GS为:GS:SaSb|Sb|b4【解答】(1)分别画出对应两句型的语法树,如图2-8-2所示句柄:AaB Bd Sa A c B AaB b S c AB d cb(a)S a A c BB S c AB d c(b
12、)图2-8-2 语法树(2)句子acabcbbdcc的最左推导如下: SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcA acabcbbdcAacabcbbdcc S( L )L , SS ( L ) S a图2-8-3 句型(S,(a)的语法树5【解答】(1)句型(S,(a)的语法树如图2-8-3所示(2)由图2-8-3可知:短语:S、a、(a)、S,(a)、(S,(a);直接短语:a、S;句柄:S;素短语:素短语可由图2-8-3中相邻终结符之间的优先关系求得,即;# (,(a ) ) #因此素短语为a。TT * FF PP ( T )T * F图2-8-4
13、 句型T*P(T*F)的语法树6【解答】首先构造T*P(T*F)的语法树如图2-8-4所示。由图2-8-4可知,T*P(T*F)是文法GT的一个句型。直接短语有两个,即P和T*F;句柄为P。第三章一、单项选择题1、词法分析所依据的是 。a. 语义规则b. 构词规则c. 语法规则d. 等价变换规则2、词法分析器的输出结果是 。a. 单词的种别编码b. 单词在符号表中的位置c. 单词的种别编码和自身值d. 单词自身值3、正规式M1和M2等价是指 。a. M1和M2的状态数相等b. M1和M2的有向弧条数相等c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向弧条数相等4、状态转换图(见
14、图3-6-1)接受的字集为 。 0 1 0图3-6-1YXa. 以 0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确,因此, 。a. 词法分析器应作为独立的一遍 b. 词法分析器作为子程序较好c. 词法分析器分解为多个过程,由语法分析器选择使用 d. 词法分析器并不作为一个独立的阶段二、多项选择题1、在词法分析中,能识别出 。a. 基本字b. 四元式c. 运算符d. 逆波兰式e. 常数2、令=a,b,则上所有以b开头,后跟若干个ab的字的全体对应的
15、正规式为 。a. b(ab)*b. b(ab)+c.(ba)*bd. (ba)+be. b(a|b)三、填空题1、确定有限自动机DFA是 的一个特例。2、若二个正规式所表示的 相同,则认为二者是等价的。3、一个字集是正规的,当且仅当它可由 所 。四、判断题1、一个有限状态自动机中,有且仅有一个唯一终态。( )2、设r和s分别是正规式,则有L(r|s)=L(r)|L(s)。( )3、自动机M和M的状态数不同,则二者必不等价。( )4、确定的自动机以及不确定的自动机都能正确地识别正规集。( )5、对任意一个右线性文法G,都存在一个NFA M,满足L(G)=L(M)。( )6、对任意一个右线性文法G
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 习题 答案 整理
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。