Почему эта очень простая грамматика заставляет парсеры GLR подавляться?

К сожалению, bison действительно настаивает на выполнении (одного) синтаксического анализа, поэтому вам нужно указать какой-то способ слияния неоднозначных синтаксических анализов. Если вы этого не сделаете, и существует более одного возможного синтаксического анализа, синтаксический анализатор GLR bison действительно будет жаловаться на неоднозначность синтаксического анализа.

Если вам все равно, какой из множества синтаксических разборов будет принят, то подчинить bison своей воле слишком не составит труда. Самый простой способ - просто назначить разные %dprec каждому, возможно, неоднозначному продукту. Затем Bison выберет ту подходящую продукцию, которая имеет наилучший приоритет.

Вы даже можете заставить bison сообщать вам о множественном синтаксическом анализе с помощью простой %merge функции; есть пример в руководстве по bison. (Документация по этой функции невелика, но она может быть адекватной вашим потребностям. Если нет, не стесняйтесь задавать более конкретный вопрос.)

У меня нет большого опыта работы с 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

Ваша грамматика не заставляет парсеры GLR задыхаться.

Вам нужен механизм синтаксического анализа GLR, который обеспечивает то, что должны выполнять синтаксические анализаторы GLR: синтаксический анализ перед лицом двусмысленности и передачу вам результата. Предположительно, вы используете дополнительный контекст, чтобы разрешить двусмысленность. (Вы можете запутать проверку контекста в процессе синтаксического анализа, если вы действительно настаиваете на том, чтобы избегать создания неопределенностей, предотвращаемых контекстом. Если вы это сделаете, вы получите те же сложности, что и у ребят из GCC, когда они пытались разобрать C и C ++ с помощью LALR).

Вот вывод для проблемы OP, переданный генератору синтаксического анализатора GLR нашего DMS Software Reengineering Toolkit. Мне нужно было определить лексер и грамматику, совместимые с 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.