完整word版编译原理复习题word文档良心出品.docx

完整word版编译原理复习题word文档良心出品.docx

《完整word版编译原理复习题word文档良心出品.docx》由会员分享，可在线阅读，更多相关《完整word版编译原理复习题word文档良心出品.docx（24页珍藏版）》请在冰点文库上搜索。

完整word版编译原理复习题word文档良心出品

编译原理复习

一、简述题

1、简述编译程序的工作过程

编译程序的工作，即从输入源程序开始到输出目标程序为止的整个过程是非常复杂的。

通常，编译程序的工作过程可以划分为5个阶段：

第1阶段，词法分析。

词法分析的任务是输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如保留字（基本字）、标识符、算符、界符等。

依循的原则：

构词规则

描述工具：

有限自动机

第2阶段，语法分析。

语法分析的任务是在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴），如语句、程序块、函数等，判断整个输入串是否是一个语法上正确的“程序”。

依循的原则：

语法规则

描述工具：

上下文无关文法

第3阶段，语义分析与中间代码产生。

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

通常的中间代码有三元式、四元式、间接三元式、逆波兰式等。

依循的原则：

语义规则

第4阶段，优化。

优化的任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生更为高效（省时间和空间）的目标代码。

优化的主要方法有公共子表达式的提取、循环优化等。

依循的原则：

程序的等价变换规则

第5阶段，目标代码生成。

这一阶段的任务是把中间代码（或经优化处理之后的中间代码）变换成特定机器上的低级语言代码。

目标代码三种形式:

绝对指令代码:

可直接运行

可重新定位指令代码:

需要连接装配

汇编指令代码:

需要进行汇编

2、编译程序在分析语言程序的过程中将源语言程序的各种信息都保留在各种表格中，同时，在源语言程序出错时，编译程序要帮助进行错误判断、错误定位等，因此表格管理及出错处理和编译程序的各个阶段都有关联。

编译程序的结构图如图所示。

其中词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。

语法分析器，简称分析器，对单词符号串进行语法分析，识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。

语义分析器与中间代码产生器，按照语义规则对语法分析器规约出的语法单位进行语义分析并把它们翻译成一定形式的中间代码。

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

目标代码生成器，把中间代码翻译成目标程序。

3、程序语言的定义

一个程序语言是一个记号系统。

如同自然语言一样，程序语言主要是由语法和语义两方面定义的。

有时，语言定义也包含语用信息，语用主要是有关程序设计技术和语言成分的使用方法，它使语言的基本概念与语言的外界（如数学概念或计算机的对象和操作）联系起来。

任何语言程序都可以看做是一定字符集（称为字母表）上的一个字符串。

合乎语法的字符串才算是一个合法的程序。

语言的语法是用来形成一个合法程序的一组规则。

这些规则的一部分称为词法规则，另一部分称为语法规则（或产生规则）。

语言的词法规则是指单词符号的形成规则。

语法规则则规定了如何从单词符号形成更大的结构（即语法单位），因此语法规则也可以说是语法单位的形成规则。

词法规则和语法规则定义了程序语言的形成规则，而程序的意义则用语言的语义规则来定义。

语义规则规定了语言的单词符号和语法单位的意义，是定义一个程序意义的一组规则。

4、上下文无关文法

文法是描述语言的语法结构的形式规则即语法规则。

这些规则必须是准确的，易于理解的，而且，应当有相当强的描述能力，足以描述各种不同的结构。

所谓上下文无关文法是这样的一种文法，它所定义的语法范畴是完全独立于这种范畴可能出现的环境。

这里有许多重要的概念需要深入理解。

（1）上下文无关文法严格的定义

形式上说，一个上下文无关文法G是一个四元式（VT，VN，S，P），其中

VT是一个非空有限集，它的每个元素称为终结符号；

VN是一个非空有限集，它的每个元素称为非终结符号，且VTVN=

S是一个非终结符号，称为开始符号，SVN

P是一个产生式集合（有限），每个产生式形式为P，其中PVN，（VTVN）*

开始符S至少必须在某个产生式的左部出现一次。

（2）关于文法应用的若干基本概念

严格地说，我们称A直接推出，即

A

仅当A是一个产生式，且、（VTVN）*。

