编译原理总复习.doc

alphabet字母表 symbol符号 string串 length长度 catenation连接
power方幂 gather集合 product乘积 empty set空集 closure 闭包
program程序 logic structure逻辑结构 generating产生 executing执行
machine language机器语言 instruction指令 function函数 assembler汇编程序
interpreter解释程序 translator翻译程序 source language源语言 finite有穷的
source program源程序 target language目标语言 attribute属性 possess占有
preprocess预处理 compiler编译程序 break中断 Intermediate language中间语言
definition定义 reconstructed重构 normal正规 character sequences 符号序列
programming language程序设计语言 operand操作数 instead替换 memory内存
element元素 high-level language高级语言 object program目标程序
address地址 input输入 output输出 terminal终结符 compilation编辑
equivalence等价 nonterminal非终结符 recursion递归 deterministic确定的
nondeterministic非确定的 Backus-Normal Form巴科斯范式 syntax语法
tree树 expression表达式 grammar文法 automata自动机 prefix前缀
suffix后缀 infix中缀 identify识别 identifier标识符 analyses分析
predigest化简 symbol set符号集 performed执行 forecast预测 state状态
formula产生式 conversion变换 precedence优先 simple简单 handle句柄
operator算符 terminal state终态 first state初态 optimizer优化程序
concatenation连接 word单词 alphabet字母表 lexical词法 scanner扫描器
analyzer分析器 syntax tree语法树 symbol table符号表 pass趟，遍
regular expression正规表达式 code generator代码生成器 backdate回溯
derivation推导 educe推导 derivation tree推导树 path路径 ambiguous二义性
simple phrase简单短语 context-sensitive上下文有关 context-free上下文无关
right-linear 右线形 phrase-structured短语结构 regular grammar文法
direct derivation直接推导 sentence句子 sentential form句型 root node根结点
subtree子树 semantic语义的 terminal node端末结点 attribute grammar属性文法canonical derivation规范推导 top-down自上而下 bottom-up自下而上
viable prefix活前缀 nondeterminate finite automata非确定的有穷自动机
总复习
一、基本概念：
1、请简单解释编译程序的概念。
答：编译程序是现代计算机系统的基本组成部分之一。简而言之, 编译程序就是一种语言翻译程序。所谓翻译程序，是指这样一个程序，它能将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言) 程序。编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。
2、请解释编译程序的前端和后端的概念，试问前端通常包括那些阶段，后端包括那些阶段？ (10分)
答：编译程序的前端只依赖于源语言，由几乎独立于目标机器的阶段或阶段的一部分组成。编译程序的前端通常包括词法分析程序、语法分析程序、语义分析程序、中间代码生成程序及相关的表格管理程序和出错处理程序。编译程序的后端是指编译器中依赖于目标机器的部分,它们一般独立于源语言，而与中间代码有关。通常包括目标代码生成程序、代码优化程序以及相关的表格管理程序和出错处理程序。
3、语言的语法描述方法有其三，请列举出来。
答：用自然语言描述语言的语法，用语法图描述语言的语法和用巴科斯-瑙尔范式及扩充的巴科斯-瑙尔范式 (EBNF)两种形式给出语言的语法描述。
答：根据 Chomcky文法的定义，该文法是2类文法，即上下文无关文法。
4、请写出Chomcky关于文法的定义。
答： Chomcky文法的定义：文法G定义为四元组,记为:
G=(VN,VT,P,S)
其中：VN —非空有限的非终结符号集
VT —非空有限的终结符号集
P — 产生式集
S — 开始符号/识别符号
5、已知文法：（20分） E→X|E+X
X→Y|X*Y
Y→（E）|i
请判定该文法是那类文法？
5、简单说明词法分析程序的主要任务。
答：词法分析程序是编译程序的一个构成成分，它的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。
6、请简单介绍确定的有穷自动机。
答：确定的有穷自动机也称有限自动机，它是作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合。具体而言，一个确定的有穷自动机可以用一个五元组表示，即M=(K,Σ,f, S,Z)。K是一个有穷状态集，Σ是一个有穷字母表，f是转换函数，S是初态，Z是一个终态集。
7、简单说明语法分析程序。
答：语法分析程序是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)，目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）分析两大类。
8、请说明有关句型、句子、句柄概念？（10分）
答：设G[S]是一文法，如果符号串x是从文法的识别符号推导出来的，则称符号串x是文法G[S]的句型。若符号串x还满足仅由终结符号组成的条件，则称x为G[S]的句子。一个句型的最左直接短语称为该句型的句柄。
9、请说明有关规范句型的概念？
答：最右推导，即推导的每一步都是替换当前句型最右边的非终结符，被称为规范推导，由规范推导得到的句型称为规范句型。
10、请说明有关预测符号集的概念？
答：产生式A→α预测符号集表示：在确定的自上而下的语法分析过程中，当需要替换的非终结符是A时，而当前需要匹配的终结符属于产生式A→α预测符号集中的符号，则能够采用该产生式进行推导。当α不能推出ε时，产生式A→α预测符号集是α的首符号集；当α能推出ε时，产生式A→α预测符号集是α的首符号集与A的后跟符号集的并集，但是不包括ε。
11、简单说明LR分析器由那几部分组成？
答：简单而言LR分析器由3部分组成，它们是：总控程序、分析表（ACTION表和GOTO表）和分析栈（符号栈和状态栈）。
12、简单说明拓广文法、活前缀和可归前缀的概念？
答：拓广文法：在原文法中增加一个产生式，Ｓ′→Ｓ，得到的新文法称之为原文法的拓广文法；活前缀：在规范句型中，不包括该句型句柄右边符号的前缀称之为活前缀；可归前缀：活前缀与句柄有3种关系，：活前缀不含句柄的任何符号；：活前缀含有句柄的部分符号；：活前缀包含句柄的全部符号。包含句柄的全部符号的活前缀称之为可归前缀。
13、请简单说明编译中的语义处理。
答：编译中的语义处理是指两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。第二，如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。
14、编译程序所使用的中间代码经常见的有那几种形式？
答：编译程序所使用的中间代码常见的有逆波兰记号、三元式、四元式和树形表示。
15、简单说明代码优化的概念。
答：所谓代码优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。
16、简单说明代码生成器的概念。
答；代码生成器是把某种高级程序设计语言编写的程序经过语法、语义分析，或再经过优化后的中间代码作为输入，将其转换成特定机器的机器语言或汇编语言作为输出，这样的转换程序称为代码生成器。

二、应用题（每题10分，共40分）
1、文法G（S）的产生式为：S→aAS,A→SbA,A→aA,A→b,S→a,请写出该文法的非终结符号集、终结符号集及文法的开始符号，根据文法画出句型aSbSbaAa的语法树，并且指出该句型的短语、直接短语和句柄？
答：该文法的非终结符号集是{S,A}、终结符号集是{a,b}及文法的开始符号是{S}
句型aSbSbaAa的语法树为：

该句型的短语为：aA,SbaA, SbSbaAa, aSbSbaAa,a
直接短语为：aA, a
句柄为：aA
2、正规式为：b((ab)*|bb)ba，请根据所列正规式，画出对应的NFA的状态转换图，并且将NFA确定化，画出对应的DFA的状态转换图。
答： （1）正规式为：b((ab)*|bb)ba 对应的NFA的状态转换图如下：

（2）利用转换矩阵将以上NFA确定化，转换矩阵如下：

I
Ia
Ib
{1}

{2,3,4,7}
{2,3,4,7}
{5}
{6,8}
{5}

{4,7}
{6,8}
{9}
{7}
{4,7}
{5}
{8}
{7}

{8}
{8}
{9}

{9}

（3）将状态重新编号，NFA确定化后，生成DFA状态转换矩阵如下：

a
b
0

1
1
2
3
2

4
3
7
5
4
2
6
5

6
6
7

7

（4）DFA状态转换图如下：

3、请根据文法G写出所有产生式的预测符号集，并且判定该文法是否是LL(1)文法，如果是，请画出对应的预测符号表。
文法G(S)：S→aBA A→Ba|ε B→bB|a
答：（1）求出各个产生式的预测符号集：
Select(S→aBA)={a}
Select(A→Ba)={b,a}
Select(A→ε)={#}
Select(B→bB)={b}
Select(B→a)={a}
(2) 由于Select(A→Ba) ∩ Select(A→ε)=Φ
Select(B→bB) ∩ Select(B→a)=Φ
所以该文法是LL(1)文法。
(3) 该文法对应的LL(1) 预测符号表如下：

a
b
#
S
→aBA

A
→Ba
→Ba
→ε
B
→a
→bB

4、写出下面所列的文法的拓广文法，并且找出该拓广文法所有的项目，请构造识别该文法所有活前缀的NFA。
文法G(S)：S→SbBa|B B→a|ε
答：（1）该文法的拓广文法是：
S´→S S→SbBa|B B→a|ε
(2) 该拓广文法所有的项目为：
(0) S´→.S ①S´→S.
②S→.SbBa ③S→S.bBa
④S→Sb.Ba ⑤S→SbB.a
⑥S→SbBa. ⑦S→.B
⑧S→B. ⑨B→.a
⑩B→a. ⑾B→.
(3) 识别该文法所有活前缀的NFA如下：

5、根据以下文法，直接写出该文法的拓广文法和所有项目，构造项目集规范族及识别该文法所有活前缀的DFA，由识别该文法所有活前缀的DFA，判定该文法是否是LR(0)文法，如果是请构造相应的LR（0）分析表，通过查找 LR（0）分析表写出对于输入串ade#的分析过程。
文法G(S)：①S→ABC ②A→a ③B→b ④B→d ⑤C→e
答：（1）该文法的拓广文法是：S´→S S→ABC A→a B→b B→d C→e
该文法的所有项目：共计14个
S´→.S S´→S. S→.ABC S→A.BC S→AB.C S→ABC. A→.a A→a.
B→.b B→b. B→.d B→d. C→.e C→e.
（2）直接构造项目集规范族及识别该文法所有活前缀的DFA，如下图所示：

从DFA可以看出项目集规范族中不存在移进与归约的冲突，也不存在归约与归约的冲突，所以可以判定该文法属于LR(0)文法
(3)由DFA直接构造相应的LR（0）分析表如下：

状态
ACTION
GOTO
a
b
d
e
#
S
A
B
C
0
S5

1
2

1

ACC

2

S6
S7

3

3

S8

4
4
r1
r1
r1
r1
r1

5
r2
r2
r2
r2
r2

6
r3
r3
r3
r3
r3

7
r4
r4
r4
r4
r4

8
r5
r5
r5
r5
r5

（4）通过查找LR（0）分析表，对于输入串ade#的分析过程如下：

步骤
状态栈
符号栈
输入串
ACTION表
GOTO表
1
0
#
ade#
S5

2
05
#a
de#
r2
2
3
02
#A
de#
S7

4
027
#Ad
e#
r4
3
5
023
#AB
e#
S8

6
0238
#ABe
#
r5
4
7
0234
#ABC
#
r1
1
8
01
#S
#
acc