编译原理超强复习纲领

编译原理课程英文词汇

alphabet字母表symbol符号string串length长度catenation连接

power方暴gaiher集合product乘积empiysei空集closure闭包

program程序logicstructure逻辑结构generating产生executing执行

machinelanguage机器语言inslruction指令funclion函数assembler汇编程序

interpreter解释程序translator翻译程序sourcelanguage源语言finite有穷的

sourceprogram源程序targetlanguage目标语言atTibute属性possess占有

preprocess预处理compiler编译程序break中断Intennediatelanguage中间语言

definition定义reconstructed重构normal正规charactersequences符号序列

programminglanguage程序设计语言operand操作数instead替换memory内存

element元素high-levellanguage高级语言objectprogram目标程序

address地址input输入outpul输出lerminal终结符compilalion编辑

equivalence等价nonieminal非终结符recursion递归deterministic确定的

nondeteiministic非确定的Backus-NormalForm巴科斯范式syntax语法

tree树expression表达式grammar文法automata自动机prefix前缀

suffix后缀infix中缀identify识别identifier标:只符analyses分析

predigesl化简symbolset符号集performed执行forecast预测state状态

formula产生式conversion变换precedence优先simple简单handle句柄

operator算符terminalstate终态firststale初态optimizer优化程序

concatenation连接word单词alphabet字母表lexical词法scanner扫描器

analy,ci分析器syntaxUcc语法树synibollublc符号表pass趟，遍

regularexpression正规表达式codegenerator代码生成器backdate回溯

derivation推导educe推导derivationtree推导树path路径ambiguous二义性

simplephrase简单短语context-sensitive上下文有关contexl-free上下文无关

right-1incar右线形phrasc-structurcd短语结构regulargrammar文法

directderivation直接推导sentence句子sententialform句型rootnode根结点

subtree子树semantic语义的terminalnode端末结点attributegrammar属性文法

canonicalderivation规范推导top-down自上而下bottom-up自卜.而上

viableprefix活前缀nondeterniinatefiniteautomata非确定的有穷自动机

编译复习：一.专业术语英汉对译：复习老师给出的编译原理课程英文词汇

二、概念题（单项选择题、填空题、判断正误题、名词解释题、简答题）

1.翻译程序的种类有哪些？把汇编语言程序翻译成机器可执行的目标程序的工作是由什么来

完成的？

2.编译程序生成的结果是什么？目标程序；不一定是机器语言的程序。

3.高级语言的翻译处理只有编译一种方式？

4.在LR分析法中，分析栈中存放的状态是识别规范句型的什么状态？

5.词法分析器用于识别什么？语法分析器接收以什么为单位的输入？

6.在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是什么集合？

7.若一个文法是递归的，则它所产生的语言的句子有多少？

8.按逻辑上划分，一个编译程序的组成部分有哪些？它的工作过程由哪几部分来完成的？各部

分的任务是什么？

9.属性有哪些分类？它们如何传递信息？

10.乔姆斯基（Chomsky）把文法分为几种类型？各是什么名称？

11.无符号常数的识别和拼数工作通常是在什么阶段完成？

12.在语法分析方法中，自底向上的分析的关键是什么？自顶向下的分析的关键是什么？

13.一个上下文无关文法G的定义是什么？语义规则的定义是什么？语法分析的定义是什么？

四元式的定义是什么？语言的定义是什么？可归前缀的定义是什么？句型的定义是什么？句子

的定义是什么？后缀式的定义是什么？扫描遍的定义是什么？活前缀的定义是什么？句柄定义

14.源程序经翻译后能直接运行的目标程序是什么程序？

15.正则文法产生的语言是否都可以用上下文无关文法来描述？

16.编译程序在优化阶段是否要用到源程序中的注释？

17.用高级语言书写的源程序是否都必须通过编译产生.目标代码后才能投入运行？

18.解糕与编译方式的区别是否是解释方式对源程序没有真正进行翻译？

19.对任何NFAM,是否都存在一个正则表达式e或正则文法与之等价？对任何正则表达式e,

是否都存在一个NFAM,满足L(M)4(e)?对任何正则文法G,都存在一个NFAM,满足L(M)

=L(G)?

20.任何句型是否都存在一个规范推导，任何句子是否也都存在一个规范推导？

21.定义一个语言的文法是否是唯一的？

22.对任一编译程序来说，产生中间代码是不是必要的？

23.具有优化功能的编译程序的效率是否较高？

24.符号表由词法分析程序建立，是否只能由语法分析程序使用？

25.一个句型的句柄与文法某产生式的右部是什么关系？

