大学编译原理课程复习试题及答案

编译原理复习材料

选择题

1. 文法S→0S | S1 | 0的语言是( )。

A. { 0 m1m| m >=0 }

B. { 0 m1m| m >=1 }

C. { 0 m1n | m>=1,n>=0 }

D. { 0 m1n | m>=0,n>=1 }

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. 优先函数的优点是( )。

A.形象直观

B.便于进行比较运算

C.语法分析速度快

D.语法分析方法简单

8. 文法符号的属性通常分为( )两类。

A. 共用属性和私有属性

B.固有属性和可变属性

C.语法属性和语义属性

D.综合属性和继承属性

9. 在程序流图中，组成循环的结点序列应满足( )

A. 它们是强连通的

B.它们中间有唯一的入口结点

C.它们中间有一条回边

D.它们是强连通的且有唯一的入

口结点

10. 在利用寄存器R生成T1:=C/B的目标代码同时,还应记录信息( )。

A. C/B在T1中

B. T1在C/B中

C. R含有T1, T1在R中

D. R含有C/B, C/B在R中

1.D

2.B

3.C

4.B

5.B

6.A

7.B

8.D

9.D 10.C

1. 编译方式与解释方式的根本区别在于( )

A.是否生成目标代码

B.是否生成中间代码

C.是否生成汇编代码

D.是否生成优化代码

2. 编译程序生成的目标程序( )

A.一定是机器语言的程序

B.不一定是机器语言的程序

C.一定不是机器语言的程序

D.一定是汇编语言的程序

3. 设字母表∑={0,1,x,y}, 则∑上的正规式ε所对应的正规集为( )

A.ε

B. {ε0,1,x,y }

C. {ε}

D.Φ

4. *

假设G是一个文法，S是文法的开始符号，如果S===> x,则称x是( )

A.短语

B.句柄

C.句子

D.句型

5. 一个算符文法的任何产生式的右部都不含有两个相继的( )

A.终结符

B.非终结符

C.终结符和非终结符

D.ε字

6. 设有文法G[A]：A →Ax|Ay|Aa|Ac|a|b|c，

下列哪些是该文法的句子( )

(1) aby (2) aycyx (3) aaa (4) bcxy

A.(1) (2) (3)

B. (1) (2) (4)

C.(2) (3) (4)

D.全部

7. ＬＲ分析器的核心部分是( )

A.带先进后出存贮器的DFA

B.一张动作表

C.一张GOTO表

D.一张分析表

8. 在程序流图中，组成循环的结点序列应满足( )

A.它们是强连通的且有唯一的入

B.它们中间有唯一的入口结点

口结点

C.它们中间有一条回边

D.它们是强连通的

9. 表达式a≤b＋c∧a＞d∨a＋b≠e的后缀式式为( )。

A.abc≤ad＋＞∧ab＋e≠∨

B.ab≤c＋∧da＞ab＋e≠∨

C.abc＋≤ad＞∧ab＋e≠∨

D.abc＋≤ad＞ab＋∧e≠∨

10. 程序基本块是指 ( )

A.一个子程序

B.一个仅有一个入口和一个出口的语句

C. 一个没有嵌套的程序段

D.一组顺序执行的程序段，仅有一个入口和一个出口

1.A

2.B

3.C

4.D

5.B

6.C

7.D

8.A

9.C 10.D

1. BNF是一种用于( )的工具。

A. 描述句型

B.描述句子

C.描述语言

D.描述文法

2. 设字母表∑={0,1,x,y}, 则∑上的正规式ε所对应的正规集为( )

A.ε

B. {ε}

C. {ε0,1,x,y }

D.Φ

3. 规范推导也称为( )

A. 最右推导

B.最左推导

C.一般推导

D.自左向右推导

4. 在规范归约中, 任何可归约串的出现必在( )

A.栈的内部

B.栈顶

C.剩余的输入串中

D.在先进后出栈中

5. 一个算符文法的任何产生式的右部都不含有两个相继的( )

A.终结符

B.非终结符

C.终结符和非终结符

D.ε字

6. ＬＲ分析器的核心部分是( )

A.一张分析表

B.一张动作表

C.一张GOTO表

D.带先进后出存贮器的DFA

7. 算符优先分析的关键问题是寻找( )。

A.句柄

B.最左素短语

C.短语

D.直接短语

8. 四元式之间的联系是通过( )

A.指示器

B.临时变量

C.四元式的编号

D.中间运算结果

9. 表达式a≤b＋c∧a＞d∨a＋b≠e的逆波兰式为( )。

A.abc＋≤ad＞∧ab＋e≠∨

B.ab≤c＋∧da＞ab＋e≠∨

C.abc≤ad＋＞∧ab＋e≠∨

D.abc＋≤ad＞ab＋∧e≠∨

10. 代码外提时要求该不变运算所在的结点是循环的( )。

A.某个出口的必经结点

B.至少是一个入口的必经结点

C.入口的必经结点

D.所有出口的必经结点

1.D

2.B

3.A

4.B

5.B

6.A

7.B

8.B

9.A 10.D

填空题

1. 一个状态转换图可用于一定的字符串。

2. 设∑＝｛a , b , c｝，则∑*中最短的符号串为。

3. 若由文法的开始符号可以推导出串α ，且，则α为原文法的一个句子。

4. 若文法的某非终结符P满足，称文法含有左递归。

5. 表达式-(a+b)/(c*d)-e的逆波兰式为

______________________________。

6. 后序遍历一棵表达式树，可得到它的。

7. 中间代码是一种面向语法，易于翻译成的代码。

8. 四元式序列中各四元式出现的顺序与是一致的。

9. 若每个程序对应一个流图，则流图中的结点对应一个。

10.

若从流图首结点出发, 到达n j的任一通路必须经过n i，则

称的必经结点。

1. 识别或接受

2. ε

3. α ? VT*

4. Ｐ==＋＞Ｐα

5. ab+@cd*/e-

6. 逆波兰式

7. 目标代码

8. 运算顺序

9. 基本块

10. ni为nj

1. 一个非确定的有限自动机可以表示为一个元式。

2. 若文法的某非终结符P满足，称文法含有左递归。

3. 设∑＝｛1 , 2, 3｝，则∑*中最短的符号串为。

4. 用∑+表示∑上所有的集合。

5. 三地址代码的一般形式为。

6. 递归下降法对每个构造一个相应的子程序。

7. 在算符优先分析中，用作为可归约串。

8. 在形式语言中，最推导被称为规范推导。

