大工20秋《编译原理基础》在线作业1

编译原理作业标准答案第一章引言一、解释下列各词源语言:编写源程序的语言（基本符号，关键字），各种程序设计语言都可以作为源语言。

源程序: 用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。

目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。

目标程序（结果程序）一般可由计算机直接执行。

低级语言：机器语言和汇编语言。

高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。

如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。

翻译程序: 能够把某一种语言程序（源语言程序）改变成另一种语言程序（目标语言程序），后者与前者在逻辑上是等价的。

其中包括：编译程序，解释程序，汇编程序。

编译程序: 把输入的源程序翻译成等价的目标程序（汇编语言或机器语言），然后再执行目标程序（先编译后执行），执行翻译工作的程序称为编译程序。

解释程序: 以该语言写的源程序作为输入，但不产生目标程序。

按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。

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

三、简述编译程序的基本过程的任务。

编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分5个阶段。

词法分析：输入源程序，进行词法分析，输出单词符号。

语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语法正确的“程序”。

中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。

优化：对中间代码进行优化处理。

目标代码生成：把中间代码翻译成目标语言程序。

四、编译程序与解释程序的区别？编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。

《编译原理》习题(一)——词法分析一、就是非题(请在括号内,正确得划√,错误得划×)1.编译程序就是对高级语言程序得解释执行。

(× )2.一个有限状态自动机中,有且仅有一个唯一得终态。

(×)9.两个正规集相等得必要条件就是她们对应得正规式等价。

(× )二、选择题1.词法分析器得输出结果就是_____。

A.( ) 记号B.( ) 相应条目在符号表中得位置C.( ) 记号与属性二元组D.( ) 属性值2. 正规式M 1 与M 2 等价就是指_____。

A.( ) M1与M2得状态数相等B.( ) M1与M2得有向边条数相等C.( ) M1与M2所识别得语言集相等D.( ) M1与M2状态数与有向边条数相等3.语言就是A.句子得集合B.产生式得集合C.符号串得集合D.句型得集合4.编译程序前三个阶段完成得工作就是A.词法分析、语法分析与代码优化B.代码生成、代码优化与词法分析C.词法分析、语法分析、语义分析与中间代码生成D.词法分析、语法分析与代码优化5.扫描器所完成得任务就是从字符串形式得源程序中识别出一个个具有独立含义得最小语法单位即A. 字符B.单词C.句子D.句型6.构造编译程序应掌握______。

A.( )源程序B.( ) 目标语言C.( ) 编译方法D.( ) 以上三项都就是7.词法分析得任务就是A.识别单词B.分析句子得含义C.识别句子D.生成目标代码三、填空题1.计算机执行用高级语言编写得程序主要有两种途径:___解释__与__编译___。

3、编译过程可分为( 词法分析) ,(语法分析),(语义分析与中间代码生成),(优化)与(目标代码生成)五个阶段。

6、扫描器得任务就是从( 源程序中)中识别出一个个( 单词符号)。

17、一张转换图只包含有限个状态,其中有一个被认为就是(初)态;而且实际上至少要有一个(终)态。

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．中间代码⽣成e．⽬标代码⽣成三、填空题1、解释程序和编译程序的区别在于是否⽣成⽬标程序。

2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码⽣成、代码优化和⽬标代码⽣成。

3、编译程序⼯作过程中，第⼀段输⼊是源程序，最后阶段的输出为标代码⽣成程序。

4、编译程序是指将源程序程序翻译成⽬标语⾔程序的程序。

⼀、单项选择题1、⽂法G：S→xSx|y所识别的语⾔是。

c. x n yx n(n≥0)d. x*yx*2、⽂法G描述的语⾔L(G)是指。

a. L(G)={α|S + ?α , α∈VT*} b. L(G)={α|S*?α, α∈VT*}c. L(G)={α|S *?α,α∈(VT∪V N*)} d. L(G)={α|S+ ?α, α∈(VT∪V N*)}3、有限状态⾃动机能识别。

a. 上下⽂⽆关⽂法b. 上下⽂有关⽂法c.正规⽂法d. 短语⽂法4、设G为算符优先⽂法，G的任意终结符对a、b有以下关系成⽴。

a. 若f(a)>g(b)，则a>bb.若f(a)c. a~b都不⼀定成⽴d. a~b⼀定成⽴5、如果⽂法G是⽆⼆义的，则它的任何句⼦α。

