编译原理复习提纲

【❤作者简介：研究生在读 IT女; 如果文章有错请指正，让我们一起学习，天天向上，一起进步！ 如果对你有帮助，还请点赞收藏哦~❤】
【写在前面：不要问为什么有的没写答案，原因很简单，我也不会,如果你不懂，别问我，我也不懂，仅供参考，如果有错，请指正，谢谢！】

课堂派题目

第1章

问答题

1、叙述编译程序结果框架。P5（教材）

(1)第一-阶段，词法分析，任务是，输入源程序，对构成源程序的字符串进行扫描和分解，识别出一一个个单词。

(2)第二阶段，语法分析，任务是，在词法基础上，根据语言的语法规则，把单词符号串分解成各类语法单位(语法范畴)。

(3)第三阶段，语义分析与中间代码生成，任务是，对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译

(4)第四阶段，优化，任务是，在对于前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码

(5)第五阶段，目标代码生成，任务是，把中间代码变换成特定机器上低级语言代码。

2、什么是编译的前端和后端？P7

概念上，我们有时把编译程序划分为编译前端和编译后端。前端主要由与源语言有关但与目标机无关的那些部分组成。这些部分通常包括词法分析、语法分析、语义分析与中间代码产生， 有的代码优化工作也可包括在前端。后端包括编译程序中与目标机有关的那些部分，如与自标机有关的代码优化和目标代码生成等。通常，后端不依赖于源语言而仅仅依赖于中间语言。

3、编译过程的五个阶段，哪些阶段是与硬件⽆关，哪⼀些是与硬件相关的？

前四个阶段与硬件无关，最后一个阶段与硬件有关。

第⼆章

问答题：

1、描述乔姆斯基四型⽂法。P34

乔姆斯基把文法分为0、1、2、3型四种，0强于1, 1强于2…
0型文法也称短语文法，能力相当于图灵机
1型文法也称上下文有关文法，非终结符替换时务必考虑上下文关系条件
2型文法也称上下文无关文法，非终结符替换时无需考虑上下文
3型文法也称正规文法/左线性、右线性文法。

2、什么是句型、句⼦? P29

假定G是一个文法，S是它的开始符号，如果
　　*
S　=>　α

则称α是一个句型；

仅含终结符的句型是一个句子；

文法G所产生的句子的全体是一个语言，记为L(G)。

3、什么是语⾔？⽤形式语⾔描述什么是语⾔。P29

假定G是一个文法，S是它的开始符号，如果
　　*
S　=>　α

则称α是一个句型；

仅含终结符的句型是一个句子；

文法G所产生的句子的全体是一个语言，记为L(G)。

第三章

问答题：

1、请⽤状态图和正规式描述标识符。P41

状态图

2、确定有限⾃动机的形式化描述。P47

对状态图进行形式化，则可以下定义:

自动机M是一个五元式M=(S, Z,f, So, F),其中:1. S:有穷状态集，

2. Z:输入字母表(有穷),

3. f:状态转换函数，为Sx2 >S的单值部分映射，f(s, a)=s’表示:当现行状态为S,输入字符为a时，将状态转换到下一一状态s’。我们把s’称为s的一个后继状态。

4. So∈S是唯一的一个初态;

5. F（属于）S:终态集(可空)。

3、⾮确定有限⾃动机的形式化描述P49

4、什么是lex？P61

解答题：

1、64⻚12题

（找到的类似题目）

第四章

问答题：

1、⾃上⽽下语法分析为什么要消除左递归？P68（下面）如何消除左递归？P69

为了构造不带回溯的自上而下分析算法

2、⾃上⽽下语法分析为什么要消除算法的回溯？P68（中间）

含有左递归的文法会使自上而下的分析过程陷入无限循环

3、请写出First集（P71）和Follow集（P73）的形式化定义。

怎么求first集和follow集 DJ写的很详细

4、什么是LL（1）⽂法？P73

5、简述LL（1）分析的基本思想。P73

6、递归下降分析有什么优缺点？P74-75

好处是，直观易懂，便于表示左递归消去和因子提取。
缺点 。。。（我也不知道）
解答题：

1、简单重复简单描述第76⻚，5节有关LL（1）分析过程。

预测分析表 栈 。。。

2、第82⻚第3题

（1）

第五章

问答题：

1、什么是短语？什么是直接短语？什么是句柄？P85

2、什么是规范规约？什么是规范推导？P86

3、什么是前缀？什么是活前缀？P104

4、简述LR分析的基本思想。P99

最左规约-最右推导的逆过程

5、什么是LR分析中的有效项⽬？

解答题：

1、第134⻚第5题的（1）和（2）

2、简单重复简单描述第101⻚⾄110⻚，有关LR（0）分析过程。

第六章

问答题：

1、什么是属性⽂法？什么是综合属性？什么是继承属性？P136

第七章

问答题：

1、中间代码⽣成对编译器构造的意义是什么？P166（中间）

这样做的好处是:

(1)便于进行与机器无关的代码优化工作;

(2)使编译程序改变目标机更容易;

(3)使编译程序的结构在逻辑上更为简单明确。以中间语言为界面，编译前端和后端的接口更清晰。

第10章

问答题：

1、代码优化的原则是什么？P272

(1)等价原则。经过优化后不应改变程序运行的结果。
(2)有效原则。使优化后所产生的目标代码运行时间较短，占用的存储空间较小。
(3)合算原则。应尽可能以较低的代价取得较好的优化效果。

第11章

问答题：

1、代码⽣成器的输出是⽬标程序，⽬标程序有哪⼏种形式？P309

(1)能够立即执行的机器语言代码,所有地址均已定位(代真)。

(2)待装配的机器语言模块。当需要执行时，由连接装人程序把它们和某些运行程序连接起来,转换成能执行的机器语言代码。

(3)汇编语言代码，尚需经过汇编程序汇编,转换成可执行的机器语言代码。

参考题目

选择题

第一章

单项选择题

1.将编译程序分成若干个“遍”是为了_【b】__
a.提高程序的执行效率
b.使程序的结构更加清晰
c.利用有限的机器内存并提高机器的执行效率
d.利用有限的机器内存但降低了机器的执行效率

2.构造编译程序应掌握—【d】
a.源程序
b.目标语言
C.编译方法
d.以上三项都是

3. 变量应当_【c】
   a.持有左值
   b.持有右值
   c.既持有左值又持有有值
   d.既不持有左值也不持有右值

4.编译程序绝大多数时间花在【d】上?
a. 出错处理
b.词法分析
c. H标代码生成
d. 建管理表格

5._【d】不可能是目标代码。
a. 汇编指令代码
b.可重定位指令代码
c.绝对指令代码
d 中间代码

6.数组A1—2.,1–10]的首地址偏移量为0,按列存储，每个元素占一个字节，存储基按字节编址，则A[ij]的偏移地址为_【d】_.

a. (i-1)X 10+(j-1)
b. (i-])X20H(j-1)
c. (i-1)+(-1)X10
d. (i-1)+(j-1)X20

7.使用__【a】 可以定义一个程序的意义。
a.语义规则
b.词法规则
C.产生规则
d.左结合规则

1.表达式x:=5中，变量x__【c】_。
b.只有右值
a. 只有左值
c.既有左值又有右值
d.没有左值也没有右值

2. 词法分析器的输入是【b】
   a. 单词符号串
   b.源程序
   c.语法单位
   d.日标程序

3. 中间代码生成时所遵循的是【c】
   a. 语法规则
   b.训法规则
   d.语义规则
   d.等价变换规则

4.编译程序是对【d】
a. 汇编程序的翻译
b.高级语言程序的解释执行
C.机器语言的执行
d.高级语言的翻译

5.词法分析应遵循【c】
a.语义规则
b.语法规则
c.构词规则
d.等价变换规则

第二章

1.词法分析所依据的是【b】
a.语义规则
s. 构词规则
c. 语法规则
d.等价变换规则

2.词法分析器的输出结果是【c】
a. 单词的种别编码
b.单词在符号表中的位置
c.单词的种别编码和自身值
d.单词自身值

3.正规式M;和M2等价是指【d】
a. M1和M2的状态数相等
b.M和M2的有向弧条数相等
C. M1和M2所识别的语言集相等
d. Mi和M2状态数和有向弧条数相等

4.状态转换图(见图2.5)接受的字集为__【b】_。

a.以0开头的二进制数组成的集合
b.以0结尾的.二进制数组成的集合
c.含奇数个0的二进制数组成的集合
d.含偶数个0的一.进制数组成的集合

5.词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，__【b】_。
a. 词法分析器应作为独立的一遍
b.词法分析器作为子程序较好
c. 词法分析器分解为多个过程，由语法分析器选择使用
d.词法分析器并不作为一个独立的阶段

