# 如何使用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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
