编译原理试题及参考答案.doc

课程测试试题（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型文法也称 ，它的所有规则α→β 都满足：α∈ ，β∈ ((VN∪VT) *且 ，仅当β= ε时例外。
3、现代编译系统多采用 方法，即在语法分析过程中根据各个规则所相联的 或所对应的语义子程序进行翻译的办法。该方法使用 为工具来说明程序设计语言的语义。
4、构造与NFA M等价的正规文法G的方法如下：（1）对转换函数f(A，a)=B或f(A，ε)=B，改成形如 或 的产生式；（2）对可识别终态Z，增加一个产生式： 。
5、代码生成要考虑的主要问题：充分利用 的问题、选择 的问题、选择 的问题。
6、设有穷自动机M=(K，S，f，S，Z)，若当M为 时，满足z0∈f(S，α)且z0∈Z，或当M为 时，满足f(S，α)=P∈Z，则称符号串α∈S*可被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∈VN，a∈VT或#。若有产生式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 =（VN，VT，P，S）中，元素VN，VT 分别是非空有限的 。且二者交集为φ；P为产生式/规则集，是文法的核心部分；S ∈ VN，是文法的开始符号(或识别符) ，它是一个非终结符，至少要在一条规则中作为 出现。
3、构造ＬＲ（０）项目集规范族的项目类型分为四种：形如A→α.aβ的 、形如 的待约项目、形如A→αBβ.的归约项目、形如S'→α.的 。
4、一个优先关系矩阵对应的优先函数 ；所表示优先关系唯一的矩阵不一定存在优先函数；当两个终结符对之间无优先关系时， 可以将相应元素置出错信息，而使用 却无法识别这种情况，不能准确指出出错位置。
5、在编译程序中用符号表来存放语言中出现的有关 的语义特征属性信息。程序设计语言中通用的标识符属性主要有如下几种：符号名、符号的 、符号的存储类别、符号的 、符号变量的存储分配信息及数组的内情向量等其它属性。
6、如果文法G=（ VN，VT，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]=Sj，则把 入符号栈，把 入状态栈，并使 ip 指向下一个输入符号；如果action[S,a]=rj，则从栈顶弹出第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 a<b or c<d and e>f 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]是一个文法,如有Sx,则称x是该文法G的（ ）；文法G产生的（ ）的全体称为该文法所描述的语言。
4、所谓2型文法就是指（ ）文法，若用G =（VN，VT，P，S）表示它，则它要求G中的所有规则α→β都满足：α是（ ），而β属于（VN U VT）*。
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…ai-1NiaiNi+1ai+1…ajNj+1aj+1Nj+2…中，寻找的最左素短语NiaiNi+1ai+1…ajNj+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、所谓规则或产生式是指形如α→β或α::=β的(α,β)有序对，其中α是
1、
字母表V的正闭包元素,而β是字母表V的闭包元素。

3、设文法G =（VN，VT，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
参考答案
代码优化、前后端、源语言与目标机器
上下文无关文法、VN、|β|>=|α|
语法制导翻译、语义动作、属性文法
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) 假定S={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中I4、T5中都包含有移进—归约冲突，所以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 a<b or c<d and e>f 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’→ε)={#，)} SELECT(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分)

16 / 16