编译原理是通过一定的过程来转换的，我们将高级语言编写的代码翻译成对应的机器语言。
我把编译过程按照理解的程度画了一个图，如下面所示，
以考带学编译原理部分主要掌握的重点知识是：
1、文法：
1.1文法定义
1.2文法分类
2、正规式
2.1正规式与正规文法之间的转换
3、有限自动机
3.1确定的有限自动机与不确定的有限自动机的定义。（DFA和NFA）
4、语法分析
4.1语法推导树
文法定义：描述语言的语法结构的形式规则称为文法。
文法G的一个四元组，可表示为G（VT,VN,S, P）。
VT是一个非空有限集，每个元素称为终结符。（终结符不能单独出现在推导式左边，不能被分解，也不能被代替。一般用小写字母表示）
VN是一个非空有限集，每个元素称为非终结符。（非终结符理解为可以拆分的元素，一个程序可以理解为一个非终结符。一般用大写字母表示）
S是一个产生式集合（有限）。
P是一个非终结符，称为开始符号；它至少要在一条产生式中作为左部出现。
文法的描述：α→β
例子：
a→b （×）（这种写法是错误的，因为a是终结符，不能单独的出现在推导式左边）
S→aT （√）（S 、T是非终结符，a是终结符）
文法分类：
0型文法：对任一产生式α→β，都有α∈(VN∪VT)*，且α至少包含一个非终结符，
β∈(VN∪VT)*
1型文法：此文法对应于线性有界自动机。他是在0型文法的基础上每一个产生式α→β，都有|β|≥|α|。这里的|β|表示的是β的长度。
特例：α→ε也满足1型文法。
2型文法：对任一产生式α→β，都有α∈VN， β∈(VN∪VT)*
3型文法（1）右线性文法：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN，B∈VN
，a∈VT。
（2）左线性文法：任一产生式α→β的形式都为A→Ba或A→a，其中A∈VN
，B∈VN ，a∈VT。
四种文法的关系图：
正规式：
确定的有限自动机（DFA）：
一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中
1.K是一个有穷集，它的每个元素称为一个状态；
2.Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表
3.f是转换函数，是在K×Σ→K上的映射，即，如
f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；
4. S∈K是唯一的一个初态；
5. Z是K的子集，是一个终态集；
举例：
DFA M=（{S，A，B，C}，{1，0}，f，S，{C}）其中f定义为：
f（S，1）=A
f（B，1）=A
f（S，0）=B
f（B，0）=C
f（A，1）=C
f（C，1）=C
f（A，0）=B
f（C，0）=C
其对应的状态图如图：
不确定的有限自动机（NFA）：
与确定的有限自动机比较，唯一的区别就是不确定的有限自动机的S是K的子集，可以有多个初态值。
举例：
NFA M=（{S，A，B}，{0，1}，f，{S，A}，{B}）
其中
f（S，0）={A}
f（B，0）={A}
f（A，1）={B}
f（B，1）={A}
f（S，1）={S，B}
其对应的状态图如图
语法推导树：
语法树的特征：
1、每个节点都有一个标记，此标记是V的一个符号；
2、根的标记是S；
3、若一节点n至少有一个它自己除外的子孙，并且有标记A，则A可定在VN中；
4、如果节点n的直接子孙，从左到右的次序是节点n1,n2...nk，其标记分别是：A1,A2...Ak,那么A→A1,A2...Ak一定是P中的一个产生式。
构造句型推导树
例子：
文法G=（｛a,b｝,{S,A},S,P）,其中：
S→aAS|a
A→SbA|SS|ba
请构造句型aabAa的推导树。
写开：
S→aAS
S→a
A→SbA
A→SS
A→ba
