您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# 如何使用Flex与Bison实现计算器
本文将详细介绍如何利用Flex和Bison工具实现一个功能完整的计算器程序。我们将从基础概念讲起，逐步构建词法分析器、语法分析器，最终实现一个支持四则运算、函数、变量等高级功能的计算器。
## 目录
1. [Flex与Bison简介](#flex与bison简介)
2. [开发环境搭建](#开发环境搭建)
3. [计算器需求分析](#计算器需求分析)
4. [词法分析器设计](#词法分析器设计)
5. [语法分析器设计](#语法分析器设计)
6. [语义分析与计算](#语义分析与计算)
7. [错误处理与恢复](#错误处理与恢复)
8. [高级功能扩展](#高级功能扩展)
9. [构建与测试](#构建与测试)
10. [性能优化](#性能优化)
11. [总结](#总结)
## Flex与Bison简介
### 什么是Flex和Bison
Flex（Fast Lexical Analyzer Generator）是一个生成词法分析器的工具，它根据用户定义的规则将输入流分解为一系列标记（tokens）。Bison是一个语法分析器生成器，与Yacc兼容但功能更强大，它根据用户定义的语法规则来分析标记序列的结构。
### 工作原理
1. **Flex**负责：
- 读取输入字符流
- 根据正则表达式规则匹配词法单元
- 生成标记（tokens）供Bison使用
2. **Bison**负责：
- 接收Flex生成的标记
- 根据上下文无关文法规则分析语法结构
- 执行关联的语义动作
### 典型工作流程
```mermaid
graph LR
A[源代码] --> B[Flex词法分析]
B --> C[Tokens流]
C --> D[Bison语法分析]
D --> E[抽象语法树AST]
E --> F[语义分析与代码生成]
在Ubuntu/Debian系统上：
sudo apt-get install flex bison gcc
在MacOS上：
brew install flex bison
flex --version
bison --version
建议采用如下目录结构：
calculator/
├── src/
│ ├── lexer.l # Flex词法规则
│ ├── parser.y # Bison语法规则
│ └── main.c # 主程序
├── include/
│ └── calculator.h # 头文件
└── Makefile
x = 3 + 5 * (10 - 4)
y = sin(pi/2)
print x + y
%{
#include "calculator.h"
#include "parser.tab.h" // Bison生成的头文件
%}
%option noyywrap
DIGIT [0-9]
INTEGER {DIGIT}+
FLOAT {DIGIT}+\.{DIGIT}*|\.{DIGIT}+
ID [a-zA-Z_][a-zA-Z0-9_]*
%%
{INTEGER} { yylval.num = atoi(yytext); return INTEGER; }
{FLOAT} { yylval.fnum = atof(yytext); return FLOAT; }
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return TIMES; }
"/" { return DIVIDE; }
"(" { return LPAREN; }
")" { return RPAREN; }
"=" { return ASSIGN; }
{ID} { yylval.str = strdup(yytext); return IDENTIFIER; }
[ \t\n] ; // 忽略空白字符
. { yyerror("非法字符"); }
%%
// 辅助函数可以放在这里
yylval是Flex与Bison通信的联合体，需要在Bison中定义yytext包含匹配的文本内容yyerror用于错误处理%{
#include "calculator.h"
#include <math.h>
#include <string.h>
// 变量存储结构
typedef struct {
char* name;
double value;
} Variable;
Variable vars[100];
int var_count = 0;
double get_variable(char* name) {
for(int i=0; i<var_count; i++) {
if(strcmp(vars[i].name, name) == 0) {
return vars[i].value;
}
}
yyerror("未定义的变量");
return 0;
}
void set_variable(char* name, double value) {
for(int i=0; i<var_count; i++) {
if(strcmp(vars[i].name, name) == 0) {
vars[i].value = value;
return;
}
}
// 新变量
vars[var_count].name = strdup(name);
vars[var_count].value = value;
var_count++;
}
%}
%union {
int num;
double fnum;
char* str;
}
// Token声明
%token <num> INTEGER
%token <fnum> FLOAT
%token <str> IDENTIFIER
%token PLUS MINUS TIMES DIVIDE MOD
%token LPAREN RPAREN
%token ASSIGN
%token SIN COS SQRT LOG EXP // 函数token
// 优先级和结合性
%left PLUS MINUS
%left TIMES DIVIDE MOD
%right UMINUS // 一元负号
%type <fnum> expr
%%
input:
/* 空 */
| input line
;
line:
'\n'
| expr '\n' { printf("= %g\n", $1); }
| IDENTIFIER ASSIGN expr '\n' {
set_variable($1, $3);
printf("%s = %g\n", $1, $3);
free($1);
}
;
expr:
INTEGER { $$ = $1; }
| FLOAT { $$ = $1; }
| IDENTIFIER { $$ = get_variable($1); free($1); }
| expr PLUS expr { $$ = $1 + $3; }
| expr MINUS expr { $$ = $1 - $3; }
| expr TIMES expr { $$ = $1 * $3; }
| expr DIVIDE expr {
if($3 == 0) yyerror("除零错误");
$$ = $1 / $3;
}
| expr MOD expr { $$ = fmod($1, $3); }
| MINUS expr %prec UMINUS { $$ = -$2; }
| LPAREN expr RPAREN { $$ = $2; }
| SIN LPAREN expr RPAREN { $$ = sin($3); }
| COS LPAREN expr RPAREN { $$ = cos($3); }
| SQRT LPAREN expr RPAREN {
if($3 < 0) yyerror("负数不能开平方");
$$ = sqrt($3);
}
;
%%
int yyerror(char *s) {
fprintf(stderr, "错误: %s\n", s);
return 0;
}
int main() {
// 初始化内置变量
set_variable("pi", 3.141592653589793);
set_variable("e", 2.718281828459045);
yyparse();
return 0;
}
%union定义了所有可能的语义值类型%token和%type声明了标记和非终结符的类型%left,%right,%prec指定我们的计算器需要处理多种数据类型：
扩展前面的简单变量系统：
typedef enum { VAR, FUNC } SymbolType;
typedef struct {
char* name;
SymbolType type;
union {
double value; // 变量值
double (*func)(double); // 函数指针
};
} Symbol;
Symbol symtab[1000];
int symcount = 0;
void init_symbols() {
// 内置变量
add_symbol("pi", VAR)->value = 3.141592653589793;
add_symbol("e", VAR)->value = 2.718281828459045;
// 内置函数
add_symbol("sin", FUNC)->func = sin;
add_symbol("cos", FUNC)->func = cos;
add_symbol("sqrt", FUNC)->func = sqrt;
}
Symbol* add_symbol(char* name, SymbolType type) {
Symbol* sym = find_symbol(name);
if(sym != NULL) {
if(sym->type != type) yyerror("符号类型冲突");
return sym;
}
sym = &symtab[symcount++];
sym->name = strdup(name);
sym->type = type;
return sym;
}
Symbol* find_symbol(char* name) {
for(int i=0; i<symcount; i++) {
if(strcmp(symtab[i].name, name) == 0) {
return &symtab[i];
}
}
return NULL;
}
Bison提供了error特殊符号用于错误恢复：
input:
/* 空 */
| input line
| input error '\n' { yyerrok; } // 错误恢复
;
line:
'\n'
| expr '\n' { printf("= %g\n", $1); }
| error '\n' { yyerrok; } // 行内错误恢复
;
int yyerror(char *s) {
extern int yylineno;
fprintf(stderr, "行%d: 错误: %s\n", yylineno, s);
return 0;
}
void semantic_error(char* msg, char* detail) {
fprintf(stderr, "语义错误: %s: %s\n", msg, detail);
}
扩展语法：
expr:
// ...其他规则...
| expr '>' expr { $$ = $1 > $3 ? 1 : 0; }
| expr '<' expr { $$ = $1 < $3 ? 1 : 0; }
| expr EQ expr { $$ = fabs($1 - $3) < 1e-9 ? 1 : 0; }
| IF expr THEN expr ELSE expr { $$ = $2 ? $4 : $6; }
;
// 语法规则
func_def:
DEF IDENTIFIER LPAREN params RPAREN '=' expr
;
params:
/* 空 */
| IDENTIFIER
| params ',' IDENTIFIER
;
// 语义动作需要实现函数存储和调用
int main() {
init_symbols();
printf("Calculator v1.0 - 输入表达式或输入q退出\n");
while(1) {
printf("> ");
yyparse();
}
return 0;
}
CC = gcc
CFLAGS = -g -Wall
FLEX = flex
BISON = bison
TARGET = calculator
OBJS = lex.yy.o parser.tab.o main.o
all: $(TARGET)
$(TARGET): $(OBJS)
$(CC) $(CFLAGS) -o $@ $^ -lm
lex.yy.c: lexer.l parser.tab.h
$(FLEX) $<
parser.tab.c parser.tab.h: parser.y
$(BISON) -d $<
%.o: %.c
$(CC) $(CFLAGS) -c -o $@ $<
clean:
rm -f $(TARGET) *.o lex.yy.c parser.tab.*
# 简单算术
1 + 2 * 3
(1 + 2) * 3
# 变量测试
x = 10
y = x * 2 + 5
# 函数测试
sin(pi/2)
sqrt(16)
# 错误测试
1 +
a + b
1 / 0
sqrt(-1)
将线性搜索改为哈希表：
#define TABLE_SIZE 1024
typedef struct SymbolNode {
Symbol sym;
struct SymbolNode *next;
} SymbolNode;
SymbolNode *symtab[TABLE_SIZE];
unsigned hash(char *s) {
unsigned hashval;
for(hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;
return hashval % TABLE_SIZE;
}
Symbol* find_symbol(char* name) {
SymbolNode *np = symtab[hash(name)];
for(; np != NULL; np = np->next)
if(strcmp(np->sym.name, name) == 0)
return &np->sym;
return NULL;
}
避免内存泄漏：
void free_symbols() {
for(int i=0; i<TABLE_SIZE; i++) {
SymbolNode *np = symtab[i];
while(np != NULL) {
SymbolNode *tmp = np;
np = np->next;
free(tmp->sym.name);
free(tmp);
}
}
}
对于复杂表达式，可以先构建抽象语法树(AST)再计算：
typedef struct ASTNode {
int nodetype;
union {
double num;
char *id;
struct { struct ASTNode *left, *right; } child;
};
} ASTNode;
ASTNode* new_num(double d) {
ASTNode *a = malloc(sizeof(ASTNode));
a->nodetype = 'K';
a->num = d;
return a;
}
ASTNode* new_op(int nodetype, ASTNode *l, ASTNode *r) {
ASTNode *a = malloc(sizeof(ASTNode));
a->nodetype = nodetype;
a->child.left = l;
a->child.right = r;
return a;
}
double eval(ASTNode *a) {
switch(a->nodetype) {
case 'K': return a->num;
case '+': return eval(a->child.left) + eval(a->child.right);
case '*': return eval(a->child.left) * eval(a->child.right);
// ...其他操作...
default: yyerror("未知节点类型"); return 0;
}
}
通过本文，我们完整实现了一个基于Flex和Bison的计算器：
Flex和Bison是强大的语言处理工具，掌握它们可以轻松实现各种DSL和编程语言。希望本文能为你打下坚实基础，助你开发更复杂的语言处理器。
项目代码已托管在GitHub：calculator-project
Q: 如何处理运算符优先级？
A: Bison通过%left,%right和%nonassoc声明优先级，先声明的优先级低。
Q: 为什么我的变量查找很慢？
A: 使用哈希表代替线性搜索可以显著提高性能。
Q: 如何添加新的数据类型？
A: 扩展%union定义，添加新的token类型和语义动作。
Q: 如何调试语法分析？
A: 使用-t选项生成调试代码，或添加YYDEBUG=1和yydebug=1。
本文共7150字，完整实现了Flex与Bison计算器的开发过程。 “`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。