# Parsing

L'analisi sintattica o parsing oppure parsificazione è un processo che analizza un flusso continuo di dati in ingresso, in modo da determinare la correttezza della sua struttura grazie ad una data grammatica formale. Il termine parsing proviene dal latino pars ("parte"), che indica una parte di un discorso più ampio.
Il programma che esegue questa analisi è detto analizzatore sintattico o parser. Di solito i parser non sono scritti a mano, ma realizzati attraverso dei generatori di parser.
Il termine "analisi sintattica" fa riferimento al riconoscimento di una grammatica e alla conseguente costruzione di un albero sintattico, che mostra le regole utilizzate durante il riconoscimento dell'input; l'albero sintattico viene poi visitato (anche più volte) durante l'esecuzione di un interprete o di un compilatore. Nella maggior parte dei linguaggi, l'analisi sintattica opera sulla sequenza di token ottenuta dal lavoro dell'analizzatore lessicale sui dati in ingresso.

## Descrizione
### Esempio

L'esempio seguente mostra un caso comune di parsing di un linguaggio per un calcolatore (o calcolatrice) con due livelli di grammatica: lessicale e sintattica.
Come detto, il primo passo è la generazione di token, o analisi lessicale. Per esempio, l'input potrebbe essere il seguente "12*(3+4)^2", in questo caso il parser divide l'input in token nel modo seguente: 12, *, (, 3, +, 4, ), ^ e 2, ognuno dei quali è un simbolo con significato in un'espressione matematica. Il parser potrebbe contenere regole che gli dicono che i caratteri *, +, ^, ( e ) determinano l'inizio di un nuovo token, quindi i token come "12*" o "(3" non verrebbero generati.
L'analisi sintattica propriamente detta riceve in input la sequenza dei token e controlla che i token formino espressioni valide. Questo lavoro è svolto basandosi su una grammatica libera dal contesto, che ricorsivamente definisce i componenti che determinano un'espressione e l'ordine in cui devono comparire.
La fase finale è l'analisi semantica, che trova le implicazioni dell'espressione appena validata ed esegue le conseguenti azioni. Nel caso del calcolatore, l'azione è quella di valutare l'espressione; un compilatore, d'altra parte, può generare il linguaggio macchina che esegue la funzionalità presente nel codice.

### Tipi di parser

Il lavoro del parser è essenzialmente quello di determinare se e come l'input può essere derivato dal simbolo iniziale con le regole della grammatica formale. Questo può essere fatto essenzialmente in due modi:
* Analisi top-down - un parser può partire con il simbolo iniziale e cercare di trasformarlo nell'input. Intuitivamente, il parser parte dal più grande elemento e lo divide in parti sempre più piccole. I parser LL sono esempi di parser top-down.
* Analisi bottom-up - un parser può partire con l'input e cercare di riscriverlo sino al simbolo iniziale. Intuitivamente, il parser cerca di trovare il più elementare simbolo, quindi elabora gli elementi che lo contengono, e così via. I parser LR sono esempi di parser bottom-up.
Un'altra importante distinzione è quella tra parser che generano per leftmost derivation o per rightmost derivation. I parser LL generano una derivazione leftmost e i parser LR una derivazione rightmost.

### Linguaggi di programmazione

Genericamente i parser sono utilizzati con i linguaggi di programmazione, i quali hanno delle grammatiche semplici e regolari; i parser di questo tipo tendono ad essere basati su grammatiche libere dal contesto poiché con queste grammatiche si possono scrivere parser veloci ed efficienti.
In realtà, le grammatiche libere dal contesto non riescono a descrivere da sole la maggior parte dei linguaggi di programmazione di uso comune. Informalmente, la ragione è che la memoria di ogni linguaggio è limitata; la grammatica non può ricordare la presenza di un costrutto dopo un'arbitraria lunghezza in input, è necessario per esempio in quei linguaggi dove i nomi possono essere referenziati.
Usare grammatiche più potenti, quali quelle grammatiche dipendenti dal contesto, tuttavia, vuol dire perdere in efficienza. Di conseguenza è una strategia comune quella di utilizzare grammatiche libere dal contesto per una versione "rilassata" (con minori vincoli) del linguaggio. Queste grammatiche accetteranno tutti i costrutti validi del linguaggio in considerazione, oltre ad altri costrutti non validi che vengono scartati durante l'analisi semantica dell'input. Per esempio, la grammatica potrebbe accettare un programma che usa una variabile non dichiarata in precedenza.