9. 语法树中，一个结点的属性由此结点的父结点和/或兄弟结点的属性确

定。

10. 如果循环中对变量I只有唯一的形如I=I±C的赋值，则称I为循环中

的变量。

1.

2. 五

Ｐ==＋＞Ｐα

3. ε

4. 长度不为0的串

5. x:=y op z

6. 非终结符

7. 最左素短语

8. 右

9. 继承

10. 基本归纳

1. 终态与非终态的区别在于。

2. 用∑+表示∑上所有的集合。

3. 一个状态转换图可用于一定的字符串。

4. 用于词法分析的扫描缓冲区可将两个半区使用。

5. 一个句型的称为该句型的句柄。

6. 递归下降法对每个构造一个相应的子程序。

7. 算符优先法尤其适用于的分析。

8. 规范归约的关键在于如何确定。

9. 文法符号的属性值可自底向上应用语义规则计算出来。

10. DAG代表。

1. 终态可接受空串

2. 长度不为0的串

3. 识别

4. 互补

5. 最左简单短语

6. 非终结符

7. 表达式

8. 句柄

9. 综合

10. 有向无环图

判断题

1. 若一个文法是递归的，则由它产生的语言的句子个数是有

（）限的。

2. 用于词法分析的扫描缓冲区可将两个半区重叠使用。（）

3. 一个LR分析器实质上是一个带有后进先出存储器的

（）DFA。

4. 符号表的每一项一般包含入口栏和信息栏两大部分。（）

5. DAG是对循环进行优化的有效工具。（）

（）

6. 代码外提时要求该不变运算所在的结点是循环的某个出口

的必经结点。

1. ×无限

2. ×互补

3. √

4. ×名字

5. ×基本块

6. ×所有

1. 描述程序语言所采用的Ⅲ型文法是上下文无关文法。（）

2. 状态转换图实现的简单方法是使每个状态结点对应一个非

（）终结符

3. 欲构造行之有效的自下而上分析器，则必须清除文法中含（）

有的左递归。

4. 在规范归约中, 任何可归约串的出现必在栈的内部。（）

（）

5. 循环优化中的强度削弱主要是指将循环中的乘法变成加

法。

6. 符号表的信息栏中的内容称为关键字。（）

1. ×正规文法

2. ×一段小程序

3. ×自上而下

4. ×栈顶

5. ×递归加法

6. ×名字

（）

1. 设α是某句型的一个子串，若它能被一次直接归约为一个

非终结符，则α是该句型的一个直接短语。

2. 语法分析过程可用一棵树表示出来,这棵树叫做语法树。（）

3. 欲构造行之有效的自下而上分析器，则必须清除文法中含

（）有的左递归。

（）

4. 四元式作为中间语言，用于翻译除表达式外的其他语句代

码。

（）

5. 循环优化中的强度削弱主要是指将循环中的乘法变成加

法。

6. 流图中有向边a→b为回边的条件是a DOM b。（）

1. ×要求这个非终结符取代α后，原句型还可继续向开始符方向归约。

2. ×分析树

3. ×自上而下

4. ×各种

5. ×递归加法

6. ×b DOM a

简答题

1. 简述正规式与有限自动机的关系。

2. 已知文法G: S → iSeS | iS | i

该文法是否具有二义性？请根据句子iiiei构造语法树予以说明。

3. 何谓递归下降分析法？应用此种分析法的文法应满足什么条件？

4．简述代码优化所依据的原则与优化的级别，并列举三种常用的优化技术。

1. 正规式用来描述正规集，而有限自动机用来识别正规集，在正规

集的意义上它们存在等价关系。

即：

对每一个正规式所代表的正规文法G，都存在一个有限自动机M，

使得L(M)=L(G)，M所能识别的字的全体恰为这个正规文法G的

语言集合；

对每一个有限自动机M，都存在一个可以用正规式表示的正规文

法G，使得L(G)=L(M)，这个正规文法G的语言集合中的任一个

字可以由M识别。

2. 对于句子iiiei，该文法具有两棵不同的语法树与之对应，故为二义性

文法。

S S

/ / \ \ / \

i S e S i S

/ \ | / / \ \

i S ii S e S

| | |

Iii

3. 当文法满足LL(1)条件时，可以为它构造一个不带回溯的自上而

下分析程序。

它由一组递归过程（函数）组成，每个过程（函数）对应文法的

一个非终极符，这样的分析程序称为递归下降分析器。

利用这种分析程序进行语法分析的方法称为递归下降分析法。

4. 代码优化所依据的原则是：等价原则、有效原则和合算原则。

代码优化所依据的级别是：局部优化、循环优化与全局优化。

常用的代码优化技术有：删除公共子表达式、删除无用赋值、合

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

1. 什么是编译器的前端和后端，通常两者之间用什么作为接口？

2. 简述NFA和DFA的联系与区别。

3.

4. 何谓中间语言？简述它的作用。

1. 前端主要由与源语言有关但与目标机无关的那些部分组成，通常

包括词法分析、语法分析、语义分析与中间代码产生，有的代码

优化工作也可包括在前端。（2分）后端包括编译程序中与目标机

有关的那些部分，如与目标机有关的代码优化和目标代码生成

等。（2分）通常，前端和后端以中间语言作为接口（1分）

2. 联系：NFA和DFA都是有限自动机，都用于接收、识别一定的字符串。

NFA是DFA的推广，DFA是NFA的特例。

（2分）

区别：NFA多值函数，DFA是单值函数。

NFA可以有多个初态，DFA只有一个初态。

NFA的每条弧允许用∑*上的一个字作标记，DFA的每条弧

只允许用∑上的一个字符作标记。

（3分）

3. 按照语法分析树的建立方法，可以把语法分析方法分为两类：

自上而下分析法与自下而上分析法。

（2分）

自上而下分析法面对的主要问题是：如何消除文法的左递归，

以及在由文法的开始符出发推导句子的过程中如何避免回

溯。

（2分）

自下而上分析法面对的主要问题是：在由输入串出发向文法

的开始符归约的过程中，如何确定可归约子串（句柄或最左

素短语）。

（1分）

4. 中间语言是一种面向语法，复杂性介于用高级语言书写的源

程序和用机器语言表示的目标程序之间，是一种易于翻译成

目标代码的代码形式。

（3分）

中间语言的作用在于：利用它作为中间环节，不仅可以较快

地实现源程序翻译过程，而且可在此基础上应用优化方法，

