编译原理试题及答案

《编译原理》考试试题

（所有答案必须写在答题纸上）

(2006.12.25)

一、回答下列问题：(30分)

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

解答：

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

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

（1） 产生式Xj的左边符号X1,X2…Xj-1的属性；

（2） A的继承属性。 （2分）

S-属性文法是L-属性文法的特例。 （2分）

2．什么是句柄？什么是素短语？

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

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

解答：

（1）程序第一个语句，或

（2）能由条件转移语句或无条件转移语句转移到的语句，或

（3）紧跟在条件转移语句后面的语句。

4．(6分)运行时的DISPLAY表的内容是什么？它的作用是什么？

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

三、写一个文法使其语言为L(G)={ anbmambn | m,n≥1}。(6分)

答：文法G(S):

S  aSb | B

B  bBa | ba

四、对于文法G(E): (8分)

ET|E+T

TF|T*F F(E)|i

1. 写出句型(T*F+i)的最右推导并画出语法树。

编译原理试题与答案

第1讲 绪论

本讲模拟练习题(不计分)

1. 编译是对( )。

A. 机器语⾔的执⾏

B. 汇编语⾔的翻译

C. ⾼级语⾔的翻译

D. ⾼级语⾔程序的解释执⾏

正确答案：C你选对了

2. ⽤⾼级语⾔编写的程序经编译后产⽣的程序叫( )。

A. 源程序

B. ⽬标程序

C. 连接程序

D. 解释程序

正确答案：B你选对了

3. ( )不是编译程序的组成部分。

A. 词法分析程序

B. 代码⽣成程序

C. 设备管理程序

D. 语法分析程序

正确答案：C你选对了

4. 源程序是句⼦的集合，( )可以较好地反映句⼦的结构。

A. 线性表

B. 树

C. 完全图

D. 堆栈

正确答案：B你选对了

5. 编译程序是⼀种( )。

A. 汇编程序

B. 翻译程序

C. 解释程序

D. ⽬标程序

正确答案：B你选对了

6. 按逻辑上划分，编译程序第三步⼯作是( )。

A. 语义分析

B. 词法分析

C. 语法分析

D. 代码⽣成

正确答案：A你选对了

7. 编译程序中语法分析器接收以( )为单位的输⼊。

A. 单词

B. 表达式

C. 产⽣式

D. 句⼦正确答案：A你选对了

8. 编译过程中，语法分析器的任务就是( )。

A. 分析单词是怎样构成的

B. 分析单词串是如何构成语句和声明的

C. 分析语句和声明是如何构成程序的

D. 分析程序的结构

正确答案：B你选对了

9. 语法分析时所依据的是( )

A. 语法规则

B. 词法规则

C. 语义规则

D. 等价变换规则

正确答案：A你选对了

第1讲 测验（计分）

1. 单选(1分) 把汇编语⾔程序翻译成机器可执⾏的⽬标程序的⼯作是由把汇编语⾔程序翻译成机器可执⾏的⽬标程序的⼯作是由( )完成的。

A. 编译器

B. 解释器

C. 预处理器

D. 汇编器

正确答案：D你选对了

2. 单选(1分) ( )不是编译程序的组成部分。

A. 词法分析程序

B. 语法分析程序

C. 代码⽣成程序

D. 设备管理程序

正确答案：D你选对了

3. 单选(1分) 通常⼀个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码⽣成，代码优化，

英文含义：

机器语言：Machine language 汇编语言：Assembly language

高级语言：High-level language 源语言：Source language

目标语言：Target language 翻译程序：Translator

编译程序：Compiler 交叉编译程序：Cross compiler

预处理程序：Preprocessor 解释程序：Interpreter

中间代码：Intermediate code 词法分析器：scanner

语法分析器：Parser 前端：Front end

后端：back end 遍：pase

文法：Grammar 正规文法：Regular grammar

正则式：Regular expression 有穷自动机：Finite automata

术语解释：

