语法分析的目的

    词法分析与语法分析处于编译器的前端，对输入的源程序进行分析。词法分析，类似于将语句切分为关键字、记号、操作符等助于语法分析识别的记号流；而语法分析，是将记号流生成抽象语法树，便于后面语义分析。

语法分析的工具

    数学理论

        上下文无关文法（CFG）

    自顶向下分析

        递归下降分析法

        LL分析算法

    自底向上分析法

        LR分析算法

上下文无关文法

    上下文无关文法G={T,N,P,S},T表示终结符集合，N表示非终结符集合，P表示一组运算规则，S为唯一开始符号。

    对于一个句子，它首先由开始符号S为开端，并不断地转化为非终结符，最终转为终结符。而它们的转化，并填充产生式规则集合。

    非终结符只有E，而E可以推出：E->num,E->id,E->E+E,E->E*E；最后推出上图左边的式子。一个具体的例子，就是3+4*5这个例子。

    对于上述文法，使用最左推导：

            E->E+E,

            E->3+E,

            E->3+E*E,

            E->3+4*E,

            E->3+4*5.

    对于语法分析程序，回复YES。

    而另一种推导：

            E->E*E,

            E->E+E*E,

            E->3+4*5.

    这两种推导的结果是一样的，但是表达式的运算取决于语法分析树的后序遍历。

    对于存在二义性的文法，编译器是不可接受的，只能重写文法。

文法重写

    我们将上述文法重写为左递归文法

    E-> E+T | T,

    T-> T*F | F,

    F-> id | num

    根据上述文法，我们的表达式可以递归扩展，比如E->E+T，右边的E又可以替换为E+T，所以我们得到E->E+E+T，累加符号就解决了。同理，T=T*...F，连乘符号解决了。

    对于上述3+4*5的文法推导，为E->E+T->T+T->T+T*F->T+F*F->F+F*F，而F为数字或者id，从而得到分析树。

自顶向下分析法

    通过对文法的不断推导，来匹配输入的这个字符串是否为可匹配的文法。譬如文法G，和输入s，通过G的不断尝试回溯生成t，以匹配文法s。

    例子：G -> N V N ,N -> a | b | c,V -> e | f。

    输入cfc，首先通过栈存储开始符号G，并通过循环转化为下一个推导，N V N，注意这里是从右往左入栈；随后，对每一个栈顶的非终结符进行尝试，找到终结符匹配。比如转化为a V N，与输入第一位c匹配不上，触发回溯尝试下一个句子翻译 b V N，不断往复直到匹配出cfc为止。

    因为编译器需要处理大量的程序，回溯是一个比较昂贵的过程，避免回溯，就是在替换终结符的时候直接拿到对应的终结符号，按照写代码的理解，就是对符号集合存储使用的是HashMap而不是Array。

递归下降分析算法

对每一个token，对应的是一个分析函数，而文法的未终结符之间都是分析函数的关联。    

LL(1)分析算法

L采用左递归，以及从左读入一个前看符号的分析算法。

每次分析token输入符号的时候，回溯将会造成大量的资源损耗，此算法提出是基于表驱动的解决方案，也就是通过当前符号与输入符号的映射来确定解析路径。不需要使用next一个前看符号，而是使用correct一个前看符号。

使用一个非终结符左看第一个符号生成FIRST集合，进而生成LL(1)表。LL(1)表中表示的是第几条产生式规则。