程序设计语言编译原理_考试重点(终)

1 2 3 开

4

1

0 1

1

1 0 1

3 0 1 2 a a a ，a

b b

b 第一章 引论

1.编译程序分几个阶段，每个阶段的任务是什么？

五个阶段：词法分析、语法分析、语义分析、中间代码生成、优化、目标代码生成

词法分析任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。（如基本字，标识符，常数，算符和界符）。

语法分析任务：在词法分析基础上，将单词符号串转化为语法单位（语法范畴）（短语、子句、句子、程序段、程序），并确定整个输入串是否构成语法上正确的程序。

语义分析和中间代码生成任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。

代码优化任务：对于代码（主要是中间代码）进行加工变换，以期能够产生更为高效（省时间和空间）的目标代码 。 目标代码生成任务：将中间代码变换成特定机器上的低级语言代码

2.表格管理和出错处理：编译各阶段均须维持表格并进行表格管理，建表的技术支持是数据结构，表格的分类、结构、处理方法决定于语言及机器，还有优化措施。一个好的编译程序应该：全，最大限度发现错误；准，准确指出错误的性质和发生地点；局部化，将错误的影响限制在尽可能小的范围内。源程序中的错误通常分为 ：语法错误，不符合语法（或词法）规则的错误，如单词拼写错误、括号不匹配 ... 语义错误，不符合语义规则的错误，如说明错误、作用域错误、类型不匹配 ...

3.前端、后端：编译前端主要由与源语言有关，但与目标机无关的那些部分组成。编译后端包括编译程序中与目标机有关的那些部分。

4.遍：根据系统资源的状况、运行目标的要求……等，可以将一个编译程序设计成多遍扫描的形式，在每一遍扫描中，完成不同的任务。遍可以和阶段相对应，也可无关。单遍代码不太有效。遍 是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。

5.“运算符与运算对象类型不符”属于语义错误

6.算法逻辑上的错误属于语义错误

7.编译程序：能够把某一种语言程序转换成另一种语言程序，而后者与前者在逻辑上是等价的一种程序。通常是从高级语言转换成为低级语言。

8.解释程序：它以该语言写的源程序作为输入，但是不产生目标代码，而是边解释边执行源程序本身。

9.诊断编译程序：专门用于帮助程序开发和调试的编译程序。

10.优化编译程序：着重于提高目标代码效率的编译程序。

11.宿主机：运行编译程序的计算机。 12.目标机：运行编译程序所产生目标代码的计算机。

13.交叉编译程序：一个程序产生不同

于宿主机的机器代码的程序。 14.可变目标编译程序：如果不需要重新编译程序中与机器无关的部分就能改变目标机，则该编译程序就叫做可变目标编译程序。

PS ：世界上第一个编译程序——FORTRAN 编译程序——20世纪50年代

15.编译过程

第一阶段：词法分析——词法分析器 1)任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），标示符，常熟，算符和界符。2）单词符号是语言的基本组成成分，是人们理解和编程的基本要素。3)描述词法规则的有效工具是：正规式和有限自动机 第二阶段：语法分析——（词法）分析器

1)任务：在词法分析的基础上，根据语言的语法规则，把单词符号分解成各类语法单位，如“短语”、“子句”、“句子”、“程序段”和“程序”等。通过语法分析，确定整个输入串是否构成语法上正确的“程序”。2)语法分析所依据的是语言的语法规则。通常是上下文无关文法描述、3)词法分析是一种线性分析，而语法分析是一种层次结构分析。

第三阶段：语义分析和中间代码产生——语义分析器

1)任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。2)对每种语法范畴进行静态语义检查—>进行中间代码的翻译。3)语义分析所依据的是语言的语义规则，通常使用属性文法描述语义规则。4)中间代码：一种含义明确、便于处理的记号系统，它通常独立于具体的硬件。5)中间代码的四元式表示形式。此外还有三元式、间接三元式、逆波兰记号和树。

第四阶段：优化——优化器

1)任务：在于前段产生的中间代码进行加工交换，，以期在最后阶段能产生更为高效（省时间和空间）的目标代码。2)优化的主要方面有：公共字表达式、优化循环、删除无用代码等等。3)优化所依据的原则：程序的等价变化原则。 第五阶段：目标代码生成——目标代码生成器

1)任务：吧中间代码（或经优化处理后）变换成特定机器上的低级语言代码。2)形式：绝对指令代码或可重定位的指令代码或汇编指令代码。 16.编译程序的结构

语法错误：指源程序中不符合语法（或词法）规则的错误，他们可在词法分析和语法分析时检测出来

语法错误：指源程序中不符合语义规则的错误，一般在语义分析时检测出来，有的要在运行时才能检测出来。通常有：说明错误、作用域错误、类型不一致等

遍：对源程序或源程序的中间结果从头

到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。 编译前段：由与源程序有关但与目标程序无关的那些部分组成。包括词法分析、语法分析、语义分析与中间代码和一些优化工作。

编译后端：编译程序中与目标机有关的那些部分，后端不依赖于源语言而仅仅依赖于中间语言。

集成化的程序设计环境的特点：它将相互独立的程序设计工具集成起来，以使为程序员提供完整的、一体化的支持，从而进一步提高程序开放效率，改善程序质量。 17.T 形图

第二章 高级语言及其语法描述 1. 程序语言是由语法和语义两方面定义的。

2.上下文无关文法的定义：四个组成部分：一组终结符号、一组非终结符号、一个开始符号、一组产生式。一个上下文无关文法G 是一个四元式（VT,VN,S, P ），其中: VT ：是非空有限集，它的每个元素是终结符号；VN ：是非空有限集，它的每个元素是非终结符号，

VT ∩VN=Φ，VT ∪VN=V;S ：S ∈VN ，称为开始符号；P ：产生式集合（有限），每个产生式形式是{ P->α| P ∈VN ， α∈(VT ∪VN)*，S 至少一次为P }； 3.推导、最左推导、最右推导：1、推导：如两个串u0、un ，存在一个串序列u0=>u1=>…=>un ，则我们称这个序列是从u0到un 的一个推导。 U1un ：表示从u0出发，经一步或若干步，可推导出un. U1

un ：表示从u0出发，经0步

或若干步，可推导出un.

最左推导是指，任何一步α=>β都是对α中的最左非终结符进行替换的。最右推导是指，任何一步α=>β都是对α中的最右非终结符进行替换的。

4.语法树：在编译中产生语法树是为了语法分析。

5、什么是句型？什么是句子？什么是语言？

假定G 是一个文法，S 是它的开始符号。如果S=> α，则称α是一个句型。仅含终结符的句型是一个句子。文法G 所产生的句子的全体是一个语言。 语言是由句子组成的集合，是由一组记号所构成的集合。

6.乔姆斯基把文法分成4种类型，即0型文法、1型文法、2型文法和3型文法。0型文法也称为短语文法。1型文法也称为上下文有关文法。2型文法也称为上下文无关文法。3型文法也称为正规文法。与程序语言语法有关的文法是上下文无关文法。 第三章 词法分析

1.状态转换图：使用状态转换图是设计词法分析程序的一种好途径，状态转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。一个状态转换图可用于识别（或接受）一定的字符串。

2.确定的有限自动机（DFA ）、非确定有限自动机（NFA ）。五元式：有限状