推导: 连续使用产生式右部去替换左部某个非终结符的过程,得到的连续序列称为一个推导。

直接推导：又称一步推导(用 符号=>表示),就是用某条规则的右部去替换该规则的左部

最左推导：如果整个推导中，每一步都是替换句型中最左边的非终结符。

最右推导：在推导的每一步都替换最右边的非终结符。

规范推导：又称最右推导

句型：设Ｇ(s)是一文法，如果符号串x是从开始符号推导出来的，即有s=>x,则称x是文法G(s)的一个句型。

句子：若x仅由终结符号组成，则称x为G(S)的句子。

语言：一个文法G可以推导出的所有句子构成的一个集合, 就确定了一个语言。

非确定有限自动机：（NFA）M是一个五元组：M=（S，Σ，δ，s0，F）。

确定有限自动机：一个确定的有穷自动机（DFA）M是一个五元组：M=（S，Σ，δ，s0，F）。

编译原理

一、 是非题(下列各题你认为正确的，请在题干的括号内打“√”，错的打“×”。 每题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分）

编译原理题库

一、选择题：

1.编译原理是对（C）。A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行

2.编译程序是将高级语言程序翻译成D。A、汇编语言程序 B、机器语言程序C、高级语言程序 D、汇编语言或机器语言程序

3.文法：G：S→xSx | y所识别的语言是（D）。A、xnyxm B、(xyx)*C、x*yx* D、xnyxm（n≥0）

4.设有文法G[I]：

I→I0|I1|I a|Ic|a|b|c

下列符号串中是该文法的句子的有B。

①ab0 ②a0c01 ③aaa ④bc10

可选项有A、① B、②③④ C、③④ D、①②③④

5.词法分析器的输出结果是（C）。A、单词自身值B、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值

6.为了使编译程序能够对程序设计语言进行正确的翻译，必须采用_C_方法定义程序设计语言。A、非形式化B、自然语言描述问题C、形式化D、自然语言和符号体系相结合

7. 若文法G定义的语言是无限集，则文法必然是（C）A.前后文无关文法B.正规文法C.二义性文法D.递归文法

8、描述一个语言的文法是B。A、唯一的B、不唯一的C、个数有限的

9、表达式（a+b）*c的逆波兰表示为_C_A、ab+c* B、abc+* C、a*c+b*c

10、递归下降分析法和预测分析法要求描述语言的文法是_C_A、正规文法B、ＬＲ（１）文法Ｃ、LL（1）文法D、右线性文法

11编写一个计算机高级语言的源程序后，到正式上机运行之前，一般要经过_A_这

几步①编辑② 编译③ 连接 ④运行

A、①②③④ B、①②③ C、①③ D、①④

12、符号表的查找一般可以使用_B_：①顺序查找 ②折半查找 ③杂凑查找 ④排序查找

可选项有：A、①②③④ B、①② C、③④ D、①②③

13、语法分析的常用方法是B：①自顶向下 ②自底向上 ③自左向右 ④自右向左 可选项有：

编译原理试题

集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-

编译原理试题

一、单项选择题

1．将编译程序分成若干个“遍”是为了( B )

A．提高程序的执行效率

B. 使程序的结构更加清晰

C．利用有限的机器内存并提高机器的执行效率

D．利用有限的机器内存但降低了机器的执行效率

2．不可能是目标代码的是( D )

A．汇编指令代码 B．可重定位指令代码

C．绝对指令代码 D．中间代码

3．词法分析器的输入是( B )

A．单词符号串 B．源程序

C．语法单位 D．目标程序

4．中间代码生成时所遵循的是( C )

A．语法规则 B．词法规则

C．语义规则 D．等价变换规则

5．编译程序是对( D )

A．汇编程序的翻译 B．高级语言程序的解释执行

C．机器语言的执行 D．高级语言的翻译

6．词法分析应遵循( C )

A．语义规则 B．语法规则

C．构词规则 D．等价变换规则

7．词法分析器的输出结果是( C )

A．单词的种别编码 B．单词在符号表中的位置

C．单词的种别编码和属性值 D．单词属性值

8．正规式M1和M2等价是指( C )

A．M1和M2的状态数相等 B．M1和M2的有向弧条数相等

C．M1和M2所识别的语言集相等 D．M1和M2状态数和有向弧条数相等

9．词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，( B )

A．词法分析器应作为独立的一遍

B．词法分析器作为子程序较好

C．词法分析器分解为多个过程，由语法分析器选择使用 ．

二、编译过程通常分为哪几个主要阶段？每个阶段的主要功能？（15分）

答：编译过程通常分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个主要阶段。各个阶段的主要功能如下：

词法分析阶段：读入源程序，对构成源程序的字符流进行扫描和分解，识别出一个个单词，并表示成计算机内部的形式（TOKEN字）。

语法分析阶段：在词法分析的基础上，将单词序列分解成各类语法短语，如“表达式”、“语句”、“程序”等，确定整个输入串是否构成语法上正确的程序。

语义分析阶段：审查源程序有无语义错误，为代码生成阶段收集类型信息。

中间代码生成阶段：将源程序翻译成一种复杂性介于源程序与目标程序之间的内部形式（中间代码）。

代码优化：对前阶段产生的中间代码进行等价变换，目的是使将来生成的目标代码更为高效。

目标代码生成：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。

四、考虑以下文法:

D → T V

T → int | float

V → id ,V | id

a. 在该文法中提取左公因子。

b. 为所得的文法的非终结符构造First集合和Follow集合。

c. 说明所得的文法是LL(1)文法。

d. 为所得的文法构造LL(1)分析表

e. 假设有输入串

int x,y,z

写出相应的LL(1)分析程序的动作。

答：在看一遍消除左递归

a. 文法存在左公因子，提取左公因子后的文法为：

D → T V

T → int | float

V → id V'

V'→ ,V |ε

b. 非终结符 First集合 Follow集合

D { int , float } { $ }

T { int , float } { id }

V { id } { $ }

黑龙江大学

编译原理第1页（共7页） 编译原理

一.填空题

1.一个典型的编译程序，它一般包括八个方面的内容：

① 词法分析程序 ⑤ 代码优化程序

② 语法分析程序 ⑥ 目标代码生成

③ 语义分析程序 ⑦ 错误检查处理

④ 中间代码生成 ⑧ 信息表管理

2.编译执行和解释执行的区别在于：是否产生目标代码。

3.一个文法通常可表示成一个四元式G[S]=（VN,,VT,P,S)。

