当前位置：文档之家 › 编译原理作业参考答案

编译原理作业参考答案

  • 格式：doc
  • 大小：887.50 KB
  • 文档页数：19

编译原理 作业参考答案 1 第1章 引 言 1、解释下列各词 源语言:编写源程序的语言（基本符号，关键字），各种程序设计语言都可以作为源语言。 源程序: 用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。 目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序 （结果程序）一般可由计算机直接执行。 低级语言：机器语言和汇编语言。 高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。 翻译程序: 能够把某一种语言程序（源语言程序）改变成另一种语言程序（目 标语言程序），后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。 编译程序: 把输入的源程序翻译成等价的目标程序（汇编语言或机器语言）， 然后再执行目标程序（先编译后执行），执行翻译工作的程序称为编译程序。 解释程序: 以该语言写的源程序作为输入，但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。

2、什么叫“遍”？ 指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。

3、简述编译程序的基本过程的任务。 编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分5个阶段。 词法分析：输入源程序，进行词法分析，输出单词符号。 语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语法正确的“程序”。 中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。 优化：对中间代码进行优化处理。 目标代码生成：把中间代码翻译成目标语言程序。 4、编译程序与解释程序的区别？ 编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。

5、有人认为编译程序的五个组成部分缺一不可，这种看法正确吗？ 编译程序的5个阶段中，词法分析，语法分析，语义分析和代码生成生成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量，没有这一部分工作，仍然能够得到目标代码。

6、编译程序的分类 目前基本分为：诊断编译程序，优化编译程序，交叉编译程序，可变目标编译程序。

编译原理 作业参考答案 2 第2章 高级语言及其语法描述 1（P36）令文法为 N  DND D  0129 （1）文法描述的语言L（G）是什么？ （2）给出句子34，568的最左推导和最右推导。 答：（1） L（G）={为可带前导0的正整数} 或L（G）={（0129）+ } 或 L（G）={为数字串} （2） 最左推导：NNDDD3D34 NNDNDDDDD5DD56D568 最右推导：NNDN4D434 NNDN8ND8N68D68568

2*．写出一个文法，使其语言是奇数集，且每个奇数是不以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 | AB B  1 | 3 | 5 | 7 | 9 A  AD | N N  2 | 4 | 6 | 8 | B D  0 | N 或：（未考虑正负号） S  C | ABC C  1 | 3 | 5 | 7 | 9 A  1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 B  BA | B0 |

2.（P36, 8）令文法为 E  TE+TE-T T  FT*FT/F F  （E）i （1）给出该文法的VN、VT和S。 （2）给出i+i*i，i*（i+i）的最左推导和最右推导。 （3）给出i+i+i，i+i*i的语法树。 答：（1） VN = { E, T, F } VT = { +, -, *, /, (, ), i } 编译原理 作业参考答案 3 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)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 + T

E + T i

T i

i

3.（P36, 9）证明下面的文法是二义的： S  iSeS | iS  i 答：对于句子iiiei有两棵不同的语法树。因此该文法是二义的。 S  iSeS  iiSeS  iiieS  iiiei S  iS  iiSeS  iiieS  iiiei 编译原理 作业参考答案

4 第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’的转换矩阵: I Ia Ib {x} ① {x，y} ② {y} ③ {x，y} ② {x，y} ② {x，y} ② {y} ③ {x，y} ②

② 确定DFA M’的初始状态和终态： （a）转换矩阵中I列的第一个状态①为DFA M’的初始状态结点。 （b）含有y状态的子集均为DFA M’的终态结点(②、③为终态结点)。 ③ 根据DFA M’的转换矩阵画出对应的状态转换图：

（3）最小化： ① 首先将其划分成终态集{2，3}和非终态集{1} ② {2，3}a=｛2｝ {2，3}， {2，3}b=｛2｝ {2，3}

因此{2，3}已是不可再区分的,所以该DFA M’已是最小化的。 2. （P64，7(1)）构造正规式1(01)*101相应的DFA M。 答：（1）构造NFA M。

1（01）*101 X Y 编译原理 作业参考答案 5 1 （01）* 1 0 1 1   1 0 1

01 0 1   1 0 1 1

