Quali sono i casi in cui non possiamo eseguire l'analisi LR senza grammatica aumentata?

Question

Molti testi di progettazione del compilatore standard menziona la costruzione della grammatica aumentata come primo passo del parsing LR.

Il motivo è frequentemente

.
1. È necessario nei casi in cui il simbolo di avvio arriva sulla mano destra di qualsiasi produzione
2. è necessario quando l'avvio del simbolo RHS ha più produzione.

Ho pensato che, se nella parte della tabella di Parse è parte del primo stato del primo stato di DFA, forniamo "successo" in entrata di "$" non richiederemmo la grammatica aumentata.È corretto o mi manca qualcosa?

Modifica: Ecco come penso che possiamo dichiarare un analizzo come successo:

Considera S -> .a Dopo aver ridotto "A" invece di andare a goto (s) dal nostro stato attuale un Ttop di pila, possiamo semplicemente guardare '$' e successo di output

Answer 1

Una volta che abbiamo un tavolo antigas, possiamo analizzare (o rifiutare) qualsiasi frase senza alcun riferimento alla grammatica. Quindi, a quel punto, il fatto che la grammatica sia o non fosse stata aumentata è sostanzialmente discutibile. (Sarebbe significativo se ci fossero un'azione semantica dell'utente allegata alla sola produzione di Symbol Aumented Symbol, ma sembra impossibile, dal momento che la produzione di Symbol Aumented Symbol è stata aggiunta automaticamente, non dall'utente.)

Ed è davvero il caso che la maggior parte dei generatori di parser per ottimizza infatti la loro tabella di analisi rendendo shift del marcatore di estremità dell'ingresso, l'azione accetta, piuttosto che attendere l'avvio aumentato La produzione del simbolo da ridurre. Con quell'ottimizzazione, il simbolo di avvio aumentato non viene mai utilizzato in un'azione del parser, quindi il simbolo stesso non deve esistere. Se il generatore di parser aumentò la grammatica, che l'aumento è essenzialmente annullato, ad eccezione di un piccolo mistero: qual è questo simbolo di fine input che può essere spostato? Non appare in alcun lato destro riducibile.

Comunque, il punto è che non è analizzato che richiede una grammatica aumentata; La grammatica aumentata è necessaria per creare la tabella antigas. I casi in cui è necessario sono essenzialmente i casi in cui vi sono alcune azioni di riduzione non predefinita associate a un simbolo di fine-input lookahead. Quell'azione di riduzione potrebbe essere stata giustamente aggiunta correttamente alla tabella di analisi attraverso l'analisi di uno stato che include la produzione di simbolo di avvio aumentato.

(rigorosamente parlando, come accennato in precedenza, il simbolo di fine input non può esistere davvero nella tabella antigas a meno che non sia presente in un lato destro nella grammatica, e non è presente fino a quando La grammatica è aumentata; l'aumento non solo aggiunge un ulteriore non terminale, aggiunge anche il simbolo di fine input stesso.)