LL(1)无回溯的递归下降语法分析器

发表于 2021-04-11 分类于 CS ， Compiler Waline：

本文字数： 15k 阅读时长 ≈ 14 分钟

使用递归下降法实现语法分析器，同时使用预测分析法实现非回溯。结合词法分析器对输入进行分析，输出其最左推导。

实现目标

使用递归下降法实现LL(1)文法的语法分析器，为了实现不回溯，需要使用预测分析表。结合词法分析器对输入进行分析，输出最左推导。

原文法

改写文法

提取左公因子

\[A\rightarrow\alpha\beta_1\ |\ \alpha\beta_2\ |\ ...\ |\ \alpha\beta_n\ |\ \gamma\]

改写成 \[ A\rightarrow{\alpha}A^{'}\ |\ \gamma \\ A^{'}\rightarrow\beta_1\ |\ \beta_2\ |\ ...\ |\ \beta_n \]

消除左递归

\[ A{\rightarrow}A\alpha_1\ |\ A\alpha_2\ |\ ...\ |\ A\alpha_n\ |\ \beta_1\ |\ \beta_2\ |\ ...\ |\ \beta_n \]

改写成 \[ A{\rightarrow}\beta_1A^{'}\ |\ \beta_2A^{'}\ |\ ...\ |\ \beta_nA^{'}\\ A^{'}{\rightarrow}\alpha_1A^{'}\ |\ \alpha_2A^{'}\ |\ ...\ |\ \alpha_nA^{'}\ |\ \varepsilon \]

新文法

构造预测分析表

计算FIRST集

找到对应所有产生式中的第一个终结符，如果是非终结符则递归进去。如果有$\epsilon$则看下一个非终结符，全部可以推出$\epsilon$则$FIRST$集包含$epsilon$。

计算FOLLOW集

若$S$为开始符号，则$FOLLOW(S)$包含$ {$} $
若$A{\rightarrow}{\alpha}B$，则$FOLLOW(A)$也加到$FOLLOW(B)$里
若$A{\rightarrow}{\alpha}B{\beta}$，将$FIRST({\beta})-\varepsilon$加到$FOLLOW(B)$里。如果确实有$\varepsilon{\in}FIRST(\beta)$，则$FOLLOW(A)$也加到$FOLLOW(B)$里

计算SELECT集

为了构造预测分析表，需要使用上面计算得到的$FIRST$和$FOLLOW$。预测分析表第一维是非终结符，第二维是输入的终结符，每个格子就是$M[A,\alpha]$。一种直接构造分析表的方法是按照下面两个步骤：

对于任意$A\rightarrow \alpha$:

对$FIRST(\alpha)$中的每个终结符$a$，将$A\rightarrow \alpha$填入$M[A,a]$
如果$\varepsilon \in FIRST(\alpha)$，则对于$FOLLOW(A)$中的每个终结符$b$，将$A\rightarrow \alpha$填入$M[A,b]$。
如果$\varepsilon \in FIRST(\alpha)$，且$属于$FOLLOW(A)$，则将$A \rightarrow \alpha$填入$M[A,\$]$。

按照上面的步骤会比较容易出错，一种比较直观的做法是先计算$SELECT$集：

对于一个产生式$A\rightarrow \alpha$，其$SELECT(A\rightarrow \alpha)$就是可以使用这个产生式进行推导的输入符号的集合。

计算很简单，对于任意$A\rightarrow \alpha$：

如果$\epsilon \notin FIRST(A)$，则$SELECT(A)=FIRST(A) $
如果$\epsilon \in FIRST(A)$，则\[SELECT(A\rightarrow \alpha)=FIRST(A)-\epsilon + FOLLOW(A) \]

计算过程与上面的差不多，其中把额外判断$ $ $的一步省掉了，计算起来更加方便。

预测分析表

比如\[SELECT(A\rightarrow \alpha)=\{+, )\} \]，则预测分析表$M$中：$M[A, +]=M[A, )]=A$。

为了方便书写，可以对产生式编号，比如:$A\_1$就表示$A$的第一条产生式。

最后得到的预测分析表：

一个格子里有两条产生式就是有冲突了（红色标注）。

处理二义性的if语句

由预测分析表第一张图可知，该文法中的if语句还存在着二义性（有冲突），有三种方法可以进行处理。