26.数组元素的地址计算与数组的存储方式是否有关？

27.每个文法是否都能改写为LL(1)文法？

28.在中间代码优化中循环的优化包含哪些优化工作？

29.语义分析过程中的主要问题是否是候选式的选择？

30.在程序中出现的标识符仅为使用件由现的？

31.在编译中进行语法检查的目的仅是为了发现程序中各种错误？

32.递归下降法是否允许任一非终极符是直接左递归的？

33.自顶向下语法分析的思想是什么？自底向上语法分析的思想是什么？

34.代码生成是否与具体的机器硬件无关？

35.基本块的定义是什么？

36.何谓语法制导翻译？目标代码有哪几种形式？

37.什么是文法的二义性？证明给定文法G[N]的二义性。

38.DFA与NFA有何区别？

39.在规范归约中，用什么来刻画可归约事？

40.四元式之间的联系是通过什么实现的？

41.过程的DISPLAY表中记录J'过程的什么？

三.自动机转换题

给定一个NFAM：(此处自动机略)

1.把此自动机转换为等价的确定自动机DFAo

2.给出与此DEA等价的正则表达式。

四.给定中缀式，写出它们等价的后缀式和四元式。

五.给出一个三地址代码序列，请用DAG进行局部优化：

(此处三地址代码序列略)

1.画出DAG图；2.假设基本块出口时只有某些变量还被引汨，写出优化后的三地址代码序列。

六.给定文法G[S]：(此处文法略)

1.文法G属于chomsky哪〜型文法？

2.给定符号串，判定该符号串是不是该文法的一个句子，清证实。

3.若是句了，写出该句型的所有短语、简单短语，以及句柄。

4.构造识别该文法的活前缀的DFAo

5.判断该文法是LR(0)还是SLR(1),并构造其分析表？

6.对于给定的属性文法和输入符号串Q,该翻译方案的输出是什么？(需要给出解题过程)

一.名词解释：

1）前缀

答：前缀一一是指符号串任意首部。

2）可归前缀

答：可归前缀一一是指规范句型的一个前缀，这种前缀包含句柄且不含句柄之后的任何符号。

3）活前缀

答：活前缀一一规范句型的一个前缀，这种前缀不含句柄之后的任何符号。

或给定文法规范句型的可归前缀的任意首部。

4）简单短语

答：简单短语一一设G[Z]是给定文法,w=xuy£V'，为该文法的句型，如果满足下面两个条件：

①Z冬xUy；②Unu；

则称句型xuy中的子串u是句型xuy的简单短语。

5）扫描遍

答：扫描遍一一指编译程序对源程序或中间代码程序从头到尾扫描一次。

6）句柄

答：句柄一一给定句型中的最左简单短语就是句柄。

7）句型

答：句型一一设G是一个给定的文法，S是文法的开始符号，如果S耳x（其中xWV"）,则称x是

文法的一个句型。

8）句子

答：句子一一设C是一个给定的文法，S是文法的开始符号，如果S其中义£**）,则称义

是文法的一个句子。

9）非”结符

答：非终结符一出现在文法产生式的左部且能派生出符号或符号串的那些符号称为非终结符号。

10）终结符

答：终结符一一出现在文法产生式的右部且不能派生出符号或符号串的那些符号称为终结符号。

11）属性文法

答：一个属性文法形式的定义为一个三元组AG,AG=（G,V,E）o

其中G为一个上下文无关文法；V为属性的有穷集；E为一组语义规则。

12）语法制导翻译

答：语法制导翻译一一语法制导翻译就是在语法分析的过程中，当进行推导或归约时同步完成

附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。

13）后缀式

答：后缀式------种把运算量（操作数）写在前面，把算符写在后面（后缀）的表示法。

14）短语

答：短语一一设G[Z]是给定文法,w=xuy£『，为该文法的句型，如果满足下面两个条件：

①Z±xlly：②U当u：

则称句型xuy中的子串u是句型xuy的短语。

或：句型语法树的全部子树的叶从左到右排列起来构成的符号串均是句型的短语。

15）基本块

答：基本块一一源程序或者中间代码程序中只有一个入口和一个出口的顺序执行的代码段。

16）语义规则

答：对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。

17）语法分析

答：语法分析一一按文法的产生式识别输入的符号串是否为一个句子的分析过程。

18）四元式

答：四元式——是一个带有四个域的记录结构，这四个域分别称为操作符域、左运算对象域、

解答:是由文法的开始符号推出的所有终结符串的集合。或说是句子的集合。

18）乔姆斯基把文法分为四种类型，即0型、1型、2型、3型,其中2型文法叫什么？

