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：

然后得到下表：

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;}

编译运行：