（2）构造转换矩阵 I I0 I1 {X} ① {1, 2, 3} ② {1, 2, 3} ② {2, 3} ③ {2, 3, 4} ④ {2, 3} ③ {2, 3} ③ {2, 3, 4} ④ {2, 3, 4} ④ {2, 3, 5} ⑤ {2, 3, 4} ④ {2, 3, 5} ⑤ {2, 3} ③ {2, 3, 4, Y} ⑥ {2, 3, 4, Y } ⑥ {2, 3, 5} ⑤ {2, 3, 4} ④

（3）由转换矩阵构造DFA M

10011

1

1

1

012

3

456

0

3．（P64，12(a)）将下图所示的NFA M转换为等价的DFA M’，并将该DFA’最小化。 答： 该有限自动机状态0输入同一字符a时到达两个不同的结点,所以是NFA。 （1）构造转换矩阵 I Ia Ib {0} ① {0，1} ② {1} ③ {0，1} ② {0，1} ② {1} ③ {1} ③ {0} ①

X 31 5 4 2 Y X 1 2 3 4 5 Y

X 3 5 1 4 Y 编译原理 作业参考答案

6 （2）由转换矩阵构造DFA M a a b a b

（3）将DFA M最小化 ① 将DFA M的状态划分为非终态集{3}和终态集{1，2} ② 对每一个子集及每一个a进行考察； {1，2}a = {2}  {1，2} {1，2}b = {3}  {3} 因此{1，2}是不可区分的，所以最终状态为： {1，2}，{3} 构造最小化的DFA M： a b

a

4. （P64，12（b））将下图所示的NFA M转换为等价的DFA M’，并进行最小化。

aaabaa012345bbbbba

答：从图上可知该图已经是DFA M，先只需将其最小化。 首先划分为两个集合：{0,1}和{2,3,4,5} {2,3,4,5}a = {1,3,0,5}，划分为：{2,4}和｛3,5｝ {2,4}a = {1,0}，{2,4}b = {3,5}，无需划分 {3,5}a = {3,5}，{3,5}b = {2,4}，无需划分 {0,1}a = {1}，{0,1}b = {2,4}，无需划分 因此，最终的划分为：{0,1}、{2,4}和｛3,5｝，化简后的结果：

abbaaa0,1b2,43,5

