1、递归下降语法分析（RDP）
我们知道，对于一个CFG而言，不管规则多么复杂，规则集中总是会有非终结符到终结符的简单推导，就像递归中的出口一样。例如：
这样的特点是递归下降法能够顺利执行递归的基本条件。
RDP做的事情就是把每个非终结符看作是函数，从这个非终结符推导出的规则是函数体。例如：
可以看到，函数体内部的书写范式是：
case 终结符{eat(终结符);处理下一个;}
RDP是一种预测分析，预测的意思是：接下来要做什么可以通过case后面那个终结符知道。如果一条规则中，->后面的非终结符是不明确的，RDP就失效了，例如：
A->A+B
A->A-B
A->a
B->b
函数A应写作：
void A(void){
switch(tok){
case ?:A();eat(+);B();
case ?:A();eat(-);B();
case a:eat(a)
}
}
2、Nullable、FIRST和FOLLOW
为方便后面的讨论（例如，将递归下降法表示成一张表），引入三个定义：
（1）Nullable的定义：
若非终结符A可以推导出空串，则Nullable(A)为真，表示A是"可空的"。
（2）FIRST的定义：
FIRST(A)表示非终结符A推导的规则中，->后面的第一个终结符；
FIRST(ABC...)=FIRST(A)∪FIRST(B)∪FIRST(C)∪...，如果ABC是可空的。
（3）FOLLOW的定义:
对于非终结符A，如果在任意推导中出现At，其中t是终结符，那么t∈FOLLOW(A)，如果是ABCt这种情况，但BC是可空的，那么也有t∈FOLLOW(A)
例如：
Nullable |
FIRST |
FOLLOW |
|
X |
yes |
a c |
a c d |
Y |
yes |
c |
a c d |
Z |
no |
a c d |
虽然可以通过观察法找到答案但是形式化的计算更不容易出错，在知道了
Nullable以后，我们完全可以从定义出发，列式计算，例如：因为X，Y都是可空的，则FIRST(Z)={d}∪FIRST(X)∪FIRST(Y)。
计算FOLLOW同样有一些捷径，例如X的FOLLOW，因为观察到规则集中有XYZ，那么Y的FIRST一定是X的FOLLOW的子集，又因为Y是可空的，所以Z的FIRST也一定是X的FOLLOW的子集，于是可毫不费力地写出{a c d}
3、构造分析预测表
由此可以得到2中文法对应的表：
A |
c |
d |
|
X |
X->a X->Y |
X->Y |
X->Y |
Y |
Y-> |
Y-> Y->c |
Y-> |
Z |
Z->XYZ |
Z->XYZ |
Z->d Z->XYZ |
初看这个规则可能会觉得变扭，下面给出具体计算步骤：
①在X行，找到由X推导的规则：
X->Y
X->a
计算FOLLOW(x)、FIRST(Y)和FIRST(a)，FOLLOW(x)={a c d}，FIRST(Y)={c}，FIRST(a)={a}，请注意：终结符的FIRST就是它本身。于是可将X->a写到(X, a)处，由于Y是可空的，所以，对于每个FOLLOW(x)都要写上X->Y
②在Y行，找到由Y推导的规则：
Y->
Y->c
计算FOLLOW(Y)、FIRST( )、FIRST(c)，它们分别是{a c d}、{ }、{c}。于是可将Y->c写到(Y, c)处，由于Y-> 中的终结符为空，所以这条规则要写到任何一个Y行、FOLLOW(Y)列处。
③仿上，相信你懂了。
另外，寻找FOLLOW的时候，有几种情况要注意：
①产生式中没有显然的FOLLOW但是可以通过其他产生式导出，例如：
其中的E'没有明显的FOLLOW，但是可以通过规则替换找到。结果如下：
②对于AB来说，如果已经知道了B的FOLLOW，又知道B可以为空，那么A的FOLLOW一定包含B的FOLLOW。
这是显然的，熟练运用可以提高寻找效率。
4、LL(1)文法
3中的表存在歧义，即推导规则不唯一，例如X行a列就有两个规则。
如果每个表项只有一个规则，则与这个表对应的文法叫LL(1)文法（第一个L表示"从左到右分析"，即left-to-right parsing；第二个L表示"最左推导"，即left-most derivation；1表示超前查看一个字符）。
歧义产生的根源在于存在左递归，可以通过改写文法规则消除左递归，同时不影响原意，例如把：
改成：
有公共左因子的时候，递归下降分析也会出问题，可以通过提取公共左因子来解决：
这样处理以后得到的表是无歧义的，得到表的步骤和前文一样，略。
5、LR分析
LL(k)文法的弱点在于在看到k个右边的符号后就必须做出预测。
下面要介绍的LR分析可以延缓这种预测。
（1）LR(0)
表示left-to-right parsing，right-most derivation，0 word look-ahead。
①理解使用的符号
s表示shift，后面的数字是状态号
r表示reduce，后面的数字是产生式编号
g表示go-to，后面的数字是状态号
a表示accept
空格表示潜在的错误状态
那么shift和go-to有什么区别？区别是：shift用在终结符的转移，go-to用在非终结符的转移。
②如何通过文法构造DFA？
引入符号.做闭包运算。
来看一个LR(0)的例子：
从这个图可以得到如下的DFA：
然后得到下表：
( |
) |
x |
, |
$ |
S |
L |
|
1 |
s3 |
s2 |
g4 |
||||
2 |
r2 |
r2 |
r2 |
r2 |
r2 |
||
3 |
s3 |
s2 |
g7 |
g5 |
|||
4 |
a |
||||||
5 |
s6 |
s8 |
|||||
6 |
r1 |
r1 |
r1 |
r1 |
r1 |
||
7 |
r3 |
r3 |
r3 |
r3 |
r3 |
||
8 |
s3 |
s2 |
g9 |
||||
9 |
r4 |
r4 |
r4 |
r4 |
r4 |
LR(0)的缺点是可能出现reduce-reduce冲突或者shift-reduce冲突，发生这样的情况是因为：在当前状态下有多个可用的reduce规则；或者既可以reduce，又可以通过吃掉下一个字符发生转移，例如：
这是某个LR(0)文法对应的DFA的一部分，当下一个符号是+时，究竟是用E->T.来规约，还是按E->T.+E来发生转移？这就是shift-reduce冲突。
（2）SLR
SLR表示Simple LR，它赋予了LR向前看一个符号的能力，可以一定程度上解决上述的冲突。但是注意，SLR仍然是可能存在冲突的（具体可以参见虎书的课后习题）。
SLR的特别之处在于利用了FOLLOW集合，它规定：
对于一个状态中的每条规约规则A->a.
只有当遇到FOLLOW(A)的时候才执行规约，否则不执行。
可以看一个例子：
这个文法对应的DFA如下：
按照SLR的规则，得到如下的表：
x |
+ |
$ |
E |
T |
|
1 |
s5 |
g2 |
g3 |
||
2 |
a |
||||
3 |
s4 |
r2 |
|||
4 |
s5 |
g6 |
g3 |
||
5 |
r3 |
r3 |
|||
6 |
r1 |
也就是说，例如对状态3，FOLLOW(E)={$}，那么就只有当遇$时才规约，又例如对状态6，也一样。对状态5，FOLLOW(T)={+,$}，那么只在这两处规约即可。
对比一下，如果不按SLR而是LR(0)，那么表就有歧义了：
由此可见SLR确实消去了歧义。
（3）LR(1)
一种比SLR更强大的文法是LR(1)。它的每一项由(A->a.b，x)组成，x叫做超前查看符号。
在计算闭包的过程中，每一项的超前超前查看符通过如下算法计算：
开始项的超前查看符总是?，表示无关紧要。
不妨通过一个例子来理解：
计算过程：
于是得到：
类似地可以构造DFA：
（4）LALR(1)
叫做Look-Ahead LR(1)，它的分析范围比LR(1)小，但是表达起来更方便。方便在哪里？
LALR(1)将LR(1)中除lookahead以外，其它地方完全相同的item给合并掉。比如下图中：
不同颜色圈起来的四对状态是可以合并的。这样，在转换成表格的时候就简化了许多。
6、使用Bison
（1）基本格式
FIRST PART
%%
SECOND PART
%%
THIRD PART
第一部分写定义
第二部分和CFG对应，写要执行的C语句
第三部分写其他C语句，例如main。
（2）一个例子
①calc.y
%{
void yyerror(char *s);
#include<stdio.h>
#include<stdlib.h>
int symbols[52];
int symbolVal(char symbol);
void updateSymbolVal(char symbol,int val);
%}
%union {int num; char id;}
%start line
%token print
%token exit_command
%token <num> number
%token <id> identifier
%type <num> line exp term
%type <id> assignment
%%
line: assignment ';' {;}
| exit_command ';' {exit(EXIT_SUCCESS);}
| print exp ';' {printf("Printing %d\n",$2);}
| line assignment ';' {;}
| line print exp ';' {printf("Printing %d\n",$3);}
| line exit_command ';' {exit(EXIT_SUCCESS);}
;
assignment: identifier '=' exp {updateSymbolVal($1,$3);}
;
exp: term {$$=$1;}
| exp '+' term {$$=$1+$3;}
| exp '-' term {$$=$1-$3;}
;
term: number {$$=$1;}
| identifier {$$=symbolVal($1);}
;
%%
int computeSymbolIndex(char token){
int idx=-1;
if(islower(token)){
idx=token-'a'+26;
}else if(isupper(token)){
idx=token-'A';
}
return idx;
}
int symbolVal(char symbol){
int bucket=computeSymbolIndex(symbol);
return symbols[bucket];
}
void updateSymbolVal(char symbol,int val){
int bucket=computeSymbolIndex(symbol);
symbols[bucket]=val;
}
int main(void){
int i;
for(i=0;i<52;i++){
symbols[i]=0;
}
return yyparse();
}
void yyerror(char* s){fprintf(stderr,"%s\n",s);}
②calc.l
%{
#include"y.tab.h"
%}
%%
"print" {return print;}
"exit" {return exit_command;}
[a-zA-Z] {yylval.id=yytext[0];return identifier;}
[0-9]+ {yylval.num=atoi(yytext);return number;}
[ \t\n] ;
[-+=;] {return yytext[0];}
. {ECHO;yyerror("unexpected character");}
%%
int yywrap(void){return 1;}
编译运行：