4.一个递归文法所产生的句子，其个数必然是无穷个。

5.设G[S]为一文法，由文法的开始符号S推导出的符号串称为G的

_句型_。

6.一个句型的最左_直接短语_（即规范分析中，最先被规约的子串）称为该句型的句柄。

7.Chomsky定义了四类基本的文法，分别称之为：

①0型方法(短语结构) ③2型方法(前后文无关)

②1型方法(前后文有关) ④3型方法(正规)

8.词法分析的任务就在于依次扫描输入串中的各个字符并从其中识别出一系具有独立意义的单词，我们通常把构成各个单词的字符串称为该单词的_词文。

9.一般来说各类单词的语法都能用相应的正规(3型)文法来描述。

10我们通常把一个有限自动机表示为M=(K,∑,∮,S0,Z)。

11引入具有ε动作的NFA主要目的是_把识别各类单词的有限自动机用ε失线连接起来,组成一个单一的NFA,然后把所得的NFA确定化后再据此设计编译程序的词法分析器。

12正规文法、正规式，在描述语言的意义下是的。

13状态转换图、状态矩阵、有限自动机，在识别语言的意义下是。

14状态转换图中结点没有射入矢线，终态结点没有射出矢线。

15通常构造词法分析程序的两种途径是:

① ②等价

等价的

初态

手工方式编程

借助工具自动生成

