Bison中规则无法归约问题：NOT与括号规则为何未被归约？

问题描述 #

开发一套Flex词法分析器与Bison语法分析器，用于校验逻辑公式有效性：公式包含小写标识符、TRUE/FALSE常量、AND/OR逻辑运算符、括号、需忽略的空格、比较运算符，且必须以句号加换行结尾，无需语义解析或判断真假。

Flex部分已完成标识符与TRUE/FALSE映射为ZDANIE_POJEDYNCZE token，AND/OR与比较运算符映射为OPERATOR token，运行正常。

Bison期望实现：

• 带NOT、括号的语句归约为ZDANIE_POJEDYNCZE类型
• 两个该类型搭配运算符的语句也归约为ZDANIE_POJEDYNCZE
• 最终校验是否以句号结尾

但运行Bison时出现yacc: 2 rules never reduced错误，verbose输出显示问题出在处理NOT和括号的规则上。

附代码 #

Flex代码 #

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "TJF.tab.h"
%}

identyfikator      [a-z]+
stala_logiczna     "TRUE"|"FALSE"
operator_relacyjny "<"|"<="|"=="|">="|">"|"<>";
i_lub              "AND"|"OR"
nie                "NOT"
nawias_otw         "("
nawias_zam         ")"
zakoncz            "."
spacja             [ \t]+
nowa_linia         "\n"|"\r"
nieprawidlowy_znak .


%%
{identyfikator}      {return ZDANIE_POJEDYNCZE;}
{stala_logiczna}     {return ZDANIE_POJEDYNCZE;}
{operator_relacyjny} {return OPERATOR;}
{i_lub}              {return OPERATOR;}
{nie}                {return NIE;}
{nawias_otw}         {return NAWIAS_OTW;}
{nawias_zam}         {return NAWIAS_ZAM;}
{zakoncz}            {return ZAKONCZ;}
{spacja}             {}
{nowa_linia}         {return NOWA_LINIA;}
{nieprawidlowy_znak} {return NIEPRAWIDLOWY_ZNAK;}
%%

Bison代码 #

%{
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
void yyerror(const char* s);
int yylex(void);
char czy_poprawny = 1;
%}

%token ZDANIE_POJEDYNCZE OPERATOR NIE NAWIAS_OTW NAWIAS_ZAM ZAKONCZ NOWA_LINIA NIEPRAWIDLOWY_ZNAK

%%
kropka:
      ZDANIE_POJEDYNCZE ZAKONCZ NOWA_LINIA
    | error {czy_poprawny = 0;}
    | NIEPRAWIDLOWY_ZNAK {czy_poprawny = 0;}
    ;

zdanie_podwojne:
    ZDANIE_POJEDYNCZE OPERATOR ZDANIE_POJEDYNCZE {$$ = ZDANIE_POJEDYNCZE;}
    ;

zdanie_pojedyncze:
      NIE ZDANIE_POJEDYNCZE                   {$$ = ZDANIE_POJEDYNCZE;}
    | NAWIAS_ZAM zdanie_pojedyncze NAWIAS_ZAM {$$ = ZDANIE_POJEDYNCZE;}
    ;

%%

int main(){
    yyparse();
    if (czy_poprawny == 1){
        printf("OK!\n");
    }
    else{
        printf("ERROR!\n");
    }
    czy_poprawny = 1;
}

void yyerror(const char* s) {}

Bison Verbose输出 #

0  $accept : kropka $end

   1  kropka : zdanie_podwojne ZAKONCZ NOWA_LINIA
   2         | error
   3         | NIEPRAWIDLOWY_ZNAK

   4  zdanie_podwojne : ZDANIE_POJEDYNCZE OPERATOR ZDANIE_POJEDYNCZE

   5  zdanie_pojedyncze : NIE ZDANIE_POJEDYNCZE
   6                    | NAWIAS_ZAM zdanie_pojedyncze NAWIAS_ZAM

state 0
    $accept : . kropka $end  (0)

    error  shift 1
    ZDANIE_POJEDYNCZE  shift 2
    NIEPRAWIDLOWY_ZNAK  shift 3
    .  error

    kropka  goto 4
    zdanie_podwojne  goto 5


state 1
    kropka : error .  (2)

    .  reduce 2


