编译原理笔记第三部分，由于内容过长所以分为了两部分，跳转链接在总阅读目录处，内容参考：北航软院教师邵兵课堂课件及内容、张莉著《编译原理及编译程序构造》、国防工业出版社的《编译原理——学习指导与典型题解析》、AlvinZH的学习笔记以及个人理解
目前是包含了全部内容的版本，后续会推出精简版和复习知识点版
如有建议或错误错误欢迎在评论中指出或联系我：QQ：847590417
总阅读目录
第一部分：
3.1 词法分析程序的功能及实现方案
3.2 单词的种类及词法分析程序的输出形式
3.3 正则文法及状态图
3.4 正则表达式与有穷自动机FA
第二部分：
本章总内容
重点：词法分析介绍、词法分析单词种类划分、正则文法、状态图、正则表达式、自动机、自动机的转化、表达式文法和自动机的转化、词法分析程序的设计实现，词法分析程序自动生成器LEX。
之前的内容
词法分析介绍、词法分析单词种类划分、正则文法、状态图、正则表达式、自动机、自动机的转化会在第三章的第一部分进行介绍。
3.5 有穷自动机、正则文法、正则表达式的转化
转化流程图：
以下转换的顺序是按图上箭头的顺序进行排序的（NFA包含DFA，所以和NFA的转化可能称之为DFA的转化）。
0.正则文法G转状态图
绘制左线性文法的状态图（状态图只能用于左线性文法，这是和后面的DFA的明显区别）状态图的绘制没有严格规定（右线性的暂时不做考虑）
1.文法的非终结符号是一个个的结点
2.设一开始状态S（句子）
3.对规则Q::=t（t为终结符），需要一条从S到Q的一条弧，弧上标记为t
4.对Q::=Rt，画一条从R到Q的弧，弧上标记为t
（倒，谁规约于谁，谁指向谁）
5.根据自动机方法，可加上开始状态和终止状态标志，识别符号作终止状态，用双圆圈标识
1.DFA M转正则文法 G
规则：
1.对(A,t) = B，写成：A→tB（只推右线性，左线性在推导时可能递归）
2.对每个可接受状态Z（终止状态），增加产生式Z→ε
3.有穷自动机的初态对应文法开始符号，有穷自动机的字母表为文法的终结符号集
例：
规则：（和状态图的转化类似）
1.字母表（弧上的所有符号组成的表）和G的终结符号相同
2.为G中的每个非终结符生成M的一个状态，G大的开始符号S是开始状态S
3.增加一个新状态Z，作为NFA的终态
4.对G中的形如A→tB，其中t为终结符或空字符，A和B为非终结符号的产生式，构造M的一个转换函数(A,t)=B
4.对G中形如A→t的产生式，构造M的一个转换函数(A,t)=Z
例：
他们是等价的
定理：在Σ上的一个字集V，V是Σ*的子集，是正则集合，当且仅当存在一个DFA M使V=L(M).
规则：
一个正则表达式，构建时从左到右拆解分析即可
a. 对空集φ不作处理
b. 对正则式ε，由x射出符号为空符号的弧到y