使用Flex和Bison制作编译器

这学期的编译原理课上,我们以C-Minus,一个C语言子集,作为源语言,实现词法分析、语法分析、三地址代码生成等功能的编译器(或解析器)。
代码见GitHub:https://github.com/nyanim/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

Show CommentsClose Comments

4 Comments

  • Tom
    Posted 2018 年 12 月 3 日 at 下午 12:23 0Likes
    Google Chrome 70.0.3538.110 Google Chrome 70.0.3538.110 Windows 10 x64 Edition Windows 10 x64 Edition

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

    • Frank
      Posted 2018 年 12 月 3 日 at 下午 1:01 0Likes
      Chrome 70.0.3538.75 Chrome 70.0.3538.75 iPhone iOS 12.1 iPhone iOS 12.1

      谢谢,不过这个课程太久远以至于基本上已经忘光了,坑怕是填不了了

  • antior
    Posted 2018 年 6 月 29 日 at 下午 8:28 0Likes
    Opera 53.0.2907.99 Opera 53.0.2907.99 Windows 8.1 x64 Edition Windows 8.1 x64 Edition

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

    • Frank
      Posted 2018 年 6 月 29 日 at 下午 9:22 0Likes
      Chrome 67.0.3396.87 Chrome 67.0.3396.87 iPhone iOS 11.4.1 iPhone iOS 11.4.1

      其实如果把原理弄明白的话,就不会觉得那么复杂了。

Leave a comment