使用Flex和Bison制作编译器

这学期的编译原理课上，我们以C-Minus，一个C语言子集，作为源语言，实现词法分析、语法分析、三地址代码生成等功能的编译器（或解析器）。
代码见GitHub：https://github.com/frankgx97/compiler

Flex与词法分析

进行词法分析之前首先对字符表进行定义。根据CMinus的语法定义，需要进行识别的字符集主要包括如下部分：
关键字：
if，else，while，int，void，return
运算符：
+，-，*，/
比较运算符：
<，<=，>，>=，==，!=，，
标识符：
ID
数字：
NUM

一个flex词法分析文件和bison一样分为声明，定义，规则4个部分。
其中,定义部分用来通过正则表达式定义单词，如数字可定义为{digit}+。

letter  [a-zA-Z]
digit   [0-9]
ID  ({letter}|{digit})+|{letter}+({letter}|{digit})*
NUM {digit}+
SPACES  (\t|\0|\r|\n|\ )+
COMMENT \/\*([^\*^\/]*|[\*^\/*]*|[^\**\/]*)*\*\/

规则部分定义了遇到相应单词时的动作。通常来说需要进行的动作有两个，一个是将当前单词赋值到相应的数据结构（比如Node类），然后将已初始化的对象赋值给yylval。yylval会将变量传递给bison产生式右部的相应位置（$1, $2等等）。然后返回该符号的标识，如下面的ID和NUM。该标识是一个整数常量的宏定义，我们可以自行用#define定义它们，如果用户没有定义，则Flex将会自动从数字258开始依次定义。

{ID}   { yylval = new Terminal( ID   , string(yytext) ); return ID; }
{NUM}  { yylval = new Terminal( NUM , string(yytext) ); return NUM; }

Bison与语法分析

bison 是一个语法分析器的生成器，与Flex配合使用，它可以将用户提供的语法规则转化成一个语法分析器。简单来说，bison读取用户提供的语法的产生式，生成一个 C 语言格式的 LALR(1) 动作表，并将其包含进一个名为yyparse的 C 函数，这个函数的作用就是利用这个动作表来解析由 flex 生成的词法分析器扫描源程序得到的单词流。

%{
//声明
#include 
#include 
#include "Node.h"
using namespace std;
%}
//定义
%token  K_ELSE K_IF K_RETURN K_WHILE K_PRINTF K_READ K_INT K_VOID

%%
//产生式
Program:
        Declaration_list                                { $ = gen_expr(0,"Program", 1, $1 ); head = $; }
;
%%
//用户代码
int main(int argc,char* argv[]) {
    yyin = fopen(argv[1],"r");
    yyparse();
}

一个Bison的.y文件分为如下四个部分。其中，%{和%}之间为声明区域，其中包含对头文件，宏定义，函数定义等的声明，这部分代码会被原样复制到生成的C++代码中；
%}和%%之间为定义区域，其中含有终结符和非终结符的定义，通常用于定义某类符号在union中的何处来存储。此外还有一些bison配置，如报错的等级等；
由两个%%包裹的是产生式区域，里面是用BNF表示的产生式。其中:表示产生式的推导，等价于:=；同一非终结符的不同产生式用|分隔，用;表示产生式的结尾。每条产生式的后面都有一段C++代码，将在产生式归约时被执行。
最下面是用户代码区域，这部分代码也会被原样复制到目标代码中。

符号定义

在所有产生式中，我定义了如下的符号，其中终结符使用%token%定义，非终结符使用%type%定义，其中尖括号内的内容代表用来存储当前符号所用数据结构，且该类型已在下面所述的%union中定义。

%token  K_ELSE K_IF K_RETURN K_WHILE K_PRINTF K_READ K_INT K_VOID
%token  ID NUM 
%token  O_ASSIGN O_COMMA O_SEMI
%token  O_LSBRACKER O_RSBRACKER O_LMBRACKER O_RMBRACKER O_LLBRACKER O_RLBRACKER
%token  O_ADD O_SUB O_MUL O_DIV 
%token  O_LESS O_L_EQUAL O_GREATER O_G_EQUAL O_EQUAL O_U_EQUAL
%token  COMMENT SPACES U_LEGAL

%type  E Id FunctionName ReturnType FunctionDeclare Program Args ArgType Arg
%type  AssignStmt IfStmt Stmts WhileStmt DeclareStmt PrintfStmt ReadStmt CallStmt ReturnStmt
%type  Stmt

在bison文件的定义区域，%union定义一个所有符号的数据类型的集合。

%union{
    char * code;
    int addr;
    Node * node;
}

根据上面%type和%token的定义，在每个产生式归约时，一个相应类型的对象将被初始化并赋值。

移进归约冲突

在bison生成代码的过程中，bison会报出类似如下的移进归约冲突。

parser.y: warning: 27 shift/reduce conflicts [-Wconflicts-sr]

在执行bison时加上-v参数，bison将会把分析表输出到一个.output文件，其中会指明哪个状态出现了冲突

算符优先级引起的冲突

对于下面的产生式，如果没有定义其优先级，则会引发冲突。

E:
    E O_ADD E    {}
    E O_SUB E    {}
;

解决方法是在bison文件的定义区域声明运算符的优先级，避免引起冲突。%left表示该符号是左结合的。

%left O_ADD O_SUB
%left O_MUL O_DIV

Dangling else 引起的冲突

对于下面所述的If语句的文法。

IfStmt:
    K_IF O_LSBRACKER E O_RSBRACKER Stmt          
|   K_IF O_LSBRACKER E O_RSBRACKER Stmt K_ELSE Stmt

由于其含有公共前缀，在分析到K_IF O_LSBRACKER E O_RSBRACKER Stmt时，可以移进else或规约到IfStmt。在移进归约冲突中，如果没有额外处理，bison会倾向于移进。

解决方案是将文法改写成如下的形式：

selection_stmt:
    matched_if      { $ = gen_expr( 0, "expression_stmt", 1, $1 ); }
|   unmatched_if    { $ = gen_expr( 0, "expression_stmt", 1, $1 ); }

matched_if:
    K_IF O_LSBRACKER expression O_RSBRACKER statement K_ELSE statement { 
        $ = gen_expr( 18, "matched_if", 7, $1, $2, $3, $4, $5, $6, $7 ); 
    }

unmatched_if:
    K_IF O_LSBRACKER expression O_RSBRACKER statement                   
        { $ = gen_expr( 16, "unmatched_if", 5, $1, $2, $3, $4, $5 ); }
|   K_IF O_LSBRACKER expression O_RSBRACKER matched_if K_ELSE unmatched_if      
        { $ = gen_expr( 18, "unmatched_if", 7, $1, $2, $3, $4, $5, $6, $7 ); }
;

抽象语法树

抽象语法树的每个节点为一个定义为一个Node对象，Node类的定义如下

class Node{
public:    
    int type;
    string value;
    Node *lchild, *rchild;
    Node():lchild(NULL),rchild(NULL){}

    virtual bool isTerminal();
    virtual string toString();
};

class Terminal: public Node{
public:
    Terminal(int t,string val);
    string toString();
    bool isTerminal();
};

class Var:public Node{
public:
    string expr;
    Var(string e);
    string toString();
    bool isTerminal();
};

由于抽象语法树是一棵多叉树，其中还含有代码块等，实现较为困难。我最开始将每种节点都定义了一个继承自Node类的类，如果其中含有代码块（stmts）等，则使用vector来存储。这种方式使代码过于复杂且难以维护，因此我将这棵树改造为一棵二叉树。
在这棵语法树中，左孩子指针表示产生式的推导，右孩子指针连接一个产生式的右部的所有符号。
我们定义了一个带有动态参数表的gen_expr()函数。在每次产生式被归约时，将$1, $2, $3…通过动态参数传入该函数，该函数将$1, $2等节点用右孩子指针连接起来，形成一棵子树。最后将头节点赋值给$$。
示例代码

int main(){
    x = 5+10;
    if(5){
        y = 10;
    }
    c = 99;
}

打印出的语法树如下图：

语义分析与中间代码

…待续…

TroubleShooting

这里列举了我在开发过程中遇到的问题及其解决方案。

使bison打印详细错误信息而不仅仅是”syntax error”

在bison文件的%%前加入如下语句即可打印详细错误，注意此方法需要bison版本>3。

%define parse.error verbose

按照如下步骤，即可使bison打印出错的行号。

So, here I’m a with a step-by-step solution :
We add the %locations directive in our grammar file (between %} and the first %%)
We make sure that our lexer file contains an include for our parser (e.g. #include “mygrammar.tab.h”), at the top
We add the %option yylineno option in our lexer file (between %} and the first %%)
And now, in our yyerror function (which will supposedly be in our lexer file), we may freely use this… yylineno (= current line in file being processed) :

void yyerror(const char *str)
 {
  fprintf(stderr,"Error | Line: %d\n%s\n",yylineno,str);
 }

报错：unexpected $end, expecting xxx

奇怪的bug，我也不知道怎么修好的。
参考：

https://stackoverflow.com/questions/12755874/why-is-bison-expecting-end-after-the-first-token
https://stackoverflow.com/questions/41292555/lex-yacc-line-1-syntax-error-unexpected-end-expecting-function-lex-compil

parser输出为null

词法分析中加入

{ID} { yylval = strdup(yytext); return ID ;}

yylval用于将lexer得到的数据传递给parser。因此需要在词法分析的语句里被赋值。其类型由YYSTYPE宏来定义。

参考：https://stackoverflow.com/questions/32083387/bison-parser-token-string-value-returning-null

报错：parser.y:27.8-14: fatal error: start symbol Program does not derive any sentence

通常是由于产生式存在很弱智的错误。

报错：expecting $end

http://www.4answered.com/questions/view/1a4f2a0/Expecting-end-after-first-input

nonterminal useless in grammar: const_declaration [-Wother]

通常伴随大片的warning，原因是产生式有误导致不能正确归约。

参考：

https://stackoverflow.com/questions/41674927/warning-nonterminal-useless-in-grammar-const-declaration-wother
https://stackoverflow.com/questions/21070135/bison-nonterminal-useless-in-grammar

使flex和bison输出cpp

要使flex和bison输出.cpp文件，加上-o参数使其输出为cpp文件，且使用g++编译即可。flex和bison文件无需做额外改动。

union中不允许含有string

union中禁止含有std::string，只能用char * 替代了。

参考：https://stackoverflow.com/questions/7299171/union-member-has-a-non-trivial-copy-constructor?rq=1

报错：xxx has no declared type

bison中的每个非终结符需要在定义区域（%} 和 %%之间）声明其类型。

参考：https://stackoverflow.com/questions/1014619/how-to-solve-bison-warning-has-no-declared-type

通过父类指针访问子类成员

解决方案是写一个虚函数getter。虚函数在基类要有实现，否则报a missing vtable usually means the first non-inline virtual member function has no definition.

参考：https://www.cnblogs.com/zhangbaochong/p/5380016.html

Comments

4 responses to “使用Flex和Bison制作编译器”

Tom

2018-12-03

大佬，代码很棒，语义分析和中间代码生成的坑还填吗_(:з」∠)_

回复/Reply
1. Frank
  
  2018-12-03
  
  谢谢，不过这个课程太久远以至于基本上已经忘光了，坑怕是填不了了
  
  回复/Reply
antior

2018-06-29

看完觉得没当程序员也比较幸运吧，好复杂的语法。

回复/Reply
1. Frank
  
  2018-06-29
  
  其实如果把原理弄明白的话，就不会觉得那么复杂了。
  
  回复/Reply

发表回复/Leave a Reply Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.