方法一
将 \[ \begin{align*} stmt \rightarrow &\ \ \mathbf{if} \mathbf{(}bool\mathbf{)}\ stmt \\ &|\ \mathbf{if} \mathbf{(}bool\mathbf{)}\ stmt \ \mathbf{else}\ stmt \end{align*} \] 改写成 \[ \begin{align*} stmt \rightarrow &\ \ matched\_stmt\\ &|\ unmatched\_stmt \\ matched\_stmt\rightarrow &\ \ \mathbf{if}\mathbf{(}bool \mathbf{)}\ matched\_stmt\ \mathbf{else}\ matched\_stmt\\ &|\ other \\ unmatched\_stmt\rightarrow &\ \ \mathbf{if}\mathbf{(}bool \mathbf{)}\ stmt\\ &|\ \mathbf{if}\mathbf{(}bool \mathbf{)}\ matched\_stmt\ \mathbf{else}\ unmatched\_stmt\\ \end{align*} \] 然后要重新计算$FIRST$集和$FOLLOW$集以及预测分析表，再加两个函数，总之比较繁琐。
方法二
先提取左公因子 \[ \begin{align*} stmt\rightarrow &\ \mathbf{if} \mathbf{(}bool\mathbf{)}\ stmt\ else\_part\\ &|\ other\\ else\_part\rightarrow&\ \mathbf{else}\ stmt\\ &|\ \varepsilon \end{align*} \] 然后查看$lookahead$，如果是$else$就使用$elsepart$第一个产生式，否则选第二个。
方法三
观察发现$stmt$的第一个产生式是第二个产生式的前缀，于是不需要提取公因子，只要先进行$if(bool)\ stmt$的匹配，然后再看$lookahead$。如果是$else$，则继续匹配$else\ stmt$即可。这里需要注意因为先进行了其他部分匹配，在代码实现时需要对输出进行控制，否则输出的推到序列就是混乱的。

实现

词法分析器

test.l

%option yylineno

%{

#include "myyacc.tab.h"  /*对终结符的常量定义*/

int yylval;

%}

delim		[ \t\n]
ws		    {delim}+
letter	    [A-Za-z]
digit		[0-9]
id		    ({letter}|_)({letter}|{digit}|_)*
number	    {digit}+(\.{digit}+)?(E[+-]?{digit}+)?

%%
{ws}		{}
\/\/([^\n])+	{	/*printf("line comments : %s\n",yytext);*/}

\/\*([^\*])*\*([\*]|[^\*\/]([^\*])*[\*])*\/      { /*printf("Comments:%s\n",yytext); */}
"if"		{   return(IF);}
"else"      {   return(ELSE);}
"while"     {   return(WHILE);}		
"do"        {   return(DO);}
"break"     {   return(BREAK);}
"true"    	{   return(TRUE);}
"false"     {   return(FALSE);}
"int"		{   return(INT);}
"char"		{   return(CHAR);}
"float"		{   return(FLOAT);}
"bool"		{   return(BOOL);}

{id}		{	 sscanf( yytext, "%s", &yylval ); return(ID);}
{number}	{   sscanf( yytext, "%lf", &yylval); return(NUMBER);}
"<"		{   return(RELOP_LT);}
"="		{   return('=');}
">"		{   return(RELOP_GT);}
"!="    {   return(RELOP_NE);}
"=="    {   return(RELOP_EE);}
"<="    {   return(RELOP_LE);}
">="    {   return(RELOP_GE);}
"||"	{   return(OR);}
"&&"	{   return(AND);}
"+"	    {   return ('+');}
"-"     {   return ('-');}
"*"     {   return ('*');}
"/"     {   return ('/');}
","		{	return (',');}
"("		{	return ('(');}
")"		{	return (')');}
";"		{	return (';');}
"{"		{	return ('{');}
"}"		{	return ('}');}
"["		{	return ('[');}
"]"		{	return (']');}
"."		{	return ('.');}
.       {	printf("Unknown : %s\n",yytext);}
%%

/*该函数设置yyin变量，fflex对yyin变量所对应的文件进行词法分析*/
void BeginCompileOneFile( const char * filename )
{  
   yyin = fopen( filename, "r");
   fseek( yyin, 0, SEEK_SET );
}

void EndCompileOneFile(void) 
{
   fclose(yyin);
   yyin = 0;
}

int yywrap()
{
    return 1;
}

产生式声明

