왜 이렇게 간단한 문법 때문에 GLR 파서가 질식합니까?

Question

저는 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 및 %의 병합 사용 :

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

"소년이 소녀를 봤다"라는 문구가 있으면 바이손은 코드 1로 구문 분석하고 반환 할 수 없습니다. 반면에 Tom은이 문법과이 입력 문장을 완벽하게 처리하며 모든 사람에게 가능한 터미널 유형. 그러나 Bison과 달리 Tom은 큰 문법을 사용합니다. ("쵸크"란 여러 가지 다른 방식으로 실패합니다. 고장 모드가 도움이된다면, 그것들을보고 할 수 있습니다.)

누구든지 다른 아이디어가 있습니까?

Answer 1

불행히도 bison은 실제로 (단일) 구문 분석을 고집하므로 모호한 구문 분석을 병합하는 방법을 지정해야합니다. 만약 당신이하지 않고, 가능한 파싱이 여러 개라면, 바이슨의 GLR 파서는 파문이 모호하다는 사실을 정말로 불평 할 것이다.

여러 개의 구문 중 어느 것이 받아 들여 지는지 정말로 신경 쓰지 않는다면, 도이 아닙니다. 가장 간단한 방법은 모든 모호한 생산에 다른 %dprec을 할당하는 것입니다. Bison은 적용 가능한 생산이 최우선 순위로 선택되는 것을 선택합니다.

단순한 %merge 함수를 사용하면 bison에게 여러 구문 분석에 대해 알려줄 수 있습니다. bison manual에 예제가 있습니다. (이 기능에 대한 문서는 훌륭하지 않지만 필요에 따라 적절할 수도 있습니다. 더 궁금한 점이 있으면 자유롭게 질문하십시오.)

나는 DParser에 대해 많은 경험이 없지만 manual은 여러 가능한 파싱에 직면 그 동작은 유사하다 : 기본 불평하는 것입니다,하지만 당신은 당신의 자신의 사소한 병합 기능을 제공 할 수 있습니다 (따옴표는, 제 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 

Answer 2

문법이 GLR 파서는 질식의 원인이되지 않습니다.

GLR 파서가 제공해야하는 것을 제공하는 GLR 구문 분석 엔진이 필요합니다. 모호한 측면에서 파싱하고 결과를 나눠줍니다. 아마도 모호성을 해결하기 위해 추가 컨텍스트를 사용합니다. (당신은 복잡하게 얽힌 수있는 상황 확인 당신이 정말로 상황에 방지 모호성을 생산 피해를 주장하는 경우 구문 분석 프로세스에 . 당신이 여기

우리 DMS 소프트웨어 재 설계 툴킷의 GLR에게 주어진 영업 이익의 문제에 대한 출력의 것을 you get the kind of complications that the GCC guys had when they tried to parse C and C++ with LALR). 할 경우 . 파서 생성기 나는 렉서 및 DMS 호환 문법을 정의했다 :

렉서 (즉 개별 토큰을 정의; 더 확장 버전 을 같은 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 do esn't) EBNF 신경 : 처음부터 끝까지, 건물 렉서와 파서 (멍청이 약 10 분

a boy saw a girl\n 

"aboysawagirl.txt"

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' ; 

샘플 파일을 ...)

샘플 파일을 구문 분석하고 자동으로 내장 트리 덤프 :

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 

귀하의 간단한 영어 GRAMM을 ar 파서는 여러 가지 방법으로 예제 문장을 구문 분석합니다.

전체 C++ 11 문법이 훨씬 뛰어납니다.