a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同6、由⽂法的开始符经0步或多步推导产⽣的⽂法符号序列是。

编译原理一、是非题(下列各题你认为正确的，请在题干的括号内打“√”，错的打“×”。

每题1分，共5分)l、一个LL( l)文法一定是无二义的。

…………………………………………… ( )2、逆波兰法表示的表达式亦称前缀式。

……………………………………………()3、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

……………()4、正规文法产生的语言都可以用上下文无关文法来描述。

………………………()5、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。

……………………………………………………………………………………()二、填空题（每题2分，共5分）1、语法分析是依据语言的( )规则进行的，中间代码产生是依据语言的( )规进行的。

2、程序语言的单词符号一般可以分为( )等等。

3、语法分析器的输入是( )，其输出是( )。

4、所谓自上而下分析法是指( )。

5、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是( )。

6、对于文法G，仅含终结符号的句型称为( )。

7、逆波兰式ab十c＋d*e—所表达的表达式为( )。

8、一个名字的属性包括( )和( )。

9、对于数据空间的存贮分配，FORTRAN采用( )策略，PASCAL采用( )策略。

10、所谓优化是指( )。

三、名词解释题（每题2分，共10分）l、词法分析器：2、语法：3、最右推导：4、语法制导翻译：5、基本块：四、简述题（每题4分，共24分）l、考虑下面的程序：…………Var i：integer；a：array[1··2] of integer；prncedure Q( b)；Var b：integer；Begini：＝1；b：＝b十2；i：＝2；b：＝b＋3End；Begina[1]：＝5；a[2]：＝6；i：＝1；Q(a[i])；print(a[l]，a[2])End．试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出a[l]，a[2]的值是什么?2、画出识别pascal中实常数(可带正负号，但不含指数部分)的状态转换图。

《编译原理》参考资料一、单选题1.现代多数实用编译程序所产生的目标代码都是一种可重定位的指令代码，在运行前必须借助于一个（C）把各个目标模块，包括系统提供的库模块连接在一起，确定程序变量或常数在主存中的位置，装入内存中制定的起始地址，使之成为一个可运行的绝对指令代码的程序。

A.重定位程序B.解释程序C.连接装配程序D.诊断程序2.一个句型中的( A)称为该句型的句柄。

A.最左直接短语B.最右直接短语C.终结符D.非终结符3.将编译程序分成若干个“遍”是为了（B）。

A.提高程序的执行效率B.使程序的结构更加清晰C.利用有限的机器内存并提高机器的执行效率D.利用有限的机器内存但降低了机器的执行效率4.语法分析器接收以（C）为单位的输入，并产生有关信息供以后各阶段使用。

A.表达式B.产生式C.单词D.语句5.词法分析器用于识别(C )A.句子B.产生式C.单词D.句型6.语言的词法规则一般用Chomsky的（D）型文法来描述A.0B.1C.2D.37.由文法的开始符经0步或多步推导产生的文法符号序列是（C）。

A.短语B.句柄C.句型D.句子8.LR(k)文法(A )A.都是无二义性的B.都是二义性的C.一部分是二义性的D.无法判定9.Chomsky把文法分成四种类型，其中，（D）也称正规文法A.0型B.1型C.2型D.3型10.( C)不是编译程序的组成部分。

A.词法分析程序B.代码生成程序C.设备管理程序D.语法分析程序11.编译程序绝大多数时间花在（D）上。

A.出错处理B.词法分析C.目标代码生成D.管理表12.设G为算符优先文法，G的任意终结符对a、b有以下关系成立（C）。

A.若f(a)>g(b)，则a>bB.若f(a)<g(b)，则a<bC.a~b都不一定成立D.a~b一定成立13.使用（A）可以定义一个程序的意义。

A.语义规则B.词法规则C.产生规则D.词法规则14.在运行空间的划分中有一个单独的区域叫堆，用来存放（C）。

大工20春《编译原理基础》在线作业1
试卷总分:100 得分:100
一、判断题(共15 道试题,共75 分)
1.试探与回溯是一种穷尽一切可能的办法,效率低、代价高,它只有理论意义,在实践中价值不大。

答案:正确
2.预测分析的关键问题是在扩展一个非终结符时怎样为它选择合适的产生式。

答案:正确
3.移进-归约分析为输入串构造分析树是从根结点开始的,朝着叶结点方向前进。

