编译原理第三版(陈意云 张昱)知识点总结(1).doc

第一章引论

1.什么是编译程序、解释程序

编译程序将源程序(高级语言)保义地翻译为低级的目标程序(汇编语言)的程序

解释程序用源程序，初始数据计算程序的结果

2.编译的各个阶段

记号流(记号名+属性值)分析树(语法树)

记号流(记号名+属性值)

分析树(语法树)

语义树(带有语义信息的语法树)

语法分析：记号流

语义分析：语法树

中间代码生成

代码优化

代码生成：将优化后的代码翻译为目标语言

3.编译原理的其他辅助结构

符号表：名称，类型，属性值，…

出错处理：程序错误的分类，出错处理的目标与方法

字符流

1

词法分析器

记号流

L

语法分析器

语法树

语义分析器

语法树

中间代码生成器

↑

中间表示

独立于机器的代码优化器

中间表示

代码生成器

目标机器代码

依赖于机器的代码优化器

目标机器代码

符号表

第二章词法分析

词法分析是编译的第一阶段，产生用于语法分析的词法记号序列

1.词法分析器的功能

词法分析器作为语法分析器的一个字程序，接受语法分析器的命令，扫描后面的字符直到发

现一个字符记号

剥去源程序中的注释和“空白”符

对程序开头的宏定义和文件包含进行处理

2.词法分析器的二元输出

记号名(关键字所属的类别),记号的属性(具体的值)

“记号的属性”可能为一个具体的值，也可能是一个指针，只想符号表中的对应条目

3.词法记号的描述一一串和语言正规式与正规集

1)基本构成

字母表：所有可能出现的字符的集合

字符串：若干字符组成的序列(包括空串)

语言：由字母表生成的所有字符串的集合

2)串的性质

串长：所含字符数目

前缀：以字符串第一个字符开头的所有子串

e.g.x=abc,则e,a,ab,abc均是x的前缀

3)语言的运算

运算

定义

L和M的并

(写成LUM)

LUM=|sls属L或s属M

L和M的连接

(写成LM)

LM=|stls属L且t属M|

L的闭包

(写成L*)

表示零个或多个L.连接的并集

L.的正闭包

(写成L*)

t2-Ut,t表示一个或多个L.连接的并集

4)正规式与正规集的定义

正规式：用于描述记号(字符串)的构成规则

正规集：正规式描述的语言(匹配正规式的串集)

5)正规式的运算

正规集的运算==正规式的运算

优先级从高到低：*-·-|

正规式

正规集

R|S

L(R)uL(S)

R·S

L(R)·L(S)

R*

(L(R))*

(R)

L(R)

6)正规定义一一用正规式定义记号

e.g.id-letter(letter|digit)*

4.词法记号的识别——有限自动机

正规式NFADFA词法程序

1)NFA和DFA

NFA:非确定有限自动机

在某个状态下接受同样的输入可能到达不同的状态

有空转换

一个串可能存在多条不同的识别路径

规模更小，复杂度低

DFA:确定的有限自动机

在一个状态下接受同样的输入必定到达相同的状态

无空转换

对一个串的识别路径唯一

规模更大，复杂度高

NFA和DFA识别正规语言的能力相同

2)有限自动机的识别过程

FA接受串a,如果存在一个从初态到某个终态的转换路径，该路径上所有标记的字符

依次连接为a

3)根据正规式构造NFA

a)Thopmson方法

图2.14识别正规式ε的NFA

图2.15识别正规式a的NFA

N(s)

E

开始

i

E

N(t)

图2.16识别正规式slt的NFA

N(s)N(t)i开始

N(s)

N(t)

i

图2.17识别正规式st的NFA

E

E

开始iEN(s)E

E

图2.18识别正规式s*的NFA

b)简化Thopmson方法

4)根据NFA导出正规式

第一步：添加新的开始和接受状态

第二步：删除带循环的状态

第三步：归并多条路线

5)根据NFA生成DFA

基本思想：DFA的状态是NFA的非空状态子集

构造方法：

a)DFA的初态包括原NFA的初态及其经过e转换能到达的所有状态，即：

Suo={S?,u|S?→u}=e-closure({So})

其中，ε-closure(T)表示从状态集合T的每一个状态t出发，经过若干空转换

所能到达的所有状态

b)对于一般状态的状态Sd1:

Sdz

Sdz={t,u|s→at,s∈Sai,t→u}=ε-closure({t|s→at,s∈Sat})

c)