5．（P65，14）构造一个DFA M，它接受={0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。 答：

1 2，3

1 2 3

合集下载

编译原理 全部参考答案

编译原理 全部参考答案

第二章P-36-6（1）L（G）是0~9组成的数字串；（2）最左推导：N⇒ND⇒NDD⇒NDDD⇒DDDD⇒0DDD⇒01DD⇒012D⇒0127N⇒ND⇒DD⇒3D⇒34N⇒ND⇒NDD⇒DDD⇒5DD⇒56D⇒568最右推导：N⇒ND⇒N7⇒ND7⇒N27⇒ND27⇒N127⇒D127⇒0127N⇒ND⇒N4⇒D4⇒34N⇒ND⇒N8⇒ND8⇒N68⇒D68⇒568P-36-7G（S）：（没有考虑正负符号问题）S→P|APP→1|3|5|7|9A→AD|NN→2|4|6|8|PD→0|N或者：（１）S→ＡＢＣ｜CＡ→１｜２｜３｜４｜５｜６｜７｜８｜９Ｂ→ＢＡ｜Ｂ０｜εＣ→1｜3｜5｜7｜9P-36-8G（E）：E→T|E+T|E-TT→F|T*F|T/FF→（E）|i最左推导：E⇒E+T⇒T+T⇒F+T⇒i+T⇒i+T*F⇒i+F*F⇒i+i*F⇒i+i*iE⇒T⇒T*F⇒F*F⇒i*F⇒i*（E）⇒i*（E+T）⇒i*（T+T）⇒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*iE⇒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）语法树：SiSeSiSiiSiS i S eS iiP-36-9句子：iiiei 有两个语法树： S ⇒iSeS ⇒iSei ⇒iiSei ⇒iiiei S ⇒iS ⇒iiSeS ⇒iiSei ⇒iiiei因此iiiei 是二义性句子，因此 该文法是二义性的。

P-36-10 S →TS|T T →(S)|()P-36-11L1: G(S): S →AC A →aAb|ab C →cC|ε L2: G(S): S →AB A →aA|ε B →bBc|bc L3: G(S): S →AB A →aAb|ε B →aAb|ε L4: G(S): S →1S0|A A →0A1|ε或者：S →A|B A →0A1|ε B →1B0|A 第三章（1）Ei+i+iE +TE +TT F iF iF iEE +TT F iT *FF iii+i*i Ei-i-iE-TE -TT F iF iF i确定化：最小化：{0，1，2，3，4，5}，{6}{0，1，2，3，4，5}0={1，3，5} {0，1，2，3，4，5}1={1，2，4，6} {0，1，2，3，4}，{5}，{6} {0，1，2，3，4}0={1，3，5} {0，1，2，3}，{4}，{5}，{6}{0，1，2，3}0={1，3} {0，1，2，3}1={1，2，4} {0，1}，{2，3}，{4}，{5}，{6}{0，1}0={1} {0，1}1={1，2} {2，3}0={3} {2，3}1={4} {0}，{1}，{2，3}，{4}，{5}，{6}P64-8(1)（0|1）*01(2)（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*（0|5）|（0|5）(3)0*1（0|10*1）* | 1*0（1|01*0）*P84-12（a）a最小化：{0，1} {2，3}{0，1}a={1}，{0，1}b={2}{2，3}a={0，3}，{2，3}={3}{0，1}，{2}，{3}a（b）已经确定化，只需最小化：{0，1}，{2，3，4，5}{0，1}a = {1} {0，1}b = {2，4}{2，3，4，5}a = {1，3，0，5} {2，3，4，5}b = {2，3，4，5}又：{2，4}a = {1，0} {2，4}b = {3，5} {3，5}a={3，5} {3，5}b = {2，4} 分划为：{0，1}，{2，4}，{3，5}{0，1}a = {1} {0，1}b = {2，4}{2，4}a = {1，0} {2，4}b = {3，5}{3，5}a = {3，5} {3，5}b = {2，4}所以不能再分aP64-14正规式：（0|10）*还可以：然后再确定化，最小化，结果应该一样。

编译原理-第1章 编译概述--习题答案

编译原理-第1章 编译概述--习题答案

第1章编译概述1．判断下面的陈述是否正确。

（1）编译器生成的目标程序都是可执行的程序。

（2）汇编器将高级语言程序翻译成汇编语言程序。

（3）编译程序和解释程序的根本区别在于解释程序对源程序并没有真正进行翻译。

（4）因为编译程序和解释程序具有不同的功能，所以它们的实现技术也完全不同。

（5）编译程序的五个组成部分缺一不可。

（6）许多编译程序在识别出语法单位后并不真正构造语法树。

（7）高级语言程序到低级语言程序的转换是基于语义的等价变换。

（8）含有优化部分的编译程序的执行效率高。

（9）优化的任务在于对中间代码进行加工和变换，以使其能产生运行结果更为准确的目标代码。

（10）编译前端主要由与源语言和目标机相关的那些部分组成。

（11）无论一遍扫描的编译器还是多遍扫描的编译器都要对源程序至少扫描一遍。

（12）在编译过程中，既可以将几个不同的阶段合为一遍，也可以把一个阶段的工作分为若干遍。

（13）取编译程序前端改写其后端以生成不同机器上的目标代码，目前技术上还难以实现。

（14）支持程序设计人员进行程序计开发的工具，除了编译程序以外，还需要编辑程序、链接程序和调试程序等其他一些工具。

2. 指出下列错误信息是编译的哪个阶段报告的A. 词法B. 语法C. 语义（1）else没有匹配的if（2）使用的标识符没有定义（3）标识符中出现？号（4）赋值语句写成：x+y=1;（5）float a=1.1, b=2, c ; c=a%b;（6）数组下标越界3. 阅读教材第1章，回答以下问题：（1）计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？（2）画出编译程序的总体逻辑结构图，以语句“Area=3.14*r*r”编译过程为例，简述编译各个阶段的主要任务。

习题答案1．(1) × (2) × (3) × (4) × (5) × (6) √ (7) √(8) × (9) × (10) × (11) √ (12) √ (13) × (14) √2．BCABCC。

编译原理试题参考答案

编译原理试题参考答案

编译原理试题参考答案编译原理试题参考答案编译原理是计算机科学中的一门重要课程，它研究的是将高级语言源代码转换成机器语言的过程。

在学习编译原理的过程中，试题是一种常见的考核方式。

下面是一些编译原理试题的参考答案，希望对大家的学习有所帮助。

1. 什么是编译器？编译器是一种将高级语言源代码转换成机器语言的程序。

它包括了词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等多个阶段。

编译器的主要作用是将高级语言源代码转换成可执行的机器语言程序。

2. 什么是词法分析？词法分析是编译器的第一个阶段，它将源代码分解成一个个的词法单元，比如关键字、标识符、常量和运算符等。

词法分析器通常使用有限自动机来实现，它可以根据事先定义好的词法规则来识别源代码中的词法单元。

3. 什么是语法分析？语法分析是编译器的第二个阶段，它将词法分析得到的词法单元组织成一个语法树。

语法分析器通常使用上下文无关文法来描述语法规则，并通过递归下降、LL(1)分析或LR分析等算法来进行语法分析。

4. 什么是语义分析？语义分析是编译器的第三个阶段，它对语法树进行语义检查和语义规则的处理。

语义分析器通常会进行类型检查、符号表管理和语义规则的处理，以确保源代码的语义正确性。

5. 什么是中间代码生成？中间代码生成是编译器的第四个阶段，它将语法树转换成一种中间表示形式，比如三地址码、虚拟机代码或抽象语法树。

中间代码是一种与具体机器无关的表示形式，它方便后续的代码优化和目标代码生成。

6. 什么是代码优化？代码优化是编译器的第五个阶段，它通过对中间代码的分析和变换，来改进程序的执行效率和资源利用率。

代码优化的目标是在保持程序语义不变的前提下，尽可能地减少程序的执行时间和资源消耗。

7. 什么是目标代码生成？目标代码生成是编译器的最后一个阶段，它将中间代码转换成目标机器的机器语言程序。

目标代码生成器通常会进行寄存器分配、指令选择和指令调度等操作，以生成高效的目标代码。

编译原理作业与答案

编译原理作业与答案

编译原理作业与答案编译原理独⽴作业2010.5⼀、简答题1、构造⼀个⽂法使其⽣成的语⾔是不允许0打头的偶正整数集合。

2、⽂法][E G ：TT E T E E-+→，FF T F T T/*→，i E F )(→，构造句型i T T T*+-的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。

3、某LL(1)⽂法的预测分析表如下，请在下述分析过程表中填⼊输⼊串（ a , a ）$ 的分析过程。

分析过程表：4、⽂法][S G ：RL S=→，R S →，R L *→，i L →，L R →，求增⼴⽂法中LR(1)项⽬集的初态项⽬集I 0。

5、⽂法][S G ：GG S S ;→，()G G t H →，)(S a H →，求出各⾮终结符的FISTVT 和LASTVT集合。

⼆、分析题：1、构造⾃动机，使得它能识别字母表{0,1}上以00结尾的符号串，将构造的⾃动机确定化，并写出相应的正规⽂法。

2、⽂法][S G ：RT eT S →εDR T →εdR R → bd a D →，写出每个⾮终结符的FIRST 集和FOLLOW 集，并判断该⽂法是否为LL(1)⽂法。

3、若有⽂法][S G ：AB S →εaBa A →εb A b B → (1)试证明该⽂法是SLR(1) ⽂法，并构造SLR(1)分析表。

（2）给出输⼊串aa # 的分析过程。

参考答案⼀、简答题1、构造⼀个⽂法使其⽣成的语⾔是不允许0打头的偶正整数集合。

8|6|4|2|ABC Z → 9|8|7|6|5|4|3|2|1→A ε|0|B AB B →|8|6|4|2|0→C2、⽂法][E G ：TT E T E E-+→，FF T F T T/*→，i E F )(→，构造句型i T T T *+-的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。

短语：T ，T-T ，i ，T*i ，T-T+T*i直接短语：T ， i 句柄： T素短语（P72）：T-T,i 最左素短语：T-T3 某LL(1)⽂法的预测分析表如下，请在下述分析过程表中填⼊输⼊串（ a , a ）$ 的分析过程。