Risoluzione problemi grammaticali Spostamento/riduzione dei conflitti

Question

Sto utilizzando Jison (Bison) per creare un linguaggio di markup semplice. Sono chiaramente nuovo a questo, ma le leggere variazioni stanno funzionando molto bene. Semplicemente non capisco la fonte del conflitto S/R.

Non sembra importare che "Testo" sia restituito da due azioni di lexer (con condizioni di avvio diverse) e mi piace perché sembra che la grammatica abbia meno regole e perché i messaggi di errore all'utente sono coerente. Ho provato a rendere la regola "Testo" comune indipendentemente dal contesto e ho anche provato a assegnare a ciascun token un nome diverso, ma non sembra avere alcun effetto sui conflitti S/R quando è tutto insieme.

Il parser è SUPPONENTE per creare un oggetto json con matrici di testo semplice, sotto-array e vari nodi speciali.

Specifica:

/* 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*/ 
    ; 

Avvertenze:

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 ] 

diversi algoritmi generatore hanno più o meno problemi, ma tutti sembrano avere problemi.

Grazie!

Answer 1

Il conflitto deriva fondamentalmente da queste due regole:

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

Il motivo è che dopo aver visto un sentence e un [ e guardando il token successivo essendo Text, il parser non sa se spostare il Text, corrispondente alla prima regola, o per trattare che Text come l'inizio di un sentenceList andando verso la corrispondenza con la seconda regola.

Ora, se si avesse un generatore di parser che utilizza il lookahead a 2 token, questo non sarebbe un problema, ma il bisonte è LALR (1) (l'1 è un token lookahead).

Ci sono un paio di cose che si potrebbe provare:

• fare lookahead supplementare nel lexer per differenziare Text-by-seguita-da] testo-non-by-seguita-] come due gettoni distinti quindi riscrivi le regole per utilizzare entrambi questi token.

• Utilizzare la funzione% glr-parser di bison per utilizzare il parser GLR. Questo analizzerà la frase in entrambi i modi e successivamente eliminerà quella che non corrisponde a

• refactoring della grammatica per non aver bisogno di lookahead a 2 token.

Uno refactoring che funziona nel tuo caso sarebbe quello di riscrivere le sentence regole per farli tutti destro ricorsiva invece di sinistra-ricorsiva:

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

Questo evita di dover sentence (o qualsiasi altra norma che inizia con sentence come sentenceList) inizia con una riduzione nulla della regola sentence: /*empty*/. Quindi il parser può spostare liberamente un Text nel caso problematico rinviando la riduzione finché non vede il token successivo.Tuttavia, ha implicazioni sull'uso della memoria, poiché risulta in un parser che essenzialmente sposta l'intero input sullo stack del parser e quindi lo riduce di una frase alla volta.

Un'altra refactoring si potrebbe fare sarebbe quella di inglobare le [Text] e [] costrutti nella [sentenceList]:

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

sentenceList: sentence 
      | sentenceList ',' sentence 

Così ora un sentenceList è uno o più frasi separate da virgole (invece di due o più), e nell'azione per la regola sentence '[' sentenceList ']', è necessario controllare lo sentenceList per vedere se erano due o più frasi e agire in modo appropriato.