flex/bison系列3：更复杂的一个编译程序实现（上）

引言

这是一个系列文章，旨在了解如何使用Flex/Lex和Yacc/Bison进行词法和语法解析。在前面，已经完成了使用Lex/flex做基础的词法解析、实现一个简单的计算器。开始这个系列的第三部分，使用flex和bison完成一个更加复杂的的编译程序。整体上有一定的复杂度，所以分上下篇分别介绍。上篇介绍：实现概要、语法、，下篇介绍数据结构与实现（包括解析树实现、执行）。

下篇介绍：数据结构与实现
- 与Grammar对应的“解析树”
- “解析树”的执行
- 解析树的节点，Terminals 和 Non-Terminals
- 一个“简单语句”的解析树结构
- 一个“略微复杂语句”的解析树结构

解析与执行包含赋值、IF、WHILE等语句的程序

在前面的案例中，我们实现了一个简单的加减乘运算的计算器程序。这里我们尝试实现一个更复杂一些的编译程序，语法能够支持如下内容：

包含了变量，可以对变量赋值，也可以在表达式中使用变量。但是为了简化程序，这里变量仅限于使用单个小写字母，即[a-z]
支持条件运算，这里定义简单的语法如下：if ( expr ) expre ; （忽略了else语法）
支持比较运算符，包括大于、小于
支持循环运算，支持while循环
和前面案例的一样，仅处理整数，故不处理除法，也不考虑整数溢出等边界问题

我们用这几个能力，可以编写如下的程序：

i = 1;
a = 0;
while ( a < 100 ) {
  i = i + 1;
  a = a + i;
}
print i;

这个程序实现了一个简单的功能，解决的问题是：在自然数序列（1、2、4…）中，前面多少个自然数的和首次大于100。你可以使用上面的命令编写其他的任意程序。

解析树的节点

如果只是使用前面的指令，似乎难以实现对if/while语句的支持。这里，就需要使用典型的编译与执行思路了，先使用语法解析构建一个“语法树”（也叫“解析树”），然后再执行该解析树。具体的，一些设计如下：

使用一个全局数组（int * var[26]）存储变量，因为在前面限制了变量名只能是[a-z]
每个grammar rule对应一个tree node，并依次构建一棵语法树
语法树的节点设计如下：

typedef struct t_node{
    enum NODETYPE nt;
    struct t_node* left;
    struct t_node* right;
    int i;  // for NT_INTEGER NT_VAR_NAME node
}t_node;

这里为了简化：

所有语法节点都存放在该结构中
对于变量名，本应该是一个字符，这里在存储时，直接使用其ASCII码将其存储为整数

语法规则设计

在开始实现与执行解析树之前，我们先定义语法规则，以支持赋值、if、while、print等语法。语法规则定义时，需要注意尽量避免出现shift/reduce冲突，并且这里的语法规则不包含Action部分：

//start symbol
program: 
        | program statement_block   { printf("\n job done! \n"); }
;

statement_block: 
        | statement_block statement
;

statement: assignment
        | print_func
        | if_block
        | while_block 
;

while_block: WHILE '('  bool_expr ')' '{' statement_block '}'

if_block: IF '(' bool_expr ')' '{' statement_block '}'

assignment: VAR_NAME '=' expression ';'

print_func : PRINT expression ';'  
        | PRINT VAR_NAME ';'

bool_expr: expression GT expression
        |  expression LT expression

expression: INTEGER
        | VAR_NAME
        | expression O_ADD expression
        | expression O_MINUS expression
        | expression O_MULTIPLY expression

节点分析

节点分析：INTEGER VAR_NAME

节点类型（enum NODETYPE）分别是：NT_INTEGER NT_VAR_NAME
没有子节点，故left/right node都是NULL
在初始化时，
- 对于INTEGER：t_node.a 存储的是具体的整数
- 对于VAR_NAME：则存储的变量名，这了变量名为[a-z]，则将其ASCII存放于t_node.a

节点分析：expression 与 O_ADD O_MINUS O_MULTIPLY

expression对应的语法规则如下

expression: INTEGER
        | VAR_NAME
        | expression O_ADD expression
        | expression O_MINUS expression
        | expression O_MULTIPLY expression

那么，再看看O_ADD O_MINUS O_MULTIPLY这类节点：

NODETYPE 分别是 NT_O_ADD NT_O_MINUS NT_O_MULTIPLY
都有两个子节点，left / right
在execute之后存储，各个expression计算的结果值t_node.a中
注意，在这个设计中，无需有一个独立的expression节点

bool表达式（bool_expr），通常用于条件判断

bool_expr: expression GT expression 
        |  expression LT expression

节点类型（enum NODETYPE）为 NT_BOOL_EXPR
有两个子节点，执行该节点时，需要执行两个子节点之后，获得两个子节点的结果值，再进行比较
返回值为为bool型，这里使用int存储，0表示FALSE 1表示TRUE

print_func节点

这个节点实现一个打印整数值的功能，参数可以是一个变量，也可以是一个表达式：

print_func : PRINT expression ';'  
        | PRINT VAR_NAME ';'

NODETYPE为 NT_PRINT_FUNC
只有一个子节点，为一个 expression 或 VAR_NAME （注：这里应该只用expression就可以了，因为VAR_NAME也是expression）
执行该节点时，则需要实际调用一次打印函数，向标准输出打印expression的结果值

assignment 赋值语句

assignment: VAR_NAME '=' expression ';'

赋值语句左边是变量名，这里定义是[a-z]，右边是一个表达式，语句以分号结束。

其节点类型（NODETYPE）为：NT_ASSIGNMENT
左子节点为 VAR_NAME ，右子节点为 expression
其执行时，需要将expression的结果值，存储到变量数组对应的整型变量中

while_block WHILE子句

while_block: WHILE '('  bool_expr ')' '{' statement_block '}'

其节点类型（NODETYPE）为：NT_WHILE
左子节点为: bool_expr 右子节点为 : statement_block
执行该节点时，也是也while循环执行，条件部分是执行并判断bool_expr的真假，再决定是否执行右子节点。这里需要注意，每次获取bool_expr的时候，都需要先执行一次该节点。

if_block IF子句

if_block: IF '(' bool_expr ')' '{' statement_block '}'

其节点类型（NODETYPE）为：NT_IF
左子结点为 bool_expr 右子节点 : statement_block
执行时，先执行左子节点，再获取其结果的真/假，再判断是否执行右子节点

statement

statement: assignment
        | print_func
        | if_block
        | while_block

可以看到，statement由assignment、print_func、if_block、while_block是这些中的任何一个。所以，在实际构建中，并不会有该节点。与expression类似。

statement_block 多个statement

statement_block: 
        | statement_block statement
;

其节点类型（NODETYPE）为：NT_STATEMENT_BLOCK
左子节点为 : statement_block，即为statement_block或者assignment、print_func、if_block、while_block中的任意一个；右子节点为 : assignment、print_func、if_block、while_block
执行时，先执行左子节点，再执行右子节点

program

program:
        | program statement_block  { printf("\n job done! \n"); }
;

主要的数据结构与函数

build_node：构建当前语法规则的节点，该函数返回当前构建出来节点的指针，通常也是各个语法规则Action部分的返回值。

t_node* build_node( 
    enum NODETYPE nt,
    t_node* left,
    t_node* right,
    int i)

exec_node：执行某个节点，并执行其左/右子节点（如果存在的话）。不同的节点的执行操作会有一些不同，例如：
- if节点需要做一些判断，再决定是否执行；
- while节点则需要循环bool_expr以决定是否执行某段代码。
- 加法节点，则需要执行左右子节点执行结果，并相加

各类节点的exec操作可以参考上一节的详细描述。该函数定义如下

int exec_node(t_node *n)

解析树的节点与节点类型

typedef struct t_node{
    enum NODETYPE nt;
    struct t_node* left;
    struct t_node* right;
    struct t_node* rrnode;
    int i;  // for NT_INTEGER NT_VAR_NAME node
}t_node;

enum NODETYPE{
    NT_STATEMENT,
    NT_IF,
    NT_WHILE,
    NT_PROGRAM,
    NT_STATEMENT_BLOCK,
    NT_O_ADD,
    NT_O_MINUS,
    NT_O_MULTIPLY,
    NT_INTEGER,
    NT_VAR_NAME,
    NT_BOOL_EXPR_GT,
    NT_BOOL_EXPR_LT,
    NT_PRINT,
    NT_ASSIGNMENT
};

下一篇，我们将基于此完成完整的代码。

不包含Action代码的语法

补充完整的语法文件cal.y

包括：

入口函数
NODETYPE 定义
解析树的节点 t_node
声明节点便利函数 exec_node
用于存储变量的数组 int var[26];
YYSTYPE （似乎是不需要）
定义lex需要处理的TOKEN
定义运算符优先级、结合律

%{
// 入口函数

#include <stdio.h>

int main (){
    yyparse();
    return 0;
}

enum NODETYPE{
    NT_PROGRAM,
    NT_STATEMENT_BLOCK,
    NT_STATEMENT,
    NT_IF,
    NT_WHILE,
    NT_O_ADD, 
    NT_O_MINUS,
    NT_O_MULTIPLY,
    NT_INTEGER,
    NT_VAR_NAME
};

typedef struct t_node{
    enum NODETYPEP nt;
    t_node * left;
    t_node * right;
    t_node * rrnode;
    YYSTYPE yval;
}t_node;

//递归执行整个parser tree
int exec_node(t_node *n){
    return 0;
}

int var[26];

%}

// 定义YYSTYPE
%union {
    int a;  // for integer
    char c; // for var_name
    bool b; // for bool_expr
}


// 定义Token
%token <c> VAR_NAME 
%token <a> INTEGER
%token O_ADD O_MINUS O_MULTIPLY 

%token GT LT

%token WHILE IF
%token PRINT

// 定义运算符
%left O_ADD O_MINUS
%left O_MULTIPLY

补充Lex文件

%{
    #include "cal.tab.h"
%}
%option noyywrap
%%
[[:digit:]]+ {
    yylval.a = atoi(yytext);
    return INTEGER;
}

[a-z] {
    yylval.c = yytext[0];
    return VAR_NAME;
}

"+" { return O_ADD;};
"-" { return O_MINUS;};
"*" { return O_MULTIPLY;};

"while"  {return WHILE;}
"if"  {return IF;}
"print"  {return PRINT;}

">" {return GT;}
"<" {return LT;}

[();={}]  {return yylval.c = *yytext;}

%%

生成代码并编译、修改

lex cal.l 
bison -d cal.y 
gcc cal.tab.c lex.yy.c -o a.out


bison -W -d cal.y

cal.y:62.8: warning: empty rule without %empty [-Wempty-rule]
 program:
        ^
cal.y:66.16: warning: empty rule without %empty [-Wempty-rule]
 statement_block:
                ^
cal.y: warning: 6 shift/reduce conflicts [-Wconflicts-sr]

错误1：这里的 PRINT expression ‘;’ ~~PRINT VAR_NAME ‘;’~~ 是有包含关系，重复的。因为VAR_NAME本身也是一个expression。故修改如下：

print_func : PRINT expression ';'  
        | PRINT VAR_NAME ';' 

expression: INTEGER
        | VAR_NAME
        | expression O_ADD expression
        | expression O_MINUS expression
        | expression O_MULTIPLY expression

疑问与思考：左边/右边的表达有什么不同。（注意，左边的表达会报shift/reduce conflict）

program: 
        | program statement_block 
;

statement_block: 
        | statement_block statement
;

statement: assignment
        | print_func
        | if_block
        | while_block 
;

program: statement_block 
;


statement_block:
        | statement_block statement
;

statement: assignment 
        | print_func 
        | if_block 
        | while_block 
;

修改后的cal.y文件，仅语法部分，不包含Action

%%
program:  statement_block { printf("\n job done! \n");}
;

statement_block:
        | statement_block statement
;

statement: assignment 
        | print_func 
        | if_block 
        | while_block 
;

if_block: IF '(' bool_expr ')' '{' statement_block '}' 

while_block: WHILE '('  bool_expr ')' '{' statement_block '}' 

assignment: VAR_NAME '=' expression ';'

print_func : PRINT expression ';'

bool_expr: expression GT expression
        |  expression LT expression

expression: INTEGER
        | VAR_NAME
        | expression O_ADD expression
        | expression O_MINUS expression
        | expression O_MULTIPLY expression

orczhou.com