语法分析的作用：识别单词符号序列是否是给定文法的正确程序。分为自顶向下分析(确定和不确定)，自底向上分析(算符优先和LR分析)。
自顶向下分析法又称面向目标的分析方法，从开始符号出发，企图推导出与输入的单词串完全匹配的句子。确定的方法需要对文法有一定的限制，简单直观；不确定的方法如带回溯的分析方法——穷举的试探法，缺点是效率低、代价高。
4.1 确定的自顶向下分析思想
主要思想：从文法的开始符号出发，如何根据当前的单词符号，唯一地确定选用哪个产生式来替换相应的VN向下推导。
为得到唯一的推导过程，条件为：左部相同的产生式，其右部的首符号集合不相交。
定义：设$G=(V_T,V_N,S,P)$是上下文无关文法，$FIRST(\alpha)={a|\alpha\Rightarrow^a\beta,a\in V_T,\alpha,\beta\in V^}$若$\alpha\Rightarrow^*\epsilon$，则规定$\epsilon\in FIRST(\alpha)$。
为得到唯一的推导过程，条件为：当某一$V_N$的产生式含空产生式，则它的非空产生式的$First$集两两互不相交，且与推导过程中紧跟该$V_N$可能出现的$V_T$集合也不相交。
定义：设$G=(V_T,V_N,S,P)$是上下文无关文法，$A\in V_N$，$S$是开始符号。$FOLLOW(A)={a|S\Rightarrow^\mu A\beta且a\in FIRST(\beta),\mu\in V_T^,\beta\in V^+}$。若$S\Rightarrow^\mu A\beta$，且$\beta\Rightarrow^\epsilon$，则规定$#\in FOLLOW(A)$，$#$作为输入串的结束符，或称为句子括号。
通俗地讲，$FOLLOW(A)={a|S\Rightarrow^\dots Aa\dots,a\in V_T}$，若$S\Rightarrow^\dots A$，则规定$#\in FOLLOW(A)$。
若$A\rightarrow\alpha,A\rightarrow\beta$，其中$A\in V_N,\alpha,\beta\in V_N^*,\alpha$不推导出空，$\beta$能推导出空，则$FIRST(\alpha)\cap((FIRST(\beta)-{\epsilon})\cup FOLLOW(A))=\empty$。
定义：给定上下文无关文法的产生式$A\rightarrow\alpha,A\in V_N,\alpha\in V^*$
若$\alpha\nRightarrow^*\epsilon$，则$SELECT(A\rightarrow\alpha)=FIRST(\alpha)$
若$\alpha\Rightarrow^*\epsilon$，则$SELECT(A\rightarrow\alpha)=(FIRST(\alpha)-{\epsilon})\cup FOLLOW(A)$
可使用自顶向下分析的文法称为$LL(1)$文法。
定义：一个上下文无关文法是$LL(1)$文法的充要条件：对每个$V_N,A$的两个不同产生式$A\rightarrow\alpha,A\rightarrow\beta$，满足$SELECT(A\rightarrow\alpha)\cap SELECT(A\rightarrow\beta)=\empty$，其中，$\alpha、\beta$不能同时推导出$\epsilon$。
4.2 LL(1)文法的判别
判别步骤：求出能推出$\epsilon$的非终结符；计算$FIRST$集；计算$FOLLOW$集；计算$SELECT$集；判别是否是$LL(1)$文法。
1.求出能推出$\epsilon$的非终结符
2.计算$FIRST$集
3.计算$FOLLOW$集
4.计算$SELECT$集
5.判别
$LL(1)$文法：左部相同的产生式的$SELECT$集的交集均为空。
4.3 某些非LL(1)文法到LL(1)文法的等价变换
若文法含有直接或间接左递归，或含有左公共因子，则一定不是LL(1)文法，非LL(1)文法到LL(1)文法等价变换的方式是提取左公共因子，消除左递归。
4.3.1 提取左公共因子
对形如$A\rightarrow\alpha\beta_1|\alpha\beta_2|\dots|\alpha\beta_n$进行等价变换为$A\rightarrow(\beta_1|\beta_2|\dots|\beta_n)$，进一步变换(引入新非终结符$A’$)：$A\rightarrow\alpha A’,A’\rightarrow\beta_1|\beta_2|\dots|\beta_n$。若后者中仍含左公共因子，再次提取，直到所有的产生式不再有左公共因子。
文法中不含左公共因子只是LL(1)文法的必要条件。
右部以$V_N$开始的产生式，用该$V_N$对应的产生式进行相应替换，再用一般式进行提取。(可能导致出现多余产生式)
不是所有文法，都能在有限的步骤内提取完左公共因子。
4.3.2 消除左递归
文法提取左公共因子后，并不一定是LL(1)文法。只有不含空产生式，且无左公共因子，且无左递归时，文法才是LL(1)文法，否则需要进行判别。
左递归的形式有直接左递归$A\rightarrow A\beta;A\in V_N,\beta\in V^$和间接左递归$A\rightarrow B\beta,B\rightarrow;A\alpha;A,B\in V_N,\alpha,\beta\in V^$。
消除直接左递归的方式是把直接左递归改为右递归：
$A\rightarrow A\alpha_1|A\alpha_2|\dots|A\alpha_m$
$A\rightarrow\beta_1|\beta_2|\dots|\beta_n$
改写为：
$A\rightarrow\beta_1A’|\beta_2A’|\dots|\beta_nA’$
$A’\rightarrow\alpha_1A’|\alpha_2A’|\dots|\alpha_mA’$
$A’\rightarrow\epsilon$
消除间接左递归的方式是先把间接左递归变为直接左递归，再化为右递归。
消除文法中一切左递归：
以某种顺序将$V_N$的排序为：$A_1,A_2,\dots,A_n$
for(i=1;i<=n;i++)
{ for(j=1;j<=i-1;j++) //以$A1,\dots,A{i-1}$的产生式代入$A_i$产生式
{ 若$A_j$的产生式为：$A_j\rightarrow\delta_1|\delta_2|\dots|\delta_k$
则形如$A_i\rightarrow A_j\gamma$的产生式变为：$A_i\rightarrow\delta_1\gamma|\delta_2\gamma|\dots|\delta_k\gamma$
}
消除$A_i$中的一切直接左递归
}
删除多余产生式
4.4 不确定的自顶向下分析思想
非LL(1)文法不能用“确定的”自顶向下分析，但可以使用“不确定的”自顶向下分析(“带回溯的”自顶向下分析)。
引起回溯的原因有：(1)由于左部相同的产生式的右部$First$集交集不为空。(2)由于左部相同的$V_N$的右部能推导出$\epsilon$，且该$V_N$的$Follow$集中含有其右部$First$集的元素。(3)由于文法中含有左递归。
4.5 确定的自顶向下分析方法
4.5.1 递归子程序法
主要思想：对文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选时能够按LL(1)形式可唯一地确定选择某个候选进行推导。
优点：简单、直观、易于构造。
缺点：对文法要求高，必须满足LL(1)文法；由于递归调用多，速度慢，占用空间多。
4.5.2 预测分析法
预测分析器的组成：预测分析程序、先进后出栈、预测分析表。
预测分析法的步骤：(1)提取左公共因子，消除左递归。(2)判断文法是否为LL(1)文法。(3)若是，构造预测分析表；否则，不能进行“确定的自顶向下”分析。(4)预测分析程序根据“预测分析表”并利用“分析栈”，对输入串进行分析。
构造预测分析表的方法：对每个$V_T$或”#”用符号$a$表示，若$a\in SELECT(A\rightarrow\alpha)$，则把$A\rightarrow\alpha$放入$M[A,a]$中，所有空白的$M[A,a]$表示出错。