编译原理 试题及答案

课程测试试题（04A卷）

I、命题院（部）：数学与计算机科学学院

II、课程名称：编译原理

III、测试学期：2006－2007 学年度第1 学期

IV、测试对象：数计、国交学院计科专业2004 级1、2、国交班

V、问卷页数（A4）：3 页

VI、答卷页数（A4）：4 页

VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）

VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）

一、填空题（共30分，30个空，每空1分）

1、典型高级程序设计语言编译系统的工作过程一般分为六个阶段，即词法分析、语法分析、语义分析、中间代码生成、、目标代码生成。编译阶段的两种组合方式是组合法和按遍组合法，这两种组合方式的主要参考因素都是的特征。

2、Chomsky将文法按其所表示语言的表达能力，由高往低分为四类：0型，1型，2型，3型文法。其中，2型文法也称，它的所有规则α→β 都满足：α∈，β∈ ((V N∪V T) *且，仅当β= ε时例外。

3、现代编译系统多采用方法，即在语法分析过程中根据各个规则所相联的或所对应的语义子程序进行翻译的办法。该方法使用为工具来说明程序设计语言的语义。

4、构造与NFA M等价的正规文法G的方法如下：（1）对转换函数f(A，a)=B或f(A，ε)=B，改成形如或的产生式；（2）对可识别终态Z，增加一个产生式：。

5、代码生成要考虑的主要问题：充分利用的问题、选择的问题、选择的问题。

6、设有穷自动机M=(K，∑，f，S，Z)，若当M为时，满足z0∈f(S，α)且z0∈Z，或当M为时，满足f(S，α)=P∈Z，则称符号串α∈∑*可被M所。

7、符号表中每一项对应一个多元组。符号表项的组织可分为组织、组织、组织等。

8、对于A∈?ＶN 定义A的后续符号集：FOLLOW(A)={a|S=*>uAβ，a∈ＶT，且a∈，u∈ＶT*，β∈Ｖ+;若，则#∈FOLLOW(A)。也可以定义为：FOLLOW(A)={a|S=*>…Aa…，a∈ＶT}。若有，则规定#∈FOLLOW(A)。

9、基本块的定义：一个基本块是指程序中一个执行的语句序列，其中只有一个入口和一个出口。入口是程序第一个语句或转移语句的目标语句，或转移语句的后继第一个语句。出口是程序或转移语句。在基本块范围内的优化称为。

10、预测分析器由预测分析表、先进后出栈（用来存放分析过程的语法符号）和三部分组成。其中预测分析表是一个二维矩阵，其形式为M[A，a]，其中A∈V N，a∈V T或#。若有产生式A→α，使得a∈，则将A→α填入M[A，a]中。(书写时，通常省略规则左部，只填→α)。对所有的M[A，a]标记为出错。

二、简述题（共20分，4个小题，每小题5分）

1、简述将NFA转换为最小化DFA的步骤。

2、简述静态存储分配、栈式存储分配和堆式存储分配的特点和主要用途。

3、以表达式 a:=b*(-c)+b/(-d)为例，简述常用的三种中间代码表示形式。

4、简述判别文法Ｇ是否为LL(1)文法的步骤和将一个非LL(1)文法转换为LL(1)文法的方法。

三、应用题（共50分）

1、有文法G[S]：(12分)

S→aAS|a A→SbA|SS|ba

(1)证明aabbaa是文法的一个句子。(3分)

(2)构造句子aabbaa的语法树。(3分)

(3)指出该句子的所有短语、直接短语和句柄。(6分)

2、对文法G[E']：(15分)

E'→#E# E→E+T|T T→T*F|F F→P^F|P P→(E)|i

(1)计算G[E']的FIRSTVT和LASTVT。(5分)

(2)构造G[E']的算符优先关系表,并说明G[E']是否为算符优先文法。(5分)

(3)给出输入串w=i+i# 的算符优先分析过程。(5分)

3、对以下基本块：（8分）

A：=5 B：=R+r T0：=A+B T1：=2*A

T2：=B+A T3：=A+A X1：=T1+T2 X2：=T0*T3（1）画出基本块的DAG图。(3分)

（2）根据DAG结点原来的构造顺序重写四元式。(2分)

（3）假设基本块出口后只有X1，X2还被引用，试写出优化后的四元式序列。(3分)

4、对文法G[S’]： (15分)

0)S’→S 1)S →A 2)S →B 3)A →aAe

4)A →a 5)B →bBd 6)B →b

(1)试构造G[S’]的LR(0)项目集规范族DFA。(4分)

(2)试构造G[S’]的SLR(1)分析表，并判断它是否为SLR(1)文法。(4分)

(3)试用SLR（1）方法分析输入串aae#。(4分)

(4)G[S’]是否为LR(0)、LR(1)和LALR(1)文法？为什么？(3分)

课程测试试题（04B卷）

I、命题院（部）：数学与计算机科学学院

II、课程名称：编译原理

III、测试学期：2006－2007 学年度第1 学期

IV、测试对象：数计、国交学院计科专业2004 级1、2、国交班

V、问卷页数（A4）：3 页

VI、答卷页数（A4）：4 页

VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）

VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）

一、填空题（共30分，30个空，每空1分）

1、典型编译过程一般分为词法分析、语法分析、语义分析、（并非所有的编译程序都包含此阶段）、代码优化、目标代码生成六个阶段，其中词法分析的任务是对构成源程序的字符串进行扫描和分解，识别出(如标识符等)符号；为代码生成阶段收集类型信息，并进行类型审查和违背语言规范的报错处理是的任务。

2、文法是一些规则的有穷集合，它是以有穷规则集来刻划无穷集合的工具。文法的四元组表示G =（V N，V T，P，S）中，元素V N，V T 分别是非空有限的。且二者交集为φ；P为产生式/规则集，是文法的核心部分；S ∈ V N，是文法的开始符号(或识别符) ，它是一个非终结符，至少要在一条规则中作为出现。

3、构造ＬＲ（０）项目集规范族的项目类型分为四种：形如A→α.aβ的、形如

的待约项目、形如A→αBβ.的归约项目、形如S'→α.的。

4、一个优先关系矩阵对应的优先函数；所表示优先关系唯一的矩阵不一定存在优先函数；当两个终结符对之间无优先关系时，可以将相应元素置出错信息，而使用却无法识别这种情况，不能准确指出出错位置。

5、在编译程序中用符号表来存放语言中出现的有关的语义特征属性信息。程序设计语言中通用的标识符属性主要有如下几种：符号名、符号的、符号的存储类别、符号的、符号变量的存储分配信息及数组的内情向量等其它属性。

