Parsing

In linguistica computazionale il parsing, definito altresì analisi sintattica o parsificazione, è 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 correttezza della sua struttura grazie ad una data grammatica formale. Un parser è un programma che esegue questo compito.

Il termine parsing proviene dal latino pars ("parte"), che indica una parte di un discorso più ampio.

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 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, 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 dell'analisi lessicale e dell'analisi sintattica vera e propria.

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.

Bibliografia

• (EN) Denis Howe, Parsing, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
• Compilers: Principles, Technique, and Tools. Aho, Lam, Sethi, Ullman. Addison-Wesley, (2nd Edition) 2006. ISBN 0-321-48681-1
• Linguaggi Formali e Compilazione. Crespi Reghizzi. Pitagora Editrice, 2006. ISBN 978-8837116323

Voci correlate

• Augmented transition network

Parser top-down

• Parser LL
  • Parser a discesa ricorsiva
• Parser packrat
• Unger's method

Parser bottom-up

• Parser LR
  • Parser SLR
  • Parser LALR
• Parser di Earley
• CYK algorithm
• Tomita's Algorithm

Generatori di parser

• ANTLR
• GNU Bison
• SableCC
• JavaCC
• Yacc
• Spirit (Boost)
• VisualLangLab

Altri progetti

Altri progetti

• Wikiversità
• Wikimedia Commons

• Wikiversità contiene risorse sul parsing
• Wikimedia Commons contiene immagini o altri file sul parsing

Collegamenti esterni

• Parsing Simulator Questo simulatore è concepito per aiutare lo studente a comprendere in tutta semplicità i vari passaggi per la costruzione delle tabelle di Parsing. Utile per chi vuole esercitarsi sull'argomento
• TFunctionParser Un parser matematico esauriente (più di 90 funzioni e operazioni)
• UCalc Fast Math Parser Un parser di espressioni, commerciale
• muParser Un parser di espressioni matematiche, open source
• Parsing Techniques - A Practical Guide by Dick Grune and Ceriel J.H. Jacobs.
• Operator Precedence Parsing Un parser di espressioni matematiche, open source, in linguaggio C
• Turin University Parser Parser del linguaggio naturale, italiano, open source, in linguaggio Common Lisp (di Leonardo Lesmo, Università di Torino)
• Stanford Parser Parser di Stanford