下载文档原格式
何谓源程序、目标程序、翻译程序、编译程序和解释程序它们之间可能有何种关系一个典型的编译系统通常由哪些部分组成各部分的主要功能是什么选择一种你所熟悉的程序设计语言，试列出此语言中的全部关键字，并通过上机使用该语言以判明这些关键字是否为保留字。
选取一种你所熟悉的语言，试对它进行分析，以找出此语言中的括号、关键字END以及逗号有多少种不同的用途。
试用你常用的一种高级语言编写一短小的程序，上机进行编译和运行，记录下操作步骤和输出信息，如果可能，请卸出中间代码和目标代码。
第一章习题解答1.解：源程序是指以某种程序设计语言所编写的程序。
目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。
翻译程序是将某种语言翻译成另一种语言的程序的统称。
编译程序与解释程序均为翻译程序，但二者工作方法不同。
解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。
即边解释边执行，翻译所得的指令序列并不保存。
编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。
即先翻译、后执行。
2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。
3.解：C语言的关键字有：auto break case char const continue default do double else enum externfloat for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while。
第1章引论第1题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。
（2） 源程序：源语言编写的程序称为源程序。
（3） 目标程序：目标语言书写的程序称为目标程序。
（4） 编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。
通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。
（5） 后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。
（6） 遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。
第2题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。
答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。
其各部分的主要功能简述如下。
词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。
语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。
语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。
中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。
中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。
目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。
表格管理程序：负责建立、填写和查找等一系列表格工作。
表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。
编译原理⾃测（⼀、⼆、三）及答案编译原理⾃测⼀⼀、是⾮题(下列各题，你认为正确的，请在题⼲的括号内打“√”，错的打“×”。
每题1分,共5分)1、算符优先关系表不⼀定存在对应的优先函数。
A.正确B.不正确2、数组元素的地址计算与数组的存储⽅式有关。
A.正确B.不正确3、仅考虑⼀个基本块，不能确定⼀个赋值是否真是⽆⽤的。
A.正确B.不正确4、每个⽂法都能改写为LL(1)⽂法。
A.正确B.不正确5、对于数据空间的存贮分配，FORTRAN采⽤动态贮存分配策略。
A.正确B.不正确⼆、填空题1、从功能上说，程序语⾔的语句⼤体可分为两⼤类。
2、扫描器的任务是从3、所谓最右推导是指：(任何⼀步αβ都是对α中最右⾮终结符进⾏替换的)4、语法分析最常⽤的两类⽅法是5、⼀个上下⽂⽆关⽂法所含四个组成部分是(⼀组终结符号，⼀组⾮终结符号、⼀个开始符号、⼀组产⽣式)6、所谓语法制导翻译⽅法是(为每个产⽣式配上⼀个翻译⼦程序，并在语法分析的同时执⾏这些⼦程序)7、符号表中的信息栏中登记了每个名字的有关的性质，如8、⼀个过程相应的DISPLA Y表的内容为9、常⽤的两种动态存贮分配办法是配。
10、产⽣式是⽤于定义三、名词解释1．遍－－指编译程序对源程序或中间代码程序从头到尾扫描⼀次。
2．⽆环路有向图(DAG)－－如果有向图中任⼀通路都不是环路，则称庐有向图为⽆环路有向图，简称DAG。
3．语法分析－－按⽂法的产⽣式识别输⼊的符号串是否为⼀个句⼦的分析过程。
4．短语－－令G是⼀个⽂法。
S划⽂法的开始符号，假定αβδ是⽂法G的⼀个句型，如果有SαAδ且AB，则称β是句型αβ相对⾮终结符A的短语。
5．后缀式－－⼀种把运算量写在前⾯，把算符写在后⾯的表⽰表达式的⽅法。
编译原理⾃测⼆⼀、是⾮题(下列各题，你认为正确的，请在题⼲的括号内打“√”，错的打“×”。
每题1分,共5分)1、⼀个LL(1)⽂法⼀定是⽆⼆义的。
A.正确B.不正确2、逆波兰法表⽰的表达式亦称前缀式。
第一章能够完成从一种语言到另一种语言的变换的软件称为翻译器编译器是一种翻译器，他进行语言变换的特点是目标语言比源语言低级编译的各个阶段：字符流-词法分析器-记号流-语法分析器-语法树-中间代码生成器-中间表示-独立与机器的代码优化器-中间表示-代码生成器-目标机器代码-依赖于机器的代码优化器-目标机器代码第二章语法分析器的任务是把构成源程序的字符流翻译成词法记号流。
2.1词法分析是编译的第一阶段，它的主要任务是扫描输入字符流，产生用于词法分析的词法记号序列。
完成的其他任务（实验一）其一是剥去源程序的注解和由空格、制表或换行符等引起的空白，另一任务是把来自编译器各个阶段的错误信息和源程序练习起来。
2.12词法记号的属性必考略2.21 字母表上的串是该字母表符号的有穷序列术语语言表示字母表上的一个串集，属于该语言的串称为该语言的句子或字。
如果x和y都是串，那么x和y的链接（xy）是吧y加到x后边形成的串。
对连接运算而言，空串是一个恒等元素。
表2.2 语言运算的定义（未打印）例2.2 略2.3 语言的识别器是一个程序，它取串x作为输入，当x是语言的句子时，他回答是，否则回答不是。
可以通过构造称为优先自动机的更一般的转换图，把正规式翻译成识别器。
有限自动机分为确定的和不确定的两种情况。
不确定的含义是：存在这样的状态，对于某个输入符号，它存在不止一种转换。
NFA转化为DFA 略DFA 化简略课后习题：第三章源程序 图3.1 分析器在编译器模型中的位置3.1 一个上下文无关文法G是一个四元组（Vt,Vn,S,P），其中：Vt是一个终结符集合，Vn是非终结符集合Vt并Vn=空集，S是一个终结符，称为开始符号，P是产生式的有限集合。
3.1.2代换句型中最左边非终结符的推导，这样的推导叫做最左推导。
最右推导，略。
3.14二义性一个文法如果存在某个句子有不止一颗分析树与之对应，那么称这个文法是二义的。
3.2.5 消除二义性。
1第2章 习题2-1 设有字母表A 1 ={a,b,c,…,z}，A 2={0,1,={0,1,……,9},9}，试回答下列问题：，试回答下列问题：，试回答下列问题：(1) 字母表A 1上长度为2的符号串有多少个？的符号串有多少个？ (2) 集合A 1A 2含有多少个元素？含有多少个元素？(3) 列出集合A 1(A 1∪A 2)*中的全部长度不大于3的符号串。
的符号串。
2-2 试分别构造产生下列语言的文法：试分别构造产生下列语言的文法：试分别构造产生下列语言的文法： （1）{a nb n|n≥0}；|n≥0}； （2）{a n b m c p |n,m,p≥0}；|n,m,p≥0}；（3）{a n#b n|n≥0}∪|n≥0}∪{c {c n#d n|n≥0}；|n≥0}；（4）{w#w r # | w ∈{0,1}*,w r 是w 的逆序排列的逆序排列 } }； （5）任何不是以0打头的所有奇整数所组成的集合；的集合；（6）所有由偶数个0和偶数个1所组成的符号串的集合。
号串的集合。
2-3 试描述由下列文法所产生的语言的特点：试描述由下列文法所产生的语言的特点： （1）S→10S0）S→10S0 S→aA S→aA A→bA A→bA A→a A→a （2）S→SS S→1A0S→1A0 A→1A0A→1A0A→ε （3）S→1A ）S→1A S→B0S→B0 A→1A A→1A A→C A→C B→B0B→B0 B→C B→C C→1C0C→1C0C→ε（4）S→aSS ）S→aSS S→a S→a 2-4 试证明文法试证明文法试证明文法 S →AB|DC A →aA|a B →bBc|bc C →cC|c D →aDb|ab为二义性文法。
为二义性文法。
2-5 对于下列的文法对于下列的文法对于下列的文法 S →AB|c A →bA|a B →aSb|c试给出句子bbaacb 的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。
第二章高级语言的语法描述6、令文法G 6为：N →D|ND D → 0|1|2|3|4|5|6|7|8|9（1）G 6 的语言L （G 6）是什么？（2）给出句子01270127、、34和568的最左推导和最右推导。
解答：思路：由N N →→ D|ND 可得出如下推导N ＝＞＝＞ND ND ND＝＞＝＞＝＞NDD NDD NDD＝＞…＝＞＝＞…＝＞＝＞…＝＞D D n（n ＞=1=1））可以看出，N 最终可以推导出1个或多个（也可以是无穷）D ，而D D →→ 0|1|2|3|4|5|6|7|8|9可知，每个D 为0～9中的任一个数字，所以，中的任一个数字，所以，N N N 最终推导出的就是由最终推导出的就是由0～9这10个数字组成的字符串。
（1）G 6 的语言L （G 6）是由0～9这10个数字组成的字符串个数字组成的字符串,,或{0{0，，1,1,……,9}+。
(2)(2)句子句子01270127、、34和568的最左推导分别为的最左推导分别为: : N ＝＞＝＞ND ND ND＝＞＝＞＝＞NDD NDD NDD＝＞＝＞＝＞NDDD NDDD NDDD＝＞＝＞＝＞DDDD DDDD DDDD＝＞＝＞＝＞0DDD 0DDD 0DDD＝＞＝＞＝＞01DD 01DD 01DD＝＞＝＞＝＞012D 012D 012D＝＞＝＞＝＞0127 0127 N ＝＞＝＞ND ND ND＝＞＝＞＝＞DD DD DD＝＞＝＞＝＞3D 3D 3D＝＞＝＞＝＞34 34N ＝＞＝＞ND ND ND＝＞＝＞＝＞NDD NDD NDD＝＞＝＞＝＞DDD DDD DDD＝＞＝＞＝＞5DD 5DD 5DD＝＞＝＞＝＞56D 56D 56D＝＞＝＞＝＞568 568 句子01270127、、34和568的最右推导分别为的最右推导分别为: :N ＝＞＝＞ND ND ND＝＞＝＞＝＞N7N7N7＝＞＝＞＝＞ND7ND7ND7＝＞＝＞＝＞N27N27N27＝＞＝＞＝＞ND27ND27ND27＝＞＝＞＝＞N127N127N127＝＞＝＞＝＞D127D127D127＝＞＝＞＝＞0127 0127 N ＝＞＝＞ND ND ND＝＞＝＞＝＞N4N4N4＝＞＝＞＝＞D4D4D4＝＞＝＞＝＞34 34N ＝＞＝＞ND ND ND＝＞＝＞＝＞N8N8N8＝＞＝＞＝＞ND8ND8ND8＝＞＝＞＝＞N68N68N68＝＞＝＞＝＞D68D68D68＝＞＝＞＝＞568 5687、写一个文法，使其语言是奇数集，且每个基数不以0开头。
编译原理 第一、二章单元测验（答案）姓名 学号 班级一．填空（40分）1. 编译系统一般可以分为① 词法分析 ② 语法分析 ③语义分析及中间代码生成 ④ 优化处理 ⑤ 目标代码生成 等5大部分组成，其中① 词法分析 ② 语法分析 ⑤ 目标代码生成 是每个编译程序必不可少的，而③语义分析及中间代码生成 ④ 优化处理 则是可有可无的。
这5个部分在工作过程中都会涉及到⑥ 表格处理 ⑦ 出错处理2. 中间代码生成所依据的是语言的 语义 规则3. 在使用高级语言编程时，首先可以通过编译程序发现源程序的全部 语法 错误和 语义 错误。
4. 由于受到具体机器主存容量限制，编译程序几个阶段的工作往往被组合成 遍 。
5. 编译程序绝大多数时间花在 管理表格/扫描 上。
6. 语法分析的依据是 语法/语义 规则。
7. 高级语言源程序执行有两种方式：即 编译 和 解释 。
8. 编译程序各阶段的工作往往是 穿插 进行的。
9. 文法G 产生的 句子 的全体构成该文法所描述的语言。
10. 乔姆斯基定义的4种形式的文法中，0型又称 短语结构文法 可由 图灵机 识别， 1型又称 前后文（或上下文）有关文法 可由 线性限界自动机 识别，2型又称 前后文（或上下文）无关文法 可由 非确定下推自动机 识别，3型包括 左线性文法 和 右线性文法 ，可由 有限自动机 识别。
11. 最左推导是指 对于一个推导序列中的每个直接推导，被替换的总是当前符号串中的最左非终结符号。
12. 产生式是用于定义 语法范畴 的一种书写规则。
13. 高级语言经过编译生成的语言一般是 机器语言 和 汇编语言 。
14. 句柄是指当前句型的 最左直接短语 。
15. 简单地说，文法中无用符号和无用产生式的删除必须满足：1.是否被用到过 2. 可否推出终结符号 。
16. 规范推导是指 最右推导 ，规范归约是指 最左归约 ，二者互为逆过程。
二．写一个语言，使其语言是奇数集，且每个奇数不以0开头。
编译原理 第一、二章单元测验（答案）
姓名 学号 班级
一．填空（40分）
1. 编译系统一般可以分为① 词法分析 ② 语法分析 ③语义分析及中间代码生成 ④ 优化处理 ⑤ 目标代码生成 等5大部分组成，其中① 词法分析 ② 语法分析 ⑤ 目标代码生成 是每个编译程序必不可少的，而③语义分析及中间代码生成 ④ 优化处理 则是可有可无的。
这5个部分在工作过程中都会涉及到⑥ 表格处理 ⑦ 出错处理
2. 中间代码生成所依据的是语言的 语义 规则
3. 在使用高级语言编程时，首先可以通过编译程序发现源程序的全部 语法 错误和 语义 错误。
4. 由于受到具体机器主存容量限制，编译程序几个阶段的工作往往被组合成 遍 。
5. 编译程序绝大多数时间花在 管理表格/扫描 上。
6. 语法分析的依据是 语法/语义 规则。
7. 高级语言源程序执行有两种方式：即 编译 和 解释 。
8. 编译程序各阶段的工作往往是 穿插 进行的。
9. 文法G 产生的 句子 的全体构成该文法所描述的语言。
10. 乔姆斯基定义的4种形式的文法中，0型又称 短语结构文法 可由 图灵机 识别， 1型又称 前后文（或上下文）有关文法 可由 线性限界自动机 识别，2型又称 前后文（或上下文）无关文法 可由 非确定下推自动机 识别，3型包括 左线性文法 和 右线性文法 ，可由 有限自动机 识别。
11. 最左推导是指 对于一个推导序列中的每个直接推导，被替换的总是当前符号串中的最左非终结符号。
12. 产生式是用于定义 语法范畴 的一种书写规则。
13. 高级语言经过编译生成的语言一般是 机器语言 和 汇编语言 。
14. 句柄是指当前句型的 最左直接短语 。
15. 简单地说，文法中无用符号和无用产生式的删除必须满足：1.是否被用到过 2. 可否推出终结符号 。
16. 规范推导是指 最右推导 ，
规范归约是指 最左归约 ，二者互为逆过程。
二．写一个语言，使其语言是奇数集，且每个奇数不以0开头。
（20分）
解法1： G = ({S,A},{0,1,2,3,4,5,6,7,8,9},P,S)
P: S →d 1A ∣d 3 A →d 2A ∣d 3
d 1代表1-9的数字，d 2代表0-9的数字， d 3代表1，3，5，7，9中的任意一个。
解法2：G = ( {N,A,B,C,D},{0,1,2,3,4,5,6,7,8,9},P,S)
P: N →AB ∣B A →AC ∣D B →1∣3∣5∣7∣9 D →2∣4∣6∣8∣B C →0∣D
三．证明下列文法是二义性文法： S →iSeS ∣iS ∣i （20分）
解：1. 不同最左（右）推导推导出相同的符号串 2. 对同一符号串有两颗不同语法树 (答案多样化)
四．写出下面语言的上下文无关文法： }0,1{1≥≥=i n c b a L i n n (20分)
解： 1. G1：N →S ∣SA S →aSb ∣ab A →c ∣Ac （或者A →c ∣cA ）
2. G1：N →S ∣SA S →aSb ∣ab A →Ac ∣ε（或者A →cA ∣ε） 再消除ε，得到 答案1。