态集合、有穷字母表、转换函数、唯一的初始状态、终止状态集合。一个确定有限自动机（DFA ） M 是一个五元式：M ＝ (S,∑,δ,s0 ,F) ，其中S 是一个有限集，它的每个元素称为一个状态，∑是一个有穷字母表，它的每个元素称为一个输入字符，δ是一个从S ×∑至S 的单值部分映射。 δ(s,a)=s ′意味着：当现行状态为、输入字符为a 时，将转换到下一状态s ′。我们称s ′为s 的一个后继状s0∈S 是唯一的初态F 是一个终态集（可空）。一个非确定有限自动机（NFA ） M 是一个五元式：M ＝ (S,∑,δ,S0 ,F) ，其中S 是一个有限集，它的每个元素称为一个状态，∑是一个有穷字母表，它的每个元素称为一个输入字符，δ是一个从S ×∑*至S 的子集的映射，即δ： S ×∑* → 2s ，S0∈S 是唯一的初态，F 是一个终态集（可空）。 3.设有确定的有限自动机DFA M = ({0,1,2,3},{a,b},δ,0,{3})，其中δ为:δ(0,a)=1 δ(0,b)=2 δ(1,a)=3 δ(1,b)=2 δ(2,a)=1 δ(2,b)=3 δ(3,a)=3 δ(3,b)=3

请画出状态转换矩阵和状态转化图。相应的状态转换矩阵如下表： 对应的状态转换图

4.设计一个DFA,要求能够识别∑={0,1}上能被5整除的二 进制数。

5.词法分析的流

程 第四章 语法分析——自上而下分析 1.语法分析器的功能：识别语法成分,并作语法检查.

2.自上而下语法分析方法遇到的主要问题是回溯和左递归。

3.把一个文法改造成任何非终结符的所有候选式首符集两两不相交的方法是提取公共左因子。

4.LL （1）分析法中，第一个L 表示从左到右扫描输入串，第二个L 表示最左推导。1表示分析时每步只需向前看一个符号。

5.LL （1）文法的条件：1文法不含左递归2）FIRST(α)∩ FIRST(β) = φ3）

算符 左操作数

右操作数

结果

状态 a b 0 1 2 1 3 2 2 1 3 3

3

3

对文法中的每个非终结符A，若它存在某个候选首符集包含ε，则FIRST（A）∩FOLLOW（A）=Φ。

6. 对下文法，计算每个非终结符的FIRST集合和FOLLOW集合。E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|∧

