编译原理
什么是编译程序，编译系统
编译：将高级语言翻译成汇编语言或机器语言的过程
编译系统：源程序通过预处理器获得预处理源程序，通过编译器获得汇编语言程序，通过汇编器获得重定位机器代码，通过连接器和加载器获得目标机器代码
2.2定义:闭包、正、克林
正闭包：设E为字母表，E的正闭包：E并E2并E3….(由长度正数符号串组成的集合)
克林封包:E是字母表，E克林封包:空并E并EE2并E3…. (任何符号串，长度可由0组成)
啥是句子
句子：设置E为字母表，任意X属于E的克林闭包，x它被称为E上的句子，句子可以行，串
句型：设文法G=(V，T，P，S)，对于?α∈(V∪T)*，如果S通过若干步骤推出α，则称α是G产生的句型
语言：任意L是E克林字母表上的语言
词法单元流：单词内部形式：种类、属性值
句柄：句型分析树中最左边只有父子两代子树的所有叶子从左到右排列。最左直接短语
活前缀是句柄的子集
文法的定义（VTPS代表什么）
V：非空有穷集合、非终结符(语法变量、语法范畴)
T：终结符，V并空称为文法符号或语法符号
P：左边定义为右边(定义，语法规则)
S：开始符号在产生式左侧至少出现一次
推导:最左最右
最左：A->Ba
最右：A->aB
前后缀
前缀：若x=yz，y是前缀，z不是空的是真正的前缀
后缀：若x=yz，z是后缀，同样
文法分类
0型文法：PSG(短语结构文法)
1型文法：CSG(上下文相关文法)，左长小于右长
2型文法：CFG(上下文与文法无关)，左边只有一个非终结符
3型文法：RG(正则文法)A→Ba或A→a，右线性A→aB或A→a
0>1>2>3包含
语法树
CFG语法树称为分析树(parse tree)、推导树(derivation tree)、派生树(derivation tree)
设有CFG G=(V，T，P，S)，G句型最左直接短语叫句柄(handle)
短语：子树的所有叶子从左到右排列，形成相对于子树根的短语。
直接短语:父子两代只有一棵子树，同上
句柄：句型分析树中最左边只有父子两代子树的所有叶子从左到右排列。最左直接短语
规约与推导
最右规定:对应最左推导，即将替换最左侧的非终结符
最左规定:对应最右推导也是如此
最右推导也叫规范推导
最左规则也称为规范规则
二义性
如果一个文法句子有两棵分析树，那么句子是二义的
若文法中含有二义性的句子，则称文法为二义性
词法分析器
输入：字符流
输出：词法单元流
语法分析器（核心部分）
输入：词法单元流
输出：语法树
语义分析器（一般和语法分析同时进行，称为语法制导翻译）
输入：语法树
输出：符号表和语法报错信息
中间代码生成（和语义分析一起称为语义翻译）
输入：语法树
输出：中间表示形式
根据正则文法构造正则表达式
反过来转换
正则文法与Fa（有穷自动机）的转换
正则表达式的运算优先级：*，连接，|
FA有穷自动机：有输入输出信息，内部状态
多个终止状态：多个前缀匹配时，会找最长匹配
正则文法与正则表达式等价与自动机
NFA的画，先把简单的画出来
有穷状态自动机
具有离散输入输出的系统的数学模型
具有有穷个内部状态
根据当前状态和面临输入确定后继的行为
语法分析
最右推导是规范推导
最左规约是规范规约
自顶向下：最左推导（选择最左非终结符替换）
自底向上：最左规约（规范规约）？？？？？？
二义性
如果一个文法的句子存在两棵分析树,那么,该句子是二义性的
如果一个文法包含二义性的句子,则称这个文法是二义性的
如果L(G)中存在一个具有两个或两个以上最左(或最右)推导的句子，则G是二义性文法
自顶向下的问题：回溯，左递归，二义性
解决二义性：
人为定义规则，比如划分优先级和结合性、引入新的非终结符
解决回溯：会删掉不符合的一直找符合的，因为有共同前缀，
解决：将公共因子后面的用其他变量替换如：aA|aB => aS S->A|B
解决左递归：会陷入无穷推导（循环），有直接左递归和间接左递归，
转换成右递归4.2.2
消除二义性：通过引入新的语法变量
回溯问题162：解决：左递归转换成右递归（间接左递归要转换成直接左递归再做）
自顶向下：预测分析法first和follow集计算
Follow：句型中紧跟在A后边的终结符a 的集合，如果 A是某个句型的的最右符号，则将结束符“$”添加
First：串首第一个符号，并且是终结符
什么情况是LL1文法
LL(1)文法既不是二义性的，也不是左递归的
什么时候不是LL1文法
预测分析法（器的构成）
LL1自顶向下分析过程
栈放待分解的字符
通过First与follow集合来构造
LR分析法（LR(0)，SLR，LR（1），LALR）
自底向上分析
自底向上语法分析的关键问题-
找句柄
增广文法：E’->E（本来有两个E，让开始符号变成一个），即引入这个新的开始产生式的目的是使得文法开始符号仅出现 在一个产生式的左边，从而使得分析器只有一个接受状态
为啥要有增广文法
让树根只有一个
等价项目集的概念
形如：下一个待移进的符号有产生式可替换
LR0
如果LR(0)分析表中 没有语法分析动作冲突，那么给定的文法 就称为LR(0)文法
不是所有CFG都能用LR(0)方法进行分析，也就是说，CFG不总是LR(0)文法
LR(0)分析过程的冲突：
移进与规约的冲突：
SLR
如果给定文法的SLR分析表中不存在有冲突的动作， 那么该文法称为SLR文法
因为存在移进与规约的问题，所以新增follow集，对左部出现的非终结符操作，当状态遇到follow集合里的终结符时，使用对应的规约即可
LR1的提出
如果LR(1)分析表中没有语法分析动作冲突， 那么给定的文法就称为LR(1)文法
无二义性但可能左递归
展望符：谁的展望符就是谁后面必须紧跟的终结符
但是一个形如[A→α·, a]的项在只有在下一个输入符号等于a时才可 以按照A→α 进行归约
LALR
形式和LR1相同，将相同状态的合并在一起，展望符用或关系
合并同心项集 不会产生移进- 归约冲突，但会有规约规约冲突