Spec di grammatica che risolve il turno / riducono i conflitti

Question

Sto usando JISON (BISON) per creare una semplice lingua di markup.Sono chiaramente nuovo a questo, ma le lievi variazioni stanno funzionando molto bene.Non capisco la fonte del conflitto S / R.

Non sembra che il "testo" sia restituito da due azioni Lexer (con diverse condizioni di avvio) e mi piace perché sembra consentire alla grammatica di avere meno regole e perché i messaggi di errore all'utente sono coerenti.Ho provato a rendere il governo del "testo" comune indipendentemente dal contesto e ho anche provato a dare a ciascun token un nome diverso, ma non sembra avere alcun effetto sui conflitti S / R quando è tutto insieme.

.

Il parser dovrebbe creare un oggetto json con testo normale, sub-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 ]

.

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

Grazie!

Answer 1

Il conflitto arriva 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 che è generatori di Text, il parser non è noto se spostare il Text, corrispondente alla prima regola o per trattare il Text come l'inizio di A sentenceList andando verso la corrispondenza della seconda regola.

Ora se avessi un generatore di parser che utilizza lookahead a 2 token, questo non sarebbe un problema, ma Bison è LALR (1) (il 1 Essere un token lookahead).

Ci sono un paio di cose che potresti provare:

.

• Do Lookahead extra nel Lexer per differenziare il testo-seguita da-] dal testo-non-seguito da-] come due token distinti, quindi riscrivono le regole per utilizzare entrambi questi token.

• Usa la funzionalità% GLR-Parser di Bison per utilizzare GLR Parser. Questo analizzerà la frase in entrambe le direzioni e in seguito butta via quella che non corrisponde

• Refactor La grammatica non ha bisogno di 2-token lookahead.

Un refactoring che funziona nel tuo caso sarebbe quello di riscrivere le regole sentence per renderli tutti i destra-ricorsive anziché i sinistro-ricorsive:

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

.

Questo evita di avere sentence (o qualsiasi altra regola che si avvia con sentence come sentenceList) Avvia con una riduzione NULL della regola sentence: /*empty*/. Quindi il parser può spostare liberamente un Text nel caso problematico che differisce la riduzione fino a quando non vede il token successivo. Ha la memoria che utilizza implicazioni, tuttavia, poiché si traduce in un parser che si trasferirà essenzialmente l'intero ingresso sullo stack del parser e quindi ridurlo una frase alla volta.

Un altro refattore che si potrebbe fare sarebbe quello di sottostruggere il [Text] e il [] costrutti nel [sentenceList]:

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

sentenceList: sentence
            | sentenceList ',' sentence

.

Allora, un sentenceList è una o più frasi separate da virgole (anziché due o più), e nell'azione per la regola sentence '[' sentenceList ']', controllere il sentenceList per vedere se fossero due o più frasi e agire in modo appropriato .