根据新文法和预测分析表进行命名：

// MyProduction.h 产生式定义
#include "myyacc.tab.h"
#include <cstdio>

void Program();
void Block();
void Decls();
void Decl();
void Type();
void Stmts();
void Stmt();
void Bool();
void Bool1();
void Expr();
void Expr1();
void Term();
void Term1();
void Factor();

void Match(int);

#define PN(x)       printf(x"\n");

#define PROGRAM_1   PN("Program\t-> Block") Block();

#define BLOCK_1     PN("Block\t-> { Decls Stmts }") Match('{'); Decls(); Stmts(); Match('}');

#define DECLS_1     PN("Decls\t-> Decl Decls") Decl(); Decls();
#define DECLS_2     PN("Decls\t-> epsilon") 

#define DECL_1      PN("Decl\t-> Type id ;") Type(); Match(ID); Match(';');

#define TYPE_1      PN("Type\t-> int") Match(INT);
#define TYPE_2      PN("Type\t-> float") Match(FLOAT);
#define TYPE_3      PN("Type\t-> char") Match(CHAR);

#define STMTS_1     PN("Stmts\t-> Stmt Stmts") Stmt(); Stmts();
#define STMTS_2     PN("Stmts\t-> epsilon")

#define STMT_1      PN("Stmt\t-> id = Expr ;") Match(ID); Match('='); Expr(); Match(';');
#define STMT_2      PN("Stmt\t-> if ( Bool ) Stmt") Match(IF); Match('('); Bool(); Match(')'); Stmt();
#define STMT_3      PN("Stmt\t-> if ( Bool ) Stmt else Stmt") Match(IF); Match('('); Bool(); Match(')'); Stmt(); Match(ELSE); Stmt();
#define STMT_4      PN("Stmt\t-> while ( Bool ) Stmt") Match(WHILE); Match('('); Bool(); Match(')'); Stmt(); 
#define STMT_5      PN("Stmt\t-> do Stmt while ( Bool ) ;") Match(DO); Stmt(); Match(WHILE); Match('('); Bool(); Match(')'); Match(';'); 
#define STMT_6      PN("Stmt\t-> break ;") Match(BREAK); Match(';'); 
#define STMT_7      PN("Stmt\t-> Block") Block();

#define BOOL_1      PN("Bool\t-> Expr Bool1") Expr(); Bool1();

#define BOOL1_1     PN("Bool1\t-> < Expr") Match(RELOP_LT); Expr();
#define BOOL1_2     PN("Bool1\t-> <= Expr") Match(RELOP_LE); Expr();
#define BOOL1_3     PN("Bool1\t-> > Expr") Match(RELOP_GT); Expr();
#define BOOL1_4     PN("Bool1\t-> >= Expr") Match(RELOP_GE); Expr();
#define BOOL1_5     PN("Bool1\t-> epsilon") 

#define EXPR_1      PN("Expr\t-> Term Expr1") Term(); Expr1();

#define EXPR1_1     PN("Expr1\t-> + Term Expr1") Match('+'); Term(); Expr1();
#define EXPR1_2     PN("Expr1\t-> - Term Expr1") Match('-'); Term(); Expr1();
#define EXPR1_3     PN("Expr1\t-> epsilon") 

#define TERM_1      PN("Term\t-> Factor Term1") Factor(); Term1();

#define TERM1_1     PN("Term1\t-> * Factor Term1") Match('*'); Factor(); Term1();
#define TERM1_2     PN("Term1\t-> / Factor Term1") Match('/'); Factor(); Term1();
#define TERM1_3     PN("Term1\t-> epsilon") 

#define FACTOR_1    PN("Factor\t-> ( Expr )") Match('('); Expr(); Match(')');
#define FACTOR_2    PN("Factor\t-> id") Match(ID);
#define FACTOR_3    PN("Factor\t-> num") Match(NUMBER);

#endif

语法分析器

基本按照预测分析表写switch语句即可。

// parser.cpp 语法分析器

// 直接调用用词法分析的函数
#include "lex.yy.c"
#include "MyProduction.h"

#include <cstdio>
#include <cstring>

int lookahead; // 向前看符号

// 提示错误信息
void Error(){
    printf("Error at line %d:%s\n", yylineno, yytext);
}

// 匹配终结符，并取下一个
void Match(int TokenID)
{
    if( lookahead == TokenID ){
        lookahead = yylex();
    }
    else{
        Error();
    }
}

