编译原理 考题及复习题.docx
- 文档编号:17964462
- 上传时间:2023-08-05
- 格式:DOCX
- 页数:67
- 大小:352.30KB
编译原理 考题及复习题.docx
《编译原理 考题及复习题.docx》由会员分享,可在线阅读,更多相关《编译原理 考题及复习题.docx(67页珍藏版)》请在冰点文库上搜索。
编译原理考题及复习题
课程测试试题(A卷)
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、构造与NFAM等价的正规文法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∈VN定义A的后续符号集:
FOLLOW(A)={a|S=*>uAβ,a∈VT,且a∈,u∈VT*,β∈V+;若,则#∈FOLLOW(A)。
也可以定义为:
FOLLOW(A)={a|S=*>…Aa…,a∈VT}。
若有,则规定#∈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、简述判别文法G是否为LL
(1)文法的步骤和将一个非LL
(1)文法转换为LL
(1)文法的方法。
三、应用题(共50分)
1、有文法G[S]:
(12分)
S→aAS|aA→SbA|SS|ba
(1)证明aabbaa是文法的一个句子。
(3分)
(2)构造句子aabbaa的语法树。
(3分)
(3)指出该句子的所有短语、直接短语和句柄。
(6分)
2、对文法G[E']:
(15分)
E'→#E#E→E+T|TT→T*F|FF→P^F|PP→(E)|i
(1)计算G[E']的FIRSTVT和LASTVT。
(5分)
(2)构造G[E']的算符优先关系表,并说明G[E']是否为算符优先文法。
(5分)
(3)给出输入串w=i+i#的算符优先分析过程。
(5分)
3、对以下基本块:
(8分)
A:
=5B:
=R+rT0:
=A+BT1:
=2*A
T2:
=B+AT3:
=A+AX1:
=T1+T2X2:
=T0*T3
(1)画出基本块的DAG图。
(3分)
(2)根据DAG结点原来的构造顺序重写四元式。
(2分)
(3)假设基本块出口后只有X1,X2还被引用,试写出优化后的四元式序列。
(3分)
4、对文法G[S’]:
(15分)
0)S’→S1)S→A2)S→B3)A→aAe
4)A→a5)B→bBd6)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分)
编译原理课程测试试卷评分标准
(数计学院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)假定={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:
=5T1=10T3=10B:
=R+r
T0:
=A+BT2:
=T0X1:
=T0+T1X2:
=T0*T1
(3)假设基本块出口后只有X1,X2还被引用,则通过重新命名临时变量的基本块保结构变换,可将基本块的四元式代码进一步优化为:
(3分)
C:
=R+rD:
=5+CX1:
=D+10X2:
=D*10
4、0)S’→S1)S→A2)S→B3)A→aAe
4)A→a5)B→bBd6)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分)
吉首大学课程考核命题双向细目表
学院:
数计专业:
计算机科学技术课程:
编译原理(B卷)
考核对象:
2004级1、2班考核所需时间:
120分钟
题性
分值
章节
题型(以分数计)
合
计
客观性题
主观性题
选
择
填
空
判
断
名词解释
简
答
论述
或
论证
计
算
应
用
1章
1.2节
3
3
3章
3.3—3.8节
3
13
16
4章
4.2—4.7节
12
12
5章
5.1—5.6节
16
16
6章
6.2—6.4节
6
5
3
14
7章
7.2—7.5节
7
5
12
8章
8.5节
6
6
9章
9.1—9.3节
3
3
10章
10.1节、10.3节
2
5
7
11章
11.1—11.3节
3
5
8
12章
12.1节
3
3
合计
30
20
50
100
命题组(教师)
签名:
莫礼平2006年12月11日
教研室(系)主任审查意见
签名:
年月日
学院(部)分管教学工作
领导意见
签名:
年月日
课程测试试题(B卷)
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、构造LR(0)项目集规范族的项目类型分为四种:
形如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|TT→T*F|FF→(E)|i
(1)证明T+T*F+i是文法的一个句型。
(3分)
(2)构造型T+T*F+i的语法树。
(3分)
(3)指出该句型的所有短语、直接短语和句柄。
(7分)
(4)指出该句型的所有素短语和最左素短语。
(3分)
2、将下列条件语句翻译成四元式的中间代码形式:
(6分)
ifa
3、有正规文法G[S]:
(12分)
S→aA|bBA→bS|bB→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|TT→T^F|FF→(E)|a
(1)判断G[E]是否为LL
(1)文法。
若不是,改造为LL
(1)文法。
(8分)
(2)构造预测分析表,并对输入串w=a-a^a#进行预测分析。
(8分)
编译原理课程测试试卷评分标准
(数计学院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’→SG[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、ifa
(6分)
(1)ifa (2)goto(3) (3)ifc (4)goto(p+1) (5)ife>fgoto(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)文法。 (
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理 考题及复习题 编译 原理 考题 复习题