Rozdzielczość właściwości gramatyki Przesunięcie/zmniejszenie liczby konfliktów

Question

Używam Jison (Bison) do tworzenia prostego języka znaczników. Jestem na to zupełnie nowy, ale niewielkie różnice działają bardzo dobrze. Po prostu nie rozumiem źródła konfliktu S/R.

Nie ma znaczenia, że ​​tekst jest zwracany przez dwie akcje leksujące (z różnymi warunkami początkowymi) i podoba mi się to, ponieważ wydaje się, że gramatyka ma mniej reguł i ponieważ komunikaty o błędach dla użytkownika są zgodny. Próbowałem stworzyć regułę "Tekstu" powszechnie, niezależnie od kontekstu, a także próbowałem nadać każdemu tokenowi inną nazwę, ale wydaje się, że nie ma to żadnego wpływu na Konflikt S/R, kiedy wszystko jest razem.

Parser jest SUPPOSED, aby utworzyć obiekt Json za pomocą zwykłego tekstu, pod-macierzy i różnych specjalnych węzłów.

Specyfikacja:

/* lexical grammar */ 
%lex 

%s bracketed 

%% 

<bracketed>(\\.|[^\\\,\[\]])+  { yytext = yytext.replace(/\\(.)/g, '$1'); return 'Text'; } 
<INITIAL>(\\.|[^\\\[])+    { yytext = yytext.replace(/\\(.)/g, '$1'); return 'Text'; } 
"["         { this.begin('bracketed'); return '['; } 
"]"         { this.popState(); return ']'; } 
","         return ',' 
<<EOF>>        return 'END' 

/lex 

%start template 

%%  

template 
    : sentence END 
    ; 

sentence 
    : /* empty */ 
    | sentence Text 
    | sentence '[' ']' 
    | sentence '[' dynamic ']' 
    ; 

dynamic 
    : sentence 
    /*| dynamic ',' sentence*/ 
    ; 

Ostrzeżenia:

Conflict in grammar: multiple actions possible when lookahead token is ] in state 5 
- reduce by rule: sentence -> 
- shift token (then go to state 6) 

States with conflicts: 
State 5 
    sentence -> sentence [ .] #lookaheads= END Text [ ] 
    sentence -> sentence [ .dynamic ] #lookaheads= END Text [ ] 
    dynamic -> .sentence #lookaheads= ] 
    sentence -> . #lookaheads= ] Text [ 
    sentence -> .sentence Text 
    sentence -> .sentence [ ] 
    sentence -> .sentence [ dynamic ] 

Różne algorytmy generatory mają więcej lub mniej problemów, ale wszystkie one wydają się mieć kłopoty.

Dzięki!

Answer 1

Konflikt pochodzi zasadniczo z tych dwóch zasad:

sentence: sentence '[' Text ']' 
     | sentence '[' sentenceList ']' 

Powodem jest to, że po obejrzeniu sentence i [ i patrząc na następny znak będącego Text, parser nie wiadomo, czy przesunięcie Text, dopasowując pierwszą regułę lub traktując to jako Text jako początek sentenceList idąc w kierunku dopasowania drugiej reguły.

Teraz, jeśli dysponowałeś generatorem parsera, który używa 2-tokenowego wyprzedzenia, nie byłoby to problemem, ale żubr to LALR (1) (1 to jeden znak wyprzedzający o jeden znacznik).

Istnieje kilka rzeczy, można spróbować:

• zrobić dodatkowy uprzedzona w lexer odróżnić tekstowej następuje po kroku] Z tekstu nie-następnie po kroku] jako dwa odrębne tokeny następnie przepisz reguły, aby użyć obu tych tokenów.

• Użyj funkcji% glr-parser bison do użycia parsera GLR. Spowoduje to przeanalizowanie zdania w obie strony, a następnie odrzucenie tego, który nie pasuje do tego, aby nie modyfikować gramatyki, aby nie potrzebować 2-token-a-wcześnie-przedrostka.

Jeden refaktoryzacji, który działa w Twoim przypadku byłoby przepisać zasady sentence aby uczynić z nich wszystko w porządku-rekurencyjne zamiast lewej rekurencyjne:

sentence: /* empty */ 
     | Text sentence 
     | '[' ']' sentence 
     | '[' Text ']' sentence 
     | '[' sentenceList ']' sentence 
     ; 

ten sposób unika się konieczności sentence (lub jakakolwiek inna reguła rozpoczynające się od sentence, takie jak sentenceList) rozpoczynają się od zerowej redukcji reguły sentence: /*empty*/. Dlatego też parser może swobodnie przesuwać Text w problematycznym przypadku odraczając redukcję, dopóki nie zobaczy następnego żetonu.Ma jednak implikacje związane z wykorzystaniem pamięci, ponieważ powoduje, że analizator składni zasadniczo przenosi całe wejście na stos parsera, a następnie redukuje go jedno zdanie na raz.

Innym Refactor można zrobić byłoby podciągnąć się [Text] i [] konstrukty do [sentenceList]:

sentence: /* empty */ 
     | sentence Text 
     | sentence '[' sentenceList ']' 
     ; 

sentenceList: sentence 
      | sentenceList ',' sentence 

Więc teraz sentenceList jest jeden lub więcej zdań oddzielone przecinkami (zamiast dwóch lub więcej), a w akcji dla reguły sentence '[' sentenceList ']', sprawdź, czy jest to dwa lub więcej zdań i działaj prawidłowo.