3. 语法分析器bison实战
任务目标
使用 flex 生成词法分析器、bison 生成语法分析器，实现一个支持 + - * / 和括号的计算器。程序读取表达式后构建 AST，并递归求值输出结果。
环境依赖
- GCC、GNU Make
- flex（词法分析器生成器）
- bison（语法分析器生成器）
Ubuntu/Debian 安装：sudo apt install flex bison gcc make
实现文件
共 4 个文件：calc.l（词法规则）、calc.y（语法规则与 AST 构建）、ast.h（AST 节点定义）、Makefile（构建脚本）。
ast.h
```c
#ifndef AST_H
#define AST_H
typedef struct ASTNode {
char op; // 运算符: '+', '-', '*', '/', 数字节点用 '\0'
double value; // 当 op == '\0' 时有效
struct ASTNode *left;
struct ASTNode *right;
} ASTNode;
ASTNode *new_num_node(double v);
ASTNode *new_op_node(char op, ASTNode *l, ASTNode *r);
void free_ast(ASTNode *node);
double eval(ASTNode *node);
#endif
```
calc.y
```c
%{
#include
#include
#include "ast.h"
int yylex(void);
void yyerror(const char *s);
ASTNode *root = NULL;
%}
%union {
double num;
ASTNode *node;
}
% NUMBER
%type expr term factor
%%
input:
expr { root = $1; }
;
expr:
expr '+' term { $$ = new_op_node('+', $1, $3); }
| expr '-' term { $$ = new_op_node('-', $1, $3); }
| term { $$ = $1; }
;
term:
term '*' factor { $$ = new_op_node('*', $1, $3); }
| term '/' factor { $$ = new_op_node('/', $1, $3); }
| factor { $$ = $1; }
;
factor:
'(' expr ')' { $$ = $2; }
| NUMBER { $$ = new_num_node($1); }
;
%%
void yyerror(const char *s) {
fprintf(stderr, "语法错误: %s\n", s);
}
int main(void) {
if (yyparse() == 0 && root) {
printf("结果: %.6g\n", eval(root));
free_ast(root);
}
return 0;
}
```
calc.l
```c
%{
#include "calc.tab.h"
#include
%}
%%
[0-9]+(\.[0-9]+)? { yylval.num = atof(yytext); return NUMBER; }
[ \t\n] { /* 跳过空白 */ }
"+" { return '+'; }
"-" { return '-'; }
"*" { return '*'; }
"/" { return '/'; }
"(" { return '('; }
")" { return ')'; }
. { yyerror("非法字符"); }
%%
int yywrap(void) { return 1; }
```
ast.c（AST 实现）
```c
#include "ast.h"
#include
#include
ASTNode *new_num_node(double v) {
ASTNode *n = malloc(sizeof(ASTNode));
n->op = '\0';
n->value = v;
n->left = n->right = NULL;
return n;
}
ASTNode *new_op_node(char op, ASTNode *l, ASTNode *r) {
ASTNode *n = malloc(sizeof(ASTNode));
n->op = op;
n->left = l;
n->right = r;
return n;
}
void free_ast(ASTNode *node) {
if (!node) return;
free_ast(node->left);
free_ast(node->right);
free(node);
}
double eval(ASTNode *node) {
if (!node) return 0;
if (node->op == '\0') return node->value;
double l = eval(node->left);
double r = eval(node->right);
switch (node->op) {
case '+': return l + r;
case '-': return l - r;
case '*': return l * r;
case '/': return l / r;
default: return 0;
}
}
```
Makefile
```makefile
calc: calc.tab.c lex.yy.c ast.c
gcc -o calc calc.tab.c lex.yy.c ast.c -lm
calc.tab.c: calc.y
bison -d calc.y
lex.yy.c: calc.l
flex calc.l
clean:
rm -f calc calc.tab.c calc.tab.h lex.yy.c
run: calc
./calc
```
构建与运行
- 将上述 5 个文件（
ast.h、ast.c、calc.y、calc.l、Makefile）放入同一目录。
- 执行
make 编译生成可执行文件 calc。
- 运行
./calc，输入表达式后按 Ctrl+D（EOF）结束输入。
验证方法
输入以下表达式并检查输出：
3+5*2 → 预期输出 结果: 13（验证优先级）(3+5)*2 → 预期输出 结果: 16（验证括号）10/4 → 预期输出 结果: 2.5（验证除法）2*3+4*5 → 预期输出 结果: 26（验证结合性）
若输出与预期一致，说明词法、语法分析、AST 构建与求值均正确。输入非法字符（如 3@4）时应输出错误提示而非崩溃。
关键说明
- 语法规则中
expr 与 term 的递归定义天然实现了运算符优先级：*、/ 优先于 +、-；左递归保证左结合。
- AST 节点在
yyparse 过程中随归约动作创建，最终根节点存入全局变量 root，在 main 中求值并释放内存。
- 除零操作会产生
inf 或 nan，本案例未做特殊处理，属于可接受的简化范围。
