Come posso espandere il set di elementi per questa grammatica?
Ho questa grammatica
E -> E + i
E -> i
La grammatica aumentata
E' -> E
E -> E + i
E -> i
Ora provo ad espandere il set di elementi 0
I0)
E' -> .E
+E -> .E + i
+E -> .i
Quindi, da quando ho .Edentro, I0lo espanderei ma poi otterrò un'altra Eregola, e così via, questo è il mio primo dubbio.
Supponendo che questo sia corretto, lo sono i set di elementi successivi
I0)
E' -> .E
+E -> .E + i
+E -> .i
I1) (I moved the dot from I0, no variables at rhs of dot)
E' -> E.
E -> E. + i
E -> i.
I2) (I moved the dot from I1, no vars at rhs of dot)
E -> E +. i
I3) (I moved the dot from I2, also no vars)
E -> E + i.
Allora avrò questo DFA
I0 -(E, i)-> I1 -(+)-> I2 -(i)-> I3
| |
+-(∅)-> acpt <-(∅)--+
Mi manca qualcosa perché E -> E + idevo accettare i + i + ..ma il DFA non torna all'I0, quindi mi sembra sbagliato. La mia ipotesi è che dovrebbe avere una transizione da I0 a I0, ma non so che abbia a che fare con il punto.
Risposte
Ciò che chiamate "espansione" dell'insieme di elementi è in realtà una chiusura; è così che è descritto in tutte le descrizioni dell'algoritmo che ho visto (almeno nei libri di testo). Come ogni operazione di chiusura, continui a fare la trasformazione fino a raggiungere un punto fisso; una volta incluse le produzioni per E, sono incluse.
Ma il punto essenziale è che non stai creando un DFA. Stai costruendo un automa pushdown e il DFA è solo una parte di esso. Il DFA viene utilizzato per le operazioni a turni; quando sposti un nuovo terminale (perché lo stack di analisi corrente non è un handle), esegui una transizione di stato secondo DFA. Ma sposti anche lo stato corrente sullo stack del PDA.
La parte interessante è cosa accade quando l'automa decide di eseguire una riduzione, che sostituisce il lato destro di una produzione con il suo lato sinistro non terminale. (Il lato destro in cima alla pila è chiamato "maniglia".) Per eseguire la riduzione, srotoli la pila, facendo scoppiare ogni simbolo sul lato destro (e il corrispondente stato DFA) fino a raggiungere l'inizio di la produzione. Ciò che fa è riavvolgere il DFA allo stato in cui si trovava prima di spostare il primo simbolo dal lato destro. (Tieni presente che è solo a questo punto che sai con certezza quale produzione è stata utilizzata.) Con il DFA così ripristinato, puoi ora spostare il non terminale che è stato rilevato, eseguire la transizione DFA corrispondente e continuare con l'analisi.
La base di questa procedura è il fatto che lo stack del parser è sempre un "prefisso valido"; cioè una sequenza di simboli che sono il prefisso di una forma sentenziale destra che può essere derivata dal simbolo di inizio. La cosa interessante dell'insieme di prefissi validi per una grammatica priva di contesto è che si tratta di una lingua normale e di conseguenza può essere riconosciuta da un DFA. La procedura di riduzione data sopra rappresenta precisamente questa procedura di riconoscimento quando le maniglie vengono "potate" (per usare il vocabolario originale di Knuth).
In questo senso, non importa quale procedura viene utilizzata per determinare quale handle deve essere eliminato, purché fornisca una risposta valida. Potresti, ad esempio, eseguire il fork del parse ogni volta che viene notato un potenziale handle in cima allo stack e continuare in parallelo con entrambi i fork. Con una gestione intelligente dello stack, questa ricerca parallela può essere eseguita nel caso peggiore O (n 3 ) per qualsiasi grammatica libera dal contesto (e questo può essere ridotto se la grammatica non è ambigua). Questa è una descrizione molto approssimativa dei parser Earley.
Ma nel caso di un parser LR (k), richiediamo che la grammatica sia univoca, e richiediamo anche di poter identificare una riduzione guardando non più di kpiù simboli dal flusso di input, che è un O (1) operazione poiché kè stato risolto. Se in ogni punto dell'analisi sappiamo se ridurre o meno, e in tal caso quale riduzione scegliere, le riduzioni possono essere implementate come descritto sopra. Ogni riduzione può essere eseguita in tempo O (1) per una grammatica fissa (poiché la dimensione massima di un lato destro in una particolare grammatica è fissa), e poiché il numero di riduzioni in un'analisi è lineare nella dimensione del input, l'intera analisi può essere eseguita in tempo lineare.
Era tutto un po 'informale, ma spero serva come spiegazione intuitiva. Se sei interessato alla dimostrazione formale, il documento originale del 1965 di Donald Knuth ( Sulla traduzione delle lingue da sinistra a destra ) è facile da trovare e altamente leggibile mentre vanno queste cose.