引言
这是一个系列文章,旨在了解如何使用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