Come risolvere un conflitto shift-ridurre in grammatica non ambigua

Question

Sto cercando di analizzare una grammatica semplice utilizzando un LALR (1) generatore di parser (Bison, ma il problema non è specifico a tale strumento), e sto colpendo un conflitto shift-ridurre. La documentazione e le altre fonti che ho trovato circa la fissazione di tali tendono a dire uno o più dei seguenti elementi:

• Se la grammatica è ambigua (ad esempio if-then-else ambiguità), cambiare la lingua per risolvere l'ambiguità.
• Se è un problema di precedenza degli operatori, specificare la precedenza in modo esplicito.
• Accetta la risoluzione di default e dire al generatore di non lamentarsi.

Tuttavia, nessuno di questi sembra applicarsi alla mia situazione: la grammatica è ambigua per quanto posso dire (anche se, naturalmente, è ambiguo con un solo carattere del lookahead), ha un solo operatore, e i conduttori di risoluzione di default per analizzare errori sull'ingresso correttamente formata. Ci sono delle tecniche per rielaborare la definizione di una grammatica per eliminare i conflitti di turno-reduce che non rientrano nei secchi di cui sopra?

Per concretezza, ecco la grammatica in questione:

%token LETTER

%%
%start input;
input:          /* empty */ | input input_elt;
input_elt:      rule | statement;
statement:      successor ';';
rule:           LETTER "->" successor ';';
successor:      /* empty */ | successor LETTER;
%%

L'intento è quello di analizzare linee virgola-separate della forma "[A-Za-z] +" o "[A-Za-z] -> [A-Za-z] +"

.

Answer 1

Utilizzando la versione di Solaris di yacc, ottengo:

1: shift/reduce conflict (shift 5, red'n 7) on LETTER
state 1
    $accept :  input_$end
    input :  input_input_elt
    successor : _    (7)

    $end  accept
    LETTER  shift 5
    .  reduce 7

    input_elt  goto 2
    rule  goto 3
    statement  goto 4
    successor  goto 6

Quindi, il problema è, come molto spesso è, la regola vuota - in particolare, il successore vuota. Non è del tutto chiaro se si desidera consentire un punto e virgola come un input valido - in questo momento, lo è. Se si è modificato la regola successore di:

successor: LETTER | successor LETTER;

spostamento / ridurre il conflitto è eliminato.

Answer 2

Grazie per tagliuzzare giù la grammatica ed inviarla. Cambiare la regola successore -

successor:      /* empty */ | LETTER successor;

... ha lavorato per me. ITYM il lingua guardato inequivocabile.