4

我尝试了几种不同的解析器生成器(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 girl”,Bison 无法解析并返回代码 1。另一方面,Tom 完美地处理了这个语法和这个输入语句,甚至通过将未知终端分配给所有可能的终端来自然地处理它们终端类型。但与 Bison 不同的是,Tom 对大型语法感到窒息。(“扼流圈”是指以各种不同的方式失败。如果失败模式有帮助,我可以报告这些。)

有人有其他想法吗?

4

2 回答 2

4

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

如果您并不真正关心接受多个解析中的哪一个,那么让野牛屈服于您的意愿并不难最简单的方法是为%dprec每个可能模棱两可的产生式分配一个不同的值。然后,Bison 将选择恰好具有最佳优先级的任何适用产品。

你甚至可以让 bison 用一个简单的%merge函数告诉你多个解析;野牛手册中有一个例子。(此功能的文档不是很好,但可能足以满足您的需求。如果没有,请随时提出更具体的问题。)

我对 DParser 没有太多经验,但是手册表明它在面对多个可能的解析时的行为是相似的:默认是抱怨,但您可以提供自己的琐碎合并功能:(引用来自 Section 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
于 2014-02-20T03:55:29.217 回答
1

您的语法不会导致 GLR 解析器阻塞。

您需要一个 GLR 解析引擎来提供 GLR 解析器应该提供的功能:面对歧义进行解析,并将结果交给您。大概您使用其他上下文来解决歧义。(如果你真的坚持避免产生上下文防止的歧义,你可以将上下文检查纠缠到解析过程中。如果你这样做,你会遇到 GCC 人在尝试使用 LALR 解析 C 和 C++ 时遇到的那种复杂情况) .

这是 OP 问题的输出,提供给我们的 DMS Software Reengineering Toolkit 的 GLR 解析器生成器。我必须定义一个与 DMS 兼容的词法分析器和语法:

Lexer(将单个标记定义为单词;更具可扩展性的版本可能已定义单词类标记,例如 DPVN):

%%
%%main
#skip "\s+"
#skip "[\u000d\u000a]+"
#token 'the' "the"
#token 'a' "a"
#token 'in' "in"
#token 'with' "with"
#token 'saw' "saw"
#token 'girl' "girl"
#token 'boy' "boy"
#token 'park' "park"
#token 'telescope' "telescope"
%%

语法(DMS 不打扰 EBNF):

S = NP VP ;
S = NPA VP ;
NPA = D N ;
NPA = NP PP ;
NP = D N ;
NP = NP PP ;
NP = NPA ;
VP = V NP ;
VP = VP PP ;
PP = P NP ;
D = 'the' ;
D = 'a';
P = 'in' ;
P = 'with' ;
V = 'saw' ;
N = 'saw' ;
N = 'girl' ;
N = 'boy' ;
N = 'park' ;
N = 'telescope' ;

示例文件“aboysawagirl.txt”

a boy saw a girl\n

从头到尾,构建词法分析器和解析器(大约 10 分钟的摸索……)

解析示例文件并转储自动构建的树:

C:\DMS\Domains\simpenglish\Tools\Parser\Source>run ..\domainparser ++AST ..\..\Lexer\aboysawagirl.txt
simpenglish Domain Parser Version 2.5.15
Copyright (C) 1996-2013 Semantic Designs, Inc; All Rights Reserved; SD Confidential
Powered by DMS (R) Software Reengineering Toolkit
24 tree nodes in tree.
3 ambiguity nodes in tree.
(AMBIGUITY<S=11>@simpenglish=31@#1f35140^0{2} Line 1 Column 1 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
 (S@simpenglish=1@#1f350e0^1#1f35140:1 Line 1 Column 1 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
  (AMBIGUITY<NP=12>@simpenglish=31@#1f34ba0^1#1f350e0:1{2} Line 1 Column 1 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   (NP@simpenglish=5@#1f34b80^1#1f34ba0:1 Line 1 Column 1 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   |(D@simpenglish=12@#1f34aa0^2#1f34b80:1#1f34b40:1 Line 1 Column 1 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   | ('a'@simpenglish=22@#1f349c0^1#1f34aa0:1[Keyword:0] Line 1 Column 1 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt)'a'
   |)D#1f34aa0
   |(N@simpenglish=18@#1f34b20^2#1f34b80:2#1f34b40:2 Line 1 Column 3 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   | ('boy'@simpenglish=27@#1f34a80^1#1f34b20:1[Keyword:0] Line 1 Column 3 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt)'boy'
   |)N#1f34b20
   )NP#1f34b80
   (NP@simpenglish=7@#1f34c60^1#1f34ba0:2 Line 1 Column 1 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   |(NPA@simpenglish=3@#1f34b40^2#1f35040:1#1f34c60:1 Line 1 Column 1 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   | (D@simpenglish=12@#1f34aa0^2... [ALREADY PRINTED] ...)
   | (N@simpenglish=18@#1f34b20^2... [ALREADY PRINTED] ...)
   |)NPA#1f34b40
   )NP#1f34c60
  )AMBIGUITY#1f34ba0
  (VP@simpenglish=8@#1f34fc0^1#1f350e0:2 Line 1 Column 7 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   (V@simpenglish=15@#1f34d60^1#1f34fc0:1 Line 1 Column 7 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   |('saw'@simpenglish=25@#1f34b00^2#1f34d60:1#1f34d40:1[Keyword:0] Line 1 Column 7 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt)'saw'
   )V#1f34d60
   (AMBIGUITY<NP=12>@simpenglish=31@#1f34f00^2#1f34f80:2#1f34fc0:2{2} Line 1 Column 11 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   |(NP@simpenglish=5@#1f34e60^1#1f34f00:1 Line 1 Column 11 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   | (D@simpenglish=12@#1f34da0^2#1f34e60:1#1f34de0:1 Line 1 Column 11 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   |  ('a'@simpenglish=22@#1f34ce0^1#1f34da0:1[Keyword:0] Line 1 Column 11 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt)'a'
   | )D#1f34da0
   | (N@simpenglish=17@#1f34dc0^2#1f34e60:2#1f34de0:2 Line 1 Column 13 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   |  ('girl'@simpenglish=26@#1f34d80^1#1f34dc0:1[Keyword:0] Line 1 Column 13 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt)'girl'
   | )N#1f34dc0
   |)NP#1f34e60
   |(NP@simpenglish=7@#1f34f20^1#1f34f00:2 Line 1 Column 11 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   | (NPA@simpenglish=3@#1f34de0^1#1f34f20:1 Line 1 Column 11 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   |  (D@simpenglish=12@#1f34da0^2... [ALREADY PRINTED] ...)
   |  (N@simpenglish=17@#1f34dc0^2... [ALREADY PRINTED] ...)
   | )NPA#1f34de0
   |)NP#1f34f20
   )AMBIGUITY#1f34f00
  )VP#1f34fc0
 )S#1f350e0
 (S@simpenglish=2@#1f35040^1#1f35140:2 Line 1 Column 1 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
  (NPA@simpenglish=3@#1f34b40^2... [ALREADY PRINTED] ...)
  (VP@simpenglish=8@#1f34f80^1#1f35040:2 Line 1 Column 7 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   (V@simpenglish=15@#1f34d40^1#1f34f80:1 Line 1 Column 7 File C:/DMS/Domains/simpenglish/Tools/Lexer/aboysawagirl.txt
   |('saw'@simpenglish=25@#1f34b00^2... [ALREADY PRINTED] ...)
   )V#1f34d40
   (AMBIGUITY<NP=12>@simpenglish=31@#1f34f00^2... [ALREADY PRINTED] ...)
  )VP#1f34f80
 )S#1f35040
)AMBIGUITY#1f35140

您的简单英语语法解析器以不同的方式解析您的例句。

使用完整的 C++11 语法,这更加壮观。

于 2014-02-20T23:57:14.760 回答