为什么这个非常简单的语法会导致 GLR 解析器卡住？

Question

我尝试了几种不同的解析器生成器（Bison、DParser 等），它们声称能够生成 GLR 解析器，即可以处理不明确的语法的解析器。这是我正在讨论的类型的一个非常简单的二义性语法：

START: A | B;
A: C | D;
B: C | D;
C: T1 | T2;
D: T3 | T4;
T1: 't1';
T2: 't2';
T3: 't3';
T4: 't4';

我可以很好地生成解析器，但是当我提供应该有效的解析器输入时，我会遇到“未解决的歧义”错误或直接崩溃。当我将语法更改为明确的版本时，不会出现任何类型的问题。

我对 GLR 解析器有什么不理解的地方？我认为重点是，在歧义的情况下，所有可能的解析都会被跟踪，直到它们合并或到达死胡同。我所需要的只是一个解析器，它可以告诉我输入是否有任何有效的解析。

谢谢你的帮助。

编辑：

这令人沮丧。使用 %dprec 和 %merge 我已经能够让 Bison 处理不明确的规则和终端，但它仍然对我需要处理的那种非常简单但高度病态的伪英语语法感到窒息：

S: NP VP | NPA VP;
NPA: D N | NP PP;
NP: D N | NP PP | NPA;
VP: V NP | VP PP;
PP: P NP;
D: "the" | "a";
P: "in" | "with";
V: "saw";
N: "saw" | "girl" | "boy" | "park" | "telescope";

对于输入“a boy saw a girls”，Bison 无法解析并返回代码 1。 另一方面，Tom 完美地处理了这个语法和这个输入句子，甚至通过将未知终端分配给所有可能的终端来自然地处理它们终端类型。但与 Bison 不同的是，Tom 对大量语法感到噎住。（我所说的“阻塞”是指以各种不同方式发生故障。如果故障模式有帮助，我可以报告这些故障模式。）

有人还有其他想法吗？

Answer 1

不幸的是，bison 确实坚持生成（单个）解析，因此您必须指定某种方法来合并不明确的解析。如果你不这样做，并且有不止一种可能的解析，bison 的 GLR 解析器确实会抱怨解析不明确。

如果您并不真正关心接受多个解析中的哪一个，那么让 bison 屈服于您的意愿并不是太困难。%dprec最简单的方法是为每个可能不明确的产品分配一个不同的值。然后，Bison 将选择恰好具有最佳优先级的适用产品。

您甚至可以让 bison 通过一个简单的函数告诉您有关多个解析的信息%merge；bison手册中有一个例子。（此功能的文档不是很好，但可能足以满足您的需求。如果不能，请随时提出更具体的问题。）

我对 DParser 没有太多经验，但手册表明它在面对多个可能的解析时的行为是相似的：默认是抱怨，但你可以提供自己的简单合并功能：（引用来自第12、歧义）

根据优先级和关联性自动解决歧义。此外，当其他解析技术失败时，可以使用用户定义的模糊度解析。默认的歧义处理程序会在未解决的歧义上产生致命错误。此行为可以替换为用户定义的解析器，其签名在 中提供dparse.h。

下面是第二个示例的野牛 GLR 语法示例。我遗漏了词法分析器，这确实不相关（而且有点尴尬，因为我很着急）。

%{
  int yylex();
  void yyerror(const char* msg);
%}

%error-verbose
%glr-parser

%token WORD_A "a"
%token WORD_BOY "boy"
%token WORD_GIRL "girl"
%token WORD_IN "in"
%token WORD_LIKED "liked"
%token WORD_PARK "park"
%token WORD_SAW "saw"
%token WORD_TELESCOPE "telescope"
%token WORD_THE "the"
%token WORD_WITH "with"

%%
S  : NP VP      {puts("S: NP VP");}     %dprec 1
   | NPA VP     {puts("S: NPA VP");}    %dprec 2
   ;
NPA: D N        {puts("NPA: D N");}     %dprec 3
   | NP PP      {puts("NPA: NP PP");}   %dprec 4
   ;
NP : D N        {puts("NP: D N");}      %dprec 6
   | NP PP      {puts("NP: NP PP");}    %dprec 7
   | NPA        {puts("NP: NPA");}      %dprec 10
   ;
VP : V NP       {puts("VP: V NP ");}    %dprec 11
   | VP PP      {puts("VP: VP PP");}    %dprec 12
   ;
PP : P NP       {puts("PP: P NP");}     %dprec 14
   ;
D  : "the"      {puts("D: the");}       %dprec 15
   | "a"        {puts("D: a");}         %dprec 16
   ;
P  : "in"       {puts("P: in");}        %dprec 17
   | "with"     {puts("P: with");}      %dprec 18
   ;
V  : "liked"    {puts("V: liked");}     %dprec 19
   | "saw"      {puts("V: saw");}       %dprec 20
   ;
N  : "girl"     {puts("N: girl");}      %dprec 21
   | "boy"      {puts("N: boy");}       %dprec 22
   | "park"     {puts("N: park");}      %dprec 23
   | "saw"      {puts("N: saw");}       %dprec 24
   | "telescope"{puts("N: telescope");} %dprec 25
   ;
%%

int main(int argc, char** argv) {
  printf("yyparse returned %d\n", yyparse());
  return 0;
}

汇编：

$ make ambig2
bison30 -v -d -o ambig2.c ambig2.y 
ambig2.y: warning: 6 shift/reduce conflicts [-Wconflicts-sr]
ambig2.y: warning: 10 reduce/reduce conflicts [-Wconflicts-rr]
gcc-4.8 -ggdb -Wall -D_POSIX_C_SOURCE=200809L -std=c99 -c -o ambig2.o ambig2.c
gcc-4.8   ambig2.o   -o ambig2
rm ambig2.o ambig2.c

示例解析：

$ ./ambig2 <<<"a boy saw a girl"
D: a
N: boy
NPA: D N
V: saw
D: a
N: girl
NPA: D N
NP: NPA
VP: V NP 
S: NPA VP
yyparse returned 0

$ ./ambig2 <<<"a saw saw the saw in a saw"
D: a
N: saw
NPA: D N
V: saw
D: the
N: saw
NPA: D N
NP: NPA
VP: V NP 
P: in
D: a
N: saw
NPA: D N
NP: NPA
PP: P NP
VP: VP PP
S: NPA VP
yyparse returned 0