First(E)= First(T)= First(F)={(,a,b, ∧}

First(E’)={+, ε} ,First(T’)={(,a,b, ∧, ε}

First(F’)={*, ε} ,Follow(E)= Follow(E’)={#, )}

Follow(T)= Follow(T’)={+,#, )}

Follow(F)= Follow(F’)={(,a,b, ∧,+,),#}

Follow(P)={*, (,a,b, ∧,+,),#}

7.两种实现方法：递归下降分析法、预测分析程序。

第五章语法分析——自下而上分析1. 简述自下而上的语法分析方法:就是从输入串开始，逐步进行“规约”，直至规约到文法的开始符号；或者说从语法树的树叶开始，逐步向上规约，直至规约到根节点。

2.一个句型的句柄是该句型的最左直接短语。

3.规范规约是指最右推导的逆过程。

4.算符优先分析法1）特别适应于表达式分析的方法2）算符优先分析法中，优先表中存储的是优先关系3）算符优先分析法的可规约串是句型的最左素短语。

5.LR分析法:1）LR（K）文法是从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法2）四种分析表3）LR(0)项目的含义4）例给定文法：S→AS|b A→SA|a要求列出这个文法的所有LR(0)项目。

S→.AS S→A.S S→AS. S→.b S→b. A→.SA A→S.A A→SA. A→.a A→a.

5）写出LR(0)分析表的构造步骤:①确定G的LR(0)项目②以LR(0)项目为状态,构造一个能识别文法G的所有活前缀的NFA③利用子集法,将NFA确定化,成为以项目集合为状态的DFA根据④利用上述DFA可直接构造出LR分析表。

6）比较LR(0)、SLR（1）、LR（1）、LALR（1）分析表的优缺点:这4种分析表都能识别对应文法的全部句子，其共同特征就是用规范规约的方法寻找句柄进行规约。在这4种方法中，LR （0）分析表对文法的要求较高，其构造方法是其它表构造方法的基础；SLR （1）分析表对文法的要求有所降低，容易实现，因而很有实用价值；LR（1）分析表对文法的要求最低，适用于一大类文法，故其分析能力最强，但其实现代价过高；LALR（1）分析表的分析能力介于SLR（1）和LR（1）之间，实现代价比LR（1）低。

第六章属性文法和语法制导定义1.语法制导翻译法就是在语法分析的过程中,随分析的过程,根据为每个产生式添加的语义动作进行翻译的方法。2.写出产生式、语义规则和语义子程序

之间的关系。

①产生式:一个产生式描述了一个语法

单位,但它只说明了该语法单位能产生

的符号串,并未指明所产生的符号串有

什么实际意义,即该符号串究竟要做什

么。②语义规则:一个产生式的语义规

则描述了该产生式的具体的动作意义,

即该产生式产生的符号串要做什么。③

语义子程序:按照产生式的语义规则生

成某种中间代码,实现相应的动作。

3.对于文法的每个产生式都配备了一

组属性的计算规则，称为属性。

4.文法符号的属性有两种，一种称为综

合属性，一种称为继承属性。综合属性

传递信息的方向是自下而上。继承属性

传递信息的方向是自上而下。

5. 在分析树中，一个结点的综合属性

值是从其子结点的属性值计算出来的。

一个结点的继承属性由此结点的父结

点或兄弟结点的某些属性确定。

6.为文法S →( L ) | a L →L , S | S

写一个语法制导定义，它输出括号的对

数。

S’→S print (S. num)

S →( L ) S. num := L.num

S →a S. num := 0

L →L1 , S L. num :=max{ L1.

num , S. num}

L →S L. num := S.num

7.为文法S→( L ) | a L →L , S | S

写一个翻译方案，它输出每个a的嵌套

深度。例如，对于( a , ( a , a) )，输出

的结果是1 2 2。

S’→{S. depth := 0 } S

S→{L. depth := S. depth + 1 } ( L ) S →

a {print (S. depth) }

L →{L1. depth := L. depth }L1 , {S.

depth := L. depth }S

L→{S. depth := L. depth }S

8.S-属性文法：只含有综合属性。可借

助于LR分析器实现。采用自底向上分

析，例如LR分析，首先给出S-属性定

义，然后，把S-属性定义变成可执行的

代码段，这就构成了翻译程序。L-属性

文法，如果对于每个产生式A

－>X1X2…Xn，其每个语义规则中的每

个属性或者是综合属性，或者是Xj

（1<=j<=n) 的一个继承属性且这个继

承属性仅依赖于：

a. 产生式Xj的左边符号X1，

X2，…,Xj-1的属性

b. A的继承属性。S-属性文法是L-属

性文法。

第七章语义分析和中间代码产生

1.常用的中间代码的形式：后缀式（逆

波兰式）、三地址码（三元式、四元式、

间接三元式）。

2.会用后缀式表示：

表达式的后缀表示可以如下递归定义：

1）如果E是变量或者常数，那么E的

后缀表示就是E本身2）如果E是形式

为E1 op E2的表达式，其中op是任意

的二元算符，那么E的后缀表示是

E1'E2'op,其中E1‘和E2’分别是E1和

E2的后缀表示3）如果E是形式为（E1)

的表达式，那么E1的后缀表示也是E

的后缀表示。

3.已知A是一个10×20的数组(每维下

界均为1)，每个元素占1个单元，且按

行存放，要求写出：赋值语句X=A[I,J]

的四元式序列。

100 (*，I，20，T1) /*d2=2

101 (+，J，T1，T1) /*得到

102 (?，A，21，T2) /*得到A

103(=[ ]，T2[T1]，_，T3)/*T2[T1]即为

A[I, J]即T3=T2[1]*/

104 (=，T3，_，X)

第十章优化

1．为了获得更优化的程序，可以从哪

些层次上对程序进行优化？为了获得

更优化的程序，可以从各个环节着手：

在源代码级，可以选择适当的算法和安

排适当的实现语句来提高程序的效率。

在语义动作的设计上，考虑产生更高效

的中间代码，并为优化阶段做准备。在

中间代码级，安排专门的优化阶段，进

行各种等价变换，以改进代码的效率。

在目标代码级，考虑如何有效地利用寄

存器，如何选择指令，以及进行窥孔优

化等。

2.常用的优化方法

局部优化: 删除公共子表达式、复写传

播、删除无用代码。循环优化：代码外

提、强度削弱、删除归纳变量

3.程序基本块是指程序中一顺序执行

的语句序列，其中只有一个入口和一个

出口。

4.基本块的入口、基本块的划分、流图：

入口就是其中的第一个语句 1.求出四

元式程序中的各个基本块中的入口地

1)程序的第一个语句2)能由条件转移

语句或无条件转移语句转移到的语句

3)紧跟在条件转移语句后面的语句 2.

对以上求出的每一人口语句，构造其所

属的基本块。它是由该人口语句（开始）

到一转移语句(包括该转移语句)，或到

一停语句(包括该停语句)之间的语句序

列组成的。3. 删除无用代码。凡未被

纳入某一基本块中的语句，都是程序中

控制流程无法到达的语句，从而也是不

会被执行到的语句，我们可把它们从程

序中删除。

5.已知如下中间代码序列：1）read X

2）read Y

3）R := X mod Y 4）if R=0 goto(8)

5）X := Y

6）Y := R 7）goto (3) 8）write Y

9）halt

要求：1）写出基本块的入口语句。2）

为其划分基本块。3）为其构造流图。

①入口语句：1、3、5、8 ②基本块和

流图(最后面的图)

1.目标代码的形式

2.考虑问题1）指令选择2）寄存器分

配3）计算顺序选择

SDL

1. SDL把应用领域分为两部分SDL系

统和环境。

2. SDL中，系统与环境之间的通信可

以通过什么来通信交换信号。

3.SDL系统由系统、功能块和进程3个

层次的实体组成。

4. SDL中每个系统可以划分为多个功

能块。

5. SDL系统中的功能块最终都需要定

义为进程。

6.在SDL系统中的基本单位是进程实

例。

7. SDL描述系统行为的基础是扩展的

有限状态自动机。

8 SDL 的每个进程实例就是有限状态

自动机。

9. SDL中，进程规定了系统的动态结

构。

Block代表了系统的静态结构。

一、单项选择题(共10小题，每小题2

分，共20分)

1．语言是

A句子的集合B．产生式的集合C．符

号串的集合D．句型的集合

2．编译程序前三个阶段完成的工作是

A．词法分析、语法分析和代码优化

B．代码生成、代码优化和词法分析

C．词法分析、语法分析、语义分析和

中间代码生成

D．词法分析、语法分析和代码优化

3．一个句型中称为句柄的是该句型的

最左A．非终结符号B．短语C．句

子D．直接短语

4．下推自动机识别的语言是

A．0型语言B．1型语言C．2型语

言D．3型语言

5．扫描器所完成的任务是从字符串形

式的源程序中识别出一个个具有独立

含义的最小语法单位即

A．字符B．单词C．句子D．句

型

6．对应Chomsky四种文法的四种语言

之间的关系是

A．L0L1L2L3

B．L3L2L1L0

C．L3=L2L1L0

D．L0L1L2=L3

7．词法分析的任务是

A．识别单词B．分析句子的含义

C．识别句子D．生成目标代码

8．常用的中间代码形式不含

A．三元式B．四元式C．逆

波兰式D．语法树

9．代码优化的目的是

A．节省时间B．节省空间C．节省

时间和空间D．把编译程序进行等价交

换

10．代码生成阶段的主要任务是

A．把高级语言翻译成汇编语言

B．把高级语言翻译成机器语言

C．把中间代码变换成依赖具体机器的

目标代码

（3）R := （1）

（5）X := Y （8）

D．把汇编语言翻译成机器语言

二、填空题（本大题共5小题，每小题2分，共10分）

1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。

2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。

3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。

4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。

5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。

1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？

解答：

S-属性文法是只含有综合属性的属性文法。（2分）

L-属性文法要求对于每个产生式A X1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：

产生式Xj的左边符号X1,X2…Xj-1的属性；A的继承属性。

S-属性文法是L-属性文法的特例。2．什么是句柄？什么是素短语？

一个句型的最左直接短语称为该句型的句柄。素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短语。

3．划分程序的基本块时，确定基本块的入口语句的条件是什么？

解答：（1）程序第一个语句，或（2）能由条件转移语句或无条件转移语句转移到的语句，或（3）紧跟在条件转移语句后面的语句。

4．运行时的DISPLAY表的内容是什么？它的作用是什么？答：DISPLAY 表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层

过程的变量。

1. 简要说明语义分析的基本功能。

答：语义分析的基本功能包括: 确定类

型、类型检查、语义处理和某些静态语

义检查。

2. 考虑文法G[S]: S →(T) | a+S |

a ;T →T,S | S

消除文法的左递归及提取公共左因子。

解：消除文法G[S]的左递归：S→(T) |

a+S | a ;T→ST′;T′→,ST′| ε

提取公共左因子：S→(T) | aS′;S′→+S |

ε;T→ST′;T′→,ST′| ε

3.试为表达式w+(a+b)*(c+d/(e-10)+8)

写出相应的逆波兰表示。解：w a b + c

d e 10 - / + 8 + * +

5.已知文法G[S] 为S →

aSb|Sb|b ，试证明文法G[S] 为二义

文法。

证明：由文法G[S]：S→aSb|Sb|b，对

句子aabbbb对应的两棵语法树为：

因此，文法G[S]为二义文法。

1．词法分析

词法分析的主要任务是从左向右扫描

每行源程序的符号，按照词法规则

从构成源程序的字符串中识别出一个

个具有独立意义的最小语法单位，

并转换成统一的内部表示(token)，送

给语法分析程序。

2．LL(1)文法

若文法的任何两个产生式A |

都满足下面两个条件：

（1）FIRST( ) FIRST( ) = ；

（2）若* ，那么FIRST()

FOLLOW( A ) = 。

我们把满足这两个条件的文法叫做

LL(1)文法，其中的第一个L代表从左

向右扫描输入，第二个L表示产生最

左推导，1代表在决定分析器的每步

动作时向前看一个输入符号。除了没

有公共左因子外，LL(1)文法还有一

些明显的性质，它不是二义的，也不

含左递归。

3．语法树

句子的树结构表示法称为语法树

(语法分析树或语法推导树)。

给定文法G=(VN，VT，P，S)，对于G

的任何句型都能构造与之关联的

语法树。这棵树具有下列特征：

(1)根节点的标记是开始符号S。

(2)每个节点的标记都是V中的一个符

号。

(3)若一棵子树的根节点为A，且其所有

直接子孙的标记从左向右的排列

次序为A1A2…AR，那么A A1A2…

AR一定是P中的一条产生式。

(4)若一标记为A的节点至少有一个除

它以外的子孙，则A

∈VN。

(5)若树的所有叶节点上的标记从左到

右排列为字符串w，则w是文法G

的句型；若w中仅含终结符号，则w

为文法G所产生的句子。

4．LR(0)分析器

所谓LR(0)分析，是指从左至右扫描

和自底向上的语法分析，且在分析的

每一步，只须根据分析栈当前已移进和

归约出的全部文法符号，并至多再

向前查看0个输入符号，就能确定相对

于某一产生式左部符号的句柄是否

已在分析栈的顶部形成，从而也就可以

确定当前所应采取的分析动作(是

移进还是按某一产生式进行归约等)。

5．语言和文法

文法就是语言结构的定义和描述，是有

穷非空的产生式集合。

文法G定义为四元组的形式：G=(VN，

VT，P，S)其中：VN 是非空有穷集合，

称为非终结符号集合；VT 是非空有穷

集合，称为终结符号集合；P是产生式

的集合(非空)；S是开始符号(或识别符

号)。这里，VN∩VT=，S

∈VN。V=VN

∪VT，称为文法G的字母表，它是出现

文法产生式中的一切符号的集合。文法

G所描述的语言用L(G)表示，它由文

法G所产生的全部句子组成，即

L(G)={x| S*x，其中S为文法开始符

号，且

+

∈

T

V

x

}简单的说，文法描

述的语言是该文法一切句子的集合。

1．编译程序和高级语言有什么区别?

用汇编语言或高级语言编写的程

序，必须先送入计算机，经过转换成用

机器

语言表示的目标程序（这个过程即编

译），才能由计算机执行。执行转换过

程

的程序叫编译程序。汇编程序是指没有

编译过的汇编语言源文件。编译程序转

换过的叫目标程序，也就是机器语言。

编译程序的工作情况有三种：汇编型、

解释型和编译型。汇编型编译程序用来

将汇编语言编写的程序，按照一一对应

的关系，转换成用机器语言表示的程

序。解释型编译程序将高级语言程序的

一个语句，先解释成为一组机器语言的

指令，然后立即执行，执行完了，取下

一组语句解释和执行，如此继续到完成

一个程序止。用解释型编译程序，执行

速度很慢，但可以进行人和计算机的"

对话"，随时可以修改高级语言的程序。

BASIC语言就是解释型高级语言。编译

型编译程序将级语言编写的程序，一次

就会部翻译成机器语言表示的程序，而

且过程进行很快，在过程中，不能进行

人机对话修改。FORTRAN语言就是编

译型高级语言。

2．编译程序的工作分为那几个阶段?

词法分析、语法分析和语义分析是对

源程序进行的分析(称为编译程序的前

端)，而中间代码生成、代码优化和代

码生成三个阶段合称为对源程序进行

综合(称为编译程序的后端)，它们从源

程序的中间表示建立起和源程序等价

的目标程序。

3．简述自下而上的分析方法。

所谓自下而上分析法就是从输入串

开始，逐步进行“归约”，直至归约到文

法的开始符号；或者说从语法树的末端

开始，步步向上“归约”，直到根节点。

4．简述代码优化的目的和意义。

代码优化是尽量生成“好”的代码的编

译阶段。也就是要对程序代码进行一种

等价变换，在保证变换前后代码执行结

果相同的前提下，尽量使目标程序运行

时所需要的时间短，同时所占用的存储

空间少。

《编译原理》考试试题及答案(汇总)讲课稿

《编译原理》考试试题及答案(汇总)

《编译原理》考试试题及答案（汇总） 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．编译程序是对高级语言程序的解释执行。(× ) 2．一个有限状态自动机中，有且仅有一个唯一的终态。(×) 3．一个算符优先文法可能不存在算符优先函数与之对应。(√ ) 4．语法分析时必须先消除文法中的左递归。 (×) 5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√) 6．逆波兰表示法表示表达式时无须使用括号。 (√ ) 7．静态数组的存储空间可以在编译时确定。 (×) 8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。 (×) 9．两个正规集相等的必要条件是他们对应的正规式等价。 (× ) 10．一个语义子程序描述了一个文法所对应的翻译工作。 (×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。 A．( ) 单词的种别编码B．( ) 单词在符号表中的位置 C．( ) 单词的种别编码和自身值D．( ) 单词自身值 2．正规式 M 1 和 M 2 等价是指_____。 A．( ) M1和M2的状态数相等 B．( ) M1和M2的有向边条数相等 C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等

3．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 4．如果文法G是无二义的，则它的任何句子α_____。 A．( )最左推导和最右推导对应的语法树必定相同 B．( ) 最左推导和最右推导对应的语法树可能不同 C．( ) 最左推导和最右推导必定相同 D．( )可能存在两个不同的最左推导，但它们对应的语法树相同 5．构造编译程序应掌握______。 A．( )源程序B．( ) 目标语言 C．( ) 编译方法 D．( ) 以上三项都是 6．四元式之间的联系是通过_____实现的。 A．( ) 指示器B．( ) 临时变量 C．( ) 符号表 D．( ) 程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为_____。 A. ( ) ┐AB∨∧CD∨B．( ) A┐B∨CD∨∧ C．( ) AB∨┐CD∨∧ D．( ) A┐B∨∧CD∨ 8. 优化可生成_____的目标代码。 A．( ) 运行时间较短 B．( ) 占用存储空间较小 C．( ) 运行时间短但占用内存空间大D．( ) 运行时间短且占用存储空间小9．下列______优化方法不是针对循环优化进行的。

汇编语言程序的设计试卷与答案

汇编语言程序设计试卷 一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内，每小题1分，共20分） 1．十六进制数88H，可表示成下面几种形式，请找出错误的表示（）。 ① 无符号十进制数136 ② 带符号十进制数－120 ③ 压缩型BCD码十进制数88 ④ 8位二进制数－8的补码表示 2．指令指针寄存器是（）。 ① IP ② SP ③ BP ④ PSW 3．当执行指令ADD AX，BX后，若AX的内容为2BA0H， 设置的奇偶标志位PF＝1，下面的叙述正确的是（）。 ① 表示结果中含1的个数为偶数 ② 表示结果中含1的个数为奇数 ③ 表示该数为偶数 ④ 表示结果中低八位含1的个数为偶数 4．完成将累加器AL清零，并使进位标志CF清零， 下面错误的指令是（）。 ① MOV AL,00H ② AND AL,00H

③ XOR AL,AL ④ SUB AL,AL 5．下列指令执行后总是使CF＝0，OF＝0的是（）。 ① AND ② NEG ③ NOT ④ INC 6．完成同指令XCHG AX，BX相同功能的指令或指令序列是（）。 ① MOV AX，BX ② MOV BX，AX ③ PUSH AX POP BX ④ MOV CX，AX MOV AX，BX MOV BX，CX 7．设AH＝0，AL＝06H，BL＝09H，执行指令 ADD AL，BL AAA 之后，其结果应是（）。 ① AH＝01，AL＝05 ② AH＝1 AL＝15 ③ AH＝0 AL＝0FH ④ AH＝0 AL＝05 8．设AL＝0B4H，BL＝11H，指令“MUL BL”和指令“IMUL BL”分别执行后OF，CF的值为

编译原理试题

中间语言与语法制导翻译 重点与难点 重点：语法制导翻译的基本思想，属性文法，翻译模式，说明语句的翻译方案。 三地址码，各种语句的目标代码结构、属性文法与翻译模式。 难点：属性的意义，对综合属性，继承属性，固有属性的理解，属性计算，怎么通过属性来表达翻译。布尔表达式的翻译，对各种语句的目标代码结构、属性文法与翻译模式的理解。 基本要求 掌握语法制导翻译的基本思想，属性文法，综合属性，继承属性，固有属性，属性计算，S_属性文法，L_属性文法，说明语句的翻译方案，翻译模式、属性文法的实现掌握中间语言与语义分析的基本概念；熟练掌握语法（结构）树、三地址代码、赋值与控制语句的翻译、说明语句的翻译；掌握组合数据说明的翻译、过程调用翻译。 例题解析 例1 给定文法 E --> T { R.i := T.p } R { E.p := R.s } R --> addop T { R1.i := mknode( addop.val, R.i, T.p ) } R { R.s := R1.s } R --> { R.s := R1.s } T --> ( E ) { T.p := E.p } T --> id { T.p := mkleaf( id, id.entry ) } T --> num { T.p := mkleaf( num, num.val ) } (1) 指出文法中的各非终结符具有哪些综合属性和哪些继承属性 ⑵画出按本翻译模式处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树 【解】 (1)E的综合属性 p，R的继承属性i，综合属性s；T的综合属性p (2) 处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树如下 + （NUM, 20） - ( ID, b) (NUM, 10) 例2 定义一个计算器的属性文法,完成一个输入表达式值的计算和显示, 【解】计算器的文法 L → E

编译原理复习题2017(含试卷)

* 编译原理复习题 一．简答题： 1) 什么是句子？ 什么是语言? 解答：句子——设G 是一个给定的文法，S 是文法的开始符号，如果S x （其中x ∈V T * ），则称x 是文法的一个句子。 语言——语言是句子的集合。 或——设G[S]是给定文法，则由文法G 所定义的语言L(G)可描述为：L(G)＝{x │ S x,x ∈V T * } 。 2) DFA 与NFA 有何区别 ? 解答:DFA 与NFA 的区别表现为两个方面:一是NFA 可以有若干个开始状态，而DFA 仅只有一个 开始状态。另一方面，DFA 的映象M 是从K ×∑到K ，而NFA 的映象M 是从K ×∑到K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。 3) 自顶向下的语法分析方法的基本思想是什么? 解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接 推导，试图推导出文法的句子，使之与给定的输入串匹配。 4) 自底向上的语法分析方法的基本思想是什么? 解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图 归约到文法的开始符号。 5) 一个上下文无关文法G 包括哪四个组成部分？ 解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。 6) 在自底向上的语法分析方法中，分析的关键是什么？