1.词法分析器的输入是【b】
a.单词符号串
b.源程序
c.语法单位
d.目标程序

2.如果L(M)-L(M).则M与M’【a】
a. 等价
b. M与M都是二义的
c. M与M’都是无一义的
d.他们的状态数相等

3.图2.56所示的状态转换图接受的字集所对应的正规式为【d】__。

第三章

1.文法G: S-> xSxly所识别的语言是【c】

2.文法G描述的语言L(G)是指【a】

3.有限状态自动机能识别【c】
a. 上下文无关文法
b…上下文有关文法
C.正规文法
d.短语文法

4.设G为算符优先文法，G的任意终结符对a、b有以下关系成立【c】___。
a. 若f(a)>g(b), 则a>b
b.若f(a)<g(b), 则a<b
c.a~b都不一定成立
d.a~b 一定成立

5.如果文法G是无二义的，则它的任何句子a

【a】

a.最左推导和最右推导对应的语法树必定相同
b.最左推导和最右推导对应的语法树可能不同
c.最左推导和最右推导必定相同
d.可能存在两个不同的最左推导，但它们对应的语法树相同

6. 由文法的开始符经0步或多步推导产生的文法符号序列是【c】
   a短语
   b.句柄
   c.句型
   d.句子

7.文法G:

E一>E+TT T->T*P|P P一>(E)|T 

则句型p+T+i的句柄和最左素短语分别为____。

a.P+T和i

b.P和P+T
c.i和P+T+i
d.P和P

8.设文法为:

S->SA|A A->a|b 

则对句子aba,下面【d】_是规范推导。

a. S-SA-SAA-AAA-aAA=abA=aba
b. S=SA=SAA-AAA=AAa=>Aba= >aba
C. S-SA-SAA=>SAa -Sba->Aba-aba
d. S=SA=Sa= >SAa-Sba=Aba-aba

9.文法G:

S->b|^|(T) T->T.SIS 

则FIRSTVT(T)-【c】"
a. {b,^,( }
b. {b,^,)}
c. {b,^,(,. }
d. {b,^,),. }

1、产生正规语言的文法为【d】“
a. 0型
b.1型
C,2型
d.3型

2 任何算符优先文法【d】优先函数。
a.有一个
b.没有
c. 有若干个
d.可能有若千个

3.采用自上而下分析，必须【c】
a 消除左递归
b.消除右递归
c.消除回溯
d.提取公共左因子

4.设a、b、c是文法的终结符，且满足优先关系a二b和b=c，则_【d】

3、 必有a二c
b.必有c二a
c.必有b二a
d.a~c都不一定成立

5.在规范归约中，用【b】__来刻画可 归约串。
a. 直接短语
b.句柄
c.最左素短语
d. 素短语

6.有文法G:

E->E*TIT T->T+i|i 

句子1+2*8+6按该文法G归约，其值为【b】
a.23
b.42
C.30
d.17

7.规范归约是指【b】
a.最左推导的逆过程
b.最右推导的逆过程
C.规范推导
d最左归约的逆过程

8.文法G:

S-S+T|T T-T*P|P P->(S)|i 

则句型P+T+i的短语有_【b】

a. i,P+T

b. P,P+T，i,p+T+i

C. P+T+i

d. P，P+T,i

第四章

单项选择题

1. 若a为终结符，则A-a●a为【b】项目。

a.归约

b.移进

C.接受

d.待约
【1. A→a●称为归约项目:对文法开始符S’的归约项目，如S’→a●称为接受项目，A-a●BB (B 为非终结符)称为待约项目，A-a◆aβ (a 为终结符)称为移进项目。在此选b。】
2.两个LR(1)项目集如果除去

【c】_后是相同的，则称这两个LR()项目同心。

a.项目

b.活前缀

C.搜索符

d.前缎

3.同心集合并不会产生【c】__冲突。

a.二义

b.移进/移进

c.移进/归约

d.归约1归约

4. 左结合意味着【b】

a.打断联系实行移进

b,打断联系实行归约

C.建立联系实行移进

d.建立联系实行归约

5.若项目集k含有A→a●，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→a.”动作的一定是【d】

a. LALR文法
b. LR(0)文法
c. LR(1)文法
d. SLR(1)文法
【当用产生式A→a归约时，LR(0)无论面临什么输入符号都进行归约: SLR(1)则仅当面临的输入符号a∈FOLLOW(A)时进行归约: LR(1)则当在把a归约为A的规范句型的前缀BAa前提下，当a后跟终结符a时，才进行归约:因此选d.】
6. 就文法的描述能力来说，有【c】___。

