parsing - 为什么这个非常简单的语法会导致 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';

我可以很好地生成解析器，但是当我提供应该有效的解析器输入时，我会收到“ Unresolved 歧义”错误或完全崩溃。当我将语法更改为明确的版本时，没有任何问题。

我对 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";

输入“一个男孩看到一个女孩”，Bison 无法解析并返回代码 1。另一方面，Tom 完美地处理了这个语法和这个输入句子，甚至通过将它们分配给所有可能的来自然地处理未知终端终端类型。但与 Bison 不同的是，Tom 会因大量语法而窒息。 (“窒息”是指以各种不同的方式失败。如果失败模式有帮助，我可以报告这些。)

有人有其他想法吗？

Answer 1

不幸的是，bison 确实坚持生成(单个)解析，因此您必须指定某种方式来合并不明确的解析。如果不这样做，并且可能的解析不止一种，bison 的 GLR 解析器确实会提示解析不明确。

如果您真的不在乎接受多个解析中的哪一个，那么将野牛屈从于您的意愿并不太难。最简单的方法是只分配一个不同的 %dprec到每一个可能模棱两可的生产。然后 Bison 将选择任何适用的生产恰好具有最佳优先级。

你甚至可以让野牛通过一个简单的 %merge 告诉你关于多重解析的信息。功能; bison manual中有一个例子. (此功能的文档不是很好，但它可能足以满足您的需求。如果没有，请随时提出更具体的问题。)

我对 DParser 没有太多经验，但是 manual表示它在面对多个可能的解析时的行为是相似的:默认是提示，但您可以提供自己的微不足道的合并功能:(引用来自第 12 节，歧义)

Ambiguities are resolved automatically based on priorities and associativities. In addition, when the other resolution techniques fail, user defined ambiguity resolution is possible. The default ambiguity handler produces a fatal error on an unresolved ambiguity. This behavior can be replaced with a user defined resolvers the signature of which is provided in 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