解答:关键是寻找句柄。 7)在自顶向下的语法分析方法中，分析的关键是什么？ 解答:关键是选择候选式。 8）什么是属性文法？ 答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属 性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析过 程中，完成语义规则所描述的动作，从而实现语义处理。 一个属性文法形式的定义为一个三元组AG，AG=（G，V，E）。 其中G为一个上下文无关文法；V为属性的有穷集；E为一组语义规则。 9）语法制导翻译 语法制导翻译：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。 语法制导翻译(Syntax-Directed Translations)： –一个句子的语义翻译过程与语法分析过程同时进行。 在文法中，文法符号有明确的意义，文法符号之间有确定的语义关系。属性描述语义信息， 语义规则描述属性间的的关系，将语义规则与语法规则相结合，在语法分析的过程中计算语义 属性值。 10）词法分析的主要任务是什么？ 解答:词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫 描，依次把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度统一的属 11)图示运行时存储空间的划分（分为哪几个区）。 解答: 一般分为静态区和动态区： 程序代码区、静态数据区、栈区和堆区 12)常用的中间语言种类有哪几种？ 解答: 常用的中间语言种类有逆波兰表示、三元式、四元式和树形表示。 13）文法G所描述的语言是什么的集合？ 解答:是由文法的开始符号推出的所有终结符串的集合。或说是句子的集合。 14）乔姆斯基把文法分为四种类型，即0型、1型、2型、3型。其中2型文法叫什么？ 解答: 2型文法叫上下文无关文法。 15）常见的动态存贮分配策略有哪两种？ 解答:常见的两种动态存贮分配策略是栈式动态分配策略和堆式动态分配策略。 16）语法分析的任务是什么？