6、如果文法G=（V N，V T，P，S）中不存在形如A→…BC…的产生式，其中B、C 为非终结符，则称之为。在此基础上，如果 a,b∈VT, a≡b,a≮b,a≯b 至有一个成立，则称之为。

7、分为三类：的机器语言代码；的机器语言代码；汇编语言（宏汇编）。

8、在程序流中，一个循环必须具有以下性质：1），即序列中任意两点都可达，若只有一个结点，则有一条返回本身的回边；2），即从序列外某结点，有一条有向边指向它，或它为图中首结点。

9、LR分析步骤：1）置输入指针ip指向输入串的第一个符号；令S是栈顶状态，a 是ip 所指向的符号;将#压入符号栈，将开始状态0压入状态栈；2）根据分析表重复执行如下过程：如果action[S，a]=S j，则把入符号栈，把入状态栈，并使ip 指向下一个输入符号；如果action[S,a]=r j，则从栈顶弹出第j条规则右部串长|β|个符号，把压入符号栈，将压入状态栈，并输出规则A→β；如果action[S,a]=acc，则分析成功，否则报错。

10、过程(函数)是结构化程序设计的主要手段。调用与被调用过程两者之间的信息主要通过或参数来传递。参数分为，常用的参数传递方式有传地址、传值、传名等。

二、简述题（共20分，4个小题，每小题5分）

1、简述运行目标程序时所需空间的种类。

2、简述算符优先分析算法的步骤和算符优先分析方法的优、缺点。

3、简述代码优化的概念和分类，并列举出四种以上常用的代码优化技术。

4、简述判别任意给定的一个上下文无关文法G[S]是否为LALR(1)文法的过程。

三、应用题（共50分）

1、有文法G[E]：(16分)

E → T + E｜T T → T * F｜

F F → ( E )｜i

(1)证明T+T*F+i是文法的一个句型。(3分)

(2)构造型T+T*F+i的语法树。(3分)

(3)指出该句型的所有短语、直接短语和句柄。(7分)

(4)指出该句型的所有素短语和最左素短语。(3分)

2、将下列条件语句翻译成四元式的中间代码形式：(6分)

if af then s1 else s2

3、有正规文法G[S]：(12分)

S→aA|bB A→bS|b B→aS|a

(1)构造对应的正规式R，使得L(R)=L(G)。(3分)

(2)构造对应的NFA状态图，使得L(M)=L(R)。(3分)

(3)将所得NFA确定化为DFA。(3分)

(4)将所得DFA最小化。(3分)

4、对表达式文法G[E]：(16分)

E → E - T｜T T → T ^ F｜

F F → ( E )｜a

(1)判断G[E]是否为LL(1)文法。若不是，改造为LL(1)文法。(8分)

(2)构造预测分析表，并对输入串w=a-a^a#进行预测分析。(8分)

课程测试试题（03A 卷）

----------------------以下为教师填写--------------------

I 、命题院（部）： 数学与计算机科学学院

II 、课程名称： 编 译 原 理

III 、测试学期：2005－2006学年度第1学期

IV 、测试对象： 数计 学院 计算机科学技术 专业 2003 级 1、2、3 班 V 、问卷页数（A4）： 4 页

VI 、答卷页数（A4）： 6 页

VII 、考试方式： 闭卷 （开卷、闭卷或课程小论文，请填写清楚）

VIII 、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）

一、填空 （30分）

1、将编译过程的各阶段划分为前端或后端和将编译程序分遍的主要参考因素都是（ ）和（ ）的特征。

2、（ ）是一种语法分析程序的自动构造工具，用它可以直接构造各种语言的语法分析器；而（ ）是一种词法分析程序的自动构造工具，用它可以直接构造各种语言的词法分析器。

3、假设G[S]是一个文法,如有S *x,则称x 是该文法G 的（ ）；文法G 产生的（ ）的全体称为该文法所描述的语言。

4、所谓2型文法就是指（ ）文法，若用G =（V N ，V T ，P ，S ）表示它，则它要求G 中的所有规则α→β都满足：α是（ ），而β属于（V N U V T ）*。

5、文法中形如U →U 的规则称为（ ）规则；由不可达的非终结符或不可终止的非终结符作为左部的规则称为（ ）规则。在实用文法中一般不允许含有这两类规则。

6、在用五元组表示的确定的有穷自动机DFAM=（K ，V ，F ，S ，Z ）中，元素V 表示字母表；元素S 表示唯一的初态，它是状态集K 的一个元素；元素F 表示（ ）；元素Z 表示终态集，它是状态集K 的一个（ ）。

7、语法分析方法分为自上而下与自下而上两类，自上而下的分析方法方要有递归子程序分析法和（ ）；而自下而上的分析方法主要有（ ）和LR 分析方法。

8、LR(0)项目集规范族中的项目可分为四类，它们是移进项目、（ ）、归约

项目和接受项目。其中，接受项目是（）的一种特例。

9、将非LL(1)文法转换为等价的LL(1)文法所采用的两种方法是（）和（）。但这两种方法并不能保证所有的非LL(1)文法都能转换为等价的LL(1)文法。

10、通常局部优化是指基本块内的优化，所谓基本块是指程序中一顺序执行的语句序列，其中只有一个（）语句和一个（）语句。

11、算符优先分析时，在句型N1a1N2…a i-1N i a i N i+1a i+1…a j N j+1a j+1N j+2…中，寻找的最左素短语N i a i N i+1a i+1…a j N j+1中的终结符应满足下优先关系：（）、（）、（）。

12、在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。符号表的功能可以归结为三个主要方面，即（）、作为上下文语义合法性检查的依据和作为（）的依据。

13、根据优先关系矩阵计算优先函数可用迭代法或优先关系图法，但先关系图方法计算出来的优先函数不一定有效，当（）时，所得的优先函数无效，这时也说明该优先关系矩阵不存在优先函数。

14、当一个过程调用其他过程时，调用过程和被调用过程之间的通信经由非局部变量或者经由参数传递，常用的参数传递方式有（）、（）等。

15、现代很多编译程序都采用（）翻译方法，它是指在语法分析过程中，随着分析的步步进展，根据每个规则所对应的语义子程序或语义动作进行翻译的办法。这种方法使用（）为工具来说明程序设计语言的语义。

二、结合你所熟悉的一门高级语言的编译系统，简述典型编译程序在各个工作阶段的任务。(共7分)

三、给定正规式R=(01|10) (01|10)* ，要求： (10分)

1、构造对应的正规文法G，使得L(G)=L(R)。 (4分)