如果12n，则我们称这个序列是从1到n的一个推导。

若存在一个从1到n的推导，则称1可以推导出n。

我们用1n表示从1出发，经一步或若干步，可推导出n.1n表示从1出发，经0步或若干步，可推导出n.。

换言之，意味着，或者=或者。

对文法G（E）：

Ei|E+E|E*E|（E）

E（E）（E+E）（i+E）（i+i）

假定G是一个文法，S是它的开始符号。

如果S，则称是一个句型。

仅含终结符号的句型是一个句子。

文法G所产生的句子的全体是一个语言，将它记为L（G）。

L（G）={|S&VT*}

从一个句型到另一个句型的推导往往不唯一。

E+Ei+Ei+iE+EE+ii+i

最左推导：

任何一步都是对中的最左非终结符进行替换。

最右推导：

任何一步都是对中的最右非终结符进行替换。

（3）语法分析树与二义性的概念

我们可以用一张图表示一个句型的推导,这种表示称为语法树。

对于文法

G（E）：

Ei|E+E|E*E|（E）

（i*i+i）的语法树如下图所示

E（E）

（E+E）

（E*E+E）

（i*E+E）

（i*i+E）

（i*i+i）

一棵语法树是一些不同推导过程的共性抽象。

如果使用最左（右）推导，则一个最左（右）推导与语法树一一对应。

在文法中一个句型不一定只对应唯一一棵语法树。

如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。

例如上面的文法G（E）：

Ei|E+E|E*E|（E）是二义文法。

需要特别指出的是，文法的二义性和语言的二义性是两个不同的概念。

一个语言是二义性的，如果这个语言不存在无二义性的文法。

可见，语言的二义性是一个更强的概念。

对于某个语言L来说，可能存在两个文法G和G’，其中一个为二义的，另一个为无二义的。

但L（G）=L（G’）=L，这时，语言L不是二义性的。

可以证明二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。

但是我们可以找到一组无二义文法的充分条件。

二义文法：

G（E）：

Ei|E+E|E*E|（E）

无二义文法：

G（E）：

ET|E+T

TF|T*F

F（E）|i

5、词法分析的任务

编译原理是在单词的级别上对源程序进行分析和翻译的，而从源程序中获取单词的工作是由词法分析程序来完成的。

词法分析的任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。

。

因此，词法分析是编译的基础。

执行词法分析的程序称为词法分析器，也叫扫描器。

词法分析的功能是输入源程序，输出单词符号。

单词符号是一个程序语言的基本语法符号。

一般有5类：

（1）关键字，是程序语言定义的具有固定意义的标识符，也叫保留字或基本字，如begin，repeat，while等；