void Program()
{
    switch(lookahead){
        case '{':	PROGRAM_1 break;
        default:	Error();
    }
}

void Block()
{
    switch(lookahead){
        case '{':	BLOCK_1 break;
        default:	Error();
    }
}

void Decls()
{
    switch(lookahead){
        case ID:	DECLS_2 break;
        case INT:	DECLS_1 break;
        case FLOAT:	DECLS_1 break;
        case CHAR:	DECLS_1 break;
        case IF:	DECLS_2 break;
        case WHILE:	DECLS_2 break;
        case DO:	DECLS_2 break;
        case BREAK:	DECLS_2 break;
        case '{':	DECLS_2 break;
        case '}':	DECLS_2 break;
        default:	Error();
    }
}

void Decl(){
    switch (lookahead){
        case INT:	DECL_1 break;
        case FLOAT:	DECL_1 break;
        case CHAR:	DECL_1 break;
        default:	Error();
    }
}

void Type(){
    switch(lookahead){
        case INT:	TYPE_1 break;
        case FLOAT:	TYPE_2 break;
        case CHAR:	TYPE_3 break;
        default:	Error();
    }
}

void Stmts(){
    switch(lookahead){
        case ID:	STMTS_1 break;
        case IF:	STMTS_1 break;
        case WHILE:	STMTS_1 break;
        case DO:	STMTS_1 break;
        case BREAK:	STMTS_1 break;
        case '{':	STMTS_1 break;
        case '}':	STMTS_2 break;
        default:	Error();
    }
}

void Bool(){
    switch (lookahead){
        case ID:	BOOL_1 break;
        case NUMBER:BOOL_1 break;
        case '(':	BOOL_1 break;
        default:	Error();
    }
}

void Bool1(){
    switch(lookahead){ 
        case RELOP_LT:	BOOL1_1 break;
        case RELOP_LE:	BOOL1_2 break;
        case RELOP_GT:	BOOL1_3 break;
        case RELOP_GE:	BOOL1_4 break;
        case ')':		BOOL1_5 break;
        default:	Error();
    }
}

void Expr(){
    switch(lookahead){
        case ID:	EXPR_1 break;
        case NUMBER:EXPR_1 break;
        case '(':	EXPR_1 break;
        default:	Error();
    }
}

void Expr1(){
    switch(lookahead){
        case RELOP_LT:	EXPR1_3 break;
        case RELOP_LE:	EXPR1_3 break;
        case RELOP_GT:	EXPR1_3 break;
        case '+':		EXPR1_1 break;
        case '-':		EXPR1_2 break;
        case RELOP_GE:	EXPR1_3 break;
        case ';':		EXPR1_3 break;
        case ')':		EXPR1_3 break;
        default:		Error();
    }
}

void Term(){
    switch(lookahead){
        case ID:	TERM_1 break;
        case NUMBER:TERM_1 break;
        case '(':	TERM_1 break;
        default:	Error();
    }
}

void Term1(){
    switch(lookahead){
        case '*':		TERM1_1 break;
        case '/':		TERM1_2 break;
        case RELOP_LT:	TERM1_3 break;
        case RELOP_LE:	TERM1_3 break;
        case RELOP_GT:	TERM1_3 break;
        case '+':		TERM1_3 break;
        case '-':		TERM1_3 break;
        case RELOP_GE:	TERM1_3 break;
        case ';':		TERM1_3 break;
        case ')':		TERM1_3 break;
        default:	Error();
    }
}

void Factor(){
    switch(lookahead){
        case ID:	FACTOR_2 break;
        case NUMBER:FACTOR_3 break;
        case '(':	FACTOR_1 break;
        default:	Error();
    }
}

int main(int argc, char* argv[])
{ 
    char filename[1000];
    
    if(argc <= 1){
        printf("请输入要编译的源程序文件名："); 
        gets(filename);
    }else{
        strcpy(filename, argv[1]);
    }

    BeginCompileOneFile( filename ); // 在lex.yy.c
   
    //当flex扫描到文件末尾，yylex函数返回0
    lookahead = yylex();

    Program();

    EndCompileOneFile();

    // getchar();
    
    return 0;
}

还有一个$Stmt$的函数需要特殊处理，也就是将输出延迟。

首先在MyProduction中修改：

