如何编写LEX与Bison程序实现带变量定义的算术表达式识别

设计说明 #

我们要实现的程序需支持以下功能：

• 加减乘除运算（*、/优先级高于+、-）
• 括号()改变运算优先级
• 变量定义（如m=5）与后续引用
• 每行一个表达式或赋值语句

1. LEX词法分析器（lex.l） #

负责识别输入中的词法单元：标识符、数字、运算符、赋值符号、括号、换行等。

%{
#include "bison.tab.h"
#include <string.h>
%}

%%
[0-9]+          { yylval.num = atoi(yytext); return NUMBER; }
[a-zA-Z_][a-zA-Z0-9_]* { strcpy(yylval.id, yytext); return IDENTIFIER; }
"+"             { return PLUS; }
"-"             { return MINUS; }
"*"             { return MUL; }
"/"             { return DIV; }
"="             { return ASSIGN; }
"("             { return LPAREN; }
")"             { return RPAREN; }
"\n"            { return NEWLINE; }
[ \t]           ; /* 忽略空白字符 */
.               { printf("非法字符: %s\n", yytext); }
%%

int yywrap() {
    return 1;
}

2. Bison语法分析器（bison.y） #

定义语法规则、运算符优先级，实现变量存储与表达式求值逻辑，用数组维护变量及其值。

%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VARS 100

typedef struct {
    char name[32];
    int value;
} Variable;

Variable vars[MAX_VARS];
int var_count = 0;

int find_var(const char *name) {
    for (int i = 0; i < var_count; i++) {
        if (strcmp(vars[i].name, name) == 0) {
            return i;
        }
    }
    return -1;
}

void add_var(const char *name, int value) {
    int idx = find_var(name);
    if (idx != -1) {
        vars[idx].value = value;
        return;
    }
    if (var_count >= MAX_VARS) {
        printf("变量数量超出上限\n");
        exit(1);
    }
    strcpy(vars[var_count].name, name);
    vars[var_count].value = value;
    var_count++;
}

int get_var(const char *name) {
    int idx = find_var(name);
    if (idx == -1) {
        printf("未定义的变量: %s\n", name);
        exit(1);
    }
    return vars[idx].value;
}

void yyerror(const char *s) {
    printf("语法错误: %s\n", s);
}

int yylex();
%}

%union {
    int num;
    char id[32];
}

%token <num> NUMBER
%token <id> IDENTIFIER
%token ASSIGN PLUS MINUS MUL DIV LPAREN RPAREN NEWLINE

%left PLUS MINUS
%left MUL DIV
%right ASSIGN

%type <num> expr

%%

program:
    | program statement NEWLINE
    ;

statement:
    expr                { printf("结果: %d\n", $1); }
    | IDENTIFIER ASSIGN expr { add_var($1, $3); printf("%s = %d\n", $1, $3); }
    ;

expr:
    NUMBER              { $$ = $1; }
    | IDENTIFIER        { $$ = get_var($1); }
    | expr PLUS expr    { $$ = $1 + $3; }
    | expr MINUS expr   { $$ = $1 - $3; }
    | expr MUL expr     { $$ = $1 * $3; }
    | expr DIV expr     { 
        if ($3 == 0) {
            yyerror("除数不能为0");
            exit(1);
        }
        $$ = $1 / $3; 
    }
    | LPAREN expr RPAREN { $$ = $2; }
    ;

%%

int main() {
    printf("输入算术表达式或变量赋值，每行一个，Ctrl+C退出\n");
    yyparse();
    return 0;
}

3. 编译与运行步骤 #

1. 保存上述LEX代码为lex.l，Bison代码为bison.y
2. 执行以下命令编译：

   flex lex.l
   bison -d bison.y
   gcc lex.yy.c bison.tab.c -o calc
   

3. 运行程序：

   ./calc
   

4. 测试示例 #

输入：

m=5
y=9+5
z=(m+y)*2
z/4

输出：

m = 5
y = 14
z = 38
结果: 9

内容的提问来源于stack exchange，提问作者Heba Moufti