编译原理及编译程序构造答案

《编译原理及编译程序构造答案》由会员分享，可在线阅读，更多相关《编译原理及编译程序构造答案（14页珍藏版）》请在装配图网上搜索。

1、篇一：编译原理课后习题答案】译程序在逻辑功能上由哪几部分组成？答：编译程序主要由以下几个部分组成：词法分析、语法分析、语 义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、 表格管理。 2.实现编译程序的主要方法有哪些？ 答：主要有：转换法、移植法、自展法、自动生成法。3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程 序有哪几种主要的方式？答：编译法、解释法。4. 编译方式和解释方式的根本区别是什么？ 答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源 程序和编译程序单独执行，所以编译方式的效率高，执行速度快； 解释方式：在执行时，必须源程序和解释程序同时参与才

2、能运行， 其不产生可执行程序文件，效率低，执行速度 第二章1. 乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计 语言的设计与实现关系如何？ 答：1)0型文法、1型文法、2型文法、3型文法。2)2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以 0 为前 导。 答：z?sme | bs?1|2|3|4|5|6|7|8|9 m? | d | md d?0|s b?2|4|6|8 e?0|b n? d|nd d? 0|1|2|3|4|5|6|7|8|9请给出句子123、301和75431的最右推导和最左推导。 答：n?nd?n3?nd3?n23?d23?123 n?nd?ndd?dd

3、d?1dd?12d?123 n?nd?n1?nd1?n01?d01?301 n?nd?ndd?ddd?3dd?30d?301 n?nd?n1?nd1?n31?nd31?n431?nd431?n5431?d5431?75431 n?nd?ndd?nddd?ndddd?ddddd?7dddd?75ddd?754dd?7543d?754313. 设文法g为：答：对于句型iises存在两4. 证明文法s?ises|is| i是二义性文法。个不同的左推导：s?ises?iises s?is?iises所以该文法是二义性文法。 （1） l1=anbnci |n=1,i=0 （2）I2=aibj|j=i=1

4、 （3） I3=anbmcmdn |m,n=0答：（ 1 ） s?aba?aab | ab b?cb | （2） s?asb |ab 25. 给出描述下面语言的上下文无关文法。a?a | ?( 3) s?asd | a | ? a?bac | ?6. 设计一个最简的dfa m,使其能够识别所有的被3整除的无符号十 进制整数。 答：1|4|77. 设计一个dfa,使其能够接受被4整除的二进制数。答:8. 写出表达下列各项的正则表达式。(1)二进制数且为 5的倍数。4第三章1. 词法分析器的功能是什么？ 答：读源程序的字符序列，逐个拼出单词，并构造相应的内部表示 token；同时检查源程序中的词法

5、错误。2. 试分析分隔符(空格、跳格及回车等)对词法分析的影响。 答：空格、跳格、回车等分隔符号对词法分析不起作用，可以删除。 但是回车符号可以用于错误定位，所以在删除回车符号前需要统计 回车的个数。3.给出识别c语言全部实型常数的自动机。答： (+|-|?)(1-90-9*|0)(.0-90-9*|?) (e(+|-|?)0-90-9*) 4. 写出 识别c语言中所有单词的lex程序。答： l=a-z | a-z d=0-9 d1=1-9 % (l|_)(l|d|_)* return (1); d1d* return (2); + return (3); 51、解释下列各词源语言:编写源程序

6、的语言（基本符号，关键字），各种程序设计语 言都可以作为源语言。 源程序: 用接近自然语言（数学语言）的源语 言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。 目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目 标程序 （结果程序）一般可由计算机直接执行。低级语言：机器语言和汇编语言。高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。 如同自然语言（接近数学语言和工程语言）一样，语言的基本单位 是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。翻译程序: 能够把某一种语言程序（源语言程序）改变成另一种语言 程序（目 标语言程序），后者与前者在逻辑上是等

7、价的。其中包括：编译程 序，解释程序，汇编程序。 编译程序: 把输入的源程序翻译成等价的 目标程序（汇编语言或机器语言）， 然后再执行目标程序（先编译 后执行），执行翻译工作的程序称为编译程序。解释程序: 以该语言写的源程序作为输入，但不产生目标程序。按源 程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的 程序称为解释程序。2、什么叫“遍”？指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫 描一次，并作相应的加工处理，称为一遍。3、简述编译程序的基本过程的任务。编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分 5 个阶段。词法分析：输入源程序