static bool delay = false;
static std::queue<std::string> outputQ;

// 延迟输出（将暂存到队列中）
void DelayOutput(){
    delay = true;
}

// 刷新输出（将队列中的全部输出）
void FlushOutput(){
    delay = false;
    while(outputQ.size()){
        printf(outputQ.front().c_str());
        outputQ.pop();
    }
}

#define PN(x)       if(delay) outputQ.push(x"\n"); else printf(x"\n");

然后实现Stmt

void Stmt(){
    switch(lookahead){
        case ID:	STMT_1 break;
        case IF:	
            // 先将输出延迟，匹配左公因子
            DelayOutput(); Match(IF); Match('('); Bool(); Match(')'); Stmt();
            // 然后比较向前看符号
            if(lookahead == ELSE){
                printf("Stmt\t-> if ( Bool ) Stmt else Stmt\n"); FlushOutput(); Match(ELSE); Stmt();
            }else{
                printf("Stmt\t-> if ( Bool ) Stmt\n"); FlushOutput();
            }
            break;
        case WHILE:	STMT_4 break;
        case DO:	STMT_5 break;
        case BREAK:	STMT_6 break;
        case '{':	STMT_7 break;
        default:	Error();
    }
}

运行

构建脚本build.bat

1
2
3

flex.exe test.l
g++ parser.cpp -o parser.exe
parser.exe code.txt

输入code.txt

{
    int i ;
    i = 2;
    if(i > 0){
        i = i - 1;
    }else{
        i = i + 1;
    }
    while(i > 0){
        i = i - 1;
    }
}

输出output.txt

Program	-> Block
Block	-> { Decls Stmts }
Decls	-> Decl Decls
Decl	-> Type id ;
Type	-> int
Decls	-> epsilon
Stmts	-> Stmt Stmts
Stmt	-> id = Expr ;
Expr	-> Term Expr1
Term	-> Factor Term1
Factor	-> num
Term1	-> epsilon
Expr1	-> epsilon
Stmts	-> Stmt Stmts
Stmt	-> if ( Bool ) Stmt else Stmt
Bool	-> Expr Bool1
Expr	-> Term Expr1
Term	-> Factor Term1
Factor	-> id
Term1	-> epsilon
Expr1	-> epsilon
Bool1	-> > Expr
Expr	-> Term Expr1
Term	-> Factor Term1
Factor	-> num
Term1	-> epsilon
Expr1	-> epsilon
Stmt	-> Block
Block	-> { Decls Stmts }
Decls	-> epsilon
Stmts	-> Stmt Stmts
Stmt	-> id = Expr ;
Expr	-> Term Expr1
Term	-> Factor Term1
Factor	-> id
Term1	-> epsilon
Expr1	-> - Term Expr1
Term	-> Factor Term1
Factor	-> num
Term1	-> epsilon
Expr1	-> epsilon
Stmts	-> epsilon
Stmt	-> Block
Block	-> { Decls Stmts }
Decls	-> epsilon
Stmts	-> Stmt Stmts
Stmt	-> id = Expr ;
Expr	-> Term Expr1
Term	-> Factor Term1
Factor	-> id
Term1	-> epsilon
Expr1	-> + Term Expr1
Term	-> Factor Term1
Factor	-> num
Term1	-> epsilon
Expr1	-> epsilon
Stmts	-> epsilon
Stmts	-> Stmt Stmts
Stmt	-> while ( Bool ) Stmt
Bool	-> Expr Bool1
Expr	-> Term Expr1
Term	-> Factor Term1
Factor	-> id
Term1	-> epsilon
Expr1	-> epsilon
Bool1	-> > Expr
Expr	-> Term Expr1
Term	-> Factor Term1
Factor	-> num
Term1	-> epsilon
Expr1	-> epsilon
Stmt	-> Block
Block	-> { Decls Stmts }
Decls	-> epsilon
Stmts	-> Stmt Stmts
Stmt	-> id = Expr ;
Expr	-> Term Expr1
Term	-> Factor Term1
Factor	-> id
Term1	-> epsilon
Expr1	-> - Term Expr1
Term	-> Factor Term1
Factor	-> num
Term1	-> epsilon
Expr1	-> epsilon
Stmts	-> epsilon
Stmts	-> epsilon

还可以使用python将构建的语法分析树画出来：

详细实现见用Python绘制语法分析树