将源程序翻译成为运行时间短、占用内存少的目标程序。

（2分）

1. 何谓上下文无关文法? 它是由哪几部分组成的?

2. 简述NFA和DFA的联系与区别。

3. 语法分析方法如何分类？它们面对的主要问题是什么？

4. 何谓中间语言？简述它的作用。

1. 上下文无关文法是这样一种文法，它所定义的语法范畴（或语法

单位）是完全独立于这种范畴所处的环境的。

（3分）

上下文无关文法由四部分所组成：

一组终极符号，一组非终极符号，一个开始符号以及一组产生式。

（2分）

2. 联系：NFA和DFA都是有限自动机，都用于接收、识别一定的字符串。

NFA是DFA的推广，DFA是NFA的特例。

（2分）

区别：NFA多值函数，DFA是单值函数。

NFA可以有多个初态，DFA只有一个初态。

NFA的每条弧允许用∑*上的一个字作标记，DFA的每条弧

只允许用∑上的一个字符作标记。

（3分）

3. 按照语法分析树的建立方法，可以把语法分析方法分为两类：

自上而下分析法与自下而上分析法。

（2分）

自上而下分析法面对的主要问题是：如何消除文法的左递归，

以及在由文法的开始符出发推导句子的过程中如何避免回

溯。

（2分）

自下而上分析法面对的主要问题是：在由输入串出发向文法

的开始符归约的过程中，如何确定可归约子串（句柄或最左

素短语）。

（1分）

4. 中间语言是一种面向语法，复杂性介于用高级语言书写的源

程序和用机器语言表示的目标程序之间，是一种易于翻译成

目标代码的代码形式。

（3分）

中间语言的作用在于：利用它作为中间环节，不仅可以较快

地实现源程序翻译过程，而且可在此基础上应用优化方法，

将源程序翻译成为运行时间短、占用内存少的目标程序。

（2分）

综合题

1. 构造一个DFA，它接受Σ={a，b}上所有包含ab的字符串。

2. 对文法G（S）：

S →（L）| aS | a

L →L,S | S

1 、消除左递归和回朔；

2、构造各非终结符的FIRST和FOLLOW集合；

3、构造预测分析表。

3. 给出文法G（P）

P →bQb

Q →cR

Q →a

R →Qad

4. （1）有如下三地址码：

read(n)

i:=1

fen:=1

L1: if i<=n goto L2

Goto L3

L2: t1:=fen*i

fen:=t1

i:=i+1

goto L1

L3: write (fen)

将该代码段划分为基本块；并构造相应的程序流图。

（2）对下列四元式序列生成目标代码：

A:=B*C

D:=E+F

G:=A+D

H:=G*2

其中，H在基本块出口之后是活跃变量，R0和R1是可用寄存器。

1．构造一个DFA，它接受Σ={a，b}上所有包含ab的字符串。

2．对文法G（S）：

S →（L）| aS | a

L →L,S | S

1 、消除左递归和回朔；

2、构造各非终结符的FIRST和FOLLOW集合；

3、构造预测分析表。

答：

3．给出文法G（P）

P →bQb

Q →cR

Q →a

R →Qad

该文法是不是算符优先文法，请构造算符优先关系表证实之。

答：对于文法G，计算它的每个非终结符的FIRSTVT和LASTVT集合：

4．（1）有如下三地址码：

read(n)

i:=1

fen:=1

L1: if i<=n goto L2

Goto L3

L2: t1:=fen*i

fen:=t1

i:=i+1

goto L1

L3: write (fen)

将该代码段划分为基本块；并构造相应的程序流图。

（2）对下列四元式序列生成目标代码：

A:=B*C

D:=E+F

G:=A+D

H:=G*2

其中，H在基本块出口之后是活跃变量，R0和R1是可用寄存器。解：

1. 构造一个最简的DFA，它接受Σ={a，b}上所有满足如下条件的字符

串：所有b都有a直接跟在后面。

2. 设有文法G(X)，该文法产生式为：

X→ b | & | (Y)

Y→ Y；X| X

其中X为文法开始符号，b & ； ( )为终结符号

(1)消除左递归和回朔

(2)计算每个非终结符号的FIRST集和FOLLOW集

(3)构造它的预测分析表

3. 设文法G（S）：

S →SiA | A

A →A+

B | B

B →）A* | （

1、构造各非终结符的FIRSTVT和LASTVT集合；

2、构造优先关系表和优先函数

4. 对以下程序

(1) READ B

(2) J:=1

(3) A:=I+2

(4) E:=I*J

(5) D:=A+E

(6) B:=D+B

(7) If J>60 goto (10)

(8) J:=J+1

(9) goto (3)

(10) WRITE B

(11) halt

(1)划分基本块，画出流图

(2)对其中循环进行优化，画出优化后流图

1．构造一个最简的DFA，它接受Σ={a，b}上所有满足如下条件的字符串：所有b都有a

直接跟在后面。

答：(1)由以上正规式构造相应的NFA M'(4分)

a

(3)把DFA M ’进行化简 (4分)

①把M 状态集分为两组:终态结点{0，1}；非终态结点{2} ②考察{0，1}，因为，{0，1}a ={1}包含于{0,1}；{0，1}b={2}包含于{2}；所以，{0，1}不可再分

所以，最终把M 分割为{0，1}，{2}。状态1代替状态0，把引向状态0的箭弧都引向状态1，把0消去，得到一个DFA M ’’

2．设有文法G(X)，该文法产生式为： X → b | & | (Y) Y → Y ；X| X

其中X 为文法开始符号，b & ； ( )为终结符号 (1)消除左递归

(2)计算每个非终结符号的FIRST 集和FOLLOW 集 (3)构造它的预测分析表 答：

(1)消除左递归(4分)

X → b | & | (Y)

Y→ XY’

Y’→；XY’|ε

(2)计算每个非终结符号的FIRST集和FOLLOW集(4分) FIRST( X )={ b , & ,( };

FIRST( Y )={ b , & ,( };

FIRST( Y’)={； , ε};

FOLLOW(T)={ ) };

FOLLOW (Y’)={ ) };

