Parsing

Da Wikipedia, l'enciclopedia libera.

In informatica, il parsing o analisi sintattica è un processo che analizza un flusso continuo di dati in ingresso (input) (letti per esempio da un file o una tastiera) in modo da determinare la sua struttura grazie ad una data grammatica formale. Un parser è un programma che esegue questo compito.

Di solito i parser non sono scritti a mano, ma realizzati attraverso dei generatori di parser.

Tipicamente, il termine italiano viene utilizzato per riferirsi al riconoscimento di una grammatica e alla conseguente costruzione di un albero sintattico, che mostra le regole utilizzate durante il riconoscimento dall'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, tuttavia, l'analisi sintattica opera su una sequenza di token in cui l'analizzatore lessicale spezzetta l'input. Pertanto, il termine inglese spesso viene usato per indicare l'insieme della analisi lessicale e della analisi sintattica vera e propria.

Descrizione[modifica | modifica wikitesto]

Esempio[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi grammatica libera dal contesto.

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[modifica | modifica wikitesto]

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.

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Parser top-down[modifica | modifica wikitesto]

Parser bottom-up[modifica | modifica wikitesto]

Generatori di parser[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica