编译原理复习.pdf

编编译译原原理理复复习习

《编译原理》第⼀章：绪论

1.翻译器：把⼀种语⾔变换到另外⼀种语⾔的软件。这两种语⾔别称为源语⾔和⽬标语

⾔。

2.编译器：⼀种翻译器，它的⽬标语⾔⽐源语⾔低级。

3.典型的编译器可以划成6个逻辑阶段：词法析，语法析，语义析，中间代码⽣

成，代码优化，代码⽣成。

4.按照对⽬标机器的依赖性，把编译过程成前端（依赖于源语⾔，独⽴于⽬标机器）和

后端（依赖于⽬标机器，独⽴于源语⾔,只与中间语⾔有关（从中间代码⽣成⽬标代码））。

5.前端包括：词法析，语法析，语义析，中间代码⽣成。

6.后端包括：代码优化，代码⽣成。

7.解释器：不同于编译器的另⼀类语⾔处理器，直接执⾏源程序所指定的运算。解释器的

执⾏效率⽐编译器低，因为解释器⽆法解开循环。

8.遍：编译的⼏个阶段常⽤⼀遍（pass）扫描实现，⼀遍扫描包括读⼀个输⼊⽂件和写⼀

个输出⽂件。

《编译原理》第⼆章：词法析

⼀些概念：

1.词法单元：⼜称单词，是编程语⾔中合法的字符串。

2.词法记号：满⾜某种规则的词法单元，采⽤同⼀种记法——词法记号。该规则称为模式。

3.模式：描述词法单元与词法记号对应关系的规则。是描述源程序中某个记号的词法单

元集合的规则。

4.字母表：符号的有限集合，例：∑={0,1}

串：符号的有穷序列，例：0110,ε

语⾔：字母表上的⼀个串集{ε,0,00,000,…},{ε},?

正规式（运算符的优先级：*连接运算|）

NFA是这样⼀个数学模型，包括

1)状态集合S

2)输⼊字母表∑

3)转换函数mve:S?(∑?{ε})→P(S)

4)唯⼀的初态s∈S

5)终态集合F?S

DFA是这样⼀个数学模型，包括

1)状态集合S

2)输⼊字母表∑

3)转换函数mve:S?∑→S

4)唯⼀的初态s∈S

5)终态集合F?S

第三章语法析

3.1上下⽂⽆关⽂法

上下⽂⽆关⽂法是四元组（VT,VN

,S,P）

1)VT

:终结符集合(⾮空有限集合，记号名是其同义词)

2)VN

:⾮终结符集合（⾮空有限集合）

3)S:开始符号

4)P:产⽣式集合，产⽣式形式:A→α

上下⽂⽆关⽂法没有强制的顺序关系。这点和正规式不同。

推导：把产⽣式看成重写规则，把符号串中的⾮终结符⽤其产⽣式右部的串来代替。最左推导

E?lm-E?lm-(E)?lm-(E+E)?lm-(id+E)?lm-(id+id)

最右推导（规范推导）

E?rm-E?rm-(E)?rm-(E+E)

?rm-(E+id)?rm-(id+id)

⽂法的⼆义性，是指对于符合⽂法规则的同⼀个句⼦，存在两种可能的析树根据运算符的优先级引⼊⾮终结符可消除⼆义

性。

3.2⾃上⽽下析

消除左递归

对产⽣式组

A→Aa1|Aa2|…|Aan|b1|b2|…|bm

?⽤如下产⽣式组替换

A→b1

B|b2B|…|bmB

B→a1B|a2B|…|anB|ε

其中：B为新变量，相当于A’

提取左因⼦

将形如

A→αβ1|αβ2|…|αβm|γ1|γ2|…|γp

的规则改写为

A→αA|γ1|γ2|…|γp和A→β1|β2|…|βm

求FIRST集

FIRST集合计算⽅法

?若X→a..，则将终结符ａ加⼊FIRST(X)中

?若X→ε，则将ε加⼊FIRST(X)中

?若X→Y…，且Y属于⾮终结符，则将FIRST(Y)\{ε}加⼊到FIRST(X)中

?若X→Y1Y2..YK,且Y1,Y2,..Yi-1(2≤i≤k)都是⾮终结符，且Y1,Y2,..Yi-1的FIRST集

合中均包含ε，则将FIRST(Yj)的所有⾮ε元素加⼊到FIRST(X)中，（j=1,2,..i）.特别地，若Y1~YK均有ε产⽣式，则

将ε加到FIRST(X)中。

求fllw集

FOLLOW集合计算⽅法

?

对⽂法开始符号S,置$于FOLLOW(S)中。?

若有A→αBβ，则将FIRST(β)\{ε}加⼊FOLLOW(B)中。（此处α可