从顶向下、最左推导的语法分析
文法：已知语言的文法，给定一个词素串，判定它是否符合文法，符合的话，得出语法分析树
基于自顶向下和最左推导的语法分析存在三个问题：
左递归
左公因子
选择哪个产生式进行推导
左递归
何为左递归问题？当我们对id1+id2+id3+id4进行推导，发现推导是从输入串的最右端开始逆向逐一来匹配：不切合实际
针对左递归，我们要采用新的文法来消除它，如下
因此id1+id2+id3+id4变成了
消除了左递归存在好处和坏处
好处：实现了对输入串从左至右逐一匹配
代价：多引入了一个非终结符，语法树变得复杂，效率低
下面是通用处理文法表达，这样就消除了左递归
但是如果存在间接的左递归，则需要消除一个变量，如下
左公因子
左公因子问题是指某个非终结符，它有多个产生式，其产生式体的左端有公因子；导致在推导时，有多个产生式匹配，不知道选哪个才对
解决办法：把非公因式部分单独拿出来，新引入一个非终结符，来表达它
A→α β1 ｜α β2 ｜α β3| γ
转为
A→α A’ | γ
A’→β1 ｜ β2 ｜ β3
举例：
选择哪个产生式进行推导
前两步只是进行预处理，选择哪个产生式进行推导才是关键，一个产生式子，可能由多个分号相隔，不清楚推导的时候选哪个
对于非终结符A，它仅有两个产生式：A→α和A→β；选择其中的哪一个产生式进行推导？是问题的关键
FIRST(α)的含义是从α推导得到的串的第一个终结符的集合
FIRST(β)的含义是从α推导得到的串的第一个终结符的集合
如何FIRST(α)和FIRST(β)不相交（肯定不会相交，因为左公因子已经除掉了），则对当前输入符a
a∈FIRST(α) ，选A→α
a∈FIRST(β) ， 选A→β
对于非终结符A，它仅有两个产生式：A→α和A→θ；选择其中的哪一个产生式进行推导？
FIRST(α)的含义是从α推导得到的串的第一个终结符的集合
FOLLOW(A)的含义跟在A之后的终结符的集合
如何FIRST(α)和FOLLOW(A)不相交（肯定不会相交，因为左公因子已经除掉了），则对当前输入符a
a∈FIRST(α) ，选A→α
a∈FOLLOW(A) ， 选A→θ
FIRST()的求法
对非终结符号，由低到高排序，逐一扫描其产生式, 计算每一产生式的FIRST()
FOLLOW()求法
对非终结符，从起始非终结符S开始，由高到低依次排序
天然的已知：FOLLOW(S) 包含$ 这个终结符
规则：
举例：
因此综上，FIRST()存在的意义是选择哪一个产生式子（不含ε），FOLLOW()存在的意义存在ε的产生式，是非要选择它：
自顶向下的语法分析中，设当前输，入符为a，要推导的非终结符A：产生式A→α能被选用的条件为
a∈FIRST(α) OR (ε∈FIRST(α) ANDa∈FOLLOW(A))
如果FOLLOW()循环依赖，则另相互依赖的非终结符的FOLLOW()相等，并取它们的并集
我们计算FIRST()和FOLLOW()就是为了得到预测分析表，
预测分析表是从文法得出的，是元信息
表中的某个格子中，如果有不止一个产生式，那么该文法就不是LL(1)文法
预测表解决了产生式的选择问题
文法分析树的推导过程是一个压栈，弹栈的过程
最后：自顶向下、最左推导的语法分析LL(1)的流程？
- 1.对文法作消除左递归，提取左公因子处理
- 2.对每个产生式，计算FIRST（）
- 3.对每个非终结符号，计算FOLLOW（）
- 4.填写预测分析表
- 5.判断其是否是LL(1)文法
- 6.对输入串推导出语法分析树
