通过第二次前瞻解决野牛冲突

Question

我正在为一个项目编写解析器，但遇到了一个问题。这是一个独立的问题示例：

%error-verbose

%token ID
%token VAR
%token END_VAR
%token CONSTANT
%token AT
%token VALUE
%%

unit: regular_var_decl
    | direct_var_decl;

regular_var_decl: VAR constant_opt ID ':' VALUE ';' END_VAR;

constant_opt: /* empty */ | CONSTANT;

direct_var_decl: VAR ID AT VALUE ':' VALUE ';' END_VAR;

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

yylex() {
  static int i = 0;

  static int tokens[] = {
    VAR,
      ID, ':', VALUE, ';',
    END_VAR,
    0
  };

  return tokens[i++];
};

yyerror(str) char *str; {
  printf("fail: %s\n", str);
};

main() {
  yyparse();
  return 0;
};

有人可以建造它 bison test.y && cc test.tab.c && ./a.out。

它警告我 constant_opt 由于冲突而无用。

这个歧义可以通过使用 LALR(2) 来解决，因为在 ID 之后它可以找到 ':' 或 AT...我如何在 bison 上解决这个问题？

Answer 1

一个简单的解决方案就是不缩写可选的 CONSTANT：

regular_var_decl:  VAR ID ':' VALUE ';' END_VAR;
constant_var_decl: VAR CONSTANT ID ':' VALUE ';' END_VAR;
direct_var_decl:   VAR ID AT VALUE ':' VALUE ';' END_VAR;

这样一来，就可以推迟减排决定，直到获得足够的信息为止。（如果有用的话，您可以将 ':' VALUE ';' END_VAR 分解为非终结符。）

另一种可能性是保持语法不变，并要求 bison 生成 GLR 解析器 (%glr-parser)。 GLR 解析器将有效地保留两个（或更多）并行解析，直到可以解决歧义，这肯定会解决 constant_opt 问题。（请注意，bison 仍会报告 shift/reduce 冲突；在运行时发现歧义句子之前，它无法判断该语言是否实际上是歧义的。）大多数时候，不需要对语法进行额外的更改, 但它确实会稍微减慢解析速度。

最后一种可能性，在这里可能不太有用，是接受语言的超集，然后在操作中发出错误消息：

var_decl: VAR const_opt ID at_value_opt ':' VALUE ';' END_VAR {
   if (/* pseudocode */  && ) { /* flag a syntax error */ }
}

这取决于两个 opt 终端返回一个语义值，可以以某种方式询问是否为空。

Answer 2

另一个解决方案是进一步分解它：

var_decl: VAR constant_opt ID direct_opt ':' VALUE ';' END_VAR;

constant_opt: /* empty */ | CONSTANT;

direct_opt: /* empty */ | AT VALUE;

然后在 var_decl 的操作中，您决定它是规则的、常量的还是直接的，或者如果它同时具有 CONSTANT 和 AT VALUE，则发出错误。这样做的好处是您可以为后一种情况提供自定义的、明确的错误消息，而不仅仅是一般的 "syntax error" 消息。

通过第二次前瞻解决野牛冲突

Solving bison conflict over 2nd lookahead

bison