编译原理语法分析-自上而下分析
语法分析的过程包括自上而下的推导和自下而上的规约。
递归下降分析器的设计（LL分析，自上而下的推导）
语法分析器的自动生成（LR分析，自下而上的规约）
自上而下面临的问题：
文法的左递归问题
回溯的不确定性，要求我们将已经完成工作推倒从来，
虚假匹配的问题
不能准确地确定输入串中出错的位置
效率低
LL(1)分析法：
******消除直接左递归******
产生式
P→Pα|β (1)
其中β不以P开头，α不为ε。那么，我们可以把P的规则改为如下的非直接左递归形式：
P →βP’
P’→αP’|ε (2)
产生式
P→Pα1|Pα2|…|Pαm|β1|β2|…|βn
其中每个βi不以P开头，每个αi不为ε
消除P的直接左递归性就是把这些规则改写成：
P→β1P’|β2P’|…|βnP’
P’→α1P’| α2P’|…|αmP’| ε
间接左递归
例题如下：
消除回溯：
FIRST集
令文法G是不含左递归的文法，对G的非终结符的候选α，定义它的开始符号（终结首符）集合：
特别地，如果α ε，则ε∈FIRST(α)
如果非终结符A的任意两个候选式αi和αj的开始符号集满足FIRST(αi)∩FIRST(αj)=Φ，则A可以根据所面临的第一个输入符号，准确地指派一个候选式α去执行任务，α是那个FIRST集含a的候选式，即 a ∈FIRST(α)
改造文法： 消除公共左因子
FOLLOW集
对文法G的任何非终结符A，定义它的后继符号集合：
特别地，如果S …A，则#∈FOLLOW(A)
FOLLOW(A)集合是所有句型中出现在紧接A之后的终结符号或#所组成的集合
当非终结符A面临输入符号a，且a不属于A的任意候选式的FIRST集但A的某个候选式的FIRST集包含ε时，只有当a ∈FOLLOW(A)，才可能允许A自动匹配
******不带回溯的自上而下分析的文法条件（LL(1)文法）
(1)文法不含左递归
(2)对于文法中每一个非终结符A的各个产生式的候选式的FIRST集两两不相交。即，若
A→α1|α2|…|αn
则 FIRST(αi)∩FIRST(αj)=Φ (i≠j)
(3)对于文法中的每个非终结符A，若它的某个候选首符集包含ε,则
FIRST(A)∩FOLLOW(A)=Φ
如果一个文法G满足以上条件，则称该文法G为LL(1)文法(第1个L代表从左到右扫描输入串，第2个L代表最左推导，1表示分析时每一步只看1个符号)
******预测分析程序
执行程序
1.把#和文法起始符号E推进栈,并读入输入串的第一 个符a,重复下述过程直到正常结束或出错.
2.测定栈顶符号X和当前输入符号a,执行如下操作:
(1)若X=a=#，分析成功，停止。E匹配输入串成功.
(2)若X=a≠#，把X推出栈，再读入下一个符号。
(3)若X∈Vn，查分析表M。
a) M[X,a]= X→UVW
则将X弹出栈，将UVW压入
注：U在栈顶 （最左推导）
b) M[X, a] = error 转出错处理
c) M[X, a] = X-〉ε ---a为X的后继符号则将X弹出栈 （不读下一符号）
继续分析。
预测分析表的构造：FIRST（X)
若X终结符，则FIRST(X)={X}
若X为非终结符，且有X->a …的产生式，则把a加入到FIRST(X)中；
若X->Y…是一个产生式，且Y为非终结符，则把FIRST (Y)-ε加入到FIRST(X)中；
若X->Y1Y2Y3….YK,是产生式， Y1Y2Y3….Yi-1是非终结符，而且ε属于 FIRST (Yj)(1<=j<=i-1),则把FIRST (Yj)-ε加入到FIRST(X)中；
如果ε属于所有的FIRST (Yj)，则ε加入到FIRST(X)中
预测分析表的构造：FOLLOW（S)
对于文法的开始符，置#于FOLLOW(S)中
若A->αBβ, 则把FIRST (β)-ε加入到FOLLOW(B)中，
若A->αB 是一个产生式，或 A->αBβ是一个产生式，而β-> ε,则把FOLLOW(A)加入到FOLLOW(B)中
预测分析表的构造：
对文法G的每个产生式， A->α，进行下面的处理
对每个终结符a,如果a属于FIRST(α),则把该产生式写入到M[A,a]
若ε属于FIRST(α)，则对任何b属于FOLLOW(A), 把该产生式加入到M[A,b]
所有无定义的M[A,a]标上出错标志
*********************************************课 后 题*********************************************************
感想：
定义类的东西结合实例才能够充分更好的理解，同时用自己通俗理解的方式诠释定义在正确的条件下更容易理解记忆