Perché un compilatore non può avere un conflitto di "shift/shift"?

Question

Attualmente sto studiando i compilatori e, come ho capito in LR (0), ci sono casi in cui abbiamo conflitti "shift/reduce" o "reduce/riduci", ma è impossibile avere conflitti "shift/shift"! Perché non possiamo avere un conflitto "turno/turno"?

Answer 1

I conflitti di spostamento/riduzione si verificano quando il parser non è in grado di dire se spostare (premere il successivo token di input in cima allo stack di analisi) o ridurre (inserire una serie di terminali e non terminali dallo stack di analisi). Un conflitto di riduzione/riduzione è quando il parser sa ridurre, ma non può dire quale riduzione eseguire.

Se si dovesse avere un conflitto di maiusc/shift, il parser saprebbe che era necessario spingere il token successivo nel proprio stack di analisi, ma non avrebbe saputo come farlo. Poiché esiste un solo modo per spingere il token nello stack di analisi, generalmente non possono esserci conflitti di questo modulo.

Detto questo, è teoricamente possibile che si verifichi un conflitto di maiusc/shift se si dispone di una strana configurazione in cui sono presenti due o più transizioni che conducono da uno stato di analisi specificato con lo stesso simbolo di terminale. Il conflitto in quel caso sarebbe se spostarsi e andare in uno stato o spostarsi e andare in un altro. Questo potrebbe accadere se si provasse a comprimere un automa in un numero inferiore di stati e lo si fosse verificato in modo errato o se si stesse tentando di creare un automa di analisi non deterministico. In pratica, questo non succederebbe mai.

Spero che questo aiuti!