编译原理练习题.doc

(完整word版)编译原理练习题
一章：
1、编译程序各阶段都涉及 。
A、词法分析 B、表格管理 C、语法分析 D、语义分析
2、下列哪个程序不是编译程序的组成部分？ 。
A、词法分析程序 B、代码读入程序 C、代码生成程序 D、语法分析程序
3、编译程序各阶段的工作往往是 进行的。
A、顺序 B、并行 C、成批 D、穿插
4、词法分析所依据的是 。
A、语义规则 B、构词规则 C、语法规则 D、等价变换规则
5、编译程序的语法分析器可以发现源程序中的 。
A、语义错误 B、语法和语义错误 C、错误并校正 D、语法错误
6、高级语言源程序经编译后产生的程序是 。
A、源程序 B、目标程序 C、函数 D、过程

1、扫描器的任务是从源程序中识别出一个个单词符号。
2、高级语言源程序有两种执行方式，即解释和编译。

判断：
高级语言编写的源程序都必须通过编译，产生目标代码后才能运行。
多遍扫描的编译程序的多遍是指多次重复读源程序。
高级语言程序到低级语言程序的转换是基于语义的等价变换。
编译程序中错误处理的任务是对检查出的错误进行修改。
目标程序一定是机器语言程序。
连接装配程序可把经编译程序产生的目标程序变成可执行的机器语言程序。

简答题：
1、 请指出下列错误信息可能是编译的哪个阶段报告的？
①else没有匹配的if；
②数组下标越界；
③使用的函数没有定义；
④在数中出现了非数字信息。
答：①语法分析阶段 ②语义分析与中间代码生成阶段 ③语义分析与中间代码生成阶段
④词法分析阶段
2、 何谓源程序、中间代码和目标代码？它们三者之间有何种关系？
答：所谓源程序是指用某种高级语言编写的程序，它是编译程序的加工对象。目标程序是指低级语言（机器语言或汇编语言）编写的程序，它是编译程序的加工结果。中间代码是其结构介于源程序和目标程序之间的一种机内表示形式，它是编译程序产生的中间临时结果。它们三者之间的关系是等价关系，即结构不同，但语义相同。
二章：
1、文法G：S-àxSx|y所识别的语言是 。
A、xyx B 、（xyx）* C、xnyxn(n≥0) D、x*yx*
2、设有文法G[S]=({S,B},{b},{S-àb|bB,B-àbS},S),该文法所描述的语言是 。
A、L(G[S])={bi|i≥0} B、L(G[S])={b2i|i≥0} C、L(G[S])={b2i+1|i≥0} D、L(G[S])={b2i|≥1}
3、给定文法AàbA|cc，下面的符号串中为该文法句子的是 。
①cc ② bcbc ③bcbcc ④bccbcc ⑤bbbcc
可选项有：
A、①⑤ B、①③④⑤ C、①④ D、①④⑤
4、描述语言L={ambn|n≥m≥1}的文法为 。
A、Z--->Abb A-àaA|a B-àbB|b
B、A-àABb A-àAa|a B-àaBb|b
C、Z-àAb A-àaAb|a
D、Z-àaAb A-àAb|aAb|ε

1、假定G是一个文法，S是它的开始符号。如果S===〉α，则称α是一个句型，仅包含的句型称为句子。
2、设有文法G[S]:S-àbB B-àcC BàcCe C-àdS S-àaB，则VN={ },VT={ }。

判断
一个上下文无关文法的开始符号可以是终结符或非终结符。
1型文法对规则的限制比2型文法对规则的限制要多一些。

简答题：
1、令文法G为：
NàD|ND
Dà0|1|2|3|4|5|6|7|8|9
(1)文法G定义语言是什么？
(2)给出句子0127的最左推导和最右推导。
答：(1)G的语言是任意的数字串：L(G)={a1a2..an|ai∈[0,1,2,…,9]}。
(2) 最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127
最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127
2、证明下述文法是一个二义性文法：
SàiSeS|iS|i
句子iiiei的语法树如下图所示。