。

二.判断题

1.文法和语言之间是一一对应关系。( × )

2.设G1和G2为两个文法，若它们所产生的语言相等，即L(G1)=L(G2)，则称G1和G2等价. ( √ )

《编译原理》期末试题（九）

1．（10分）处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。

2．为语言L ＝ {ambn | 0  m  2n}（即a的个数不超过b的个数的两倍）

写一个LR（1）文法，不准超过6个产生式。（若超过6个产生式，不给分。若所写文法不是LR（1）文法，最多给5分。）

3．（10分）构造下面文法的LL（1）分析表。

D  TL

T  int | real

L  id R

R  , id R | 

4．（15分）就下面文法

S  ( L) | a L  L  S | S

 给出一个语法制导定义，它输出配对括号的个数。

 给出一个翻译方案，它输出每个a的嵌套深度。

如句子(a, (a, a) )，第一小题的输出是2，第二小题的输出是1 2 2。

5．（10分）Pascal语言for语句的含义见教材第222页习题7.13。请为该语句设计一种合理的中间代码结构。你可以按第215页图7.17的方式或者第219页图7.19的方式写出你的设计，不需要写产生中间代码的语法制导定义。

6．（5分）一个C语言程序如下：

func(i1,i2,i3)

long i1,i2,i3;

{

long j1,j2,j3;

printf("Addresses of i1,i2,i3 = %o,%o,%o\n",&i1,&i2,&i3);

printf("Addresses of j1,j2,j3 = %o,%o,%o\n",&j1,&j2,&j3);

}

main()

{

long i1,i2,i3;

func(i1,i2,i3);

}

该程序在某种机器的Linux上的运行结果如下：

Addresses of i1,i2,i3 = 27777775460,27777775464,27777775470

1 编译原理试题

一、单项选择题

1．将编译程序分成若干个“遍”是为了( B )

A．提高程序的执行效率

B. 使程序的结构更加清晰

C．利用有限的机器内存并提高机器的执行效率

D．利用有限的机器内存但降低了机器的执行效率

2．不可能是目标代码的是( D )

A．汇编指令代码 B．可重定位指令代码

C．绝对指令代码 D．中间代码

3．词法分析器的输入是( B )

A．单词符号串 B．源程序

C．语法单位 D．目标程序

4．中间代码生成时所遵循的是( C )

A．语法规则 B．词法规则

C．语义规则 D．等价变换规则

5．编译程序是对( D )

A．汇编程序的翻译 B．高级语言程序的解释执行

C．机器语言的执行 D．高级语言的翻译

6．词法分析应遵循( C )

A．语义规则 B．语法规则

C．构词规则 D．等价变换规则

7．词法分析器的输出结果是( C )

A．单词的种别编码 B．单词在符号表中的位置

C．单词的种别编码和属性值 D．单词属性值

8．正规式M1和M2等价是指( C )

A．M1和M2的状态数相等 B．M1和M2的有向弧条数相等

C．M1和M2所识别的语言集相等 D．M1和M2状态数和有向弧条数相等

9．词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，( B )

A．词法分析器应作为独立的一遍

B．词法分析器作为子程序较好

C．词法分析器分解为多个过程，由语法分析器选择使用 ．

D．词法分析器并不作为一个独立的阶段

10．如果L(M1)=L(M2)，则M1与M2( A )

试题（共10道）

1.设={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。

2.已知文法G[S’] :S’ →S

S→rD

D→D,i

D→i

(1)构造G[S’]的识别活前缀的有穷自动机DFA。

(2)该文法是LR(0)文法吗？为什么？

3.已知文法G[S’] :S’ →S (1)

S→AAA (2)

A→1A (3)

A→0 (4)

(1)构造G[S’]的识别活前缀的有穷自动机DFA。

(2)构造相应的LR(0)分析表。

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

5. 构造正规式 (0|1)*00 相应的DFA并进行化简。

6. 构造以下正规式相应的NFA，再确定化

10（1|0）*11

7. 设有语言 L={ α | α∈ {0,1} + ，且α不以 0 开头，但以 00 结尾 } 。

(1)试写出描述 L 的正规表达式；

(2)构造识别 L 的 DFA （要求给出详细过程，并画出构造过程中的

NDFA 、 DFA 的状态转换图，以及 DFA 的形式化描述 ) 。