编译原理复习题及答案

编译原理复习题及答案 一、选择题 1．一个正规语言只能对应(B) A 一个正规文法 B 一个最小有限状态自动机 2．文法G[A]：A→εA→aB B→Ab B→a是(A) A 正规文法 B 二型文法 3．下面说法正确的是(A) A 一个SLR（1）文法一定也是LALR（1）文法 B 一个LR（1）文法一定也是LALR（1）文法 4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A) A 必要条件 B 充分必要条件 5．下面说法正确的是(B) A 一个正规式只能对应一个确定的有限状态自动机 B 一个正规语言可能对应多个正规文法 6．算符优先分析与规范归约相比的优点是(A) A 归约速度快 B 对文法限制少 7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B) A 则可能存在移进/归约冲突 B 则可能存在归约/归约冲突 C 则可能存在移进/归约冲突和归约/归约冲突 8．下面说法正确的是(A) A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器 9．下面说法正确的是(A) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10．编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 11．(A)是一种典型的解释型语言。

A．BASIC B．C C．FORTRAN D．PASCAL 12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 13．用高级语言编写的程序经编译后产生的程序叫(B) A．源程序 B．目标程序C．连接程序D．解释程序 14．(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器16．编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 17．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C) A. bba B. cab C. bca D. cba

汇编语言程序设计期末考试题

汇编语言程序设计期末考试题 学院(系)：学号: 姓名: 计分: 一、项选择题(在每小题的四个备选答案中,选出一个正确答案,并将正确答案的序号填在题干的括号 内。每小题1分,共1０分） 1.CPＵ发出的访问存储器的地址是（ ) A.物理地址 B.偏移地址Ｃ.逻辑地址Ｄ.段地址 2.将高级语言的程序翻译成机器码程序的实用程序是( ) Ａ.编译程序 B.汇编程序 C.解释程序 D.目标程序 3.DＥＣ BYTE PTR[BＸ]指令中的操作数的数据类型是( ) Ａ.字 B.双字C．字节Ｄ．四字 4.在下列语句中，BUＦFER称为( ) BUFＦＥＲ DB ０1H，0AH Ａ.符号 B．变量 C.助记符Ｄ．标号 5.串操作指令中，源串操作数的段地址一定在( )寄存器中。 A． CＳ B. ＳＳ C. DS D. ＥS 6.使计算机执行某种操作的命令是( ) A.伪指令Ｂ.指令 C.标号Ｄ.助记符 7.将数据56１８H存放在存储单元中的伪指令是( ） A. DＡTA1 DW １8５６H B. DＡTＡ1 DB １8H，５６Ｈ Ｃ. DATA１EQU ５6１8Ｈ D. DＡTA1 ＤB 1８H，00H，56H，０0H 8.若ＡX＝3５００H,CX=56B８H,当AＮD ＡＸ,CX指令执行后,AX＝( ) Ａ．1400Ｈ B. ７7Ｆ８H C. ０00０Ｈ D. ０FFFＦH 9.计算机处理问题中会碰到大量的字符、符号,对此必须采用统一的二进制编码。目前,微机中普遍 采用的是( )码。 Ａ． BCＤ码 B.二进制码 C.ASCＩＩ码Ｄ.十六进制码 10.用指令的助记符、符号地址、标号和伪指令、宏指令以及规定的格式书写程序的语 言称为( ) A.汇编语言 B.高级语言 C.机器语言 D.低级语言 二、填空题(每空１分，共20分) 1.在８086/8０88汇编语言中,有五条串操作指令，其中搜索字符串指令的助记符是____＿＿。 2.通常所说的计算机系统包括___＿_＿_＿和_＿＿____＿两大部分。 3.80８6/8088存储器分四个段，这四个段的段名所对应的段寄存器分别是__＿__＿＿＿、__＿_＿ ___、___＿____、___＿_＿_＿。 4.现有AX=2０00H，ＢX=1200H, DS=3000H, DI=0002Ｈ， (31２0０H)=50Ｈ，（3120１Ｈ)=02H, (312０2Ｈ)＝40Ｈ,请写出下列各条指令独立执行完后有关寄存器及存储单元的内容，并指出标 志位ZF、CＦ的值。 A.ＡDＤＡX,1２０0H;问AＸ=_______＿Ｈ,ZF=___＿____

编译原理考试试卷