8、，进行词法分析，输出单词符号。 语法分析：在词法分析的基础上，根据语言的语法规则把单词符号 串分解成各类语法单位，并判断输入串是否构成语法正确的 “程序”。中间代码生成：按照语义规则把语法分析器归约（或推导）出的语 法单位翻译成一定形式的中间代码。优化：对中间代码进行优化处理。目标代码生成：把中间代码翻译成目标语言程序。 4、编译程序与解释程序的区别？编译程序生成目标程序后，再执行目标程序；然而解释程序不生成 目标程序，边解释边执行。 5、有人认为编译程序的五个组成部分缺 一不可，这种看法正确吗？编译程序的 5个阶段中，词法分析，语法分析，语义分析和代码生成生成是必须完成的。而中间代码生成和代

9、码优化并不是必不可少 的。优化的目的是为了提高目标程序的质量，没有这一部分工作， 仍然能够得到目标代码。6、编译程序的分类 目前基本分为：诊断编译程序，优化编译程序，交叉编译程序，可 变目标编译程序。第 2 章 高级语言及其语法描述1 (p36 )令文法为n ? d?nd d ? 0?1?2?9(1)文法描述的语言I (g)是什么?2)给出句子 34，568的最左推导和最右推导。答：1)I(g) =?为可带前导 0的正整数或 I (g) = (0?1?2?9) 或 I (g) =?为数字串 (2) 最左推导：n?nd?dd?3d?34n?nd?ndd?ddd?5dd?56d?568最右推导：

10、n?nd?n4?d4?34n?nd?n8?nd8?n68?d68?5682*写出一个文法，使其语言是奇数集，且每个奇数是不以 0 开头。 答：s ? cab|b (考虑了正负号)a ? 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | aa | a0 | ? b ? 1|3|5|7|9 c ? +|-|?s ? b | abb ? 1 | 3 | 5 | 7 | 9 a ? ad | nn ? 2 | 4 | 6 | 8 | b d ? 0 | n s ? c | abcc ? 1 | 3 | 5 | 7 | 9a ? 1 | 2 | 3 | 4 | 5 | 6 | 7

11、| 8 | 9或：(未考虑正负号)或：(未考虑正负号)b ? ba | b0 |?2.( p36, 8)令文法为 e ? t?e+t?e-tt ? f?t*f?t/f f ?(e) ?i(1)给出该文法的vn、vt和s。3)给出 i+i+i，(2)给出i+i*i, i* (i+i)的最左推导和最右推导。i+i*i 的语法树。 答：(1)vn = e, t, f vt = +, -, *, /, (, ), i s = e ( 2)最左推导 e?e+t?t+t?f+t?i+t?i+t*f?i+f*f?i+i*f?i+i*i e?t?t*f?f*f?i*f?i*(e)?i*(e+t)?i*(t+t

12、)?i*(f+t)?i*(i+t) ?i*(i+f)?i*(i+i) 最右推导 e?e+t?e+t*f?e+t*i?e+f*i?e+i*i?t+i*i?f+i*i?i+i*i e?t?t*f?t*(e)?t*(e+t)?t*(e+f)?t*(e+i)?t*(t+i)?t*(f+i) ?t*(i+i)?f*(i+i)?i*(i+i)构造语法树e 最左推导构造语法树 e +te+t it i i3.(p36, 9)证明下面的文法是二义的：s ? ises | is ? i答：对于句子iiiei有两棵不同的语法树。因此该文法是二义的。s ?ises ? iises ? iiies ? iiieis

13、? is ? iises ? iiies ? iiiei第3章 词法分析1设m= (x, y, a, b, ?, x, y)为一个非确定有限自动机 nfa m,其中？定义如下： ?( x, a) =x, y ?( x, b) =y?( y, a) =? ?( y, b) =x, y 试构造其相应的最小化的确定有限自动机 dfa m。答：由？定义可知？ (x, a), ? (y, b)均为多值函数，所以是一 个非确定有限自动机。(1)根据?函数值,先构造nfa m( 2)确定化： 构造dfa m的转换矩阵： 确定dfa m的初始状态和终态：(a) 转换矩阵中i列的第一个状态为dfa m的初始状态