a. SLR(1) C （属于）LR(0)
b. LR(1) CLR(0)
c. SLR(1)CLR(1)
d. 无二义文法CLR(1)

7.在LR(0)的ACTION子表中，如果某-行中存在标记为“rj”的栏，则_【a】 -。
a.该行必定填满rj
b.该行未填满rj
c.其他行也有rj
d. goto 子表中也有rj

8.一个_【c】指明了在分析过程中的某时刻所能看到产生式多大一部分。
a.活前缀
b.前缀
c.项目
d.项目集

1.若B为非终结符，则A-a●B，β为【d】_项目。
a.接受
b.归约
c. 移进
d.待约

2. 同心集合并有可能产生新的【d】_冲突。

a. 归约
b, 移进/移进
C. 移进/归约
d.归约1归约
3.右结合意味着【d】

a, 打断联系实行归约

b.建立联系实行归约

c. 建立联系实行移进

d,打断联系实行移进

4.若项目集1含有A→g.，则在状态K时，无论面临什么输入符号都采取“A-c归约”的动作一定是【c】

a. LR(1)文法b. LALR(U)文法

c. LR(0)文法

d. SLR(I)文法

5.就文法的描述能力来说，有_【d】__"

第五章

单项选择题

1.中间代码生成时所依据的是【c】
a.语法规则
b. 词法规则
c.语义规则
d.等价变换规则

2.四元式之间的联系是通过【b】 实现的。
a.指示器
b.临时变量
c.符号表
d.程序变量

3. 后缀式ab+cd+/可用表达式【b】来表示。
   a a+b/c+d
   b. (a+b)(c+d}
   C. a+b/(c+d)
   d. a+b+e/d

4.间接三元式表示法的优点为【a】
a.采用间接码表，便于优化处理
b. 节省存储空间，不便于表的修改
c. 便于优化处理，节省存储空间
d.节省存储空间，不便于优化处理

5.表达式(7 AV B)A(CVD)的逆波兰表示为___【b】_。

6.中间代码的树型表示入所对应的表达式为__【d】__。

a, A+B+C+D
b. A+(B+C)+D
C. (A+B)+C+D
d. (A+B)+(C+D)

7.四元式表示法的优点为.【c】
a.不便于优化处理，但便于表的更动
b.不便于优化处理，但节省存储空间
C.便于优化处理，也便于表的更动
d.便于表的更动，也节省存储空间

8.终结符具有【d】__属性。
a.传递
b.继承
C.抽象
d.综合

9【c】

I. 表达式(a+b)c的后缀式表示为【c】____。
a. abc+
b. abe*+
c. ab+c*
d. abc+*

2.后缀式【d】对应的表达式是a-(-b)c (@代表后缀式中的求负运算符)。
a. a-b@c
b. ab@-
C. ab@c-
d. ab@c*-

3.使用【a】可以把Z=(X+0.418)*Y/W翻译成四元式序列。
a.语义规则
b. 等价变换规则
c.语法规则
d.词法规则

4.采用右结合规则时，a+bc+d 可解释为_【b】(假设的优先级高于+)。

a. (a+(bc))+d
b. a+(bc)+d)
C. a+d+(bc)
d. (bc}+a+d

5.更动张__【a】 表很困难。
a.三元式
b.间接三元式
c. 四元式
d.三元式和四元式

6.有一语法制导翻译如下所示:

S-> bAb {prnt"1"} A->(B {print"2"} A->+a {print"3"} B-Aa) {print"4"} 

若输入序列为b((a)a)a)b,且采用自下而上的分析方法，则输出序列为【b】
a.
b.
C.
d.

第六章

1.过程的DISPLAY表中记录【b】
a过程的连接数据
b.过程的嵌套层次
c.过程的返回地址
d.过程的入口地址

2.过程P;调用P2时，连接数据不包含【a】
a嵌套层次显示衣
b.老SP
c. 返回地址
d.全局DISPLAY地址
【2.连接数据包括老SP、返回地址和全局DISPLAY地址，故选a】

3.程序所需的数据空间在程序运行前就可确定，称为__【c】 管理技术。
a.动态存储
b.栈式存储
c.静态存储
d.堆式存储

4.堆式动态分配申请和释放存储空间遵守原则【d】。
a.先请先放
b.先请后放
c.后请先放
d.任意
【4.堆式动态分配申请和释放存储空间不一定遵守先请后放和后请先放的原则，故选d.】

5.静态分配允许程序出现【c】
a.递归过程
b.可变体积的数据项目
c. 静态变量
d. 待定性质的名字

1.活动记录中的连接数据不包含【d】
a.老SP
b.返回地址
C.全局DISPLAY地址
d.形式单元

2.Fortan 语言采用静态分配策略时，任一活动的活动记录中不包括【a】
a.控制链
b.机器状态
c.返回地址
d.访问链

3.在编译方法中，动态存储分配的含义是【a】
a.在运行阶段对源程序中的数组、变量、参数等进行分配
b.在编译阶段对源程序中的数组、变量、参数等进行分配
c.在编译阶段对源程序中的数组、变量、参数等进行分配，在运行时这些数组、变
量、参数的地址可根据需要改变
d.以上都不正确

4.在编译时有传名功能的高级程序语言是【d】
a. Fortran
b. Basic
C. Pascal
d. ALGOL

5.栈式动态分配与管理在过程返回时应做的工作有【b】
a.保护SP
b.恢复SP
c. 保护TOP
d.恢复TOP

第七章

1.优化可生成【d】_的目标代码。
a. 运行时间较短
b.占用存储空间较小
c.运行时间短但占用内存空间大
d.运行时间短且占用存储空间小

2.下列_【c】__ 优化方法不 是针对循环优化进行的。
a.强度削弱
b.删除归纳变量
c.删除多余运算
d.代码外提

3.基本块内的优化为【b】
a.代码外提，删除归纳变量
b.删除多余运算，删除无用赋值
c.强度削弱，代码外提
d.循环展开，循环合并

4.关于必经结点的二元关系，下列叙述中不正确的是【d】
a.满足自反性
b.满足传递性
c.满足反对称性
d.满足对称性

5.对个基本块米说，【a】是正确的。
a.只有一个入口语句和一个出口语句
b.有个入口语句和多个出口语句
C.有多个入口谱句和-个出口语句
d.有多个入口语句和多个出口语句

6.在程序流图中，我们称具有下述性质【d】_的结点序列为一个循环。
a. 它们是非连通的且只有一个入口结点
b.它们是强连通的但有多个入口结点
C.它们是非连通的但有多个入口结点
d.它们是强连通的且只有一个入口结点

7.【d】_不可能是目标代码。
A. 汇编指令代码
b.可重定位指令代码
c.绝对指令代码
d.中间代码

1【b】属于局部优化。
a.代码外提
b.删除多余运算
c.强度削弱
d.删除归纳变量

2.下面【c】不能作为一个基本块的入口。
a. 程序的第一个语句
b.条件语句转移到的语句
c.无条件语句之后的下一条语句
d.无条件语句转移到的语句

3.下列【b】优化方法是针对循环优化进行的。
a.复写传播
b.删除归纳变量
c. 删除无用赋值
d.合并己知量

4.属于基本块的优化为【a】
a删除无用赋值
b.删除归纳变量
c. 强度削弱
d.代码外提

5.经过编译所得到的目标程序是__【d】__。
a.二元式序列
b.四元式序列
c.间接三元式
d.机器语言程序或汇编语言程序

6.一个控制流程图就是具有【c】的有向图。
a. 唯一入口结点
b.唯:出口结点
c.唯一首结点
d.唯一尾结点

第八章

1.编译程序使用【b】区别标识符的作用城。
a.说明标识符的过程或函数名
b.说明标识符的过程或函数的静态层次
c.说明标识符的过程或函数的动态层次
d标识符的行号

2.在目标代码生成阶段，符号表用于【d】
a.目标代码生成
b.语义检查
c.语法检查
d.地址分配

3.过程信息表不包含【b】

a.过程入口地址
b.过程的静态层次
c.过程名
d.过程参数信息

4.下列关于标识符和名字的叙述中，正确的为【c】

a. 标识符有”定的含义
b.名字是一个没有意义的字符序列
C.名字有确切的属性
d. a~C都不正确

5.错误的局部化是指_【c】
a.把错误理解成局部的错误
b.对错误在局部范围内进行纠正
c.当发现错误时，跳过错误所在的语法单位继续分析下去
d.当发现错误时立即停止编译，待用户改正错误后再继续编译

参考解答题

还有课堂派实验！！！

（别问我为什么不整理，因为我也不会555）

啊啊啊啊 ~感觉无了