编译原理（四）--语法分析
主要内容：
本章将重点介绍典型的语法分析方法及相关的概念和实现技术
语法分析分为：
自上而下：递归下降分析法（LL预测分析法—>推导
自下而上：算符优先分析法（LR分析法—>归约
4.1 语法分析器的功能 4.1.1 语法分析器任务完成的任务：
① 对词法分析器产生的单词符号进行处理，输出分析树
②与单词相关的信息记录到符号表中
③类型检查
④错误处理
4.1.2 相关约定符号的使用约定
终结符
①.字母表中比较靠前的小写字,如a,b,c
②. 操作符，如+、-等
③. 标点符号，如括号、逗号等
④. 数字0、1、。。。9
⑤. 黑体串，如if 、id等
非终结符
①.字母表中比较靠前的大写字,如A、B、C
②.字母S，常用来表示开始符号
③. 小写斜体名字，如expr、stmt
字母表中比较靠后的大写字母，如X、Y、Z等，用来表示文法符号，也就是说，可以是终结符，也可以是非终结符
字母表中比较靠后的小写字母，如u、v…z等，表示终结符的串联
5.小写希腊字母α、β、γ等表示 文法符号的串，所以一个产生式可写作：A⟶\longrightarrow⟶α
4.2 自顶向下分析法 4.2.1 使用的技术、存在的问题及解决方法 推导就是用产生式的右部的串来代替左部的非终结符
事实上，推导给出了自顶向下构成树的精确描述
例：
有描述算数表达式的文法G
E⟶\longrightarrow⟶E+E|E*E|(E)|-E|id
字符串id+id*id是该文法的推导过程：
E=>E+T=>E+T*F=>E+T*id=>E+F*id=E+id*id=> T+id*id=>F+id*id=>id+id*id
几个约定：
E=>-E:E推导出了-E
=(*)>零步或多步推导
=(+)>一步或多步推导
**最左推导：**每一步都坚持替换当前句型中最左非终结符的推导
**最右推导：**每一步都坚持替换当前句型中最右非终结符的推导，也称为规范推导
句子：S=(+)>W 称为终结符串w是文法G的句子
句型：S=(+)>α 称α是文法G的句型
语言：L(G)={w/s=>w}
语法树语法描绘了如何从文法的开始符号推导出一个句子的过程
语法树可以看成是推导的图形表示，但它不能显示出替代的顺序
语法具有如下特性的树：
1.树根标记为开始符号
2.每个叶结点由终结符或者ε标记
3.每个内结点由一个非终结符标记
4.如果A是某个内结点的非终结符标记，A1， A2，…… An是该结点从左到右排列的所有子结点的标记，则A→ A1 A2…… An是一个产生式
语法树的叶结点从左到右的排列，刚好是这个文法所产生的语言的一个句子
一个文法生成的语言就是它的某个分析树所生成的句子的集合
为给定的终结符串（句子）构造一棵分析树的过程称为这个串（句子）的语法分析（parsing)
二义性给定一个文法G，如果L（G）中存在一个具有两棵或两棵以上分析树的句子，我们就称该文法为二义性的，G也叫二义性文法。
造成二义性的原因：
文法中没有体现出结合率和优先级
消除二义性：
我们通常采用”最近匹配“原则来解决这种二义性
左递归如果文法G具有一个非终结符A使得对某个字符串α存在推导A=>A α,则称文法G是左递归的；如果A→A α，则称文法G是直接左递归的
左递归会使分析进入到无限循环之中
消除简单左递归的方法：
对于含有左递归的产生式 A→A α| β
可用下面的非左递归的产生式 代替：
A→ β A’
A’ → αA’| ε
对于一般情况而言，若某一文法G的产生式具有如下形式：
A→A α1| A α2 |…| A αm| β1| β2|…| βn
则可用如下方法消除左递归:
A→β1A’| β2A’ |…| βn A’
A’ → α1A’| α2A’|… | αmA’ | ε
消除左递归的一般算法：
输入：无限循环推导和ε产生式的方法G
输出：与G等价的无左递归文法
提取左因子输入：文法G
输出：一个等价的提取了左因子的文法
方法：对于A→ αβ1| α β2 |…| α βn| γ
可改写为： A→ αA’| γ；A’→ β1| β2 |…| βn
FIRST与FOLLOW集 first定义：FIRST（ α）是由α推导出的所有的第一个终结符号组成的集合，即：
FIRST（ α ）={a| α =>a… ,a∈VT}，如果α => ε 则 ε ∈ FIRST（ α ）。
算法：
①如果X是终结符，则FIRST（X）是{X}
②如果X →ε是一个产生式，则ε∈ FIRST（X）
⑶如果X是非终结符，且X →Y1 Y2…… Yk,则
Y1 => ε FIRST(Y1 )中的所有符号都在FIRST（X）中 Y1 Y2…… Yi-1=> ε, FIRST（ Yi ）,中的所有符号都在FIRST（X）中 Y1 Y2…… Yk=> ε,则ε ∈ FIRST（X） follow定义：FOLLOW（A）是由所有句型中紧跟在A后面的终结符a组成的集合，FOLLOW（A）={a|S=> αAa β,a ∈Vt
算法
①＄ ∈FOLLOW（S）
②对于A→ αBβ的产生式，则FIRST（ β）- ε放入FOLLOW（B）
③对于A→ αB或A→ αBβ，其中β=> ε，则将FOLLOW（A）放入FOLLOW（B）中
LL（1）文法一个上下文无关文法若满足下列条件，我们就称它为LL（1）文法
⑴文法不含左递归
⑵文法中每个非终结符A的各个产生式的首终结符集两两不相交，即，若
A→ α1| α 2 |…| α n，则 FIRST（ αi ）∩FIRST（ αj ）=φ
⑶文法中每个非终结符A若其首字符集中含有ε，则FIRST（ αi ）∩FOLLOW（A）= φ
LL(1)文法的说明：
这里LL（1）中的第一个L表示从左到右扫描输入串，第二个L表示最左推导，1表示分析时每步
只需向前查看一个符号
作者：nishizzma