8.已知 NFA＝（｛x,y,z｝,{0,1},M,{x},{z}），其中：M(x,0)={z}，M(y,0)={x,y}，,M(z,0)={x,z}，M(x,1)={x}，M(y,1)=φ，M(z,1)={y}，构造相应的

DFA。

9. 给出下述文法所对应的正规式：

1 编译原理试题及答案

一、对于文法 G[S] ：

S → 1A | 0B | ε A → 0S | 1AA B → 1S | 0BB

⑴ (3 分 ) 请写出三个关于 G[S] 的句子；

⑵ (4 分 ) 符号串 11A0S 是否为 G [S] 的句型？试证明你的结论。

⑶ (3 分 ) 试画出 001B 关于 G [S] 的语法树。

二、请构造一个文法，使其产生这样的表达式 E ：表达式中只含有双目运算符 + 、 * ，且 + 的优先级高于 * ， + 采用右结合， * 采用左结合，运算对象只有标识符 i ，可以用括号改变运算符优先级。要求给出该文法的形式化描述。

三、设有语言 L={ α | α∈ {0,1} + ，且α不以 0 开头，但以 00 结尾 } 。

⑴试写出描述 L 的正规表达式；

⑵构造识别 L 的 DFA （要求给出详细过程，并画出构造过程中的 NDFA 、 DFA 的状态转换图，以及 DFA 的形式化描述 ) 。

四、给定文法 G[S] ：

S → AB

A → aB | bS | c

B → AS | d

⑴ (6 分 ) 请给出每一个产生式右部的 First 集；

⑵ (3 分 ) 请给出每一个非终结符号的 Follow 集；

⑶ (8 分 ) 请构造该文法的 LL(1) 分析表；

⑷ (8 分 ) 什么是 LL(1) 文法？该文法是 LL(1) 文法吗？为什么？

五、给定文法 G[S] ：

S → SaA|a

A → AbS|b

⑴请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。

⑵请构造该文法的 LR(0) 分析表。

⑶什么是 LR(0) 文法？该文法是 LR(0) 文法吗？为什么？

⑷什么是 SLR(1) 文法？该文法是 SLR(1) 文法吗？为什么？

编译原理试题及答案

一、是非题(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。每题1分,共5分)

1、算符优先关系表不一定存在对应的优先函数。

2、数组元素的地址计算与数组的存储方式有关。

3、仅考虑一个基本块，不能确定一个赋值是否真是无用的。

4、每个文法都能改写为LL(1)文法。

5、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。

二、填空题(每题2分，共20分)

1 执行性、 说明性 2、 源程序、 单词符号 3、 任何一步αβ都是对α中最右非终结符进行替换的 4 自上而下、 自下而上 5、 一组终结符号，一组非终结符号、一个开始符号、一组产生式 6、 为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序

7、 类型、种属、所占单元大小、地址 8、 现行活动记录地址和所有外层最新活动记录的地址 9、 栈式、 堆式 10、 语法范畴

1、从功能上说，程序语言的语句大体可分为_______语句和______语句两大类。

2、扫描器的任务是从________中识别出一个个_______。

3、所谓最右推导是指：_______。

4、语法分析最常用的两类方法是________和_________分析法。

5、一个上下文无关文法所含四个组成部分是_______________。

6、所谓语法制导翻译方法是_____________________。

7、符号表中的信息栏中登记了每个名字的有关的性质，如_________等等。

8、一个过程相应的DISPLAY表的内容为________。

9、常用的两种动态存贮分配办法是_____动态分配和_____动态分配。