（2）标识符，用来表示各种名字，如变量名、数组名和过程名；（3）常数，常数的类型有整型、实型、布尔型、字符型等；（4）运算符，如+，-，*，/等；（5）界符，如逗号、分号、括号、/*,/*等。

词法分析程序的输出格式一般为：

词法分析程序不仅给出单词符号的值，还同时给出单词符号的类别，这有利于编译程序的后继工作——词法分析的进行。

6、语法分析

语法分析是翻译过程的核心部分。

它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。

语法分析器的工作本质上就是按文法的产生式，识别输入串是否为一个句子。

按照语法分析树的构建立方法，我们可以粗略的把语法分析办法分成两类：

一类是自上而下分析法，另一类是自下而上分析法。

7、什么是语法制导翻译法

从概念上将，基于属性文法的处理过程是这样的：

对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算（如图所示）

这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法。

8、静态语义检查

静态语义检查通常包括：

（1）类型检查。

如果操作符作用于不相容的操作数，编译程序必须报告出错信息。

（2）控制流检查。

控制流语句必须使控制转移到合法的地方。

（3）一致性检查。

在很多场合要求对象只能被定义一次。

（4）相关名字检查。

有时，同一名字必须出现两次或多次。

9、存储分配和实现

FORTRAN：

静态存储分配和实现

C：

栈式存储分配和实现

Pascal：

堆式动态存储分配

10、优化

对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码，我们通常称这种变换为优化。

二、应用题

1、写一文法，使其语言是偶正整数的集合,要求：

（1）允许0打头；

（2）不允许0打头。

解：

（1）G（S）=（{S,P,D,N},{0,1,2,…,9},P,S）

P:

S->PD|D

P->NP|N

D->0|2|4|6|8

N->0|1|2|3|4|5|6|7|8|9

（2）G（S）=（{S,P,R,D,N,Q},{0,1,2,…,9},P,S）

P:

S->PD|P0|D

P->NR|N

R->QR|Q

D->2|4|6|8

N->1|2|3|4|5|6|7|8|9

Q->0|1|2|3|4|5|6|7|8|9

2、写一个上下文无关文法，使其语言是能被5整除且不以0开头的无符号整数的集合。

（如{5，10，15，....}）

解：

能被5整除的数从形式上看，是以0,5结尾的数字串。

题目要求的不以0开头，并要注意0不是该语言的句子。

所求文法为：

G（S）:

S→MF|5

F→5|0

N→1|2|3|4|5|6|7|8|9

D→N|0

M→MD|N

其中，S代表能被5整除且不以0开头的无符号整数；F代表可以出现在个位上的数字；D代表所有数字；N代表所有非零数字；M代表所有不已零开头的数字串。

3、

（1）写一个文法使其语言为L（G）={anbm|2n>m≥n≥1}。

（2）写一个文法使其语言为L（G）={a2nbn|n≥1,ab,∈VT}。

解：

（1）所求文法为G（S）

S→aSb|aSbb|ab

（2）所求文法为G（S）

S→aaSb

S→aab|

4、在一个2型文法G（{S,A,B},{a,b},P,S）

P:

S→aB|bA

A→a|aS|baa

B→b|bS|aBB

用最左推导产生句子aabbab。

解：

S→aB→aaBB→aabSB→aabbAB→aabbaB→aabbab

5、已知正规文法G1的产生式，求出它所定义的正规式。

产生式为：

S→aS|aB

B→bB|bA

A→cA|c

解：

（1）S=aS|aB

B=bB|bA

A=cA|c

（2）根据定理2由S=aS|aB得S=a*aB=a+B

同理由B=bB|bA得B=b+A

由A=cA|c得A=c+

代入得B=b+c+,S=a+b+c+。

故正规式为S=a+b+c+。

6、求表达式文法的语法符号的FIRST集和FOLLOW集

表达式文法:

E→TE'

E'→+TE’|ε

T→FT'

T'→*FT’|ε

F→（E）|id

解：

FIRST（F）={（,id}

FIRST（T）=FIRST（F）={（,id}

FIRST（E）=FIRST（T）={（,id}

FIRST（E'）={+，ε}

FIRST（T'）={*,ε}

FIRST（+）={+},FIRST（*）={*}

FIRST（（）={（}

FIRST（））={）}

FIRST（id）={id}

FOLLOW（E）={#,）}

FOLLOW（E'）=FOLLOW（E）={#,）}

FOLLOW（T）=FIRST（E’）∪FOLLOW（E）∪FOLLOW（E’）={+,）,#}

FOLLOW（T'）=FOLLOW（T）={+,},#}

FOLLOW（F）=FIRST（T’）∪FOLLOW（T）∪FOLLOW（T’）={*,+,},#}

7、对如下文法G1，求各个非终结符号的终结符号集。

（1）E→TE’

（2）E’→+TE’（3）E’→ε（4）T→FT’

（5）T’→*FT’（6）T’→ε（7）F→I（8）F→（E）

解：

FIRST（E）=FIRST（T）=FIRST（F）={I,（}

FIRST（E’）={+,ε}

FIRST（T’）={*,ε}

编译原理样卷

考试题型：

简答（4道）、计算（4道）、综合（3道）

一、简答题：

1、什么是编译程序？

其分为几个阶段？

编译程序：

也称为编译器，能够直接将高级语言程序翻译为对应的低级语言程序。

编译程序通常分为：

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

2、文法的形式定义是什么？

文法的形式定义为G=（

，

，P，S），其中

为非终结符集，

是终结符集，P是产生式集合，S是开始符号

3、什么是上下文无关文法？

若在文法的定义中限定文法的产生式左部只有一个非终结符，则该文法称为上下文无关文法。

4、什么是文法的语言？

从文法G的开始符号S出发，所能推导出的句子的全体称为文法G产生的语言。

5、文法的分类？

乔姆斯基把文法分为0型文法（短语文法）、1型文法（上下文有关文法）、2型文法（上下文无关文法）、3型文法（正规文法）四类。

这几类的差别在于对产生式施加不同的限制。

6、词法分析的功能？

1）按规则识别单词，输出单词本身及其类别码；（主要任务）

2）滤掉程序中的无用成分；

3）调用出错处理程序，识别并定位错误；

4）调用符号管理程序，将识别出来的单词及其属性进行管理。

7、什么是符号表？

有何作用？

符号表：

是一种用于保存源程序中出现的标识符和常数的各种信息的数据结构。

作用：

编译器在分析阶段收集信息放入符号表中，在综合阶段生成目标代码时使用符号表中的信息。

8、什么是正规文法？

若文法G=（

，

，P，S）中的每个产生式P的形式都是A→aB或A→a，其中A、B∈

，a∈

，则G是正规文法。

9、语义分析的主要任务？

1）对语法分析所识别出的各类语法短语进行静态语义审查；

2）若无语义错误，再根据识别出的语法单位的类型进行处理，若是说明语句，则将变量的类型等属性填入符号表，若是可执行语句，则进行初步的翻译，将其翻译为中间代码。

10、什么是属性文法？

属性文法：

包含一个上下文无关文法和一系列的语义规则，为每个文法符号配备若干相关的“值”（属性）。

11、什么是语法制导翻译？

若遍历语法树的操作和建立语法树的操作同时进行，称为语法制导翻译。

12、什么是代码优化？

代码优化：

指的是为了提高目标程序的质量而对源程序或中间代码进行的各种合理的等价变换，使得变换后的程序能生成更有效的目标代码。

13、代码优化要遵循哪些原则？

遵循如下原则：

等价原则、有效原则、合算原则。

14、局部优化常用哪些技术？

包括：

删除公共子表达式、删除无用赋值、合并已知量、对临时变量改名、对语句变换位置、代数变换等。

15、循环优化常用哪些技术？

包括：

代码外提、强度削弱、删除归纳变量等。

*16、什么是短语文法？

若对文法中的产生式α→β的要求是：

α至少含有一个非终结符，则称该文法为短语文法。

二、计算题：

1、已知表达式的文法G为：

<表达式>→<项>|<表达式>+<项>

<项>→<因子>|<项>*<因子>

<因子>→（<表达式>）|i

给出i+i+i和i+i*i的最左推导、最右推导和语法树。

解答：

用E表示<表达式>，T表示<项>，F表示<因子>，上述文法可以写为：

E→T|E+T

T→F|T*F

F→（E）|i

最左推导：

E=>E+T=>E+T+T=>T+T+T=>F+T+T=>i+T+T=>i+F+T=>i+i+T

=>i+i+F=>i+i+i

E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i

最右推导：

E=>E+T=>E+F=>E+i=>E+T+i=>E+F+i=>E+i+i=>T+i+i

=>F+i+i=>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

i+i+i和i+i*i的语法树如下图所示。

i+i+i、i+i*i的语法树

2、考虑文法G[S]：

S→aSbS|bSaS|ε

（1）试用最左推导说明此文法的二义性。

（2）对于句子abab构造两个相应的最右推导。

（3）对于句子abab构造两棵相应的分析树。

（4）此文法所产生的语言是什么？

解答：

（1）句子abab有如下两个不同的最左推导：

S=>aSbS=>abS=>abaSbS=>ababS=>abab

  S=>aSbS=>abSaSbS=>abaSbS=>ababS=>abab

  所以此文法是二义性的。

（2）句子abab的两个相应的最右推导：

  S=>aSbS=>aSbaSbS=>aSbaSb=>aSbab=>abab

  S=>aSbS=>aSb=>abSaSb=>abSab=>abab

（3）句子abab的两棵分析树：

（a）

（b）

（4）此文法产生的语言是：

在{a，b}上由相同个数的a和b组成的字符串。

3、试构造生成下列语言的上下文无关文法：

（1）

={

|n≥1,i≥0}。

（2）语言

={x|x∈{a,b,c}

x是重复对称排列的（aabcbaa，aabbaa等）}

解答：

（1）把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：

S→AB

A→aAb|ab

B→cB|

（2）G[S]：

S→aSa|bSb|cSc|a|b|c|

4、已知文法G[E]：

E→T|E+T

T→F|T*F

F→（E）|i

（1）给出句型（T*F+i）的最右推导，并画出语法树；

（2）给出句型（T*F+i）的短语、素短语和最左素短语；

（3）证明E+T*F是文法的一个句型，指出这个句型的所有短语、直接短语和句柄。

解答：

①最右推导：

E=>T=>F=>（E）=>（E＋T）=>（E＋F）=>（E＋i）=>（T＋i）=>（T*F＋i）

语法树：

句型（T*F＋i）的语法树

②短语：

（T*F＋i），T*F＋i，T*F，i　　

　　　　素短语：

T*F，i最左素短语：

T*F

③由于E=>E+T=>E+T*F，故E+T*F为该文法的句型

短语：

T*F、E+T*F

直接短语：

T*F句柄：

T*F

5、给定文法G[S]，其产生式如下：

S→（T）|a

T→T,S|S

（1）给出输入串（a,（a,a））的最左和最右推导过程；

（2）计算该文法各非终结符的FirstVT集和LastVT集。

解答：

最左推导：

S=>（T）=>（T,S）=>（S,S）=>（a,S）=>（a,（T））=>（a,（T,S））

=>（a,（S,S））=>（a,（a,S））=>（a,（a,a））

最右推导：

S=>（T）=>（T,S）=>（T,（T））=>（T,（T,S））=>（T,（T,a））

=>（T,（T,a））=>（T,（a,a））=>（S,（a,a））=>（a,（a,a））

文法中S和T的FirstVT和LastVT集为：

FirstVT（S）={a,（}FirstVT（T）={,,a,（}

lastVT（S）={a,）}lastVT（T）={,,a,）}

6、将下面的语句翻译为四元式序列：

（1）if（A

ifA=1thenc :

=c+1

elseifA<=DthenA :

=A+2；

（4）fori :

=b*2to100do

x :

=（a+b）*（c+d）-（a+b+c）；

解答：

（1）四元式序列为：

1．（j<,A,C,3）

8.（:

=,T,-,C）

2.（j,-,-,14）

9.（j,-,-,14）

3.（j<,B,D,5）

11.（j,-,-,14）

4.（j,-,-,14）

12.（+,A,2,T2）

5.（j=,A,1,7）

13.（:

=,T2,-,A）

6.（j,-,-,10）

14.

7.（+,c,1,T1）

（4）四元式序列为：

0.（*,b,2,t0）

1.（:

=,t0,,i）

2.（:

=,100,,t1）

3.（j,,,6）

4.（+,i,1,t2）

5.（:

=,t2,,i）

6.（j>,i,t1,15）

7.（+,a,b,t3）

8.（+,c,d,t4）

9.（*,t3,t4,t5）

10.（+,a,b,t6）

11.（+,t6c,t7）

12.（-,t5,t7,t8）

13.（:

=,t8,,x）

14.（j,,,4）

15.

三、综合题：

1、已知文法G[S]，其产生式如下：

S→（L）|a

L→L,S|S

从G[S]中消除左递归，并为之构造一个非递归预测分析器LL

（1）分析表，并说明对输入符号串（a,（a,a））的分析过程。

解答：

消除所给文法的左递归，得G'：

        S→（L）|a

        L→SL'

        L'→,SL'|

实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：

根据文法G'有：

First（S）={（,a）Follow（S）={）,,,#}

First（L）={（,a）Follow（L）={）}

First（L'）={,}Follow（L'）={）}

按以上结果，构造预测分析表M如下：

文法G'是LL

（1）的，因为它的LL

（1）分析表不含多重定义入口。

预测分析器对输入符号串（a,（a,a））做出的分析动作如下：

步骤

栈

剩余输入串

输出

1

#S

（a,（a,a））#

#

2

#）L（

a,（a,a））#

S→（L）

3

#）L

a,（a,a））#

4

#）L'S

a,（a,a））#

L→SL'

5

#）L'a

a,（a,