编译原理练习题

编译原理练习题

⼀章：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、x n yx n(n≥0) D、x*yx*

2、设有⽂法G[S]=({S,B},{b},{S-→b|bB,B-→bS},S),该⽂法所描述的语⾔是。

A、L(G[S])={b i|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={a m b n|n≥m≥1}的⽂法为。

A、Z--->Abb A-→aA|a B-→bB|b

B、A-→ABb A-→Aa|a B-→aBb|bC、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，则V N={ },V T={ }。

判断

⼀个上下⽂⽆关⽂法的开始符号可以是终结符或⾮终结符。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..a n|a i∈[0,1,2,…,9]}。(2) 最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127

最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>01272、证明下述⽂法是⼀个⼆义性⽂法：

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、设∑={0，1}上的正规集S由倒数第⼆个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造⼀个识别该正规集的DFA。

构造相应的正规式：(0|1)*1(0|1)NFA:确定化：

语法分析：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 素短语：a2、考虑以下⽂法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+*+