文法分析

时间:2024-03-25 14:53:30

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

编译运行:

文法分析