答案:错误
4.句型的句柄是该句型中和一个产生式左部匹配的子串。

答案:错误
5.一个文法,如果能为它构造出所有条目都唯一的LR分析表,就说它是LR文法。

答案:正确
6.语法制导的产生式有多组语义规则。

答案:错误
7.属性文法是指语义规则函数无副作用的语法制导定义。

答案:正确
8.仅仅使用综合属性的语法制导定义称为S属性定义。

答案:正确
9.每个结点的属性值都标注出来的分析树叫做注释分析树。

答案:正确
10.过程定义是一个声明,它的最简单形式是将一个名字和一个语句联系起来,该名字是过程名,而这个语句是过程体。

答案:正确
11.过程名出现在调用语句中则称这个过程在该点被调用。

答案:正确
12.出现在过程定义中的某些名字是特殊的,它们被称为该过程的形式参数,简称形参。

答案:正确
13.一个声明起作用的程序部分称为该声明的作用域。

答案:正确。

1.Σ={0，1}上的正规式(0|1)* 表示( )。

A.0开头的串B.1开头的串C.有一个0和一个1的串D.由0、1组成的任意串【参考答案】: D2.在自下而上的语法分析方法中，分析的关键是( )。

A.寻找句柄B.寻找句型C.消除递归D.选择候选式【参考答案】: D3.描述一个语言的文法是( )。

A.唯一的B.不唯一的C.可能唯一D.可能不唯一【参考答案】: A4.( )是指源程序中不符合语法或词法规则的错误，这些错误一般在词法分析或语法分析时能检测出来。

A.语义错误B.语法错误C.短语错误D.短句错误【参考答案】: B5.下面哪个文法具有二义性( )。

A.A→AA | (A) |B.E→E＋T|TC.E→(E)D.E→a【参考答案】: A6.一个结点相应的文法符号属性值是由该结点兄弟结点和/或父节点的相应的文法符号的属性值来计算，按这种情况计算的属性值叫做( )。

A.综合属性B.继承属性C.自然属性D.赋值属性【参考答案】: B7.若一个文法是递归的，则它所产生的句子个数( )。

A.必定是无穷的B.是有限个的C.根据具体情况而定D.不确定【参考答案】: C8.下面关于解释程序的描述正确的是( )。

(1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于COBOL 和 FORTRAN 语言(3) 解释程序是为打开编译程序技术的僵局而开发的A.(1)(2)B.(1)C.(1)(2)(3)D.(2)(3)【参考答案】: B9.赋值语句X::=-(a+b)/(c-d)-(a+b*c)r的逆波兰表示是( )。

A.Xabcd-/-bc*a-:=B.Xab/cd--bc*a--:=C.Xab-cd-/abc*-:=D.Xab cd-/abc*--:=【参考答案】: D10.正则文法( )二义性的。

A.可以是B.一定不是C.一定是D.可以不是【参考答案】: B11.通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括( )。

大工20秋《编译原理基础》在线作业1
试卷总分:100 得分:100
一、判断题 (共 15 道试题,共 75 分)
1.编译器是一种翻译器,它的特点是目标语言比源语言低级。

答案:正确
2.语法树的子结点代表该运算的运算对象。

答案:正确
3.语义分析的一个重要部分是类型检查,编译器检查每个算符的运算对象,看它们的类型是否适当。

答案:正确
4.语言定义不允许运算对象的类型作隐式转换。

答案:错误
5.代码生成是指取源程序的一种中间表示作为输入并把它映射到一种目标语言。

答案:正确
6.符号表是为每个变量名字保存一个记录的数据结构,记录的域是该名字的属性。

答案:正确
7.解释器可以通过翻译来生成目标程序。

答案:错误
8.解释执行的效率比编译器生成的机器代码的执行效率高。

答案:错误
9.类型检查是一种捕捉程序中不一致性的成熟并且有效的技术。

答案:正确
10.类型检查技术不能用于捕捉多种安全漏洞。

答案:错误
11.词法分析器的任务是把构成源程序的字符流翻译成词法记号流。

答案:正确
12.词法分析难以发现源程序的错误,因为词法分析器对源程序采取非常局部的观点。

答案:正确
13.字母表上的串是该字母表符号的有穷序列。

答案:正确
14.术语语言表示字母表上的一个串集,属于该语言的串称为该语言的句子或字。