解决 shift/reduce 语法中的 Yacc/Bison 冲突

Question

我正在 GNU-Bison 中编写解析器来解析捕获的专有协议数据位。解析器具有以下标记：

H ....... Header
D .......数据
T.......终结者

和五个数字D即数据令牌组成bulkB 即

B : DDDDD
  ;

理想情况下，输入的格式应为

H DDDDD DDDDD DDDDD ... DDDDD T

又名

 H B B B ... B T

所以我写了下面的语法：

%%
CAPTURE :  H PAYLOAD T     { printf("[OK]");}
        ;

PAYLOAD :  B
        |  PAYLOAD B
        ;

B       :  DDDDDD
%%

现在，要满足一些实际情况，比如下面这样的模式：

DD H DDDDD DDDDD ... DDDDD T（前缀额外的 D）
H DDDDD DDDDD ... DDD T（截断最后 bulk 只有 3 个数据 D）

我将语法修改为

%%
CAPTURE :  H PAYLOAD T     { printf("[OK]");}
        ;

PAYLOAD :  B
        |  PAYLOAD B
        |  D PAYLOAD
        |  PAYLOAD D
        ;

B       :  DDDDDD
%%

但它正在给予 shift/reduce conflict。
需要帮助如何更正语法，以便它也能识别上述两种情况并且 shift/reduce 没有冲突。

Answer 1

%%
CAPTURE : OPTD1 H PAYLOAD OPTD2 T     { printf("[OK]");}
        ;

PAYLOAD :  B
        |  PAYLOAD B
        ;

B       :  D D D D D
        ;

OPTD1   :
        |  OPTD1 D
        ;

OPTD2   :
        |  D D D
        ;
%%

我在第一个产生式的右侧添加了两个新的非终结符 OPTD1 和 OPTD2，并保留了 PAYLOAD 的原始规则。 OPTD1可以改写为0个或多个D个终结符，OPTD2可以改写为0个或3个D个终结符。

如果您的 TOKENS、H、T 和 B 分别只是字符 'H'、'T' 和 'B'，您可以使用以下正则表达式轻松识别有效输入：

'^D*H(DDDDD)+(DDD)?T$'

无论如何，您应该能够使用有限状态自动机识别有效输入，而无需 YACC 提供的下推自动机功能。

解决 shift/reduce 语法中的 Yacc/Bison 冲突

Resolve shift/reduce conflict in Yacc/Bison grammar

yacc

bison