一、填空题（每空 2 分，共 30 分） 1、编译程序的整个过程可以从逻辑上划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等几个阶段，另外还有两个重要的工 作是表格管理和出错处理 2、规范规约中的可归约串是句柄，算符优先分析中的可归约串是最左素短语。 3、语法分析方法主要可分为自顶向下和自底向上两大类。 4、 LR （ 0）文法的项目集中不会出现移进 -归约冲突和归约 -归约冲突。 5、数据空间的动存态储分配方式可分为栈式和堆式两种。 6、编译程序是指能将源语言程序翻译成目标语言程序的程序。 7、确定有穷自动机DFA 是NFA的一个特例。 8、表达式 (a+b)*c的逆波兰表示为ab+c*。 二、选择题（每题 2 分，共 20 分） 1、 L R 语法分析栈中存放的状态是识别B的 DFA 状态。 A 、前缀B、可归前缀C、项目 D 、句柄 2、D不可能是目标代码。 A 、汇编指令代码 B 、可重定位指令代码 C、绝对机器指令代码 D 、中间代码 3、一个控制流程图就是具有C的有向图 A 、唯一入口结点B、唯一出口结点C、唯一首结点 D 、唯一尾结点 4、设有文法G[S] ： S→ b|bB B → bS ，则该文法所描述的语言是C。 A 、 L （ G）={b i|i≥ 0}B、 L （G） ={b 2i |i≥0} C、 L （ G）={b 2i+1|i≥ 0} D 、 L （ G）={b 2i+1|i ≥1} 5、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B完成的。 A 、编译器 B 、汇编器C、解释器D、预处理器6、在目标代码生成阶段，符号表用于D。 A 、目标代码生成 B 、语义检查C、语法检查D、预处理器地址分配0 7、规范归约是指B。 A 、最左推导的逆过程 B 、最右推导的逆过程C、规范推导D、最左归约逆过程 8、使用A可以定义一个程序的意义。 A 、语义规则B、词法规则C、语法规则D、左结合规则 9、经过编译所得到的目标程序是D。 A 、三元式序列B、四元式序列C、间接三元式 D 、机器语言程序或汇编语言程序 10、在一个基本块内进行的代码优化是B。 A 、全局优化B、局部优化C、循环优化D、代码外提 三、简答题（ 3 小题，共 30 分） 1、已知文法G[S]：S→Ac|aB A→ ab B→ bc 证明该文法具有二义性（本题 6 分） 证明：因为该文法的句型abc 存在如下两棵语法树： 所以，该文法具有二义性 一、填空题（每空 1分，共 20分） 1．编译过程一般分为、、中间代码生成、 和目标代码生成五个阶段。 2．语法分析最常用的两类方法是和分析法。 3．确定的有穷自动机是一个，通常表示为。

编译原理复习整理(重点含答案)

1、给出下面语言的相应文法。L1={a n b n c i|n≥1,i≥0} 从n，i的不同取值来把L1分成两部分：前半部分是anbn：A→aAb|ab后半部分是ci：B→Bc|ε所以整个文法G1[S]可以写为：G1(S):S→AB；A→aAb|ab；B→cB|ε 3、构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。 （要求：先将正规式转化为NFA，再将NFA确定化，最小化）

