使用Flex和Bison制作编译器

Frank发布

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

Flex与词法分析

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

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

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

Bison与语法分析

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

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

符号定义

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

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

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

移进归约冲突

在bison生成代码的过程中,bison会报出形如:
parser.y: warning: 27 shift/reduce conflicts [-Wconflicts-sr]
的移进归约冲突。
在执行bison时加上-v参数,bison将会把分析表输出到一个.output文件,其中会指明哪个状态出现了冲突

算符优先级引起的冲突

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

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

Dangling else 引起的冲突

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

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

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

抽象语法树

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

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

打印出的语法树如下图:

语义分析与中间代码

…待续…

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) :

报错: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

分类: 原创文章

2 条评论

antior · 2018 年 6 月 29 日 下午 8:28

Opera 53.0.2907.99 Opera 53.0.2907.99 Windows 8.1 x64 Edition Windows 8.1 x64 Edition

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

    Frank  Mod · 2018 年 6 月 29 日 下午 9:22

    Chrome 67.0.3396.87 Chrome 67.0.3396.87 iPhone iOS 11.4.1 iPhone iOS 11.4.1

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Captcha *

%d 博主赞过: