引言
这是一个系列文章，旨在了解如何使用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
- 对于INTEGER：
节点分析：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