2、构造对应的NFA M状态图，使得L(M)=L(R)。 (3分)

3、将所得NFA M确定化为DFA。 (3分)

四、现有文法G[E]： (共10分)

E→E+T|E-T|T

T→T*F|T/F|F

F→i|(E)

1、证明：E-F*(i)是文法的一个句型。(3分)

2、构造句型E-F*(i)的语法推导树。(2分)

3、指出该句型所有短语、直接短语和句柄。(5分)

五、任意给定一个文法G[S]： (10分)

1、给出判断G[S]是否为LL(1)文法的步骤。(4分)

2、如果G[S]是LL(1)文法，怎样构造它的预测分析表？(3分)

3、怎样根据预测分析表对给定的某个输入串进行预测分析？(3分)

六、现有文法G[E]：(共15分)

E → E;D|D

D→D(T)|H

H→a|(E)

T→T*E|E

1、计算G[E]的FIRSTVT和LASTVT；(4分)

2、构造G[E]的算符优先关系表,并说明G[E]是否为算符优先文法；(5分)

3、给出输入串(a*a)# 的算符优先分析过程，并据此说明算符优先分析方法的优点和缺点。(6分)

七、现有文法G[S’]： (共18分)

0) S' → S

1) S → L = R

2) S → R

3) L → * R

4) L → i

5) R → L

1、构造G[S’]的LR(0)项目集规范族DFA，并据此判断G[S’]是否为LR(0) 文

法或SLR(1)文法。(6分)

2、构造G[S’]的LR(1)项目集规范族DFA，并据此判断G[S’]是否为LR(1)文

法或LALR(1)文法。(6分)

3、给出相应的LALR(1)分析表。(3分)

4、简述LR分析算法。(3分)

课程测试试题（03B卷）

----------------------以下为教师填写--------------------

I、命题院（部）：数学与计算机科学学院

II、课程名称：编译原理

III、测试学期：2005－2006学年度第1学期

IV、测试对象：数计学院计算机科学技术专业2003 级1、2、3 班

V、问卷页数（A4）：4 页

VI、答卷页数（A4）：6 页

VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）

VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）

一、判断（15分）

1、编译程序是一种语言翻译程序，它将源语言程序翻译成功能等价的目标语言程序。

2、所谓规则或产生式是指形如α→β或α::=β的(α,β)有序对，其中α是字母表V的正闭包元素,而β是字母表V的闭包元素。

3、设文法G =（V N，V T，P，S），若P中的每一个规则都是A→aB或A→a，其中A和B是非终结符，而a是终结符，则称此文法G为正规文法或3型文法。

4、实用文法中不得含有形如U→U的有害规则，也不得含有由不可达或不可终止的非终结符所构成的多余规则。

5、对任意给定的一个正规式R，都可以将它转换为与之功能等价的正规文法，或与之功能等价的有穷自动机。

6、LEX是一个用于构造各种各样语言的词法分析程序；YACC是一个用于构造各种各样语言的语法分析程序。

7、假设现有五元组表示的有穷自动机M=（K，V，F，S，Z），若M是NFA，则S表示初态，且S具有唯一性，它是状态集K的一个元素。

8、算符优先分析方法和LR分析方法都是自下而上的分析方法，它们的分析

过程实际上就是规范归约过程。

9、LR(0)项目集规范族中的项目由两部分构成，一部分是心，即原来的LR(1)项目，另一部分是向前搜索符号集。

10、所谓优化实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前的代码运行结果相同，但运行速度或占用的存储空间加大。常用的优化技术有删除多余运算、代码外提、强度削弱、变换循环控制条件、合并已知变量与复写传播等。

11、对一个不包含空规则的算符文法，如果文法中的任意两个终结符构成的符号对之间最多只有大于、小于和等于三种优先关系中的一种成立，则称该算符文法为算符优先文法。

12、目标程序运行时的动态数据存储区分为堆区和栈区，它用于存放可变数据以及管理过程活动的控制信息。

13、在语法分析过程中，随着分析的步步进展，根据每个规则所对应的语义子程序或语义动作进行翻译的办法，称为语法制导翻译，它被现代很多编译程序所采用。

14、可归前缀本身就是活前缀，它是包含句柄在内的活前缀。

15、符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。

二、将表达式A:=B*（C-D）/D： (共9分)

3、翻译成逆波兰式的中间代码形式。(2分)

4、翻译成四元式的中间代码形式。(4分)

5、将译成的四元式用DAG表示。(3分)

三、现有文法G[E]： (共12分)

E→E+T|E-T|T

T→T*F|T/F|F

F→i|(E)

6、证明：F+T*(E)是文法的一个句型。(3分)

7、构造句型F+T*(E)的语法推导树。(3分)

8、指出该句型所有短语、直接短语和句柄。(6分)

四、给定正规式R=d(a|bc)*d，要求： (12分)

4、构造对应的NFA M状态图，使得L(M)=L(R)。 (4分)

5、将所得NFA M确定化和最小化。 (8分)

五、现有文法G[S]：(共16分)

S →S;D|D

D →D(T)|H

H →m|(S)

T →T*S|S

1、计算G[S]的FIRSTVT和LASTVT；(4分)

2、构造G[S]的算符优先关系表,并说明G[S]是否为算符优先文法；(6分)

3、给出输入串(m*m)# 的算符优先分析过程。(4分)

4、根据分析过程总结算符优先分析方法的优缺点。(2分)

六、已知G[S]： (18分)

S→(A)|a|b

A→A,S|S

1、给出(a,(b,b))的最左推导。(3分)

2、判断该文法是否为LL(1)文法。若是，直接给出它的预测分析表；若不是，先将其改写为LL(1)文法，再给出它的预测分析表；(10分)

3、给出输入串(b,b)#的分析过程，并说明该串是否为G[S]的句子。(5分)

七、对给定文法G[S’]: (共18分)

0) S’→S

1) S →A

2）S →B

3) A →aAc

4) A →a

5) B →bBd

6) B →b

5、构造G[S’]的LR(0)项目集规范族DFA，并据此判断G[S’]是否为LR(0)文

法。 (6分)

6、进一步判断G[S’]是否为SLR(1)文法，并给出对应的SLR(1)分析表。(6分)

3、给出输入串bbd#的SLR(1)分析过程。(4分)

4、判断G[S’]是否为LR(1)文法和LALR(1)文法。 (2分)

编译原理课程测试试卷评分标准

（数计学院04计科A卷）

一、填空题参考答案（共30分，30个空，每空1分）

题号 1 2 3 4

参考答案代码优化、前后端、

源语言与目标机器

上下文无关文法、V N、|

β|>=|α|

语法制导翻译、语

义动作、属性文法

A→aB、A→B、

Z→ε

题号 5 6 7 8

参考答案寄存器、计算机指令

系统、计算次序

NFA、DFA、接受(识别)线性、排序、散列

FIRST(β)、β=*>ε、

S=*>…A

题号9 10

参考答案顺序、最后一个语句、

局部优化

预测分析程序、

SELECT(A→α)、没有值

说明：各个答案可有不同表达方式，只要意思相同即可。

二、简述题参考答案（共20分，4个小题，每小题5分）

1、第一步：将NFA确定化。用造表法将NFA确定化过程如下：

(0)表的第0行和第0列作标识行列的值。

(1) 将ε-closure(I)作为表中第1行第1列。

(2) 假定 ={a1，a2，...an}，设第i行第一列已确定状态集为I，则置该行第i列为Iai，如Iai未曾在任何行第一列出现过，则将Iai加入下一空行i+1的第一列，并在第0列标记为Ti+1。

(3) 反复重复第(1) 步，直至无新状态出现为止。

(4) 重新命名新状态。（3分）

第二步：将DFA最小化。DFA最小化具体过程：用子集分割法将不含多余状态的DFA 分成一些不相交的子集，使得任何两个不同的子集中的状态都是可区别的，而相同子集中状态是等价的。分割时，首先将DFA状态分成终态子集和非终态子集，再根据输出弧所达到状态的性质逐步细分。（2分）

2、（1）静态存储分配的特点：编译时刻确定存储位置；访问效率高。主要用途：子程序的目标代码段、全局数据目标（全局变量）。（2分）

（2）栈（Stack）式存储分配的特点：嵌套调用次序、先进后出、生存期限于本次调用、自动释放。用途：过程的局部环境、活动记录。（1分）

（3）堆（Heap）式存储分配的特点：将内存空间分为若干块，根据用户要求分配；无法满足时，调用无用单元收集程序将被释放的块收集起来重新分配。主要用途：用于动态数据结构：存储空间的动态分配和释放。（2分）

3、（1）逆波兰式：abc-*bd-/+:= 。（1分）

（2）三元式：①(- , c , _ ) ②(* , b ,① ) ③(- , d , _ )

④(/ , b ,③ ) ⑤(+ ,② ,④ ) ⑥(:= ,③ ,a )。（2分）

（3）四元式: ①(- , c , _ ,t1) ②(* , b ,t1 ,t2) ③(- , d , _ ,t3)

④(/ , b ,t3 ,t4) ⑤(+ ,t2 ,t4 ,t5) ⑥(:= ,t5 ,_ , a)。（2分）

4、（1）判别步骤：先画出各非终结符能否推导出ε的情况表；然后，用定义法或关系图法计算FIRST、FOLLOW集；再计算各规则的SELECT集；最后，根据同一个左部的规则其SELECT集是否相交来判断给定文法是否为LL(1) 文法。（3分）

（2）将非LL(1) 文法转换成LL(1) 文法的两种主要方法：提取左公共因子、消除左递归。（2分）

三、应用题参考答案（共50分）

1、（1）证明(3分)：因为存在推导序列S=>aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa，即有S=*>aabbaa成立，所以，是文法的一个句子。

（2）语法树（3分）：

（3）句型分析（6分）：将句型改写为a1a2b1b2a3a4，则：该句型相对于S的短语：a1a2b1b2a3a4和a4；相对于A的短语：a2b1b2a3和b2a3；对于S→a的直接短语：a2，a4；相对于A→ba的直接短语：b2a3；句柄：a2。

2、(1)计算G[E']的FIRSTVT和LASTVT集如下：(5分)

(2)构造G[E']的算符优先关系表如下：(4分)

由上表可知G[E']是算符优先文法(1分)。

(3)输入串w=i+i# 的算符优先分析过程如下：(5分)

3、（1）基本块的DAG图如下：(3分)

（2）根据DAG结点原来的构造顺序重写四元式如下：(2分)

A ：=5 T1=10 T3=10

B ：=R+r

T0：=A+B T2：=T0 X1：=T0+T1 X2：=T0*T1

（3）假设基本块出口后只有X1，X2还被引用，则通过重新命名临时变量的基本块保结构变换，可将基本块的四元式代码进一步优化为：(3分)

C ：=R+r

D ：=5+C X1：=D+10 X2：=D*10

4、0)S ’→S 1)S →A 2)S →B 3)A →aAe

4)A →a 5)B →bBd 6)B →b

(1)G[S ’]的LR(0)项目集规范族DFA 如下：(4分)

(2)由于，得G[S ’]的SLR(1)分析表如下：(3分)

由上左表可知G[S ’]是SLR(1)文法（1分）。

(3)用SLR （1）方法分析输入串aae#过程如上右表所示：(4分)

(4)由于G[S ’]LR(0)项目集规范族DFA 中I 4、T 5中都包含有移进—归约冲突，所以G[S ’]

不是LR(0)文法，由于G[S ’]是SLR(1)文法故一定是LR(1)和LALR(1)文法。(3分)

编译原理课程测试试卷评分标准

（数计学院04计科B 卷）

一、填空题参考答案（共30分，30个空，每空1分） 题号

1 2 3 4 参考

答案 中间代码生成、单词、语义分析 句子、非终结符号集和终结符集、左部 移进项目、A→α.Bβ、接受项目 不唯一、优先矩阵、优先函数 题号

5 6 7 8 参考

答案 标识符、类型、作用域和可视性、 算符文法、多、算符优先文法 目标代码、已定位、可重定位 强连通、有且只有一个入口结点 题号 9 10

参考答案 符号a 、状态j 、归约得到的非终结符A 、goto[S,a]

的值j

全局变量、形参和实参

说明：各个答案可有不同表达方式，只要意思相同即可。

二、简述题参考答案（共20分，4个小题，每小题5分）

1、运行目标程序时所需空间分为两种容纳目标代码的空间和目标代码运行时的数据空间。（2分）

目标代码运行时的数据空间中某些部分无法在编译时确定存储位置，它主要包括：

用户所定义的变量和常量所需空间、中间结果及参数传递所需的临时单元、调用过程时的连接单元、I/O操作所需缓冲区。（3分）

2、（1）算符优先分析算法的步骤：（3分）

设单元a中存放当前输入符，S为一个符号栈，则：

1) 将当前输入符存放到a中，将#入符号栈。

