基于Flex/Bison的Lisp解释器求和表达式识别范围受限问题咨询

看起来你的问题出在Bison语法规则对求和表达式的参数限制太严格了——当前的规则只允许直接的整数或者有限个表达式混合整数，没有递归地支持任意合法表达式作为求和的参数。咱们来一步步修复这个问题：

首先，核心思路是：

• 定义一个通用的exp（表达式）规则，涵盖所有你的解释器能识别的合法表达式（比如整数、其他函数调用、变量引用等等）。
• 让求和表达式的参数列表递归地接受零个或多个exp，这样不管是整数、嵌套的求和、还是其他运算表达式，都能被正确识别并求值。

第一步：调整Bison语法规则 #

这里给出一个简化的示例，你可以根据自己的现有代码修改：

%{
#include <stdio.h>
#include <stdlib.h>
// 假设我们用int作为值类型，如果你的解释器支持更复杂类型，这里换成自定义结构体即可
typedef int Value;

// 简化的表达式求值函数，实际中你需要根据exp的类型做对应处理
Value evaluate_expression(Value val) {
    return val;
}
%}

%union {
    int num;
    Value val;
}

// 定义token：左括号、右括号、加号、整数
%token <num> INT
%token OP CP PLUS

// 定义非终结符的类型
%type <val> exp sum_expression expression_list

%%

// 程序入口：解析一个表达式并输出结果
program: exp { printf("Evaluation result: %d\n", $1); }
       ;

// 通用表达式规则：可以是整数，也可以是求和表达式（后续可扩展其他表达式）
exp: INT { $$ = $1; }
   | sum_expression { $$ = $1; }
   // 这里添加其他表达式类型，比如变量、乘法/减法表达式等
   ;

// 求和表达式：(+ 表达式列表)
sum_expression: OP PLUS expression_list CP { $$ = $3; }
              ;

// 表达式列表：递归接受任意数量的表达式，累加它们的值
expression_list: /* 空列表，返回0 */ { $$ = 0; }
               | expression_list exp { $$ = $1 + evaluate_expression($2); }
               ;

%%

// 错误处理函数
int yyerror(const char* msg) {
    fprintf(stderr, "Syntax error: %s\n", msg);
    return 1;
}

int main() {
    return yyparse();
}

第二步：配套的Flex规则 #

确保你的Flex代码能正确识别对应的token：

%{
#include "y.tab.h"  // 引入Bison生成的头文件
%}

%%
"+"         { return PLUS; }
"("         { return OP; }
")"         { return CP; }
[0-9]+      { yylval.num = atoi(yytext); return INT; }
[ \t\n]     { /* 忽略空白字符 */ }
.           { yyerror("Unknown character encountered"); }
%%

int yywrap() {
    return 1;  // 表示没有更多输入
}

关键修改说明 #

1. 通用exp规则：这是核心，它让所有合法的表达式都能作为求和的参数——不管是简单整数，还是嵌套的(+ ...)，甚至是你后续添加的其他运算（比如乘法、变量）。
2. 递归的expression_list：这个规则允许求和表达式接受任意数量的参数，从0个（返回0）到N个，每次递归都累加当前表达式的值。
3. 语义动作的累加逻辑：在expression_list的规则里，我们把每个表达式的值累加起来，最终作为求和表达式的结果。

额外注意事项 #

• 如果你的解释器支持非数值类型（比如字符串、列表），一定要在语义动作里添加类型检查，比如判断每个exp的值是否是数值类型，否则抛出错误（比如Error: Cannot sum non-numeric value）。
• 测试时可以试试嵌套场景，比如(+ 5 (+ 3 4) (- 10 2))，应该返回5+7+8=20，验证递归识别是否正常。
• 如果需要支持最少一个参数（不允许空的(+)），可以修改expression_list规则，去掉空列表的情况，改成必须至少一个exp，然后处理参数数量为0的错误。

内容的提问来源于stack exchange，提问作者Asad-ullah Khan