FOLLOW (X)={ #, ；} };

(3)构造它的预测分析表(4分)

3．设文法G（S）：

S →SiA | A

A →A+

B | B

B →）A* | （

1、构造各非终结符的FIRSTVT和LASTVT集合；

2、构造优先关系表和优先函数

答：

4．对以下程序

(1) READ B

(2) J:=1

(3) A:=I+2

(4) E:=I*J

(5) D:=A+E

(6) B:=D+B

(7) If J>60 goto (10)

(8) J:=J+1

(9) goto (3)

(10) WRITE B

(11) halt （4分）（4分）

（4分）

(1)划分基本块，画出流图

(2)对其中循环进行优化，画出优化后流图

(1)划分基本块，画出流图(6分)

(2)对其中循环进行优化，画出优化后流图(6分)

1. 构造一个DFA，它接受Σ={0，1}上所有倒数第二个字符为1的字符

串。

编译原理概念_名词解释

编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成 解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。 解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执 行结果，然后再接受下一句。 编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。 解释程序和编译程序的根本区别：是否生成目标代码 句子的二义性（这里的二义性是指语法结构上的。）:文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。 文法的二义性:一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。 LL(1)的含义：(LL(1)文法是无二义的； LL(1)文法不含左递归) 第1个L：从左到右扫描输入串第2个L：生成的是最左推导 1：向右看1个输入符号便可决定选择哪个产生式 某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子 2. 消除左递归 文法符号的属性:单词的含义，即与文法符号相关的一些信息。如，类型、值、存储地址等。 一个属性文法(attribute grammar)是一个三元组A=(G, V, F) G：上下文无关文法。 V：属性的有穷集。每个属性与文法的一个终结符或非终结符相连。属性与变量一样，可以进行计算和传递。 F：关于属性的断言或谓词(一组属性的计算规则)的有穷集。断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。 综合属性:若产生式左部的单非终结符A的属性值由右部各非终结符的属性值决定,则A的属性称为综合属继承属性:若产生式右部符号B的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B的属性为继承属性。 (1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性。 (2) 终结符只有综合属性，没有继承属性，它们由词法程序提供。 在计算时：综合属性沿属性语法树向上传递；继承属性沿属性语法树向下传递。 语法制导翻译：是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作。 语法制导翻译实现：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点处按语义规则进行计算。 中间代码（中间语言） 1、是复杂性介于源程序语言和机器语言的一种表示形式。 2、一般，快速编译程序直接生成目标代码。 3、为了使编译程序结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作，使得代码优化比较容易实现。 何谓中间代码：源程序的一种内部表示，不依赖目标机的结构，易于代码的机械生成。 为何要转换成中间代码:(1)逻辑结构清楚；利于不同目标机上实现同一种语言。 (2)便于移植，便于修改，便于进行与机器无关的优化。 中间代码的几种形式：逆波兰记号，三元式和树形表示，四元式 符号表的一般形式：一张符号表的的组成包括两项，即名字栏和信息栏。 信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，名字栏也称主栏。主栏的内容称为关键字（key word）。 符号表的功能：（1）收集符号属性(2) 上下文语义的合法性检查的依据：检查标识符属性在上下文中的一致性和合法性。(3)作为目标代码生成阶段地址分配的依据

东南大学编译原理试题

东南大学一九九三年攻读硕士学位研究生入学考试试题 试题编号:553 试题名称:编译原理 一:(15分)判断下列命题的真假,并简述理由: 1.文法G的一个句子对应于多个推导,则G是二义的. 2.LL(1)分析必须对原有文法提取左因子和消除左递归. 3.算符优先分析法采用"移近-归约"技术,其归约过程是规范的. 4.文法S→aA;A→Ab;A→b是LR(0)文法(S为文法的开始符号). 5.一个BASIC解释程序和编译程序的不同在于,解释程序由语法制导翻译成目标代码并立即执行之,而编译程序需产生中间代码及优化. 二:(15分)设计一个最小状态有穷自动机,识别由下列子串组成的任意字符串. GO,GOTO,TOO,ON 例如:GOTOONGOTOOGOON是合法字符串. 三:(15分)构造一个LL(1)文法G,识别语言L: L={ω|ω为{0,1}上不包括两个相邻的1的非空串} 并证明你的结论. 四:(20分)设有一台单累加器计算机,并汇编语言含有通常的汇编指令LOAD,STORE,ADD和MUL. 1.写一个递归下降分析程序,将如下文法所定义的赋值语句翻译成汇编语言: A→i:=E E→E+E|E*E|(E)|i 2.利用加,乘法满足交换率这一性质,改进你的分析程序,以期产生比较高效的目标代码. 五:(15分)C为大家熟知的程序语言. 1.C的参数传递采用传值的方式,而且允许函数定义和调用时的参数个数不一致(如printf).请指出其函数调用语句: f(arg1,arg2,...,argn) 翻译成的中间代码序列,并简述其含义. 2.C语言中的变量具有不同的作用范围,试述C应采用的存储分配策略. 六:(20分)设有一个子程序的四元式序列为: (1) I:=1 (2) if I>20 GOTO (16) (3) T1:=2*J (4) T2:=20*I (5) T3:=T1+T2 (6) T4:=addr(A)-22 (7) T5:=2*I (8) T6:=T5*20 (9) T7:=2*J (10) T8:=T6+T7 (11) T9:=addr(A)-22 (12) T10:=T9[T8] (13) T4[T3]:=T10+J

编译原理与技术01

编译原理与技术模拟试题一 一、填空题（20分） 1.1编译程序的工作过程可划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等 阶段，一般在语义分析阶段对表达式中运算对象的类型进行检查。 1.2 递归下降法和预测分析法是自上而下的语法分析方法。 1.3常用日的存储分配策略有静态存储分配和动态存储分配，其中，动态存储分配策略包括栈分配和堆分配。 1.4移进、归约是自下而上或LR 分析中的典型操作。 1.5对于数组M[1..6, 1..8]，如果每个元素占k个存储单元，且起始地址为a，则以行为主序存放时元素M[4,4]的地址是__ a+27*k __，以列为主序存放时元素M[4,4]的地址是__ a+21k __。 二、单选题（20分） 2.1词法分析器不能 D 。 A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 2.2给定文法A→bA|ca， C 是该文法的句子。 A. bba B. cab C. bca D. cba 2.3一个句型中的最左 B 称为该句型的句柄。 A. 短语 B. 直接短语 C. 非终结符号 D. 终结符号 2.4已知文法G[S]:S→A1A→A1|S0|0。与G等价的正规式是 C 。 A. 0(0|1)* B. 1*|0*1 C. 0(1|10)*1 D. 1(10|01)*0 2.5源程序是句子的集合， B 可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 2.6与逆波兰式ab+c*d+对应的中缀表达式是 B 。 A. a+b+c*d B. (a+b)* c+d C. (a+b)* (c+d) D. a+b*c+d 2.7识别上下文无关语言的自动机是 A 。 A. 下推自动机 B. NFA C. DFA D. 图灵机 2.8 B 是与规范归约（最左归约）互逆的一个过程。 A. 最左推导 B. 最右推导 C. 词法分析 D. 语义分析 2.9文法G产生的 A 的全体是该文法描述的语言， A. 句子 B. 短语 C. 终结符 D. 非终结符 2.10在表达式x:=y+1中， A 作为左值出现(其中，“:=”表示赋值)。 A. x B. y C. 1 D. y+1 三、简答题（30分） 3.1 （5分）请分别写出传值调用、引用调用方式下，下面代码的输出结果。 program main(input,output) procedure f(a,b) begin a := b - a; b := a * b + 1; end; begin x := 5; y := 10; f(y,x); print(x,y); end.

天津理工大学编译原理期末考试试卷

天津理工大学考试试卷 ～2010学年度第二学期 《编译原理》期末考试试卷 课程代码： 0660116 试卷编号： 1-A 命题日期： 2010 年 6 月 15 日 答题时限： 120 分钟考试形式：闭卷笔试 大题号 一二三四 总分 一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分， 得 分 1 2 3 4 5 6 7 8 9 10 D C B D D B C B D C 1. 编译程序是对（） A. 汇编程序的翻译 B. 高级语言程序的解释执行 C. 机器语言的执行 D. 高级语言的翻译 2. 词法分析器的输出结果是（） A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 3. 在规范规约中，用（）来刻画可规约串。 A．直接短语 B．句柄 C．最左素短语 D．素短语 4. 与正规式(a* | b) * (c | d)等价的正规式是（） A．a* (c | d) | b(c | d) B．a* (c | d) * | b(c | d) * C．a* (c | d)| b* (c | d) D．(a | b) * c| (a | b) * d 含有Aα·，则在状态K时，仅当面临输入符号a∈FOLLOW(A)时，才采 5. 若项目集I K 取Aα·动作的一定是（） A．LALR文法 B．LR(0) 文法C．LR(1)文法 D．SLR(1)文法 6. 四元式之间的联系是通过（）实现的。

A. 指示器 B. 临时变量 C. 符号表 D. 程序变量 7．文法G ：S x Sx | y 所识别的语言是（ ） A ．xyx B ．(xyx) * C ．x n yx n (n ≥0) D ．x * yx * 8. 有一语法制导翻译如下所示： S b Ab {print “1”} A (B {print “2”} A a {print “3”} B Aa) {print “4”} 若输入序列为b(((aa)a)a)b ，且采用自下而上的分析方法，则输出序列为（ ） A ．32224441 B. 34242421 C ．12424243 D. 34442212 9．关于必经结点的二元关系，下列叙述不正确的是（ ） A ．满足自反性 B ．满足传递性 C ．满足反对称型 D ．满足对称性 10．错误的局部化是指（ ）。 A ．把错误理解成局部的错误 B ．对错误在局部范围内进行纠正 C ．当发现错误时，跳过错误所在的语法单位继续分析下去 D ．当发现错误时立即停止编译，待用户改正错误后再继续编译 二、判断题（每小题1分，共5分） 得 分 1. 文法G 的一个句子对应于多个推导，则G 是二义性的。（× ） 2. 动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（√ ） 3. 算符优先文法采用“移进－规约”技术，其规约过程是规范的。（ × ） 4. 删除归纳变量是在强度削弱以后进行。（ √ ） 5. 在目标代码生成阶段，符号表用于目标代码生成。（ × ） 5分，共15分） 得 分 1. 构造正规式(0∣1)* 00相应的正规式并化简。（共5分） （1）根据正规式，画出相应的NFA M （2分） I I 0 I 1 {x,1,2} {1,2,3} {1,2} {1,2,3} {1,2,3,4} {1,2} {1,2} {1,2,3} {1,2 } {1,2,3, {1,2,3,4} {1,2 } X 12 3 4 01

编译原理课程设计---C语言编译器的实现

扬州大学编译原理课程设计 学号：091202122 姓名： 专业：计算机科学与技术 课程：编译原理 指导教师：陈宏建

目录 一．程序简介与分析---------------------------------------------------------3 二．程序适用范围-----------------------------------------------------------3 三．词法分析---------------------------------------------------------------3 四．语法分析---------------------------------------------------------------4 五．语义分析和中间代码生成------------------------------------------------10 六．代码生成--------------------------------------------------------------12 七．流程图----------------------------------------------------------------13 八．实现------------------------------------------------------------------14 九．程序运行结果----------------------------------------------------------14 十．总结------------------------------------------------------------------18 十一.附录（源程序）--------------------------------------------------------18

东南大学编译原理词法分析器实验报告

词法分析设计 1. 实验目的 通过本实验的编程实践，了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。 2. 实验内容 用C++语言实现对C++语言子集的源程序进行词法分析。通过输入源程序从左到右对字符串进行扫描和分解，依次输出各个单词的内部编码及单词符号自身值；若遇到错误则显示“Error”，然后跳过错误部分继续显示；同时进行标识符登记符号表的管理。 3. 实验原理 本次实验采用NFA->DFA->DFA0的过程: 对待分析的简单的词法（关键词/id/num/运算符/空白符等）先分别建立自己的FA，然后将他们用产生式连接起来并设置一个唯一的开始符，终结符不合并。 待分析的简单的词法 （1）关键字： "asm","auto","bool","break","case","catch","char","class","

const","const_cast"等 （2）界符（查表） ";",",","(",")","[","]","{","}" （3）运算符 "*","/","%","+","-","<<","=",">>","&","^","|","++","--"," +=","-=","*=","/=","%=","&=","^=","|=" relop： （4）其他单词是标识符（ID）和整型常数（SUM），通过正规式定义。 id/keywords: digit: （5）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。

编译原理和技术期末考试复习题

2.1 考虑文法G[S],其产生式如下: S→(L)|a L→L，S|S (1)试指出此文法的终结符号、非终结符号。 终结符号为：{(,),a,,,} 非终结符号为：{S,L} 开始符号为：S (2)给出下列各句子的分析树： ① (a,a)②(a,(a,a))③ (a,((a,a),(a,a))) (3)构造下列各句子的一个最左推导： ① (a,a) S (L) (L,S) (S,S) (a,S) (a,a) ② (a,(a,a)) S (L) (L,S) (S,S) (a,S) (a,(L) (a,(L,S)) (a,(S,S)) (a,(a,S)) (a,(a,a)) ③ (a,((a,a),(a,a))) S (L) (L,S) (S,S) (a,S) (a,(L)) (a,(L,S)) (a,(S,S)) (a,((L),S)) (a,((L,S),S)) (a,((S,S),S)) (a,((a,S),S)) (a,((a,a),S)) (a,((a,a),(L)))

(a,((a,a),(L,S))) (a,((a,a),(S,S))) (a,((a,a),(a,S))) (a,((a,a),(a,a))) (4)构造下列各句子的一个最右推导： ①(a,a) S (L) (L,S) (L,a) (S,a) (a,a) ②(a,(a，a)) S (L) (L,S) (L,(L)) (L,(L,S)) (L,(L,a)) (L,(S,a)) (L,(a,a)) (S,(a,a)) (a,(a,a) ③(a，((a，a)，(a，a)) S (L) (L,S) (L,(L)) (L,(L,S)) (L,(L,(L))) (L,(L,(L,S))) (L,(L,(L,a))) (L,(L,(S,a))) (L,(L,(a,a))) (L,(S,(a,a))) (L,((L),(a,a))) (L,((L,S),(a,a))) (L,((L,a),(a,a))) (L,((S,a),(a,a))) (L,((a,a),(a,a))) (S,((a,a),(a,a))) (a,((a,a),(a,a))) (5)这个文法生成的语言是什么？ L(G[S]) = (α1,α2,...,αn)或a 其中αi(1≤i≤n)，即L(G[S])是一个以a为原子的纯表，但不包括空表。 2.2 考虑文法G[S] S→aSbS|bSaS|ε (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构造两棵不同的分析树。 (一) (二) (4)此文法所产生的语言是什么？ 此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。 2.4 已知文法G[S]的产生式如下：S → (L)|a L → L,S|S 属于L(G[S])的句子是 A ，(a,a)是L(G[S])的句子，这个句子的最左推导是 B ，最右推导是 C ，分析树是 D ，句柄是 E 。 A：① a ② a,a ③ (L) ④ (L,a) B,C：① S (L) (L,S) (L,a) (S,a) (a,a) ② S (L) (L,S) (S,S) (S,a) (a,a)

编译原理及实现课后习题答案(1)

2.1 设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+和A*. x0=(aaa)0=ε| x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1∪A2∪…. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…} A* = A0 ∪A1 ∪A2∪…. ∪ A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…} 2.2 令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3 xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 2.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语 法树。 S => SS* => Sa* => SS+a* => Sa+a* => aa+a*

2.4 已知文法G[Z]：Z∷=U0∣V1 、U∷=Z1∣1 、V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。 Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z01=>U001=>1001 Z=>V1=>Z01=>V101=>0101 2.5 已知文法G[S]：S∷=AB A∷=aA︱εB∷=bBc︱bc , 写出该文法描述的语言。 A∷=aA︱ε描述的语言: {a n|n>=0} B∷=bBc︱bc描述的语言：{b n c n|n>=1} L(G[S])={a n b m c m|n>=0,m>=1} 2.6 已知文法E∷=T∣E+T∣E-T 、T∷=F∣T*F∣T/F 、F∷=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。 开始符号：E V t={+, - , * , / ,（, ）, i} V n={E , F , T} 2.7 对2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。 短语：T+T*F+i T+T*F Array i i T T*F 简单短语：i T*F T 句柄：T

2015编译原理试卷A

………密………封………线………以………内………答………题………无………效…… 电子科技大学2014 -2015学年第2学期期末考试 A 卷 课程名称：编译原理考试形式：闭卷考试日期：2015 年月日考试时长：120分钟 课程成绩构成：大班平时10 %，期中10 %，实验10 %，期末70 % 本试卷试题由___七_ _部分构成，共__8___页。 题号一二三四五六七合计 得分 得分 一、选择题（共20分，共10题，每题2分） 1.通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括（） A.模拟执行器 B.解释器 C.表格处理和出错处理 D.符号执行器 2.如果在推导过程中的任何一步α?β，都是对α中的最右非终结符进行替换，则称这种推导为（） A.直接推导 B.广义推导 C.最左推导 D.规范推导 3.设有文法G[S]=（{S，B}，{b},{S→bB | b,B→bS},S）,该文法所描述的语言是（） A．L(G[S]）={b n| n ≥0} B. L(G[S])={b2n| n ≥ 0} C. L(G[S])={b2n+1 | n ≥ 0} D. L(G[S])={b2n+1|n ≥ 1} 4.项目A α·称为（），其中A∈V N，A不是开始符。 A.移进项目 B.归约项目 C.待约项目 D.接受项目 5.编译程序生成的目标程序（）是机器语言的程序。 A．一定B．不一定C．某种情况下一定D．某种情况下不一定 6.高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。 A．自左至右B．自顶向下C．自底向上D．自右向左 7.运行阶段的存储组织和管理的目的是（） （1）提高编译程序的运行速度 （2）提高目标程序的运行速度 （3）为运行阶段的存储分配做准备 A.(1)(2) B.(1)(3) C.(2) D.(1)(2)(3) 8.如果文法G 是无二义的，则它的任何句子α（） A.最左推导和最右推导对应的语法树必定相同 B.最左推导和最右推导对应的语法树可能不同 C.最左推导和最右推导必定相同

(完整版)编译原理及实现课后习题答案

编译原理及实现课后习题解答 2.1设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5 以及A+和A*. x0=(aaa)0=ε| x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1∪A2∪ …. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…} A* = A0 ∪A1 ∪A2 ∪…. ∪A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…} 2.2令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3 xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 2.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语 法树。 S => SS* => Sa* => SS+a* => Sa+a* => aa+a*

S S S * S S + a a a 2.4 已知文法G[Z]：Z∷=U0∣V1 、U∷=Z1∣1 、V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。 Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z01=>U001=>1001 Z=>V1=>Z01=>V101=>0101 2.5已知文法G[S]：S∷=AB A∷=aA︱εB∷=bBc︱bc , 写出该文法描述的语言。 A∷=aA︱ε描述的语言: {a n|n>=0} B∷=bBc︱bc 描述的语言：{b n c n|n>=1} L(G[S])={a n b m c m|n>=0,m>=1} 2.6已知文法E∷=T∣E+T∣E-T 、T∷=F∣T*F∣T/F 、F∷=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。 开始符号：E V t={+, - , * , / ,（, ）, i} V n={E , F , T}

编译原理知识点汇总

编译原理的复习提纲 1.编译原理=形式语言+编译技术 2.汇编程序： 把汇编语言程序翻译成等价的机器语言程序 3.编译程序： 把高级语言程序翻译成等价的低级语言程序 4.解释执行方式： 解释程序，逐个语句地模拟执行 翻译执行方式： 翻译程序，把程序设计语言程序翻译成等价的目标程序 5.计算机程序的编译过程类似，一般分为五个阶段： 词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成 词法分析的任务： 扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等） 语法分析是： 在词法分析的基础上的，语法分析不考虑语义。语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。 语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。

语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序 代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码 编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序 编译程序结构包括五个基本功能模块和两个辅助模块 6.编译划分成前端和后端。 编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析 编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。 把编译程序分为前端和后端的优点是： 可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。 7.汇编器把汇编语言代码翻译成一个特定的机器指令序列 第二章 1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，Xn， 2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0 ={ε} 3.重写规则，简称规则。非xx（V

大学编译原理课程复习试题及答案

编译原理复习材料 选择题 1. 文法S→0S | S1 | 0的语言是( )。 A. { 0 m1m| m >=0 } B. { 0 m1m| m >=1 } C. { 0 m1n | m>=1,n>=0 } D. { 0 m1n | m>=0,n>=1 } 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. 优先函数的优点是( )。 A.形象直观 B.便于进行比较运算 C.语法分析速度快 D.语法分析方法简单 8. 文法符号的属性通常分为( )两类。 A. 共用属性和私有属性 B.固有属性和可变属性 C.语法属性和语义属性 D.综合属性和继承属性 9. 在程序流图中，组成循环的结点序列应满足( ) A. 它们是强连通的 B.它们中间有唯一的入口结点 C.它们中间有一条回边 D.它们是强连通的且有唯一的入 口结点 10. 在利用寄存器R生成T1:=C/B的目标代码同时,还应记录信息( )。 A. C/B在T1中 B. T1在C/B中 C. R含有T1, T1在R中 D. R含有C/B, C/B在R中 1.D 2.B 3.C 4.B 5.B 6.A 7.B 8.D 9.D 10.C

编译原理发展史

编译原理历史与发展 姓名：费张烨学号：09923206 指导老师：朱文华 基于形式语言理论中的有关概念来讨论编译实现问题。即 编译原理=形式语言理论+编译技术 编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。编译原理是计算机专业设置的一门重要的专业课程。虽然只有少数人从事编译方面的工作，但是这门课在理论、技术、方法上都对学生提供了系统而有效的训练，有利于提高软件人员的素质和能力。 编译器是将一种语言翻译为另一种语言的计算机程序。编译器将源程序（source language）编写的程序作为输入，而产生用目标语言（target language ）编写的等价程序。通常地，源程序为高级语言（high-level language ），如C或C + + ，而目标语言则是目标机器的目标代码（object code，有时也称作机器代码（machine code ）），也就是写在计算机机器指令中的用于运行的代码。这一过程可以表示为： 源程序→编译器→目标程序 编译技术的历史 在20世纪40年代，由于冯·诺伊曼在存储-程序计算机方面的先锋作用，编写一串代码或程序已成必要，这样计算机就可以执行所需的计算。开始时，这些程序都是用机器语言（machine language ）编写的。机器语言就是表示机器实

际操作的数字代码，例如：C7 06 0000 0002 表示在IBM PC 上使用的Intel 8x86处理器将数字2移至地址0 0 0 0 （16进制）的指令。

编译原理与技术练习题汇总

练习 1 1.1 为什么高级程序语言需要编译程序？ 1.2 解释下列术语： 源程序，目标程序，翻译程序，编译程序，解释程序 1.3 简单叙述编译程序的主要工作过程。 1.4 编译程序的典型体系结构包括哪些构件，主要关系如何，请用辅助图示意。 1.5 编译程序的开发有哪些途径？了解你熟悉的高级编程语言编译程序的开发方式。 1.6 运用编译技术的软件开发和维护工具有许多类，简单叙述每一类的主要用途。 1.7 了解一个真实编译系统的组成和基本功能。 1.8 简单说明学习编译程序的意义和作用。 1.9 如果机器H上有两个编译：一个把语言A翻译成语言B，另一个把B翻译成C，那么可以把第一个编译的输出作为第二个编译的输入，结果在同一类机器上得到从A到C的编译。请用T形图示意过程和结果。

练习 2 2.1 词法分析器的主要任务是什么？ 2.2 下列各种语言的输入字母表是什么？ (1) C (2) Pascal (3) Java (4) C# 2.3 可以把词法分析器写成一个独立运行的程序，也可以把它写成一个子程序，请比较各自的优劣。 2.4 用高级语言编写一个对C#或Java程序的预处理程序，它的作用是每次调用时都把下一个完整的句子送到扫描缓冲区，去掉注释和无用的空格、制表符、回车、换行。 2.5 用高级语言实现图2.5所示的Pascal语言数的状态转换图。 2.6 用高级语言编程实现图2.6所示的小语言的词法扫描器。 2.7 用自然语言描述下列正规式所表示的语言： (1) 0(0|1)*0 (2) ((ε|0)1)*)* (3) (a|b)*a(a|b|ε) (4) (A|B|...|Z)(a|b|...|z)* (5) (aa|b)*(a|bb)* (6) (0|1|...|9|A|B|C|D|E)+(t|T) 2.8 为下列语言写正规式 (1) 所有以小写字母a开头和结尾的串。 (2) 所有以小写字母a开头或者结尾（或同时满足这两个条件）的串。 (3) 所有表示偶数的串。 (4) 所有不以0开始的数字串。 (5) 能被5整除的10进制数的集合。 (6) 没有出现重复数字的全体数字串。 2.9 试构造下列正规式的NFA，并且确定化，然后最小化。 (1) (a|b)*a(a|b) (2) (a||b)*a(a|b) * (3) ab((ba|ab)*(bb|aa))*ab (4) 00|(0|1)*|11 (5) 1(0|1)*01 (6) 1(1010*|1(010)*1*0 2.10 请分别使用下面的技术证明(a|b)*，(a*|b*)*以及((a|ε)b*)*这三个正规式是等价的： (1) 仅用正规式的定义及其代数性质； (2) 从正规式构造的最小DFA的同构来证明正规式的等价。

编译原理试题B及答案

编译原理试题B 得分一、单项选择题（每题1分，共20分） 1、对编译系统有关概念描述正确的是（ B） A．目标程序只能是机器语言 B. 编译程序处理的对象是源语言 C．解释程序属于编译程序 D. 词法分析无法自动进行 2. 设有表达式a*b-c，将其中a*b识别为表达式的编译阶段是什么 （B） A．词法分析 B. 语法分析 C．语义分析 D. 代码生成 3. 下面不能用于对文法进行描述的是（A ） A．源语言 B. EBNF C．BNF D. 语法图 4. 设有文法G[S]: S→0S|1A|0，A→1|1S|0B，B→1A|0B，下列符号串中是该文法的句子的是 （）？ A．1010001001101 B.0101001110010010 C．1101010011110111 D.1010011101101010 (可画出DFA验证) 5. 文法G[S]: S→aA|bC|a A→aS|bB B→aC|bA|b C→aB|bS ,则不是L(G)句子的是（ B ）100501001000500aba B. a．a babbA5006021004010aa aaba D. aabC．abb （画出DFA） 6. 哪个不是DFA的构成成分（B） A．有穷字母表 B. 初始状态集合 C．终止状态集合 D. 有限状态集合 7.词法分析器的输入是（ B ） A．单词符号串 B.源程序 C．语法单位 D.目标程序 8.在词法分析阶段不能识别的是（C ） A．标识符 B. 运算符 C．四元式 D. 常数

9.设有一段C语言程序while(i&&++j)

{ c=2.19; j+=k; i++;经过词法分析后可以识别的单词个数是（B ）} ,．19 B.20 C．21 D.23A （ B ）10．自上而下语法分析的主要动作是 C．规约 D. 匹配A．移进 B. 推导 （ D ）分析器的自称部分是11.下面不属于LL(1) 总控程序 B. LL(1)分析表A．LL(1)．分析栈 D.源程序串C 设有文法G[S]为12.→aS|c，C→AD|b，DBS→AB|bC， A→ε|b，→ε|aD A ）则FOLLOW(A)为（．{a,#} D.{#}A．{a,c,#} B.{c,#} C G[S]: 13.设有文法）FIRST(Ap)为（ C Ap|Bq→，A→a|cA，B→b|dB ，则S 其他．{p,q} B. {b,d} C．{a,c} D. A ）自下而上语法分析的主要分析动作是（D 14. D. 移进-规约A．推导 B. 规约 C．匹配 （ C ） 15.算法优先分析中，可规约串是 ．最左素短语 D．素短语A．句柄 B．活前缀 C ）（ B →SaS|ε},S}16. 设有文法，该文法是．二义性文法 B 文法A．LL(1)C．SLR(1)文法 D．算法优先文法 17、中间代码生成时所以据的是（C ） A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 18、给定文法G: E→E+T|T，T→T*F|F，F→i|(E) 则L(G)中的一个句子i+i+(i*i)*i的逆波兰表示为（ C ） A．iii*i++ B．ii+iii**+ C．ii+ii*i*+ D．其他 19．在编译程序中与生成中间代码的目的无关的是（B ） A．便于目标代码优化 B．便于存储空间的组织 C．便于目标代码的移植 D．便于编译程序的移植 20．中间代码是介于源语言程序和什么之间的一种代码（ D） A．源代码 B. 机器语言 C. 汇编语言 D. 目标代码 得分二．简答（每题3分，共12分） 1. 什么是解释程序？ 解释程序也是一种翻译程序，它将源程序作为输入并执行之，即边解释边执行。 2. 词法分析器的主要任务是什么？ 词法分析器的主要任务是逐步扫描和分解构成源程序的字符串，识别出一个一个的单词符号。 3．文法有哪几部分组成？

编译原理第二版课后习答案

《编译原理》课后习题答案第一章 第 1 章引论 第 1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第 2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程 序的总体结构图。 答案： 一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式 的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的 各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源

四川大学编译原理期末试卷4套+复习资料

(2012-2013学年第2学期) 一．简答题 1.符号表的作用是什么？为了达到对其插入删除等操作的复杂度为O(1)，需将其组织成什么数据结构。 2.分析树和语法书的区别。 3.什么是正规集。 4.什么叫句子，什么叫句型。 5.二义文法一定不是LL（1） 二．给定文法 S→A A→A+A|B++ B→y 1.画出句子y+++y++的分析树 2.给出句子y+++y++的最右推导 三．给定正则表达式（a|b）*abb 1.使用thompson构造法构造等价的NFA。 2.用子集法对（1）得到的NFA进行确定化和最小化，得到等价的最小DFA。 3.使用双层多分支语句实现（2）得到的DFA。写出伪代码。 四．给定文法 statement→if-stmt|other|e if-stmt→if(exp)statement else-part else-part→else statement|e exp→0|1 写出递归下降子程序的伪代码。 五．给定文法 S→[SX]|a X→e|+SY|Yb Y→e|-SXc 1.对文法中的每一个非终结符构造First集和Follow集。 2.构造LL（1）分析表 3.基于分析表，使用LL(1)对句子[a+a-ac]进行自顶向下的语法分析，给出每一步的动作及分析栈和输入串的变化情况。 六．给定文法 E→E+T|T T→T*F|F F→(E)|id 1.构造LR（0）项目的DFA： 2.构造SLR（1）的分析表 3.利用2得到的分析表对id+id*id进行自顶向下的语法分析。 七． 1.给出构造Follow集合的算法描述 2.给出SLR（1）算法的描述

东南大学编译原理试卷

S o ut he a s t Uni v e r si ty E xa mi na ti o n P a per (i n-t e r m) Course Name Principles of Compiling Examination Term Score Related Major Computer & Software Examination Form Close test Test Duration120 Mins There are 5 problems in this paper. Y ou can write the answers in English or Chinese on the attached paper sheets. 1.Please construct context-free grammars with ε-free productions for the following languages (20%). (1){i|i∈N(Natural number), and i is a palindrome, and (i mod 5)=0} (2){ω| ω∈(a,b,c,d)* and the numbers of a’s ,b’s and c’s occurred in ω are even, and ωstarts with a or c , ends with d } 2.Please construct a DFA with minimum states for the following regular expression. (20%) (((a|b)*a)*(a|b))*(a|b) 3.Please eliminate the left recursions (if there are)and extract maximum common left factors (if there are) from the following context free grammar, and then decide the resulted grammar is whether a LL(1) grammar by constructing the related LL(1) parsing table.(20%) Please obey the rules of examination. If you violate the rules, your answer sheets will be invalid 共 2 页第 1 页