Corrisponde alle slide: Lez 12 - Lez 13
Un Parser (o analizzatore sintattico) è un programma che si basa su un PDA per il linguaggio riconosciuto e che usa quest'ultimo come input per trovare le produzioni da utilizzare e quindi costruire un albero di derivazione.
I parser non deterministici usano l'informazione dell'input per scegliere le produzioni da utilizzare, ma se in un secondo momento si scopre che la scelta è improduttiva e non permette di generare alcun albero, si può sempre tornare indietro e rileggere parte dell'input, e quindi disfare parte della derivazione appena fatta e scegliere un'altra produzione.
Tenderemo ad evitare questo tipo di parser perché non particolarmente efficiente, anche se più semplice da costruire.
I parser deterministici invece leggono l'input una sola volta ed ogni loro decisione è definitiva, nel senso che se in un secondo momento si scopre che l'albero non può essere generato è perché non esiste nessun albero di derivazione.
I parser deterministici però si possono costruire solo per grammatiche con certe proprietà, che vedremo pià in là. Trallallero trallalà.
Sono due tipi di parser totalmente opposti:
L'approccio Top-down è più semplice da realizzare, ma quello Bottom-up è più potente e generale.
Per creare PDA più efficienti e con minor determinismo è cruciale manipolare le grammatiche in modo da semplificarle. Vediamo in ordine i vari approcci che si possono usare.
Prima di tutto chiariamo cos'è una $\epsilon$-produzione: è una produzione della forma $A\rarr\epsilon$. Queste produzioni possono essere eliminate da una grammatica senza cambiarne il potere espressivo.
Se $\epsilon$ fa parte del linguaggio allora aggiungeremo l'unica produzione $S'\rarr\epsilon$ per ottenerlo.
Per eliminare le $\epsilon$-produzioni si prende ogni produzione una per volta e si considerano le produzioni a distanza 0, 1, 2, ecc. di questa, se ci sono produzioni che portano ad $\epsilon$ le eliminiamo.