4、对下面的文法G: E →TE ’ E ’→+E|ε T →FT ’ T ’→T|ε F →PF ’ F ’ →*F ’|ε P →(E)|a|b|∧ （1）证明这个文法是LL(1)的。 （2）构造它的预测分析表。 (1)FIRST(E)={(,a,b,^}FIRST(E')={+, ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)} FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#} (2)考虑下列产生式: '→+'→'→'→E E T T F F P E a b ||*|()|^||εεε FIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φ FIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ

编译原理考试重点题

1、设正规式r= a(a|b)*, 将r转换为相应的正规文法。 令S为文法开始符，首先形成S →a(a|b)*,然后形成S →aA和A →(a|b)*,再变换成： S→aA A→ε A→(a|b)A， 进而变换成正规文法形式： S→aA A→ε A→aA A→bA 2、令文法G[S] S→cC,S→c,C→cC,C→dC,C→c,C→d， 将该文法转换为相应的正规式。 首先有S=cC|c， C=(cC|dC)|(c|d) =(c|d)C|(c|d) =(c|d)*|(c|d) =(c|d)+ 进一步有

S=c(c|d)+|c =c(c|d)* c(c|d)*即为该文法所对应的正规式 令文法G[S]为: S->S+A|A A->A*B|B B->(S)|a|b (1)分析说明a*a+b是该文法的一个句型； (2)指出该句型的所有短语、直接短语和句柄。（1）该字符串对应的语法树为： 所以a*a+b为该文法的句型。 （2）短语为：a,a,a*a,b,a*a+b； 直接短语为：a,a,b； 句柄为：最左边的a 令文法G[S]为: S->aCcDe C->b|Cb D->d

(1)分析说明aCbcde是它的一个句型； (2)指出该句型的所有短语、直接短语和句柄。 （1）此句型对应语法树如下，故aCbcde为此文法的一个句型。 （2）短语为：aCbcde，Cb，d； 直接短语：Cb，d； 句柄: Cb。 构造正规式(a|b)*相应的最小化DFA。 1、首先构造对应的NFA： 2、将NFA确定化： 3、对其最小化：

设有非确定的有自限动机NFA M=({A，B，C}，{0，1}，δ，{A}，{C})，其中： δ(A，0)={C}， δ(A，1)={A，B}， δ(B，1)={C}， δ(C，1)={C}。 请画出状态转换距阵和状态转换图。 状态转换距阵为： 状态转换图为：

汇编语言程序设计试题A卷

陕西电子信息职业技术学院考试试卷(A) 2011至2012学年度第一学期 期末 班级： 09成教 课程: 汇编语言程序设计 题 号 一 二 三 四 五 合分人 分 数 总 分 （考试时间：120分钟 满分100分） 一、单项选择题（本大题共10小题，每小题2分，共20分） 1. 计算机硬件中最核心的部件是（ ）。 A. 运算器 B. 主存储器 C. CPU D. 输入 / 输出设备 2. 指令指针寄存器（IP ）中存放的内容（ ）。 A. 指令 B. 指令地址 C. 操作数 D. 操作数地址 3. 寄存器间接寻址方式中，要寻找的操作数位于（ ）中。 A. 通用寄存器 B. 内存单元 C. 段寄存器 D. 堆栈 4. I/O 端口的编址方式分为统一编址和（ ）。 A. 独立编址 B. 选择编址 C. 设置编址 D. 控制编址 5. 汇编语言程序中可执行的指令位于（ ）中。 A. 数据段 B. 堆栈段 C. 代码段 D. 附加数据段 6. 循环结构设计中，要考虑的核心问题是（ ）。 A. 循环的控制 B. 选择循环结构 C. 设置循环参数初始值 D. 修改循环控制参数 7. 在汇编中用于管理和控制计算机相关功能的指令是（ ）。 A. 伪指令 B. 机器指令 C. 宏指令 D. 目标指令 班级 姓名 学号 — — — — — — — — — — — — — — — — 密 — — — — — — — — — 封 — — — — — — — — — — 线 — — — — — — — — — — — — — — — —

8. 识别中断源的方法包括查询中断和（）共两种类型。 A. 指令中断 B. 故障中断 C. 矢量中断 D. 实时时钟中断 9. CPU与I/O设备之间需要传输的信息通常包括（）、状态信息 和控制信息。 A. 编址信息 B. 格式信息 C. 中断信息 D. 数据信息 10. 一般情况下，汇编源程序应由数据段、（）和代码段共三个逻 辑段组成。 A. 逻辑段 B. 堆栈段 C. 指令段 D. 类型段 二、名词解释（本大题共5小题，每小题4分，共20分） 11. 微处理器： 12. 寻址方式： 13. 伪指令： 14. 中断源：

编译原理试题

1997年编译原理试题 1．（10分）某操作系统下合法的文件名为 device:name.extension 其中第一部分（device:）和第三部分（.extension）可缺省，若device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。 2．（20分） a. 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。 S—> S and S | S or S | not S | p | q | (S) b. 下面文法是否为LL(1)文法？说明理由。 S—> A B | P Q x A—> x y B—> b c P—> d P | εQ—> a Q | ε 3．（10分）某些语言允许给出名字表的一个属性表，也允许声明嵌在另一个声明里面，下面文法抽象这个问题。 D —> attrlist namelist | attrlist (D) namelist —> id, namelist | id attrlist —> A attrlist | A A —> decimal | fixed | float | real D —> attrlist namelist的含义是：在namelist中的任何名字有attrlist 中给出的所有属性。D—> attrlist (D) 的含义是：在括号中的声明提到的所有名字有attrlist 中给出的所有属性，而不管声明嵌套多少层。写一个翻译方案，它将每个名字的属性个数填入符号表。为简单起见，若属性重复出现，则重复计数。4．（10分）把表达式 -(a+b)*(c+d)+(a+b+c) 翻译成四元式。 5．（10分）由于文法二义引起的LR（1）分析动作冲突，可以依据消除二义的规则而得到LR（1）分析表，根据此表可以正确识别输入串是否为相应语言的句子。对于非二义非LR（1）文法引起的LR（1）分析动作的冲突，是否也可以依据什么规则来消除LR（1）分析动作的冲突而得到LR（1）分析表，并且根据此表识别相应语言的句子？若可以，你是否可以给出这样的规则？ 6．（5分）UNIX 下的C编译命令cc的选择项g和O的解释如下，其中dbx 的解释是“dbx is an utility for source-level debugging and execution of programs written in C”。试说明为什么用了选择项g后，选择项O便被忽略。 -g Produce additional symbol table information for dbx(1) and dbxtool(1) and pass -lg option to ld(1) (so as to include the g library, that is:

【汇编语言程序设计】试题及答案合集

《汇编语言程序设计试题及答案》合集 汇编语言程序设计试题及答案 1．对于有符号的数来说，下列哪个值最大（D） A：0F8H B：11010011B C：82 D：123Q 2．下列有关汇编语言中标号的命名规则中，错误的是（D） A：通常由字母打头的字符、数字串组成 B：标号长度不能超过31个字符 C：？和$不能单独作为标号 D：．号不可位于标号首 3．8088/8086存储器分段，每个段不超过（D ） A.64K个字 B.32K个字节 C.1兆个字节 D.64K个字节 4．寻址指令MOV CX, [BX + DI + 20]使用的是哪一种寻址方式（B）A：寄存器寻址B：相对基址变址寻址 C：变址寻址D：基址变址寻址 5．若AX= - 15要得到AX=15应执行的指令是（A ） A.NEG AX B.NOT AX C.INC AX D.DEC AX 6．8086/8088系统执行传送指令MOV时（ A） A.不影响标志位 B.影响DF方向标志 C.影响SF符号标志 D.影响CF进位标志 7.若要求一个操作数中的若干位维持不变，若干位置?1?，可以使用（B）A：NOT B：OR C：AND D：XOR 8．下列指令中段默认为堆栈段的是（ C） A.MOV AX，[BX+SI+10] B.ADD AX，ES:[SI] C.SUB [BX]，[BP][DI] D. MOV DX，[1000H] 9．关于8086/8088微机系列，下列说法哪个是正确的（D） A：一个存储单元由16个二进制位组成，简称字。

B：当存储一个字数据时，低字节放高地址位，高字节放低地址位。 C：在内存空间中，可以无限分配段，且段的大小不受限制。 D：段与段之间可以邻接，也可以重叠。 10．下列关于堆栈的说法，错误的是（D） A：以?先入后出?为原则。 B：栈区最高地址单元的前一个单元为栈底。 C：运行中SP寄存器动态跟踪栈顶位置。 D：压栈和弹出都是以字节为单位。 11．表示过程定义结束的伪指令是（ A） A.ENDP B.ENDS C.END D.ENDM 12．BUF1 DB 3 DUP（0，2 DUP （1，2），3） COUNT EQU $－BUF1 符号COUNT等价的值是（ B） A.6 B.18 C.16 D.9 13．下列标志位中，可以用来判断计算结果正负的是（B） A：PF B：SF C：DF D：OF 14．下列指令正确的是（ CD） A. MOV [100H], [BX] B.MOV DS, ES C. ADD V[BX], CX D.MOV AX, 34H 15．下列哪个寄存器是属于指针寄存器（C） A：SI B：DX C：SP D：ES 二、填空题 (每小题4 分，共 20 分) 1．下列程序段求数组FLD的平均值，结果在AL中。请将程序填写完整（不考虑溢出） FLD DW 10, -20, 30, -60, -71, 80, 79, 56 _LEA SI,FLD______ MOV CX, 8 XOR AX, AX

编译原理考试

编译原理考试

————————————————————————————————作者：————————————————————————————————日期：

一、判断对错：（对√；错 ；每小问2分共24分） <1>算符优先分析法是一种规范归约分析法。（ ） <2>若文法Gs中不含形如T→…BD…的产生式，T、B、D∈V N，则称Gs为算符文法。（√） <3>若一个语言是有穷集合，则定义该语言的文法一定是递归的。（ ） <4>若两个正规式所表示的正规集相同，则认为二者是等价的。（√） <5>LR分析法是一种规范归约分析法。（√） <6>一个LR(0)项目集I={B →α.bβ, P →aA.},则说I中含有“移进—归约”冲突。（√） <7>SLR(1)文法是无二义性文法。（√） <8>消除左递归后的文法一定是LL(1)文法。（ ） <9>对任何编译程序而言，代码优化是必不可少的。（ ） <10>编译程序与具体的机器无关。（ ） <11>在自动机的概念中，终态与非终态是可区别的。（√） <12>逆波兰式ab+cd+*所代表的中缀表达式是：(a+b)*(c+d)（√） 1. 一个语言有文法是不惟一的。（√） 2. 若一个语言是无穷集合，则定义该语言的文法一定是递归的。（√） 3. 紧跟在条件转移语句后面的语句是基本块的入口语句。（√） 4. 算符优先分析法是一种规范归约分析法。（ ） 5. 自下而上语法自导翻译的特点：当栈顶形成句柄时，在归约的同时执行其语义动作。（√） 6. LR(0)文法、SLR(1)文法都是无二义性文法。（√） 7．K、∑分别表示有限状态集和有穷字母表, DFA M的转换函数f是一个从K ?∑到K的单值映射。（√） 8. 对任何编译程序而言，代码优化是必不可少的。（ ） 9. 直接短语是某规则的右部，它对应简单子树叶结点从左到右排列形成的符号串。（√） 10. 两个有穷自动机等价是指它们的状态数和有向弧数相等。（ ） 11. 一个LR(0)项目集为：I={A→α.bβ, D→β.},则说I中含有“移进--归约”冲突。 （√） 12. 若两个正规式所表示的正规集相同，则认为二者是等价的。（√） 13. 无左递归的文法是LL(1)文法。（ ） 14. 逆波兰式abcde/+*+所代表的中缀表达式是：a+b*(c+d/e)（√） 15. 编译程序结构中，中间代码优化及目标代码生成两个阶段与具体的机器有关。（ ） 16. LALR分析法中，同心集的合并不会产生“移进--归约”冲突。（√）

编译原理试题

中间语言与语法制导翻译重点与难点 重点：语法制导翻译的基本思想，属性文法，翻译模式，说明语句的翻译方案。 三地址码，各种语句的目标代码结构、属性文法与翻译模式。 难点：属性的意义，对综合属性，继承属性，固有属性的理解，属性计算，怎么通过属性来表达翻译。布尔 表达式的翻译，对各种语句的目标代码结构、属性文法与翻译模式的理解。 基本要求 掌握语法制导翻译的基本思想，属性文法，综合属性，继承属性，固有属性，属性计算，s_属性文法, L_属性文法，说明语句的翻译方案，翻译模式、属性文法的实现 掌握中间语言与语义分析的基本概念；熟练掌握语法(结构)树、三地址代码、赋值与控制语句的翻译、 说明语句的翻译；掌握组合数据说明的翻译、过程调用翻译。 例题解析 例1 给定文法E --> T { R.i := T.p } R { E.p := R.s } R --> addop T { R1.i := mknode( addop.val, R.i, T.p ) } R { R.s := R1.s } R --> : { R.s := R1.s } T --> ( E ) { T.p := E.p } T --> id { T.p := mkleaf( id, id.entry) } T --> num { T.p := mkleaf( n um, n um.val ) } (1) 指岀文法中的各非终结符具有哪些综合属性和哪些继承属性 ⑵ 画岀按本翻译模式处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树 【解】 (1)E的综合属性p，R的继承属性i，综合属性s ; T的综合属性p ⑵处理表达式a + 20 + ( b - 10 ) 时所生成的语法树如下 例2定义一个计算器的属性文法，完成一个输入表达式值的计算和显示 【解】计算器的文法 L T E E T E1 + T | T T T T1 * F | F F T ( E ) | digit

《编译原理》期末考试复习题

《编译原理》期末考试复习题 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） ×1．计算机高级语言翻译成低级语言只有解释一种方式。() ×2．在编译中进行语法检查的目的是为了发现程序中所有错误。() √3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 () ×4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、b∈VT 。 () √5．每个文法都能改写为 LL(1) 文法。 () √6．递归下降法允许任一非终极符是直接左递归的。 () ×7．算符优先关系表不一定存在对应的优先函数。 () ×8．自底而上语法分析方法的主要问题是候选式的选择。 () ×9．LR 法是自顶向下语法分析方法。 () ×10．简单优先文法允许任意两个产生式具有相同右部。 () 三、填空题(每空1分，共10分) 1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__ ___和 ___ _。 表格管理出错处理_ 2．若源程序是用高级语言编写的,__ __是机器语言程序或汇编程序,则其翻译程序称为 __ __ 。 _目标程序_编译程序 3．编译方式与解释方式的根本区别在于__ __。 是否生成目标代码_ 4．对编译程序而言,输入数据是__ __, 输出结果是__ ___。 _源程序目标程序

5．产生式是用于定义__ __的一种书写规则。 _语法成分 6．语法分析最常用的两类方法是___ __和__ __分析法。 自上而下_自下而上 四、简答题（20分） 1. 什么是句子？什么是语言 ? 答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。 (2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S x,x∈VT*} 。 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） ×1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。() ×2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。() √3．递归下降分析法是自顶向上分析方法。() ×4．产生式是用于定义词法成分的一种书写规则。() √5．LR 法是自顶向下语法分析方法。() √6．在SLR （1 ）分析法的名称中，S的含义是简单的。() ×7．综合属性是用于“ 自上而下” 传递信息。() ×8．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。() ×9．程序语言的语言处理程序是一种应用软件。() ×10．解释程序适用于COBOL 和FORTRAN 语言。() 三、填空题(每空1分，共10分) 1．一个句型中的最左简单短语称为该句型的___句柄__。

全国1月高等教育自学考试汇编语言程序设计试题历年试卷

做试题,没答案?上自考365,网校名师为你详细解答! 全国2005年1月高等教育自学考试 汇编语言程序设计试题 课程代码：02321 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填 在题干的括号内。每小题1分，共16分) 1.已知某操作数的物理地址是2117AH，则它的段地址和偏移地址可能是( )。 A.2025∶0F2A B.2108∶00EA C.2000∶017A D.2100∶117A 2.某程序装入内存后，DS=1200H，CS=1400H，则程序中数据段中的数据最多是( )字节。 A.2K B.4K C.8K D.16K 3.以寄存器DI间接寻址的存储器字节单元内容加1的指令是( )。 A.INC ［DI］ B.INC DI C.INC BYTE PTR［DI］ D.ADD ［DI］，1 4.有语句：COUNT EQU 256，下列四种叙述中，正确的是( )。 A.COUNT是变量 B.COUNT占用一个字节存储单元 C.COUNT是符号常数 D.COUNT占用二个字节存储单元 5.下面指令中，源操作数的寻址方式为立即寻址的是( )。 A.MOV AX，OFFSET A B.MOV AX，A C.MOV AX，A+1 D.MOV AX，A［BX］ 6.已知SP=2110H,执行POP AX后，SP寄存器的值是( )。 A.2111H B.2112H C.210FH D.210EH 7.将AX中有符号数除以2的正确指令是( )。 A.SHR AX，1 B.SAR AX，1 C.ROR AX，1 D.RCR AX，1 8.比较BX和SI中的两个存储器地址，若BX≥SI转向HIGH的正确指令是( )。 A.JAE HIGH B.JBE HIGH C.JEG HIGH D.JLE HIGH 9.指令SCASB操作数的段地址一定在( )寄存器中。 A.CS B.DS C.ES D.SS 10.有数据定义语句BUF DW 0ABH，1，10 DUP(3 DUP(1，0)，2)汇编后，为变量BUF分配 的存储单元字节数是( )。 A.48H B.90H C.120 D.60 11.下列指令执行后，不改变AL寄存器内容的指令是( )。 1

编译原理考试试卷

南京工业大学继续教育学院编译原理期末考试试卷 (2012-2013学年) A卷 一、选择题（每题2分，共20分） 得分 1. 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个_____，以及一组产生式。 A．字符串 B．运算符号 C．开始符号 D．文法 2.程序的基本块是指_____。 A．一个子程序 B．一个仅有一个入口和一个出口的语句 C．一个没有嵌套的程序段 D．一组顺序执行的程序段，仅有一个入口和一 个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于_____分析方法。 A．自左向右 B．自顶向下 C．自底向上 D．自右向左 4．经过编译所得到的目标程序是_____。 A．四元式序列 B．间接三元式序列 C．二元式序列 D．机器语言程序或汇编语言程序 5．运行阶段的存储组织与管理的目的是_____。 ①提高编译程序的运行速度②节省编译程序的存储空间 ③提高目标程序的运行速度④为运行阶段的存储分配做准备 A. ①② B. ②③ C. ③④ D. ④②6．词法分析器的输出结果是_____。 A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值 7．正规式M 1 和M 2 等价是指_____。

A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等 C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等 8．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 9．语言是_____。 A．句子的集合B．产生式的集合 C．符号串的集合D．句型的集合 10．编译程序前三个阶段完成的工作是 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析 C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化 二、名词解释（每题2分，共20分） 得分 1.最左推导： 2.语法： 3.文法： 4.基本块： 5.语法制导翻译： 6.短语： 7.规范句型：

编译原理复习要点

考试安排：7月13日（20周周三），15：00-17:00,20208 填空10X1分、选择10X2分、简答4X5分、大题5X10分 考试大题：循环优化 LL(1).定义之类的 算符优先算法 … 自下而上分析法（20分，选择、填空、大题） 第一章引论 一．编译程序(compiler): 把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序 二．编译程序的工作的五个阶段: 词法分析、语法分析、中间代码产生、优化、目标代码产生 1.词法分析 任务: 输入源程序， 符号。 依循的原则：构词规则 描述工具：有限自动机 保留字标识符等符整常数保留字整常数保留字 2.语法分析 任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。 依循的原则：语法规则 述工具：上下文无关文法 3.语义分析与中间代码产生 任务:对各类不同语法范畴按语言的语义进行初步翻译。（变量是否定义、类型是否正确等） 依循的原则：语义规则 中间代码:三元式，四元式，逆波兰记号，树形结构等。是一种独立于具体硬件的记号系统。 例：将Z:=X + 0.618 * Y 翻译成四元式为 (1) * 0.618 Y T1 (2) + X T1 T2 (3) := T2 _ Z 4. 优化 任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效 的目标代码。 依循的原则：程序的等价变换规则 FOR K:=1 TO 100 DO BEGIN M := I + 10 * K;

N := J + 10 * K; END 4.目标代码产生 任务: 把中间代码变换成特定机器上的目标代码。 依赖于硬件系统结构和机器指令的含义 目标代码三种形式: a)绝对指令代码: 可直接运行 b)可重新定位指令代码: 需要连接装配 c)汇编指令代码: 需要进行汇编 三. 编译程序结构 编译程序总框 (简答题5分) 第二章高级语言及其语法描述 2.1.1语法 词法规则：单词符号的形成规则。 a)单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基 本字、算符、界符等。 b)描述工具：正规式和有限自动机 语法规则：语法单位的形成规则。 a) 语法单位通常包括：表达式、语句、分程序、过程、函数、程序等; c)描述工具：上下文无关文法 2.1.2语义 语义：一组规则，用它可以定义一个程序的意义。 描述方法： a)自然语言描述：隐藏错误、二义性和不完整性 b)形式描述： ?无二义性 ?完整性