2) 将栈顶第一个终结符b与a比较。如果b≡a ，而b== #且栈中只剩一个非终结符时，则成功；否则a入栈；如果b≮a,则a入栈；如果b≯a,在栈顶寻找最左素短语，并将最左素短语归约为一个非终结符；如果文法中找不到相应规则，则出错；

3) 重复(2) 至成功或失败。

（2）算符优先分析方法的优、缺点：（2分）

由于只考虑终结符之间的优先关系确定句柄，所以效率高；由于去掉了单非终结符之间的归约，有可能将错误的句子识别为正确的，只适用于表达式的语法分析。

3、所谓优化实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前的代码运行结果相同，但运行速度或占用的存储空间加大。（1分）

代码优化按阶段分中间代码优化和目标代码优化，按程序范围分为局部基本块优化、循环优化、全局优化。（2分）

常用的优化技术有删除多余运算、代码外提、强度削弱、变换循环控制条件、合并已知变量与复写传播等。（2分）

4、判别任意给定的一个上下文无关文法G[S]是否为LALR(1)文法的过程：

（1）将G[S]加入一条规则：S’ →S G[S’]拓广为G[S’]，然后构造G[S’]的LR(0)项目集规范族DFA。检查DFA的项目集中有无移进—归约冲突或归约—归约冲突，若无，则G[S’]是LR(0)文法，也是LALR(1)文法。（1分）

（2）如果DFA的项目集中有无移进—归约冲突或归约—归约冲突，通过考虑归约项目左部非终结符的FOLLOW集能够解决这两类冲突，则G[S’]是SLR(1)文法，也是LALR(1)文法。（2分）

（3）如果通过考虑归约项目左部非终结符的FOLLOW集还有不能够解决的移进—归约冲突，通过考虑后跟符号来构造G[S’]的LR(1)项目集规范族DFA。如果冲突可以解决，则G[S’]是LR(1)文法。进一步合并LR(1)项目集规范族中同心集，如果依然不产生归约—归约冲突，则G[S’]是LALR(1)文法。（3分）

三、应用题参考答案（共50分）

1、（1）证明(3分)：因为存在推导序列：E=>T+E=>T+T+E=>T+T*F+E=>T+T*F+T =>T+T*F+F=>T+T*F+i，即有E=*>T+T*F+i成立，所以，T+T*F+i是文法的一个句型。

（2）语法树（3分）：

（3）句型分析（7分）：该句型相对于E的短语：T+T*F+i、T*F+i和i ；相对于T的短语有：T*F和i，相对于F的短语有i。相对于T→T*F的直接短语：T*F,相对于F→i的直接短语：i。句柄：T*F。

(4) 该句型的所有素短语：T*F和I；T*F为最左素短语。(3分)

2、if af then s1 else s2生成的三地址代码/四元式序列如下：(6分)

(1) if a < b goto (7)

(2) goto (3)

(3) if c < d goto (5)

(4) goto (p+1)

(5) if e > f goto (7)

(6) goto (p+1)

(7) s1对应的四元式序列

…

(p) goto (q)

(p+1) s2对应的四元式序列

…

(q)

3、(1)代入后有S的规则右部=a（bS|b）|b(aS|a)=ab（S|ε）|ba（S|ε）=（ab|ba）（S|ε）,故对应的正规式R=(ab|ba)(ab|ba)*。(3分)

(2)对应的NFA状态图如下左图所示：(3分)

(3)将所得NFA确定化为DFA状态图如上右图所示：(3分)

(4)将所得DFA最小化：首先根据是否终态划分为非终态集P1={S,A,B}和终态集P2={Z}；然后对P1根据a弧划分为P11={S},P12={A}，P13={B}。可见原DFA已是最小化的DFA。(3分)

4、(1)计算G[E]的SELECT集如下：(2分)