state 2
    zdanie_podwojne : ZDANIE_POJEDYNCZE . OPERATOR ZDANIE_POJEDYNCZE  (4)

    OPERATOR  shift 6
    .  error


state 3
    kropka : NIEPRAWIDLOWY_ZNAK .  (3)

    .  reduce 3


state 4
    $accept : kropka . $end  (0)

    $end  accept


state 5
    kropka : zdanie_podwojne . ZAKONCZ NOWA_LINIA  (1)

    ZAKONCZ  shift 7
    .  error


state 6
    zdanie_podwojne : ZDANIE_POJEDYNCZE OPERATOR . ZDANIE_POJEDYNCZE  (4)

    ZDANIE_POJEDYNCZE  shift 8
    .  error


state 7
    kropka : zdanie_podwojne ZAKONCZ . NOWA_LINIA  (1)

    NOWA_LINIA  shift 9
    .  error


state 8
    zdanie_podwojne : ZDANIE_POJEDYNCZE OPERATOR ZDANIE_POJEDYNCZE .  (4)

    .  reduce 4


state 9
    kropka : zdanie_podwojne ZAKONCZ NOWA_LINIA .  (1)

    .  reduce 1


Rules never reduced:
    zdanie_pojedyncze : NIE ZDANIE_POJEDYNCZE  (5)
    zdanie_pojedyncze : NAWIAS_ZAM zdanie_pojedyncze NAWIAS_ZAM  (6)


10 terminals, 4 nonterminals
7 grammar rules, 10 states

问题根源 #

1. 非终结符未被引用：zdanie_pojedyncze作为定义NOT和括号规则的非终结符，从未被其他规则（如kropka或zdanie_podwojne）调用，Bison的语法分析路径根本不会走到这两个规则，所以永远不会被归约。
2. 括号规则逻辑错误：括号规则中写反了左右括号，用NAWIAS_ZAM（右括号）作为起始符号，而实际输入的括号是左括号开头，导致该规则完全无法匹配任何合法输入。
3. 语法层级设计错误：期望将复合语句归约为ZDANIE_POJEDYNCZE，但ZDANIE_POJEDYNCZE是Flex输出的token，而非Bison的非终结符，无法通过规则将其他结构转换为该token类型，语法结构不闭合。

修复方案 #

调整Bison语法结构，让所有合法表达式路径都能被覆盖，修正规则错误：

修改后的Bison代码 #

%{
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
void yyerror(const char* s);
int yylex(void);
char czy_poprawny = 1;
%}

%token ZDANIE_POJEDYNCZE OPERATOR NIE NAWIAS_OTW NAWIAS_ZAM ZAKONCZ NOWA_LINIA NIEPRAWIDLOWY_ZNAK

%%
// 起始规则：合法公式必须是表达式+句号+换行
program: wyrazenie ZAKONCZ NOWA_LINIA { /* 匹配成功 */ }
       | error { czy_poprawny = 0; }
       | NIEPRAWIDLOWY_ZNAK { czy_poprawny = 0; }
       ;

// 递归定义所有合法表达式：覆盖原子、NOT、括号、二元运算
wyrazenie: wyrazenie OPERATOR wyrazenie  // 二元运算（AND/OR/比较）
         | NIE wyrazenie                 // NOT修饰的表达式
         | NAWIAS_OTW wyrazenie NAWIAS_ZAM  // 括号包裹的表达式
         | ZDANIE_POJEDYNCZE             // 原子表达式（标识符/TRUE/FALSE）
         ;

%%

int main(){
    yyparse();
    printf(czy_poprawny ? "OK!\n" : "ERROR!\n");
    return 0;
}

void yyerror(const char* s) { czy_poprawny = 0; }

修改说明 #

1. 新增起始规则program：引用wyrazenie非终结符，覆盖所有合法表达式路径，确保NOT、括号等规则能被触发。
2. 递归定义wyrazenie：包含所有合法表达式形式，让复合结构可以被归约，同时支持嵌套（如NOT (a AND b)）。
3. 修正括号规则：将NAWIAS_ZAM改为NAWIAS_OTW，匹配实际输入的左括号开头格式。
4. 简化逻辑：去掉冗余的zdanie_podwojne规则，统一用wyrazenie处理所有表达式类型，语法结构更清晰闭合。

内容的提问来源于stack exchange，提问作者Firana M