为什么这个非常简单的语法会导致GLR解析器出现问题?

4

我尝试了几个声称能生成GLR解析器(例如Bison、DParser等)的解析器生成器,可以处理含有歧义语法的解析。下面是一个非常简单的类型的歧义语法:

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在大型语法中会出现问题。(所谓的“出现问题”,指的是以各种不同的方式失败。如果失败模式有用,我可以报告这些模式。)有其他想法的人吗?
2个回答

4
很不幸,bison 确实坚持生成(单个)解析,因此您必须指定一种方法来合并模糊的解析。如果您不这样做,并且有多个可能的解析,则 bison 的 GLR 解析器确实会抱怨解析是模糊的。
如果您真的不在乎接受哪个多个解析,那么弯曲 bison 以符合您的意愿并不是太困难。最简单的方法是只为每个可能存在歧义的产生式分配不同的 %dprec。然后,bison 将选择具有最佳优先级的适用产生式。
您甚至可以通过一个简单的 %merge 函数让 bison 告诉您有关多个解析的信息;在 bison manual 中有一个示例。(该功能的文档不是很好,但可能足以满足您的需求。如果不行,请随时提出更具体的问题。)

我对DParser的经验不多,但是手册表明,当面临多个可能的解析时,它的行为类似:默认情况下会发出警告,但是您可以提供自己的简单合并函数:(引用来自第12节,歧义)

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


这是第二个例子的bison 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

@user3268289:在这两种情况下,只有在出现歧义时才调用歧义例程,它什么都做不了。所以,没错,这很简单。虽然Bison当然关注效率,但其行为的主要原因是它关注解析用于编译/解释的真实语言,并且通常需要无歧义的解析。%dprec解决方案需要大量键入,但除此之外是微不足道的;只需将%dprec N添加到每个产生式的末尾,其中N是唯一的整数(例如,您可以顺序编号)。 - rici
Rici,你的想法很好,改进了Bison处理一些棘手语法的能力。然而,在原问题中的第二个例子中,它仍然无法正常工作。 - user3268289
Rici,抱歉,我想你在我编辑第二个示例时看到了一个版本。你能否也让第二个示例的最新版本(包括“女孩”、“男孩”、“望远镜”等)正常工作?顺便说一句,非常感谢你的帮助。 - user3268289
@user3268289:好的,这就是您需要的。 - rici
非常感谢你的帮助,Rici。看起来我的分词器/词法分析器出了一些问题,而不是我之前认为的语法问题。现在在Bison中它运行得很好,尽管我正在迅速学习Bison和相关工具并不适用于自然语言处理(NLP),这才是我真正想做的事情。 - user3268289
显示剩余3条评论

1

你的语法不会让GLR解析器崩溃。

你需要一个能够提供GLR解析器应有功能:在面对歧义时进行解析,并将结果呈现给你的解析引擎。想必你使用了额外的上下文来解决这些歧义。(如果你真的坚持避免产生上下文防止的歧义,你可以将上下文检查纳入解析过程中。如果你这样做,你会像GCC团队在尝试使用LALR解析器解析C和C++时所遇到的那样出现各种复杂情况)。

以下是我们DMS软件重构工具包的GLR解析器生成器针对OP问题的输出。我需要定义与DMS兼容的词法分析器和语法:

词法分析器(将单个标记定义为单词;更可扩展的版本可能会将单词类标记(如D P V N)定义为标记):

%%
%%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语法,效果会更加出色。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接