编译原理知识点.docx

第一章编译概述

1.1翻译程序的三种方式

1.编译：将高级语言编写的源程序翻译成等价的机器语言或汇编语言。

2.解释：将高级语言编写的源程序翻译一句执行一句，不生成目标文件，直接执行源代码文件。

3.汇编：用汇编语言编写的源程序翻译成与之等价的机器语言。

1.2编译程序的五个阶段

1.词法分析：对源程序的字符串进行扫描和分解，识别出每个单词符号。

2.语法分析：根据语言的语法规则，把单词符号分解成各类语法单位。

3.语义分析与中间代码生成：对各种语法范畴进行静态语义检查，若正确则进行中间代码翻译。

4.代码优化：遵循程序的等价变换规则。

5.目标代码生成：将中间代码变换成特定机器上的低级语言代码。

第二章文法和语言

2.1符号串和语言

2.1.1字母表

1.定义：字母表是有穷非空的符号集合。

2.表示：通常用字母表大写字母A，B，…Z和希腊字母Σ表示。

eg：A={0,1}，Σ={a,b,c,d}

3.说明

1）字母表包含了语言中所允许出现的一切符号。

2）字母表中的符号也称字符。

2.1.2符号串

1.定义：由字母表中的符号组成的有穷序列。

2.表示：通常由t，u，v，w，x，y，z等小写英文字母来表示。

3.说明?

1）符号串由构成的符号的种类、数量、顺序共同决定。

2）不包含任何符号的符号串称为空符号串，简称空串，用ε表示。

4.对于给定的字母表Σ，符号串的递归定义如下：

1）ε是Σ上的一个符号串。

2）若x是Σ上的符号串，a是Σ的符号，则xa是Σ上的符号串。并规定

εa=a，aε=a

3）y是Σ上的符号串，当且仅当y由1）和2）导出。

5.子符号串：一个非空符号串中若干连续符号组成的部分。

6.字符串的前缀和后缀

若z=abd是字母表Σ={a,b,c,d}上的符号串，则ε，a，ab，abd都是z的前缀；ε，d，bd，abd都是z的后缀。（正序逆序排序即可，前缀为正序排序的所有子串，后缀为逆序排序的所有子串）

7.符号串之间的运算

1）连接：符号串x，y的连接xy就是把符号串y写在x后面得到的字符串。

eg：若x=ab，y=cd，则xy=abcd，yx=cdab。

2）方幂：若x是符号串，xn表示n个按顺序连接。当n=0时，x0是空符号串ε。

2.1.3语言

1.定义：由字母表上的一些符号串组成的集合。

2.说明

空集?是一个语言，仅含一个空符号串的集合{ε}也是一个语言。?和{ε}是不同的语言。

3.符号串集合之间的运算

1）并集

???设A和B是符号串的集合，则A和B的并集定义为??

A∪B=?{x|x∈Aorx∈B}

2）乘积（我觉得就是笛卡尔积）

???设A和B是符号串的集合，则A和B的乘积定义为??

AB={xy|x∈Aandy∈B}。

eg：若A={a,b}，B={b,c}，则AB={ab,ac,bb,bc}。

对任意符号串集合A，有{ε}A=A{ε}=A。

3）幂运算

???设A是符号串的集合，则A的幂运算定义为

A0={ε}

A1=A

An=AAn-1（n0）

eg：若A={0,1}，则A0={ε}，A1={0,1}，A2={00,01,10,11}。

4）正闭包与闭包

???设A是符号串的集合，则集合A的正闭包A+和闭包A*定义为

A+=A1∪A2∪…∪An∪…

A*=A0∪A1∪…∪An∪…

eg：若A={0,1}，则

A+={0,1,00,01,10,11,000,001,…}，

A*={ε,0,1,00,01,10,11,000,001,…}。

2.2文法和语言的形式化定义

2.2.1文法的形式化定义

1.产生式规则

1）定义：一个产生式规则是一个有序对(A，α)。通常写作A→α或A::=α。

???”→或”::=”表示“定义为”、“由…组成”、“生成”。

2）含义：A→α表示左部符号A生成右部符号串α。

3）若A→α；A→β，则可以写成A→α|β。”|”表示“或”。

4）非终结符号：产生式规则左部出现的符号。

5）终结符号：不是非终结符号的符号。

6）非终结符号既可以出现在产生式规则的左部，也可以出现在产生式规则的右部。终结符号不能出现在产生式规则的左部。

7）非终结符号通常用大写字母或尖括号括起来的部分表示。

2.文法

1）定义：产生式规则的非空有穷集合。由四元组G=(VN，VT，P，Z)组成。

2）VN：是一个非空有穷集合。它的每个元素称为非终结符号。且VN∩VT=?。

3）VT：是一个非空有穷集合。它的每个元素称为终结符号。

4）P：是文法规则(产生式规则)的非空有穷集合，每个产生式规则的形式是A→α或A::=α，其中A∈VN，α∈(VN∪VT)*。

5）Z：是一个非终结符号。称为开始符号或识