10、产生式是用于定义_____的一种书写规则。

三、名词解释(每题2分，共10分)

1、遍

2、无环路有向图(DAG)

3、语法分析

4、短语

5、后缀式

四、简述题(每题4分，共24分)

1、考虑下面程序

《编译原理》期末试题（一）

一、是非题（请在括号内，正确的划√，错误的划×）（每个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．( ) 最左推导和最右推导必定相同

第1页共6页 1、 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。

2、写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。

3、写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。

4、已知文法G(S)及相应翻译方案

S→aAb {print “1”}

S→a {print “2”}

A→AS {print “3”}

A→c {print “4”}

输入acab, 输出是什么？

5、 已知文法G(S)

S→bAa

A→(B | a

B→Aa)

写出句子b(aa)b的规范归约过程。

6、已知文法G[S]

S→S*aF | aF | *aF

F→+aF | +a

消除文法左递归。

1、设文法G(S):

S→^ | a | (T)

T→T,S | S

⑴ 消除左递归；

⑵ 构造相应的FIRST和FOLLOW集合；

⑶ 构造预测分析表

2.语句 if E then S

(1) 改写文法，使之适合语法制导翻译；

(2) 写出改写后产生式的语义动作。

4.设某语言的for语句的形式为

for i:＝E(1) to E(2) do S

其语义解释为

i:＝E(1)

LIMIT:＝E(2)

again: if i＜＝LIMIT then

Begin

S;

i:＝i＋1

goto again

End;

（1）写出适合语法制导翻译的产生式；

（2）写出每个产生式对应的语义动作。

7.已知文法G(S)

S→a | ^ | (T)

T→T,S | S

(1) 给出句子(a,(a,a))的最左推导；

(2) 给出句型((T,S),a)的短语, 直接短语，句柄。

8.对于 C 语言do S while E语句

第2页共6页 (1)改写文法，使之适合语法制导翻译；

历年试题及答案

一． （每项选择2分，共20分）选择题 1．将编译程序分成若干个“遍”是为了_b__。 a.提高程序的执行效率 b.使程序的结构更加清晰 c.利用有限的机器内存并提高机器的执行效率 d.利用有限的机器内存但降低了机器的执行效率 2．构造编译程序应掌握__d__。 a.源程序 b.目标语言 c.编译方法 d.以上三项都是 3．变量应当c＿。 a.持有左值 b.持有右值 c.既持有左值又持有右值 d.既不持有左值也不持有右值 4．编译程序绝大多数时间花在_d___上。 a.出错处理 b.词法分析 c.目标代码生成 d.管理表格 5．词法分析器的输出结果是_c___。 a.单词的种别编码 b.单词在符号表中的位置 c.单词的种别编码和自身值 d.单词自身值 6．正规式MI和M2等价是指__c__。 a. MI和M2的状态数相等 b.Ml和M2的有向弧条数相等。 C.M1和M2所识别的语言集相等 d. Ml和M2状态数和有向弧条数相等 7．中间代码生成时所依据的是—c。 a．语法规则 b．词法规则 c．语义规则 d．等价变换规则 8．后缀式ab+cd+/可用表达式__b_来表示。 a． a+b/c+d b． (a+b)/(c+d) c． a+b/(c+d) d． a+b+c/d 9．程序所需的数据空间在程序运行前就可确定，称为____c_＿管理技术。 a.动态存储 b.栈式存储 c.静态存储 d.堆式存储 10.堆式动态分配申请和释放存储空间遵守___d____＿原则。 a.先请先放 b.先请后放 c.后请先放 d.任意 二（每小题10分，共80分）简答题 1.画出编译程序的总体结构图，简述各部分的主要功能。 2. 已知文法G[E]: E→ET+|T T→TF* | F F→F^ | a 试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄. 3．为正规式(a|b) *a(a|b)构造一个确定的有限自动机。 4． 设文法G(S)： S→(L)|a S|a L→L，S|S (1) 消除左递归和回溯；