S S

i S e S i S

i S i S e S

i i i
同一句子对应两棵不同的语法树，故该文法是二义的。

词法分析:

1、 如果两个文法产生的语言相同，则称这两个文法是等价的。
2、 确定的有限自动机DFA是不确定的有限自动机NFA的一个特例。
3、 两个等价的正规式所表示的正规集相同，高级语言的词法结构一般可以用正规文法来实现。
4、 一张符号表的每一项（或称入口）包含两大栏，即名字栏和信息栏。
5、 符号表的查找和整理技术通常有线性查找、二叉树和杂凑技术。
6、设∑={a,b}，试写一正规式，其表示的正规集为“不以a开头，但以aa结尾的字符串集合”。正规式为：b(a|b)*aa

1、词法分析器的输入是 。
A、单词符号串 B、源程序 C、语法单位 D、目标程序
2、 不是NFA的成分。
A、有穷字母表 B、唯一的初始状态 C、终止状态集合 D、有限状态集合
3、在词法分析阶段不能识别的是 。
A、标识符 B、运算符 C、四元式 D、常数
4、对编译程序所用到的符号表，涉及的操作不包括 。
A、填写或更新信息栏内容 B、填入新名
C、给定名字，访问它的有关信息 D、输出token字序列

判断：
1、 有限自动机只有一个初态。
2、 对任一个正规式r，都存在一个NFA M，使得L(M)=L(r)。