14、结点。(b) 含有y状态的子集均为dfa m的终态结点(、为终态结点)。 根据dfa m的转换矩阵画出对应的状态转换图： 首先将其划分成终态集2, 3和非终态集12, 3a= 2 ? 2, 3,2, 3b= 2 ? 2, 3因此2, 3.=J諛已是不可再区分的,所以该dfa m已是最小化的。2. (p64, 7(1) 构造正规式1(0?1)*101相应的 dfa m。答:(1)构造nfa m。(2( 3)由转换矩阵构造 dfa ml=J3.(p64, 12(a)将下图所示的nfa m转换为等价的dfa m,并 将该dfa最小化。答：该有限自动机状态0输入同一字符a时到达两个不同的结点,所以是n

15、fa。篇三：编译原理习题及答案(整理后)】序分成若干个“遍”是为了a提高程序的执行效率b使程序的结构更加清晰c利用有限的机器内存并提高机器的执行效率 d利用有限的机器内存但降低了机器的执行效率2、构造编译程序应掌握a源程序b目标语言c编译方法d以上三项都是3、变量应当.持有左值b持有右值c.既持有左值又持有右值d既不持有左值也不持有右值4、编译程序绝大多数时间花在a出错处理b词法分析c目标代码生成d管理表格5、a汇编指令代码b可重定位指令代码c绝对指令代码d中间代码、使用可以定义一个程序的意义。a语义规则b语法规则c产生规则d词法规则7、词法分析器的输入是a单词符号串b源程序c语法单位d目标程

16、序8、中间代码生成时所遵循的是。a语法规则b词法规则c语义规则d等价变换规则9、编译程序是对。a汇编程序的翻译b高级语言程序的解释执行c机器语言的执行d高级语言的10、语法分析应遵循。a语义规则b语法规则 c构词规则d等价变换规则二、多项选择题1、编译程序各阶段的工作都涉及到。a语法分析b表格管理c出错处理d语义分析e词法分析2、编译程序工作时，通常有阶段。a词法分析b语法分析c中间代码生成 d语义检查e目标代码生成三、填空题1、解释程序和编译程序的区别在于。2、编译过程通常可分为 5个阶段，分别是语法分析、代码优化和目 标代码生成。3、编译程序工作过程中，第一段输入是程序。4、编译程序是指将

17、程序的程序。单选解答1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰 故选 b。2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知 识，故选 d。3、对编译而言，变量既持有左值又持有右值，故选 c。4、编译程序打交道最多的就是各种表格，因此选 d。5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码 3种，因此不是目标代码的只能选 d。6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意 义。因此选 a。7、b 8、c 9、d10、c多选解答1b、c 2. a、b、c、e填空解答是否生成目标程序 2

18、、词法分析中间代码生成 3、源程序 目标代码 生成 4、源程序标语言第二章一、单项选择题1、文法g： stxsxW所识别的语言是a. xyx b. (xyx)* c. xnyx (n0) d. x*yx*3、有限状态自动机能识别。a. 上下文无关文法 b. 上下文有关文法c正规文法d.短语文法4、设g为算符优先文法，g的任意终结符对a、b有以下关系成立。a.若 f(a)g(b)，则 ab b若 f(a)g(b)，则 abc. ab 都不一定成立 d. ab 一定成立a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能

19、存在两个不同的最左推导，但它们对应的语法树相同6、由文法的开始符经 0 步或多步推导产生的文法符号序列是a.短语b句柄c.句型d.句子7、文法 g： ere+t|t tft*p|p P(e)|i则句型 p+t+i 的句柄和最左素短语为 。a.p+t 和 i b. p 和 p+t c. i 和 p+t+i d.p 和 t8、设文法为：ssa|aaa|b则对句子aba，下面是规范推导。a. s?sa?saa?aaa?aaa?aba?abab. s?sa?saa?aaa?aaa?aba?aba目c. s?sa?saa?saa?sba?aba?abad. s?sa?sa?saa?sba?aba?aba

20、 9、文法 g： STb|A(t)tft,s|s则 firstvt(t) 。a. b,A,( b. fb,A,) c.b,A,( db,A,) 10、产生正规语言的文法为a. 0型 b. 1型 c. 2型 d. 3型11、采用自上而下分析，必须a.消除左递归b.消除右递归c消除回溯d.提取公共左因子12、在规范归约中，用a.直接短语b.句柄c.最左素短语d. 素短语13、有文法 g： e-e*t|ttt+i|i句子 1 +2*8+6按该文法 g 归约，其值为 。a. 23 b. 42 c.30 d. 1714、规范归约指a. 最左推导的逆过程 b. 最右推导的逆过程c.规范推导d.最左归约的逆

21、过程二、多项选择题1、下面哪些说法是错误的a. 有向图是一个状态转换图 b. 状态转换图是一个有向图c有向图是一个dfa d.dfa可以用状态转换图表示2、对无二义性文法来说，一棵语法树往往代表了。a.多种推导过程b.多种最左推导过程c.一种最左推导过程d.仅一种推导过程e.种最左推导过程3、如果文法 g 存在一个句子，满足下列条件a. 该句子的最左推导与最右推导相同b. 该句子有两个不同的最左推导c. 该句子有两棵不同的最右推导d. 该句子有两棵不同的语法树e. 该句子的语法树只有一个4、有一文法g： saba. anbmcndm|n,m0 banbncmdm|n,m0c. anbmcmdn

22、|n,m0 d. anbncmdm|n,m0e. anbncndn|n05、自下而上的语法分析中，应从a. 句型 b. 句子 c. 以单词为单位的程序d. 文法的开始符 e. 句柄6、对正规文法描述的语言，以下a0型文法b1型文法c上下文无关文法d右线性文法e左线性文 法 三、填空题1、文法中的终结符和非终结符的交集是是 ，它一定只出现在产生式的 部。2、最左推导是指每次都对句型中的3、在语法分析中，最常见的两种方法定是分析法。4、采用5、树代表归约过程。6、自下而上分析法采用7、Chomsky把文法分为生和语言，并分别用和自动机识别所产生 的语言。四、判断题rcs2、在自下而上的语法分析中，

23、语法树与分析树一定相同。（）3、二义文法不是上下文无关文法。（）4、语法分析时必须先消除文法中的左递归。（）5、规范归约和规范推导是互逆的两个过程。（）6、一个文法所有句型的集合形成该文法所能接受的语言。（）五、简答题1 、句柄 2、素短语 3、语法树 4、归约 5、推导六、问答题1 、给出上下文无关文法的定义。2、文法 gs： saspq|abq qppq bpbb bqbccqcc（1）它是Chomsky哪一型文法？ （ 2）它生成的语言是什么？3、按指定类型，给出语言的文法。 l=aibj|j 3的上下文无关文法。4、有文法 g：saacb|bdaaab|cbfbsca|b(1)试求句型

24、 aaabcbbdcc 和 aacbbdcc 的句柄；2)写出句子 acabcbbdcc 的最左推导过程。5、对于文法 gs：st (l) |as|a Ifl, s|s(1)画出句型(s, (a)的语法树。(2)写出上述句型的所有短 语、直接短语、句柄和素短语。6、考虑文法 gt：ttt*f|fffPlPpt( t) |i证明t*pt (t*f)是该文法的一个句型，并指出直接短语和句柄。单选解答1 、选 c。2、选 a。3、选 c。4、虽然a与b没有优先关系，但构造优先函数后，a与b就一定存 在优先关系了。所以，由f(a)g)(b)或f(a)g(b)并不能判定原来的a与 b 之间是否存在优先关

25、系：故选 c。5、如果文法 g 无二义性，则最左推导是先生长右边的枝叶：对于 d，如果有两个不同的是了左推导，则必然有二义性。故选 a。6、选c。7、由图2-8-1的语法树和优先关系可以看出应选bo 8、规范推导是最左推导，故选 d。9、由 tt,?和 t(?得 firstvt(t)=(, )；由s 得firstvt?firstvt(t),而 firstvt(s)=b,A,(；即 firstvt(t)=b,A,(, ；因此选 c。10、d 11、 c 12、 b13、 b14、 b多选解答 1 、 e、 a、 c 2、 a、 c、 e 3、 b、 c、 d4、 a、 c5、 b、 c6、b、

26、c、 d、 e 填空解答 1、空集终结符右2、最左3、自上而上自下而上4、自上而上5、语法 分析、移进 接受7、42 型 3型 上下文无关语言正规语言 下推自动机 有限判断解答 1、对2、错 3、错4、错5、错6、错简答解答1、句柄：一个句型的最左直接短语称为该句型的句柄。2、素短语：至少含有一个终结符的素短语，并且除它自身之外不再 含任何更小的素短语。3、语法树：满足下面4个条件的树称之为文法gs的一棵语法树。 每一终结均有一标记，此标记为vnuvt中的一个符号； 树的根结点以文法gs的开始符s标记； 若一结点至少有一个直接后继，则此结点上的标记为vn中的一个 符号； 若一个以 a 为标记的

27、结点有 k 个直接后继，且按从左至右的顺序 这些结点的标记分别为x1,x2,?,xk,则ax1,x2,?,xk,必然是g的 一个产生式。问答 1解答一个上下文无关文法g是一个四元式（vt,vn,s, p）,其中：vt 是一个非空有限集，它的每个元素称为终结符号；s 是一个非终结符号，称为开始符号；2解答（1）由于产生式左部存在终结符号，且所有产生式左部符号的长度 均小于等于产生式右部的符号长度，所以文法gs是chomskyl型 文法，即上下文有关文法。（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句 子），我们可以得到：s?abq?abc s?aspq?aabqpq?aabpqq?a

28、abbqq?aabbcq?aabbccs?aspq?aaspqpq?aaabqpqpq?aaabpqqpq?aaabpqpqq?aaapp qqq?aaabbpqqq?aaabbqqq?aaabbbcqq?aaabbbccq?aaabbbccc?于是得到文法gs生成的语言I=anbncn|n213【解答】（1）由l=aibj|jiN知，所求该语言对应的上下文无关文法首先 应有s-asb型产生式，以保证b的个数不少于a的个数；其次，还 需有STSb或STbs型的产生式，用以保证b的个数多于a的个数; 也即所求上下文无关文法gs为：gs： s*asb|sb|b4【解答】（1）分别画出对应两句型的语法树，如图 2-8-2所示句柄:aab bd