语法分析的任务是根据给定的文法识别输入句子中的各个成分，并构建分析树。如果输入串的各个单词从左自右为分析树的叶子节点，那么这个串就是该语言的一个句子。按照分析树的构造方向，语法分析可以分为两类：自顶向下的语法分析，自底向上的语法分析。

        在语法分析中，使用上下文无关文法(CFG)来描述语言的规则。一个上下文无关文法的定义为:G=(T,N,P,S)

        自顶向下从根节点向底部节点构造分析树，可以看成是从文法开始符号S推导出词串w的过程。

        对于第一个问题，有两种选择方式：最左推导；最右推导。

        对应于推导，语法分析也可以使用规约的方式，因此有相应的最左规约和最右规约。

        在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范归约，而最右推导相应地称为规范推导。

        一个串总是自左向右进行语法分析，因此自顶向下的语法分析采用最左推导的方式。构造语法分析树时，选定最左非终结符的产生式，将串的字符与产生式相匹配。

例：

        自顶向下语法分析是具体通过递归下降分析实现的。递归下降分析中，每个非终结符都有一个过程，从文法开始符号的S对应过程开始，递归调用文法中其它非终结符对应的过程，直到整个输入串都被扫描。

        自顶向下分析的伪代码描述如下：

        在尝试用产生式进行匹配时，不可避免的需要进行回朔，这导致分析效率存在极大的问题。实际情况中，总是需要线性时间的算法，因此有了递归下降分析算法和LL分析算法。

        递归下降分析算法是自顶向下分析算法的一种，通过前看符号避免回朔，基本思想如下：

        示例如下：

        当产生式的多个选择中含有公因子，前看符号就无法指导分支选择了，因此需要提取左公因子，方法如下：

        另一个可能出现的问题是，当产生式为一个递归式时，将无法调用产生式右部非终结符的分析函数，因此需要将左递归消除，方法如下：

        有些情况，使用以上方法并不能消除掉左递归，也就无法通过一个前看符号预测正确的产生式。一个上下文无关文法不一定有对应的无回朔文法，是否存在对应的无回朔文法是不可判定的。

        LL(1)分析算法是另一种自顶向下分析算法。LL(1)表示从左向右分析，使用最左推导，采用一个前看符号。该算法的基本思想是使用分析表来指导产生式规则的选择，因此被称为是一种表驱动的分析算法。

        从每个产生式S开始推导，最终产生的句子可能有多种开头，分析表就是基于这些开头进行前看分析的。这些开头的集合称为FIRST_S(p)集，这个集合也一般被称作SELECT集。而产生式的开头可能是什么非终结符，又是由产生式开头的非终结符N决定的。非终结符N开始推导得出的句子开头的所有可能终结符集合为FIRST(N)集。

        FIRST(N)集的获取，只要对N的产生式的开头的非终结符进行替换，直到替换到终结符就可以了，所有最终替换到的终结符的集合就是FIRST(N)集。但是要考虑到开头的非终结符最终可能为空串，那样的话，整个非终结符N的开头就不是由开头的非终结符产生的了。例如N->XY，而X->ε|a，那FIRST(N)就不仅仅是{a}，还要考虑Y最终可以替换为什么终结符。因此还需要考虑哪些非终结符最终能产生空串，这些非终结符的集合称为NULLABLE集。

        一个非终结符X属于NULLABLE集合由以下两种情况：

        NULLABLE集的产生过程如下：

        考虑了空串的FIRST(N)集算法如下：

        考虑一个产生式的第一个符号，存在这样一种情况，s->N1N2，N1N2可以为空串，这时就没办法知道什么时候使用产生式s了，为了知道什么时候使用产生式s，需要知道非终结符N后面会跟什么符号，N后面会出现的符号集合称为FOLLOW(N)集。

        FOLLOW(N)集的算法如下：

        计算FOLLOW集是一个遍历产生式，对每个非终结符出现的情况，向非终结符的FOLLOW集添加元素的过程。

        有了NULLABLE，FIRST，FOLLOW集，就可以求产生式的FIRST_S集(SELECT集)了。

        需要注意，SELECT集即FIRST_S集中不含有空串。有了FIRST_S集(SELECT集)，分析表的填写就很容易了，例如产生式p1，p2都是N的产生式，就在分析表上N的一行上，哪个终结符在FIRST_S(p1)/SELECT(p1)当中就在哪一列填写产生p1，p2同理。

        自底向上分析是另一种语法分析的方式，与自底向下的推导不同，自底向上是一个规约的过程。自底向上分析中最重要的是LR分析算法，即移进-规约算法。使用这种分析方法，对记号流进行规约时，使用一个 · 将已经读入的和未读入的输入分开。用一个栈表示读入的记号，读入的记号入栈，称为移进，栈顶的一些元素匹配产生式，将这些元素出栈，产生式左部入栈， 称为规约。

        什么时候进行移进，什么时候进行规约，实际上也是通过预先构造的分析表完成的。分析表为以下形式：

        其中的$表示结束，表示可以接收，结束语法分析。通常将需要分析的文法进行拓展，补充一条产生式。例如一个文法由S开始，在这个文法中加入一条产生式S&＃39;->S$，其他产生式不变，然后再进行语法分析。这个新的文法也被称为是原文法的增广文法。分析时使用两个栈，一个状态栈，一个记号栈，根据上面的分析表进行移进和规约。状态栈栈顶根据记号栈栈顶进行状态变化。

        重点就在于构建分析表，考虑不采用前看符号的自顶向下分析，即LR(0)算法中，分析表的构建。

        LR(0)分析算法中分析表的构造分为两个步骤：

        构造的DFA形式如下，每一个产生式被称作一个项目，每一个状态是状态集或者称为项目集。可以看出通过终结符产生的状态是移进的过程，通过非终结符产生的状态是规约。遇到了非终结符，就将遇到的非终结符的产生式加入到状态中。这一步也被称为求项集的闭包。

        根据DFA构造分析表的过程比较简单，注意移进，规约，转移这三个动作就可以了。在分析表中，用sn表示移进，rn表示规约，gn表示转移。

        LR(0)分析算法有两个缺点。第一个缺点是延迟了错误发现的时机，当已经读入的记号可以规约时，就进行规约，哪怕后续的记号是错误的，也先把读入的全部规约后才发现后续的错误；另一个缺点是可能存在冲突，例如有产生式S->T和S->T+，既可以移进也可以规约，无法一步作出正确的选择。为了解决LR(0)分析算法的问题，在LR(0)的基础上，修改规约表项的生成，就是SLR分析算法。

        SLR分析算法相比于LR(0)的修改之处为：生成分析表时，若某状态包含A->α·，只对FOLLOW(A)中的输入记号添加对产生式A->α的规约操作。因此对于上面在LR(0)中已经见到过的分析表，使用SLR分析算法构建的表如下：

        如果最终产生的分析表没有冲突项，那么就说这个文法是SLR文法。可能的冲突有两种：移进-规约冲突；规约-规约冲突。在分析表中，体现为一个状态在接收到一个符号后，既可以移进又可以规约，或有两个不同的规约方法。

        在SLR分析算法中，最终得到的分析表仍然可能存在冲突，因为进行规约时，对于非终结符A，只要后面出现了FOLLOW(A)的元素就进行规约。分析表的作用就是为了选择正确的产生式，但是FOLLOW(A)对于确认在哪个产生式中发生了规约是不够精确的。因此考虑采用前看符号，确认产生式的选择，即采用LR(1)分析算法。

        LR(1)中定义项目为[X ➝α•β, a]，其含义是：

        LR(1)分析算法其他和LR(0)相同，仅状态集的产生和归约表项的产生不同。

        下面是一个LR(1)中产生项集闭包的例子，可以看到第一条产生式中遇到非终结符S，而第一条产生式S后面只有$，因此下面添加S的产生式到项集时，前看符号是FIRST_S($)={$}；第二条产生式遇到了L，L后面是=，该条产生式的前看符号是$，因此下面添加L的产生式到项集时，前看符号是FIRST_S(=$)={=}。

        最后总结一下自底向上分析的步骤：