Lex/Yacc计算器无法处理末尾多余右括号的异常场景

问题描述 #

我开发了一款支持基本算术运算及括号使用的Lex+Yacc计算器，多数场景可正常处理：有效输入返回整数结果，无效输入提示错误。但测试发现，输入如5)、99+22+33)或7)asdfghjk这类以多余右括号结尾的内容时，会被判定为有效并输出正确数值；而输入(5则会正常报错。

原Lex文件 #

/* ========== DECLARATIONS SECTION ========== */
%{
    #include <stdio.h>
    #include <stdlib.h>
    #include "y.tab.h"
    extern int yylval;
%}
/* ========================================== */

/* ========== SHORTHAND DEFINITIONS ========= */
/* ========================================== */

/* ================== RULES ================= */
%%
([1-9][0-9]*|0) { 
    yylval = atoi(yytext);
    return INT;
}

[+] {return PLUS;}
[-] {return MINUS;}
[*] {return MULT;}
[/] {return DIV;}
[(] {return LPAREN;}
[)] {return RPAREN;}
[ \t] {;}
[\n] {return 0;}
. {yyerror();}
%%
/* ========================================== */

/* ================ USER CODE =============== */
int yywrap() {
    return 1;
}
/* ========================================== */

原Yacc文件 #

/* ========== DECLARATIONS SECTION ========== */
%{
    #include <stdio.h>
    #include <stdlib.h>
%}

%token INT

%left PLUS MINUS
%left MULT DIV
%left UMINUS
%left LPAREN RPAREN
/* ========================================== */

/* ============ GRAMMAR SECTION ============= */
%%
ResultantExpression: E{
    printf("Result = %d\n", $$);

    return 0;
};


E: E PLUS T {$$ = $1 + $3;}
 | E MINUS T {$$ = $1 - $3;}
 | MINUS E %prec UMINUS {$$ = -$2;}
 | T {$$ = $1;}
 ;

T: T MULT F {$$ = $1 * $3;}
 | T DIV F {if ($3 == 0) {yyerror();} else {$$ = $1 / $3;}}
 | F {$$ = $1;}
 ;

F: INT {$$ = $1;}
 | LPAREN E RPAREN {$$ = ($2);}
 ; 
%%
/* ========================================== */

/* ============ USER CODE SECTION =========== */
int main() {
    printf("Enter the expression:\n");
    yyparse();

    return 0;
}

void yyerror() {
    printf("The entered expression is invalid!\n");
    exit(1);
}

/* ========================================== */

问题原因 #

当前Yacc的ResultantExpression规则在匹配到合法表达式E后直接返回0终止解析，不会检查后续是否存在多余的token（比如冗余的右括号）。而输入(5时，解析到LPAREN E后无法匹配RPAREN，触发语法错误，因此能正常报错。

解决方案 #

1. 修改Yacc语法规则 #

要求整个输入必须是完整表达式，且后续无多余token，需添加规则确保解析到文件结束（EOF）：

/* ============ GRAMMAR SECTION ============= */
%%
ResultantExpression: E EOF {
    printf("Result = %d\n", $1);
    return 0;
};

// 其余规则保持不变
E: E PLUS T {$$ = $1 + $3;}
 | E MINUS T {$$ = $1 - $3;}
 | MINUS E %prec UMINUS {$$ = -$2;}
 | T {$$ = $1;}
 ;

T: T MULT F {$$ = $1 * $3;}
 | T DIV F {if ($3 == 0) {yyerror();} else {$$ = $1 / $3;}}
 | F {$$ = $1;}
 ;

F: INT {$$ = $1;}
 | LPAREN E RPAREN {$$ = ($2);}
 ; 
%%

同时在Yacc的声明部分添加%token EOF：

%token INT EOF

2. 调整Lex的换行处理 #

原Lex中[\n] {return 0;}会导致换行时直接返回0（相当于EOF），但此时后续的多余字符不会被扫描。修改为：

[\n] {return EOF;}

保留原本的.规则，确保多余字符触发错误：

. {yyerror();}

修改后的完整文件 #

修改后的Lex文件

/* ========== DECLARATIONS SECTION ========== */
%{
    #include <stdio.h>
    #include <stdlib.h>
    #include "y.tab.h"
    extern int yylval;
%}
/* ========================================== */

/* ========== SHORTHAND DEFINITIONS ========= */
/* ========================================== */

/* ================== RULES ================= */
%%
([1-9][0-9]*|0) { 
    yylval = atoi(yytext);
    return INT;
}

[+] {return PLUS;}
[-] {return MINUS;}
[*] {return MULT;}
[/] {return DIV;}
[(] {return LPAREN;}
[)] {return RPAREN;}
[ \t] {;}
[\n] {return EOF;}
. {yyerror();}
%%
/* ========================================== */

/* ================ USER CODE =============== */
int yywrap() {
    return 1;
}
/* ========================================== */

修改后的Yacc文件

/* ========== DECLARATIONS SECTION ========== */
%{
    #include <stdio.h>
    #include <stdlib.h>
%}

%token INT EOF

%left PLUS MINUS
%left MULT DIV
%left UMINUS
%left LPAREN RPAREN
/* ========================================== */

/* ============ GRAMMAR SECTION ============= */
%%
ResultantExpression: E EOF {
    printf("Result = %d\n", $1);
    return 0;
};

E: E PLUS T {$$ = $1 + $3;}
 | E MINUS T {$$ = $1 - $3;}
 | MINUS E %prec UMINUS {$$ = -$2;}
 | T {$$ = $1;}
 ;

T: T MULT F {$$ = $1 * $3;}
 | T DIV F {if ($3 == 0) {yyerror();} else {$$ = $1 / $3;}}
 | F {$$ = $1;}
 ;

F: INT {$$ = $1;}
 | LPAREN E RPAREN {$$ = ($2);}
 ; 
%%
/* ========================================== */

/* ============ USER CODE SECTION =========== */
int main() {
    printf("Enter the expression:\n");
    yyparse();

    return 0;
}

void yyerror() {
    printf("The entered expression is invalid!\n");
    exit(1);
}

/* ========================================== */

验证效果 #

修改后，输入5)、99+22+33)或7)asdfghjk时，多余的右括号或字符会触发yyerror()，提示表达式无效；输入合法表达式则正常返回结果，输入(5仍会正常报错。

内容的提问来源于stack exchange，提问作者Stephen Landaas