编译原理习题答案.docx
《编译原理习题答案.docx》由会员分享，可在线阅读，更多相关《编译原理习题答案.docx（29页珍藏版）》请在冰点文库上搜索。
编译原理习题答案
1、正规文法又称D
A、0型文法B、1型文法C、2型文法D、3型文法
2、对于无二义性的文法，规范归约是B
A.最左推导B.最右推导的逆过程C.最左归约的逆过程D.最右归约的逆过程。
3、扫描器的任务是从源程序中识别出一个个单词符号。
4、程序所需的数据空间在程序运行前就可确定，称为A管理技术。
A静态存储B动态存储C栈式存储D堆式存储
5、编译过程中，语法分析器的任务是（B）。
①分析单词是怎样构成的
②分析单词串是如何构成语句和说明的
③分析语句和说明是如何构成程序的
④分析程序的结构
A、②③B、②③④C、①②③D、①②③④
6、文法G：
E→E+T|TT→T*P|PP→（E）|i
则句型P+T+i的句柄和最左素短语分别为B。
A、P+T和iB、P和P+TC、i和P+T+iD、P和P
7、四元式之间的联系是通过B实现的
A.指示器B.临时变量C.符号表D.程序变量
8、程序语言的单词符号一般可以分为保留字、标识符、常数、运算符、界符等等。
9、下列B优化方法是针对循环优化进行的。
A．删除多余运算B．删除归纳变量C．合并已知量D．复写传播
10、若文法G定义的语言是无限集，则文法必然是A
A、递归的B、前后文无关的C、二义性的D、无二义性的
11、文法G产生的D的全体是该文法描述的语言。
A、句型B、终结符集C、非终结符集D、句子
12、Chomsky定义的四种形式语言文法中，0型文法又称为A文法；1型文法又称为C文法。
A.短语文法B.上下文无关文法C.上下文有关文法D.正规文法
A.短语文法B.上下文无关文法C.上下文有关文法D.正规文法
13、语法分析最常用的两类方法是自顶向下和自底向上分析法。
14、一个确定的有穷自动机DFA是一个A。
A五元组（K，∑，f,S,Z）B四元组（VN，VT，P，S）
C四元组（K，∑，f，S）D三元组（VN,VT,P）
A、语法B、语义C、代码D、运行
15、B不属于乔姆斯基观点分类的文法。
A、上下文无关文法B、算符优先文法C、上下文有关文法D、正规文法
16、一个文法所描述的语言是A；描述一个语言的文法是B。
A.唯一的B.不唯一的C.可能唯一,可能不唯一
A.唯一的B.不唯一的C.可能唯一,可能不唯一
17、语法分析是依据语言的语法规则进行的，中间代码产生是依据语言的等价变换规则进行的。
18、B不属于乔姆斯基观点分类的文法。
A上下文无关文法B算符优先文法C上下文有关文法D正规文法
19、过程调用时参数传递方式有A
（1）传地址
（2）传值（3）传标识符（4）得结果（5）传名（6）返回值
可选项有：
A、
（1）
（2）（4）（5）B、
（1）
（2）（5）（6）C、
（1）
（2）（3）（6）D、
（2）（3）（4）（6）
20、过程调用时参数传递方式有
（1）传地址
（2）传值（3）传标识符（4）得结果（5）传名（6）返回值
可选项有：
A、
（1）
（2）（4）（5）B、
（1）
（2）（5）（6）C、
（1）
（2）（3）（6）D、
（2）（3）（4）（6）
21、下列代码中D不可能是目标代码。
A、汇编指令代码B、可重定位指令代码C、绝对指令代码D、中间代码
22、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。
B。
A.正确B.不正确
23、有限自动机能识别C
A．上下文无关文法B．上下文有关文法
C．正规文法D．短语文法。
24、汇编程序是将B程序改造成目标语言程序的翻译程序。
A机器语言B汇编语言C高级语言D低级语言
25、LR（k）文法___B____二义性的。
A、都是B、都不是C、不一定都是
26、乔姆斯基方法的2型语言是这样一种语言，其产生式限制为A
A、A→B、A→a，A→aBC、→β（||||）D、→
27、局部优化是局限于一个C范围内的一种优化。
A.循环B.函数C.基本块D.整个程序
28、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。
A。
A.正确B.不正确
29、乔姆斯基方法的3型语言是这样一种语言，其产生式限制为B
AA→BA→a或A→aBC→β（||||）D→
30、运算符与运算对象类型不符属于A。
A、语法错误B、语义错误C、语用错误D、规则集合
31、词法分析器的输入是B。
A、词法记号B、源程序C、语法单位D、目标程序
32、在下述的编译方法中，自底向上的方法有F，自顶向下的分析方法有A。
①简单优先分析②算符优先分析③递归下降分析④预测分析技术⑤LR（K）分析⑥SLR（k）分析⑦LL（k）分析⑧LALR（K）分析
A.③④⑦B.③④⑧C.①②⑧D.③④⑤⑥⑦E.①②⑤⑥⑦F.①②⑤⑥⑧
A.③④⑦B.③④⑧C.①②⑧D.③④⑤⑥⑦E.①②⑤⑥⑦F.①②⑤⑥⑧
33、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。
B。
A.正确B.不正确
34、算符优先分析法每次都是对C进行归约。
A句柄B短语C最左素短语D素短语
35、编译时能进行的类型检查称为C。
A、错误检查B、动态检查
C、静态检查D、随机检查
36、规范推导的每一步总是用产生式右边符号串替换句型中B位置的非终结符号
A、最左B、最右C、最中D、任意
37、语法分析器的输入是单词符号流，其输出是分析树的某种表示
38、每个文法都能改写为LL
（1）文法。
B
A.正确B.不正确
39、对于无二义性的文法，规范推导是C
A最左推导B最右推导的逆过程C最左归约的逆过程D最右归约的逆过程。
40、描述语言L={ambn|n≥m≥1}的文法为D。
A、Z→AbbA→aA|aB→bB|b
B、Z→AB|bA→Aa|aB→aBb|b
C、Z→AbA→aAb|a
D、Z→aAbA→Ab|aAb|ε
41、间接三元式表示法的优点为A
A、采用间接码表，便于优化处理B、节省存储空间，不便于表的修改
C、便于优化处理，节省存储空间D、节省存储空间，不便于优化处理
42、编译时能进行的类型检查称为C
A错误检查B动态检查C静态检查D随机检查
43、文法G[S]：
S→xSx|y所识别的语言是A。
A、xnyxn（n≥0）B、（xyx）*C、xyxD、x*yx*
44、项目A→α·称为B，其中A∈VN，A不是开始符。
A、移进项目B、归约项目C、出错项目D、接受项目
45、设有文法G[S]:
S->S*S|S+S|（S）|a,该文法___A__二义性文法。
A、是B、不是C、不一定
46、高级语言编译程序常用的语法分析方法中，LL分析法属于B分析方法。
A、自左至右B、自顶向下C、自底向上D、自右至左。
47、有文法G：
E→E*T|T T→T＋i|i 句子2＋5*3＋3按该文法G归约，其值为B
A23B 42C 30 D17
48、高级语言编译程序常用的语法分析方法中，LL分析法属于B分析方法。
A自左至右B自顶向下C自底向上D自右至左。
49、形如A→α·Bβ的项目为A项目。
A、待约B、移进C、接受D、规约
50、活动记录的连接数据不包括A。
A、形参单元B、动态链（老SP）C、返回地址D、全局Display地址
51、高级语言编译程序常用的语法分析方法中，lALR分析法属于C分析方法。
A、自左至右B、自上而下C、自下而上D、自右至左
52、设a、b、c是文法的终结符，且满足优先关系a=•b和b=•c，则D。
A.必有a=•cB.必有c=•aC必有b=•aD答案A~C都不一定成立
53、词法分析器的输出是A。
A、词法记号流B、源程序C、语法单位D、目标程序
54、对一个基本块来说，A是正确的。
A、只有一个入口语句和一个出口语句B、有一个入口语句和多个出口语句
C、有多个入口语句和一个出口语句D、有多个入口语句和多个出口语句
55、词法分析所依据的是B。
A语义规则B构词规则C语法规则D等价变换规则
56、句型是由D推导出的符号串。
A、非终结符B、终结符C、任何符号D、开始符号
57、如果文法G是无二义的，则它的任何句子αA。
A、最左推导和最右推导对应的语法树必定相同
B、最左推导和最右推导对应的语法树可能不同
C、最左推导和最右推导必定相同
D、可能存在两个不同的最左推导，但它们对应的语法树相同
58、算符优先文法与算符优先函数的关系的描述中正确的是（B）。
A、一个算符优先文法一定存在优先函数与之对应
B、一个算符优先文法可能存在多个优先函数与之对应
C、一个算符优先文法一定存在多个优先函数与之对应
D、一个算符优先文法一定存在有限对优先函数与之对应
59、一个句型中称为句柄的是该句型的最左D。
A非终结符B短语C句子D直接短语
60、描述一个语言的文法是（B）
A、唯一的B、不唯一的C、可能唯一，也可能不唯一
61、下列C优化方法不是针对循环优化进行的。
A、强度削弱B、删除归纳变量C、删除多余运算D、代码外提
62、更动一张A表很困难。
A三元式B间接三元式C四元式D三元式和四元式
63、栈式存储分配申请和释放存储空间遵守BC原则。
A、先申请先释放B、先申请后释放C、后申请先释放D、任意
64、所谓自上而下分析法是指。
65、所谓语法制导翻译方法是。
66、确定的有穷自动机是一个五元组，通常表示为M=（S,∑,f,s0,Z）。
67、规范归约中的可归约串是指句柄；算符优先分析中的可归约串是指最左素短语。
68、编译程序在逻辑上由词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六部分组成。
69、D不可能是目标程序。
A、汇编语言模块B、可重定位目标模块C、可执行目标模块D、中间代码
70、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。
71、一个名字的属性包括继承属性和综合属性。
72、正规式的“*”读作星闭包。
73、编译程序在逻辑上由、、语义分析、中间代码生成、代码优化和目标代码生成六部分组成。
74、编译程序的各个阶段的工作都涉及到符号表管理和错误处理
75、文法用来描述语言的语法结构，它由如下4个部分组成：
文法终结符集合、文法非终结符集合、D和文法开始符号。
A、单词集合B、字母数字串
C、文法句子集合D、文法产生式的集合
76、确定的有穷自动机是一个元组，通常表示为。
77、已知文法G[E]：
E→E+T|T
T→T*F|F
F→（E）|id
该文法终结符集合VT=，文法非终结符集合VN=，该文法在乔姆斯基（Chomsky）文法分类属于2文法。
78、编译程序的各个阶段的工作都涉及到和。
79、假设G是一个文法，S是文法开始符号，如果S*>x，则称x是该文法的一。
80、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是。
81、优化时，节省一条指令MOVRi，M，节省的指令代价为C
A、0B、1C、2D、3
82、采用LL
（1）语法分析时，必须消除文法的左递归。
83、在状态转换图中，结点代表状态，用圆圈表示。
84、若源程序是高级语言编写的，目标程序是机器语言或汇编语言的程序，则相应的翻译程序称为编译程序。
85、常用的两种动态存贮分配办法是栈式分配和堆式分配。
86、翻译方案和语法制导定义不同的是它的语义动作（而不叫语义规则）放在括号{}内，并且可以插在产生式右部的任何地方
87、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是。
88、所谓最左推导是指：
。
89、上下文无关文法的可以用四元组表示，其形式为G=（VN,VT,S,P）。
90、后缀式ab+c+d*e-所表达的式子为（a+b+c）*d-e。
91、常用的两种动态存贮分配办法是分配和分配。
92、LL（K）文法中，第一个L表示从左到右扫描输入串，第二个L表示产生最左推导，K表示在决定语法分析器每步动作时向前看K个输入符。
93、一个上下文无关文法所含四个组成部分是文法终结符集合文法非终结符集合
开始符号产生式有限集合。
94、对于文法G，仅含终结符号的句型称为句子。
95、设有文法G[E]：
E→E+T|E–T|T
T→T*F|T/F|F
F→（E）|i
该文法句型E+T*F的句柄是T*F。
96、后缀式ab+c+d*e-所表达的式子为。
97、文法符号的属性有两种，一种称为继承属性，另一种称为综合属性，S属性定义是指仅使用综合属性的语法制导定义。
98、LR（0）项目和LR
（1）项目的区别在于是否有搜索符。
99、紧跟在条件转移语句后面的语句是基本块的入口语句。
100、若二个正规式所表示的DFA（或正规集）相同，则认为二者是等价的。
101、仅含终结符的句型称为。
102、编译方式与解析程序的根本区别在于是否生成目标代码。
（F）
103、规范归约和规范推导是互逆的两个过程。
（T）
104、一个上下文无关文法的开始符号可以是终结符或非终结符。
（F）
105、逆波兰表示法表示表达式时无需使用括号。
（T）
106、符号表由词法分析程序建立，由语法分析程序使用。
（F）
107、逆波兰法表示的表达式亦称前缀式。
（F）
108、代码生成器的输入包括中间代码和符号表中的信息。
（T）
109、孤立地考虑一个基本块常常不能确定一个赋值是否真是无用的。
（T）
110、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。
（T）
111、无左递归的文法是LL
（1）文法。
（F）
112、一个句型的直接短语语是唯一的。
（F）
113、正规文法产生的语言都可以用上下文无关文法来描述。
（F）
114、对任何一个编译程序来说，产生中间代码是不可缺少的一部分。
（F）
115、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。
（F）
116、一个上下文无关文法的开始符号可以是终结符或非终结符。
（F）
117、一个文法所有句子的集合构成该文法定义的语言。
（T）
118、优化实质上是对代码进行等价变换，变换后的代码结构不同但运行结果相同。
（T）
119、算符优先分析法是一种规范归约分析法。
（F）
120、非终结符可以有综合属性，但不能有继承属性。
（F）
121、所有LR分析器的总控程序都是一样的，只是分析表各有不同。
（T）
122、因名字都是用标识符表示的，故名字与标识符没有区别（F）
123、空符号串的集合{ε}={}=ø。
（F）
124、非终结符可以有综合属性，但不能有继承属性。
（F）
125、终结符可以有综合属性，也可以有继承属性。
（F）
126、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。
（）
127、若一个句型中出现了某一产生式的右部，则此右部一定是该句型的句柄。
（F）
129、DAG是一个可带环路的有向图。
（F）
130、设有符号串x和y，把y的符号写在x的符号之后所得的符号串，叫做x与y的连接，记为xy。
（T）
131、对任何一个编译程序来说，产生中间代码是不可缺少的一部分。
（F）
132、对任何正规表达式e，都存在一个DFA M，满足L（M）＝L（e）。
（T）
133、运行时的DISPLAY表的内容是什么？
它的作用是什么？
答：
内容：
1、过程R的现行活动记录的地址（sp的现值）2、R的外层Q的最新活动记录的地址3、Q的外层即主程序P的活动记录的地址
作用：
跟踪每个外层的最新活动记录的位置
134、何谓局部优化、循环优化和全局优化？
优化工作在编译的哪个阶段进行？
答：
局部优化：
在基本快内的优化。
循环优化：
对循环中的代码进行优化。
全局优化：
整个程序范围内的优化。
在中间代码优化阶段。
135、常见的存储分配策略有几种？
它们都适合于什么性质的语言？
答：
1、静态分配策略适用于无动态申请内存、无可变体积数组、无递归调用的程序语言（如Fortran）
2、动态分配策略
2.1栈式动态分配2.1.1简单栈式分配适用于没有分程序结构、不允许程序嵌套定义但允许过程递归调用、允许过程含可变数组的语言2.1.2嵌套过程语言的栈式分配适用于没有分程序结构、允许程序嵌套定义和过程递归调用、允许过程含可变数组的语言
2.2堆式动态分配适用于允许程序为变量在运行时动态申请和释放存储空间的语言
136、下面文法是否是二义文法？
试说明理由。
G[S]：
S→SaS|
答：
二义
137、已知文法G（E）
E→T|E＋T
T→F|T*F
F→（E）|i
（1）给出句型（T*F＋i）的最右推导及画出语法树；
（2）给出句型（T*F＋i）的短语、素短语。
1）E→E＋T→E+i→T+i→T*F+I树略
2）短语：
T*F+iT*Fi
素短语：
T*Fi
138、把算术表达式－（a+b）*（b+c）翻译成：
（a）后缀表示ab+bc+*@
（b）语法树图略
（c）有向无环图图略
（d）四元式三地址代码
四地址代码：
（+,a，b，t1）
（+，b，c，t2）
（*，t1，t2，t3）
（@，t3，-，t4）
139、DFA与NFA的区别？
答：
1、DFA弧上不允许有ε出现，NFA允许
2、DFA中每个状态S和输入符号a最多有一条边离开S，NFA有多条
3、NFA可以有多个初态，DFA只有一个
140、设已构造出文法G（S）：
SS（S）
S
的LR分析表如下
状态
ACTION
GOTO
（
）
#
S
0
r2
r2
1
1
S2
Acc
2
r2
r2
3
3
S4
S5
4
r2
r2
6
5
r1
r1
6
S4
S7
7
r1
r1
假定输入串为（）（），请给出LR分析过程（即状态，符号，输入串的变化过程）。
步骤状态符号输入串
步骤
状态
符号
输入串
1
0
（）（）$
2
01
S
（）（）$
3
012
S（
）（）$
4
0123
S（
）（）$
5
01235
S（）
（）$
6
01
S
（）$
7
012
S（
）$
8
0123
S（S
）$
9
01235
S（S）
$
10
01
S
$
141、对符号表的基本操作有几种，分别是什么？
答：
5类。
1、填写名称2、查找名字3、访问信息4、填写修改信息5、删除
（或者：
4类。
建立、插入、查找、删除）
142、给定代码段如下，求出按四种不同方式进行参数传递后，变量a的值
…
procedureP（w,x,y,z）;
begin
y:
=y*w;
z:
=z+x;
end
begin
a:
=5;
b:
=3;
P（a+b,a-b,a,a）;
write（a）;
end
传值:
5
传地址:
42
得结果:
7
传名:
77
143、目标代码有哪几种形式？
生成目标代码时通常应考虑哪几个问题？
答：
1、汇编语言2、机器语言又可分为a可立即执行的机器语言b可重定位的机器语言
需要考虑：
1.、如何使生成的目标代码最短2、如何分配寄存器的使用
144、下面的推导Srm…rmAbwrmlbw中，最后一步用的是Al，分别指出LL
（1）方法和LR
（1）方法在扫描到此句型的什么位置决定用此产生式？
（5分）P79
答：
LL
（1）扫描到l的时候决定用此产生式；LR
（1）扫描到b的时候决定使用次产生式
145、构造一个最简DFA，它接受正规式ab（a|b）*。
给出文法G[S]：
S→SaA|A
A→AbB|B
B→cSd|e
（1）证实AacAbcBaAdbed是文法G[S]的一个句型；
（2）请写出该句型的所有短语、素短语以及句柄。
答：
1）这里用最右推导表示，省略树S→SaA→SaB→SacSd→SacAd→SacAbBd→SacAbed→SacAbBbed→SacAbcSdbed
→SacAbcSaAdbed→SacAbcAaAdbed→SacAbcBaAdbed→AacAbcBaAdbed
2）短语：
AacAbcBaAdbedcAbcBaAdbedAbcBaAdbeAbcBaAdcBaAdBaAeA素短语：
BaAe句柄：
A
146、写出表达式a+b*（c-d）对应的逆波兰表示、三元式三地址代码序列和抽象语法树。
147、什么是活动记录？
它主要由哪些内容构成？
148、对下列四元式序列生成目标代码（10分）
T=A-B
S=C+D
W=E-F
U=W/T
V=U*S
其中，V是基本块出口的活跃变量，R0和R1是可用寄存器。
答MOVR0，A
SUBR0，B
MOVR1，A
ADDR1，D
MOVS，R1
MOvR1，E
SUBR1，F
DIVR1，R0
MULR1，S
149、设有如下的三地址码（四元式）序列：
ReadN
I∶=N
J∶=2
————————
L1：
ifI≤JgotoL3
————————
L2：
I∶=I-J
ifI>JgotoL2
————————
ifI=0gotoL4
————————
J∶=J+1
I∶=N
gotoL1
————————
L3：
Print′YES′
升级会员 