解答：2型文法叫上下文无关文法。

19）编译程序是一种解释程序吗？还是什么程序？

解答:编译程序是一种翻译程序。

20）按逻辑上划分，编译程序第二步工作是什么？

解答：编译程序第二步工作是语法分析。

21）源程序是用高级语言编写的，目标程序是机器语言程序或汇编语言程序，则其翻译程序称

为什么？

解答：其翻译程序称为编译程序。

22）编译方式与解释方式的根本区别为什么？

解答:编译方式与解释方式的根本区别在乎是否生成目标代码。

23）常见的动态存贮分配策略有哪两种？

解答:常见的两种动态存贮分配策略是栈式动态分配策略和堆式动态分配策略。

24）常用的参数传递方式有哪三种？

解答:常见的参数传递方式有传地址、传值和传名三种方式。

25）语法分析的任务是什么？

解答:语法分析的任务是识别给定的终结符串是否为给定文法的句了二

26）局部优化是局限于一个什么范围内的一种优化？

解答：是局限于一个基本块范围内的一种优化。

27）文法等价的定义是什么？

解答：设G1和G2是给定的文法，如果有L（Gl）=L（G2）,则称G1与G2等价。

28）在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是什么集合？

解答：均是终结符集。

29）通常一个编译程序中应包括哪七个部分？

解答：通常一个编译程序中应包含词法分析，语法分析，语义分析与中间代码生成，代码优化,

目标代码生成以及表格处理和出错处理等七个部分。

32）如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分为哪三个阶段？

解答：源程序的执行分为三个阶段：编译阶段，汇编阶段和运行阶段。

33）翻译程序是这样•种程序，它能够将用什么转换成与其等价的用乙语言书写的程序？

解答:能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程序。

34）说明下面文法G［法是二义性文法:S-*SaS|SbS|cSd|eS|f

解答:fafbf是文法G［S］的一个句子，并且有两个不同的最右推导。

（1）S=>SaS=>SaSbS=>SaSbf=>Safbf=>fafbf

（2）S=>SbS=>Sbf=>SaSbf=>Safbf=>fafbf

因此说明此文法有二义性。

35）在属性文法中，综合属性与继承属性是如何传递信息的？

解答：综合属性用于自下而上传递信息，继承属性用于自上而下传递信息。

36）代码优化的主要目标是什么？

解答：代码优化的主要目标是如何提高目标程序的运行速度和如何减少目标程序运行时所需的

空间。

37）写一个文法，使其语言是无符号二进制实数（不含指数

解答:文法G（N）：

N-L.LlL

L-LB|B

B-*0|l

三.应用题

1)消除下列文法G[A]的左递归。

E-*E-T|T

T-T/FIF

1(E)|i

解答：消除文法G[E]的左递归后得到:

E-TE'

E'-TE'|£

T—FT

「一/FT'|e

F-*(E)|i

2)消除下列文法G[A]的左递归。

A-*AaB|B

B-*BbCIC

C~eD|D

Df(A)|d

解答：消除文法G[A]的左递归后得到:

A-*BA，

A'-*aBA'|E

BTB，

B'fbcB'I£

CfeDID

D-*(A)|d

3)给定下列自动机：

其中：开始状态：0

终止状态：2

把此自动机转换％确定自动机DFAo

解答：有状态矩阵如图：

2

2

2

从而可得DFA如图:

极小化后

4）正规式（a|b）-a（a|b）构造一个等价的有限自动机。

解答：

四设计题

~席宿羽常

~

~

~

r—

r

f

s

2

D

b

T

i

r

l

in

r

pr

nt

e

{

DD

3

T

i

in

pr

nt

r

d

in

f

pr

nt

i

D

4

T

I

l

法？

型文

哪一

G属于

文法

类法，

sky分

chom

a.按

实。

请证

型，

个句

的一

文法

是该

i是不

ri,i,

号串

b.符

柄。

以及句

语，

单短

、简

短语

所有

型的

该句

写出

型，

是句

c.若

Ao

的DF

前缀

的活

文法

别该

造识

d.构

表。

分析

语法

应的

其相

构造

1),并

R(

是SL

0)还

R(

法是L

断该文

e.判

么？

是什

输出

后的

翻译

方案

翻译

经该

串，

符号

输入

这个

i,i

于ri,

f.对

解答：

法。

关)文

文无

(上下

于2型

法G属

a.文

。

句型

一个

法的

该文

i,i是

ri,

号串

b.符

r

。

得证

i,i,

i,

=r

,i

rD,i

i=

D,

D=>r