简答题：
1、设∑={0,1}，试写一正规式，其表示的正规集为：“含有子串010的所有串”。
答：正规式为：(0|1)*010(0|1)*
2、在实现编译程序时，常将词法分析程序从语法分析中独立出来，这样做有什么好处？
答：将词法分析程序从语法分析中独立出来，这样做有以下好处：
①建立高级语言时能独立地研究词法与语法两方面的特性。
②词法规则简单，因此可建立特别适用于这种文法的有效分析技术，也容易实现词法分析程序生成自动化。
③可以就同一个语言为每种不同的机器编写一个词法分析程序，只编写一个共同的语法分析程序，这时只要每一个词法分析程序产生相同的符号内部表示形式供该语法分析程序使用即可。
综合题：
1、设S={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。
构造相应的正规式：(0|1)*1(0|1)
NFA:
1 1

1
0
4
3
2
e e e e 1

0 0
确定化：
I

{0,1,2}
{1,2}
{1,2,3}
{1,2}
{1,2}
{1,2,3}
{1,2,3}
{1,2,4}
{1,2,3,4}
{1,2,4}
{1,2}
{1,2,3}
{1,2,3,4}
{1,2,4}
{1,2,3,4}

0
1
3
2
4
1
0
0 1 0 0

0 1

语法分析：

1、编译过程中，语法分析器的任务是 。
①分析单词是怎样构成的 ②分析单词串是如何构成语句和说明的
③分析语句和说明是如何构成程序的 ④分析程序的结构
A、②③ B、②③④ C、①②③ D、①②③④
2、在通常的语法分析方法中， 特别适用于表达式的分析。
A、算符优先分析法 B、LR分析法 C、递归下降分析法 D、LL（1）分析法
3、一个 指明了在分析过程中的某时刻所能看到的产生是多大一部分。
A、活前缀 B、前缀 C、项目 D、项目集

判断
1、 每个文法都能改写成LL（1）文法。
2、 一个LL（1）文法一定是无二义的。
3、 每一个算符优先文法，必定能找到一组优先函数与之对应。
4、 欲构造行之有效的自上而下分析器，则只需消除左递归。
5、 所有LR分析器的总控程序都是一样的，只是分析表各有不同。
6、 若B为非终结符，则Aàα.Bβ为移进项目。

1、 语法分析最常用的两类方法是自上而下和自下而上分析法。
2、 语法分析器的输入是单词符号串，其输出是语法单位。
3、 一个文法G，若它的预测分析表M不含多重定义入口，则G是LL（1）文法。
4、 LL（1）文法中，第一个L表示从左到右扫描输入串，第二个L表示最左推导。
5、 应用算符优先分析技术分析句型时，每步被直接规约的是最左素短语，而应用LR分析技术时，每步被直接规约的是句柄。
6、 活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。

简答题：
1、对于文法G（S）：Sà（L）|as|a LàL,S|S S
(1)画出句型(S,(a))的语法树
(2)给出句型(S,(a))的短语、直接短语、句柄和素短语。 ( L )

L , S

S ( L )

S

A
短语：S、a、(a)、S,(a)、(S,(a))
直接短语：a,S 句柄：S 素短语：a
2、考虑以下文法G：Sàa|∧|(T)
TàT,S|S
(1)消去G的左递归
(2)经改写后的文法是否是LL(1)的？
答：消左递归：Sà a|∧|(T) TàST’ T’à,ST’|ε
fisrt(S)={a, ∧,(} first(T)={a, ∧,(} first(T’)={,, ε}
follow(S)={#,,,}} follow(T)={}} follow(T’)={}}
1.文法不含左递归
2.每个产生式的候选首符集两两不想交
3. first(T’)∩follow(T’)=φ
所以该文法是LL(1)文法。

综合题：
1、 对下面的文法G：EàTE’ E’à+E|ε TàFT’ T’àT|ε FàPF’ F’à*F’|ε Pà(E)|a|b|∧
(1)计算这个文法的每个非终结符的FIRST和FOLLOW。
(2)证明这个文法是LL(1)的。
(3)构造它的预测分析表。

语义分析和中间代码生成：

1、语义分析和中间代码生成时所依据的是 。
A、语法规则 B、词法规则 C、语义规则 D、等价变换规则
2、终结符具有 属性。
A、传递 B、继承 C、抽象 D、综合
3、后缀式ab+cd+/可用表达式 来表示。
A、a+b/c+d B、(a+b)/(c+d) C、a+b/(c+d) D、a+b+c/d
4、语法制导的翻译程序能同时进行 和语义分析。
A、词法分析 B、语法分析 C、优化 D、目标代码生成
5、四元式之间的联系是通过 实现的。
A、指示器 B、临时变量 C、符号表 D、程序变量

1、语法制导的翻译是基于属性文法的，属性有两类，即综合属性和继承属性。
2、在语法树中，一个结点的综合属性的值由其子结点的属性确定，而继承属性则由该结点的父结点或兄弟结点的某些属性确定。
3、语义分析阶段所生成的与源程序等价的中间表示形式可以有逆波兰表示、三元式表示和四元式表示等。
4、生成中间代码主要是为了使目标代码的优化容易实现。

简答题：
1、给出下列表达式的逆波兰式：
(1)-a+b*(-c+d)
(2)a+b*(c-d)/e-f
答：(1)a-bc-d+*+
(2)abcd-*e/+f-
2、给出-(a+b)*(c+d)-(a+b+c)的三元式和四元式。(其中单目运算—用@表示)
1 (+,a,b) (+,a,b,T1)
2 (@,1,_) (@,T1,_,T2)
3 (+,c,d) (+,c,d,T3)
4 (*,2,3) (*,T2,T3,T4)
5 (+,a,b) (+,a,b,T5)
6 (+,c,5) (+,T5,c,T6)
7 (-,4,6) (-,T4,T6,T7)

优化：
1、下列 优化方法不是针对循环优化进行的。
A、强度削弱 B、删除归纳变量 C、删除公共子表达式 D、代码外提
2、对于一个基本块来说，正确的说法是 。
A、只有一个入口语句和一个出口语句
B、有一个入口语句和多个出口语句
C、有多个入口语句和一个出口语句
D、只有多个入口语句和多个出口语句

判断：
数组元素的地址计算与数组的存储方式有关。
循环中的不变运算都可以提到循环外。

根据优化设计到的程序范围，优化可分为局部优化、循环优化和全局优化三个不同的级别。
局部优化是在基本块范围内进行的一种优化。
在优化中，可把循环中的不变运算提到循环外去，这种方法称为代码外提。

简答题
1、已知三地址代码序列为：
(1) i:=1
(2) i:=i+1
(3) j:=1
(4) j:=j+1
(5) k:=i mod j
(6) if k≠0 goto (4)
(7) if i≠j goto (10)
(8)write I
(9)writeln
(10) if i<10000 goto(2)
(11)halt
划分基本块，并画出流图
read C
A:=0
B:=1
L1:A:=A+1
iF B≥C goto L2
B:=B+1
goto L1
L2:write A
halt
2、试把以下程序划分为基本块并作出其程序流图。
read C
A:=0
B:=1
L1:A:=A+1
iF B≥C goto L2
B:=B+1
goto L1
L2:write A
halt

2、 试构造以下基本块G的DAG
(1)T0：=3.14
(2)T1：=2*T0
(3)T2：=R+r
(4)A：=T1*T2
(5) B：=A
(6) T3：=2*T0
(7)T4：=R+r
(8T5：=T3+T4
(9)T6：=R-r
(10) B：=T5*T6

N1
N2
N6
N8
N5
N7
N4
N3
3.14
6.28
T0
r
R
+
T1,T3
*
-
T6
T2,T4
A,T5
B
*

已知如下翻译模式，用回填法给出a>b or c>d and e>f 的四元式序列，要求给出简单过程。
文法及其翻译模式如下：
(1)E→E1 and M E2 {backpatch(E1.truelist,M.quad);
E.truelist:= E2.truelist)
E.falselist:=merge(E1.falselist,E2.falselist )
(2) E→E1 or M E2 {backpatch(E1.falselist,M.quad);
E.truelist:=merge(E1.truelist,E2.truelist)
E.falselist:=E2.falselist}
(3)E1→id1 relop id2 {E.truelist:= makelist(nextquad);
E.falselist:=makelist(nextquad+1);
Emit(‘j’relop.op ‘,’id1.place ‘,’id2.place ‘,’ ‘0’ );
Emit(‘j,-,-,0’)}
(4)M→ε {M.quad:=nextquad}

四元式序列为：
100 （j>，a，b，0）
101 （j，--，--，102）
102 (j>，c，d，104)
103 (j，--，--，0）
104 (j>，e，f，0)
105 (j，--，--，0）
有文法G（S）：
S→A|B
A→aAb|c
B→aBb |d
试构造此方法的LR（0）项目集规范族。
1)将文法G拓广为文法G’

15

S’->S
S->A
S->B
A->aAb
A->c
B->aBb
B->d

2)列出LR（0）的所有项目：
1．S’->•S 5. A->•aAb 9. A->•c 13. B->•aBb 17.B-> •d
S->S• 6. A->a•Ab 10. A->c• 14. B->a•Bb 18 B->d•
S->• A 7. A->aA•b 11. S->•B 15. B->aB•b
S->A• 8.A->aAb• 12. S->B• 16 B->aBb•
3)用ε-CLOSURE办法构造文法G’的LR（0）项目集规范族：
I0: S’->•S ,S->• A, A->•aAb, A->•c, S->•B, B->•aBb, B-> •d
I1: S’->S•
I2: S->A•
I3: S->B•
I4: A->a•Ab, A->•aAb, A->•c, B->a•Bb, B->•aBb, B-> •d
I5: A->c•
I6: B->d•
I7: A->aA•b
I8: A->aAb•
I9: B->aB•b
I10: B->aBb•

已知现在寄存器R，其中A是活跃变量，试将以下三地址代码翻译成汇编代码的形式。
T1：=A+B
T2：=T1*C
A：=T2+D
目标代码序列为：
LD R,A
ADD R,B
MUL R,C
ADD R,D
ST R,A