SELECT(E→ E– T )={(，a} SELECT(E→ T )=={(，a}

SELECT(T→ T ^ F)={(，a} SELECT(T→ F)={(，a}

SELECT(F → ( E ))={( } SELECT(F → a)={a}

由于SELECT(E→ E–T ) ∩ SELECT(E→ T )=={(，a}≠φ；

SELECT(T→ T ^ F) ∩ SELECT(T→ F)={(，a}≠φ；

SELECT (F →( E ))∩SELECT (F →a) = {(}∩{a} =φ

故G[E]不是LL((1) 文法。(1分)

对G[E]的E → E – T和T → T ^ F两条规则消除左递归后变为：(2分)

E→T E’E’→–T E’|εT→ F T’T’→ ^ F T’｜εF→ ( E )｜a

计算消除左递归后G[E]的SELECT集如下：(2分)

SELECT(E→ T E’)={(，a} SELECT(E’→ –T E’)={– }

SELECT(E’→ε)={#，)} SE LECT(T→ F T’)={(，a}

SELECT(T’→ ^ F T’)={ ^} SELECT(T’→ε)={–，#，)}

SELECT(F→( E ))={(}SELECT(F→a)={a}

由于SELECT(E’→–T E’)∩SELECT (E'→ε) =φ

SELECT (T'→ ^ F T') ∩SELECT (T'→ε) =φ

SELECT (F →( E ))∩SELECT (F →a) = =φ

故消除左递归后的G[E]是LL((1) 文法。(1分)

（2）根据消除左递归后的G[E]的SELECT集构造预测分析表如下：(3分)

对输入串w=a-a^a#的分析过程如下表所示（注意：规则右部以逆序入栈）：(5分)

编译原理期末考试习题及答案

一、填空题|（每题4分，共20分） 1. 乔母斯基定义的3型文法（线性文法）产生式形式 A→Ba|a,或A→aB|a，A，B∈Vn, a,b∈Vt 。 2.语法分析程序的输入是单词符号，其输出是语法单位。 3 型为 B → .aB 的LR（0）项目被称为移进项目，型为 B → a.B 的LR（0） 项目被称为待约项目， 4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。 5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。 二.已知文法 G(S) (1) E → T | E+T (2) T → F | F*F (3) F →（E）| i （1）写出句型（T*F+i）的最右推到并画出语法树。（4分） （2）写出上述句型的短语，直接短语和句柄。（4分） 答：（1）最右推到（2分） E ==> T ==> F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i) (2) 语法树（2分） （3）（4分） 短语：（T*F+i），T*F+i ，T*F ， i 直接短语：T*F ， i 句柄：T*F 三. 证明文法G(S) ：S → SaS |ε是二义的。（6分） 答：句子aaa对应的两颗语法树为：

因此，文法是二义文法 四.给定正规文法G（S）： (1) S → Sa | Ab |b (2) A → Sa 请构造与之等价的DFA。（6分） 答：对应的NFA为：（6分） 状态转换表： a b {F} Φ{S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分） a b {0} {1，3} {0} {1,3} Φ{2，3} {2,3} {1,3} {2,3} （5分） 六. 已知文法G(S) : (1) S → ^ | a | (T) (2) T → T,S | S 试：（1）消除文法的左递归；（4分） （2）构造相应的first 和 follow 集合。（6分） 答：（1）消除文法的左递归后文法 G’（S）为： (1) S → ^ | a | (T)

编译原理试题(卷)汇总-编译原理期末试题(卷)(8套含答案解析-大题集)

编译原理考试题及答案汇总 一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 12．编译程序是一种___C__。 A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 13．文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __D___。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式 16．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_C____。

(精选)编译原理期末考试题目及答案

一、填空题（每空2分，共20分） 1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2．编译器常用的语法分析方法有自底向上和自顶向下两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 5．对编译程序而言，输入数据是源程序，输出结果是目标程序。 1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4．一个LL（1）分析程序需要用到一张分析表和符号栈。 5．后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题（每小题2分，共20分） 1．词法分析器的输出结果是__C。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 2．正规式 M 1 和 M 2 等价是指__C_。 A． M1和M2的状态数相等B． M1和M2的有向边条数相等 C． M1和M2所识别的语言集相等 D． M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_C____。 A． xyx B． (xyx)* C．xnyxn(n≥0) D． x*yx* 4．如果文法G是无二义的，则它的任何句子α_A____。 A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。 A．源程序B．目标语言 C．编译方法 D．以上三项都是 6．四元式之间的联系是通过__B___实现的。 A．指示器B．临时变量C．符号表 D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧C． AB∨┐CD∨∧ D．A┐B∨∧CD∨8. 优化可生成__D___的目标代码。 A．运行时间较短B．占用存储空间较小 C．运行时间短但占用内存空间大 D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱 B．删除归纳变量C．删除多余运算 D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x

期末考试编译原理试卷及答案

一． 填空题（每空2分，共20分） 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静 态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。 2. 规范规约是最（3）规约。 3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。另外还有（6）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为 （7） 。 5．文法符号的属性有综合属性和 （8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址 计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。 二． 选择题（1-6为单选题，7-8为多选题，每问2分，共20分） 1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一组 （ ）。 A ． 字符串 B ． 产生式 C ． 开始符号 D ． 文法 2.程序的基本块是指（ ）。 A ． 一个子程序 B ． 一个仅有一个入口和一个出口的语句 C ． 一个没有嵌套的程序段 D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。 A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析。 A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。 A ． 四元式序列 B ． 间接三元式序列 C ． 二元式序列 D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。 A ． 唯一的 B ． 不唯一的 C ． 可能唯一，也可能不唯一 7． 如果在文法G 中存在一个句子，当其满足下列条件（ ）之一时，则称该文法是二义文法。 A ． 其最左推导和最右推导相同 B ． 该句子有两个不同的最左推导 C ． 该句子有两个不同的最右推导 D ． 该句子有两棵不同的语法树

蒋立源 编译原理第三版第二章 习题与答案(修改后)

第2章习题 2-1 设有字母表A1 ={a,b,c,…,z}，A2 ={0,1,…,9}，试回答下列问题： (1) 字母表A1上长度为2的符号串有多少个？ (2) 集合A1A2含有多少个元素？ (3) 列出集合A1(A1∪A2)*中的全部长度不大于3的符号串。 2-2 试分别构造产生下列语言的文法： （1）{a n b n|n≥0}； （2）{a n b m c p|n,m,p≥0}； （3）{a n#b n|n≥0}∪{c n#d n|n≥0}； （4）{w#w r# | w∈{0,1}*,w r是w的逆序排列 }； （5）任何不是以0打头的所有奇整数所组成的集合； （6）所有由偶数个0和偶数个1所组成的符号串的集合。 2-3 试描述由下列文法所产生的语言的特点： （1）S→10S0S→aA A→bA A→a （2）S→SS S→1A0A→1A0A→ε （3）S→1A S→B0A→1A A→C B→B0B→C C→1C0C→ε （4）S→aSS S→a 2-4 试证明文法 S→AB|DC A→aA|a B→bBc|bc C→cC|c D→aDb|ab 为二义性文法。 2-5 对于下列的文法 S→AB|c A→bA|a B→aSb|c 试给出句子bbaacb的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。

2-6 化简下列各个文法 (1) S→aABS|bCACd A→bAB|cSA|cCC B→bAB|cSB C→cS|c (2) S→aAB|E A→dDA|e B→bE|f C→c AB|dSD|a D→eA E→fA|g (3) S→ac|bA A→c BC B→SA C→bC|d 2-7 消除下列文法中的ε-产生式 (1) S→aAS|b A→cS|ε (2) S→aAA A→bAc|dAe|ε 2-8 消除下列文法中的无用产生式和单产生式 (1) S→aB|BC A→aA|c|aDb B→DB|C C→b D→B (2) S→SA|SB|A A→B|(S)|( ) B→[S]|[ ] (3) E→E+T|T T→T*F|F F→P↑F|P P→(E)|i 第2章习题答案 2-1 答： (1) 26*26=676 (2) 26*10=260 (3) {a,b,c,...,z, a0,a1,...,a9, aa,...,az,...,zz, a00,a01,...,zzz},共有26+26*36+26*36*36=34658个 2-2 解： (1) 对应文法为G(S)=({S},{a,b},{ S→ε| aSb },S) (2) 对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε },S) (3)对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X,S→Y,X→aXb|#, Y→cYd|# },S)

编译原理试题及答案3

编译原理复习题 一、填空题： 1、编译方式与解释方式的根本区别在于（是否生成目标代码）。 2、对编译程序而言，输入数据是（源程序），输出结果是（目标程序）。 3、如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：（编译阶段）和（运行阶段）。 4、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分成三个阶段：（编译阶段）、（汇编阶段）和（运行阶段）。 5、自顶向下语法分析方法会遇到的主要问题有（回溯）和（（左递归带来的）无限循环）。 6、LL(k)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“k”的含义是（向输入串中查看K个输入符号）。 7、LL(1)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“1”的含义是（向输入串中查看1个输入符号）。 8、自顶向下语法分析方法的基本思想是：从（识别符号）出发，不断建立（直接推导），试图构造一个推导序列，最终由它推导出与输入符号相同的（符号串）。 9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行（直接归约），试图（归约）到文法的（识别符号|开始符号）。 10、LR(0)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“0”的含义是（向貌似句柄的符号串后查看0个输入符号）。 11、LR(1)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 12、SLR(1)分析法的名字中，“S”的含义是（简单的），“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 13、在编译过程中，常见的中间语言形式有（逆波兰表示）、（三元式）、（四元式）和（树形表示）。 14、在编译程序中安排中间代码生成的目的是（便于代码优化）和（便于目标程序的移植）。 15、表达式-a+b*(-c+d)的逆波兰表示为（a-bc-d+*+ ）。 16、表达式a+b*(c+d/e)的逆波兰表示为（abcde/+*+ ）。 17、表达式a:=a+b*c↑(d/e)/f的逆波兰表示为（aabcde/↑*f/+:= ）。 18、文法符号的属性有（继承属性）和（综合属性）两种。 19、一个文法符号的继承属性是通过语法树中它的（兄弟结点与父）结点的相应文法符号的属性来计算的。 20、一个文法符号的综合属性是通过语法树中它的（子）结点的属性来计算的。

编译原理考试试题

一、回答下列问题：(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 表可以访问其外层过程的变量。 5．(6分)对下列四元式序列生成目标代码： A:=B*C D:=E+F G:=A+D H:=G*2 其中，H是基本块出口的活跃变量，R0和R1是可用寄存器 答： LD R0，B MUL R0，C LD R1，E ADD R1，F ADD R0，R1 MUL R0，2 ST R0，H

编译原理考试试卷

一、填空题（每空 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．确定的有穷自动机是一个，通常表示为。

编译原理第二章-课后题答案

第二章 3.何谓“标志符”，何谓“名字”，两者的区别是什么？ 答：标志符是一个没有意义的字符序列，而名字却有明确的意义和属性。 4.令+、*和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值。 （1）优先顺序（从高到低）为+、*和↑，同级优先采用左结合。 （2）优先顺序为↑、+、*，同级优先采用右结合。 答：（1）1+1*2↑2*1↑2=2*2↑2*1↑2=4↑2*1↑2=4↑2↑2=16↑2=256 （2）1+1*2↑2*1↑2=1+1*2↑2*1=1+1*4*1=2*4*1=2*4=8 6.令文法G6为 N-〉D|ND D-〉0|1|2|3|4|5|6|7|8|9 （1）G6的语言L（G6）是什么？ （2）给出句子0127、34、568的最左推导和最右推导。 （1）由0到9的数字所组成的长度至少为1的字符串。即：L（G6）={d n|n≧1,d∈{0,1,…,9}} 答： （2）0127的最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 0127的最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 （其他略） 7.写一个文法，使其语言是奇数集，且每个奇数不以0开头。 答：G（S）：S->+N|-N N->ABC|C C->1|3|5|7|9 A->C|2|4|6|8 B->BB|0|A|ε ［注］：可以有其他答案。 ［常见的错误］：N->2N+1 原因在于没有理解形式语言的表示法，而使用了数学表达式。 8.令文法为 E->T|E+T|E-T T->F|T*F|T/F F->(E)|i (1)给出i+i*i、i*(i+i)的最左推导和最右推导。 (2)给出i+i+i、i+i*i和i-i-i的语法树，并给出短语，简单短语和句柄。 答：(1) i*(i+i)的最左推导： E=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=> i*(i+i) i*(i+i)的最右推导： E=>T=>T*F=>T*(E) =>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=> T*(i+i)=> F*(i+i) => i*(i+i) （其他略） ［注］：要牢记每一步都是对最左（右）的一个非终结符号进行一步推导。 (2) i+i+i的语法树：

编译原理期末考试试卷及答案

期末考试试卷（A）卷 一、填空题（每小题2分，共20分） 1、字母表∑，用∑*表示∑上所有有穷长的串集合，∑*称为∑的①。 2、设z=abc，则z的固有头是①。 3、如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则叫 ①。 4、设∑＝{a,b}，∑上的正规式(a|b)(a|b) 相应的正规集为① 5、NFA的映象f是从"状态×字"映射到"状态子集"，f为①值函数。 6、LR分析是按规范句型的①为可归约串。 7、结点的①属性值由该结点的兄弟结点和父结点的属性值计算。 8、如果分析树中一结点的属性b依赖于属性c，那么这个结点的属性b的语义规 则的计算必须在定义属性c的语义规则的计算①。 9、对于栈式符号表，引入一个显示嵌套层次关系表- ①表，该表总是 指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。 10、任一有向边序列n1 → n2,n2 → n3,…,nk-1 → nk为从结点n1到结点nk 的一条通路。如果n1=nk，则称该通路为①。 二、单项选择（每小题2分，共14分） 1、乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。其中3型文法也称 为（）。 A．上下无关文法 B.正规文法 C．上下文有关文法 D.无限制文法 2、生成非0开头的正偶数集的文法是（）。 A． Z::=ABC B. Z::=ABC C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|ε B::=BA|B0|0 A::=1|2|3|…|9 A::=1|2|3|…|9 C. Z::=ABC|2|4|6|8 D. Z::=ABC|2|4|6|8 C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|0 B::=BA|B0|ε A::=1|2|3|…|9 A::=1|2|3|…|9 3、简单优先分析法从左到右扫描输入串,当栈顶出现（）时进归约。

编译原理试题及答案

参考答案 一、单项选择题(共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 ．L 0?L 1?L 2?L 3 B ．L 3?L 2?L 1?L 0 C ．L 3=L 2?L 1?L 0 D ．L 0?L 1?L 2=L 3 7．词法分析的任务是 A ．识别单词 B ．分析句子的含义 C ．识别句子 D ．生成目标代码 8．常用的中间代码形式不含 A ．三元式 B ．四元式 C ．逆波兰式 D ．语法树 9． 代码优化的目的是 A ．节省时间 B ．节省空间 C ．节省时间和空间 D ．把编译程序进行等价交换 10．代码生成阶段的主要任务是 A ．把高级语言翻译成汇编语言 B ．把高级语言翻译成机器语言 C ．把中间代码变换成依赖具体机器的目标代码 装 订 线

D．把汇编语言翻译成机器语言 二、填空题（本大题共5小题，每小题2分，共10分） 1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。 5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。 三、名词解释题(共5小题，每小题4分，共20分) 1．词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则 从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位， 并转换成统一的内部表示(token)，送给语法分析程序。 2．LL(1)文法 若文法的任何两个产生式A →α | β都满足下面两个条件： （1）FIRST(α) ? FIRST(β ) = φ； （2）若β?* ε，那么FIRST(α) ? FOLLOW( A ) = φ。 我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左 向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步 动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一 些明显的性质，它不是二义的，也不含左递归。 3．语法树 句子的树结构表示法称为语法树(语法分析树或语法推导树)。 给定文法G=(V N，V T，P，S)，对于G的任何句型都能构造与之关联的 语法树。这棵树具有下列特征： (1)根节点的标记是开始符号S。 (2)每个节点的标记都是V中的一个符号。 (3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列 次序为A1A2…A R，那么A→A1A2…A R一定是P中的一条产生式。

编译原理考试试卷

一、填空题（每空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）={b2i|i≥0} C、L（G）={b2i+1|i≥0} D、L（G）={b2i+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．确定的有穷自动机是一个，通常表示为。

编译原理 第二章习题答案

第2章习题解答 1.文法G[S]为： S->Ac|aB A->ab B->bc 写出L(G[S])的全部元素。 [答案] S=>Ac=>abc 或S=>aB=>abc 所以L(G[S])={abc} ============================================== 2. 文法G[N]为： N->D|ND D->0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ [答案] G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D =============================================== 3.已知文法G[S]： S→dAB A→aA|a B→ε|bB 问：相应的正规式是什么？G[S]能否改写成为等价的正规文法？[答案] 正规式是daa*b*；

相应的正规文法为(由自动机化简来)： G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b 也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε ===================================================================== ========== 4.已知文法G[Z]： Z->aZb|ab 写出L(G[Z])的全部元素。 [答案] Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={a n b n|n>=1} ===================================================================== ========= 5.给出语言{a n b n c m|n>=1,m>=0}的上下文无关文法。 [分析] 本题难度不大，主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是：A->β,A∈Vn，β∈（Vn∪Vt）*，注意关键问题是保证a n b n的成立，即“a与b的个数要相等”，为此，可以用一条形如A->aAb|ab的产生式即可解决。 [答案] 构造上下文无关文法如下： S->AB|A A->aAb|ab B->Bc|c [扩展]

编译原理考试试题与答案(汇总)

《编译原理》考试试题及答案（汇总） 一、是非题（请在括号，正确的划√，错误的划×）（每个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．下列______优化方法不是针对循环优化进行的。 A. ( ) 强度削弱 B．( ) 删除归纳变量 C．( ) 删除多余运算 D．( ) 代码外提

编译原理期末A试卷答案

黄冈师范学院 2012—2013学年度第一学期期末试卷参考答案 考试课程：编译原理考核类型：考试A卷 考试形式：闭卷出卷教师：牛冀平 考试专业：计算机科学与技术，软件工程 考试班级：计科201001班，软件201001班 一、填空（每空0.5分，共 10分） 1、编译程序的功能是是对(高级语言)进行翻译，使之生成目标代码。 2、编译程序的工作过程一般划分为5个阶段：（词法分析）、语法分析、语义分析与中间代码生成，（代码优化）及目标代码生成。另外还有表格管理和（出错处理）。 3、一个上下文无关文法所含四个组成部分是一组终结符号、一组（非终结符号）、一个开始符号、（一组产生式）。 4、设G是一个给定的文法，S是文法的开始符号，如果S=> x（其中x∈V*），则称x 是文法的一个（句型）。 5、规范归约中的可归约串是指句柄，算符优先分析中的可归约串是指（最左素短语）。 6、在编译过程中,可采用的中间代码形式有（）、（）、（）等。（三元式、间接三元式、四元式、逆波兰式、抽象语法树）（任选三个即可） 7、语法分析最常用的两类方法是（自上而下）和（自下而上）分析法。 8、表达式（a+b)*c的后缀表达式为（ab+c*）。 9、符号表的结构一般有（线性表）、（有序表）、（散列表或哈希表）等。 分别使用的查找方法有（顺序查找）、（折半查找）和（哈希法查找） 10、代码优化的目的是（减少代码的时空开销）。 11、寄存器是CPU内部的（存储单元），其访问时间小于CPU对内存的访问时间。 12、如果一个句子存在两棵不同的语法树就说明该句子是（二义性）的。 二、选择题（每题1分，共10分）

编译原理试题及答案——加强版

编译原理试题及答案 <高级版> 一、对于文法 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 → a B | 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) 文法吗？为什么？ 六、给定下列语句： if a+b>c then x := a*(b-c) + (b*c-d)/e ⑴写出其等价的逆波兰表示； ⑵写出其等价的四元式序列。 七、已知下列 C 语言程序： int * f() { int a = 100; return &a; } main()

郑州大学编译原理试卷及答案(往年试题整合)

二填空题 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（栈式动态存储分配）和（堆式动态存储分配）。 2. 规范规约是最（左）规约。 3. 编译程序的工作过程一般划分为5个阶段：词法分析、（语法分析）、语义分析与中间代码生成，代码优化及（目标代码生成）。另外还有（表格管理）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为（xyz*ab+/+ ）。 5．文法符号的属性有综合属性和（继承属性）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i，j]的地址计算公式为（a+(i-1)*20+j-1 ）。7．局部优化是局限于一个（基本块）范围内的一种优化。 8词法规则通常可以用____正规式________，正规文法、____自动机________描述；语法规则通常用___2型文法___来描述；语义规则通常用__属性文法_____来描述。 9编译原理的工作过程一般划分为：词法分析、语法分析、语义分析、优化和目标代码生成五个阶段。 1.( 最右推导 )称为规范推导。 2.编译过程可分为（词法分析），（语法分析），（中间代码生成），（代码优化）和（目标代码生成）五个阶段。

3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（二义性的）。 4.从功能上说，程序语言的语句大体可分为（执行性）语句和（说明性）语句两大类。 5.语法分析器的输入是（单词符号），其输出是（语法单位）。 6.扫描器的任务是从（源程序）中识别出一个个（单词符号）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如（类型、种属、所占单元大小、地址）等等。 8.一个过程相应的DISPLAY表的内容为（现行活动记录地址和所有外层最新活动记录的地址）。 9.一个句型的最左直接短语称为句型的（句柄）。 10.常用的两种动态存贮分配办法是（栈式）动态分配和（堆式）动态分配。 11.一个名字的属性包括( 类型)和( 作用域 )。 12.常用的参数传递方式有（传地址），（传值）和（传名）。 13.根据优化所涉及的程序范围，可将优化分成为（局部优化），（循环优化）和（全局优化）三个级别。 14.语法分析的方法大致可分为两类，一类是（自上而下）分析法，另一类是（自下而上）分析法。 15.预测分析程序是使用一张（分析表）和一个（符号栈）进行联合控制的。 16.常用的参数传递方式有（传地址），（传值）和（传名）。