Parsing: differenze tra le versioni

Versione delle 12:07, 29 apr 2013

Versione attuale delle 19:16, 20 feb 2025

(42 versioni intermedie di 31 utenti non mostrate)

Riga 1:

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 [[Lingua latina|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 generatirealizzati attraverso dei [[generatore di parser|generatori di parser]].

Tipicamente, ilIl termine italiano viene"analisi utilizzatosintattica" perfa riferirsiriferimento al riconoscimento di una grammatica e alla conseguente costruzione di un [[albero sintattico]], che mostra le regole utilizzate durante il riconoscimento dalldell'input; l'albero sintattico viene poi visitato (anche più volte) durante l'[[Esecuzione (informatica)|esecuzione]] di un [[interprete (informatica)|interprete]] o di un [[compilatore]]. Nella maggior parte dei linguaggi, l'analisi sintattica opera sulla sequenza di ''[[Token (testo)|token]]'' ottenuta dal lavoro dell'[[analizzatore lessicale]] sui dati in ingresso.

Di solito i parser non sono scritti a mano ma generati attraverso dei [[generatore di parser|generatori di parser]].

==Descrizione==

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 (informatica)|interprete]] o di un [[compilatore]].

=== 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.

Nella maggior parte dei linguaggi, tuttavia, l'analisi sintattica opera su una sequenza di ''[[Token (testo)|token]]'' in cui l'[[analizzatore lessicale]] spezzetta l'input. Pertanto, il termine inglese spesso viene usato per indicare l'insieme della ''[[analisi lessicale (informatica)|analisi lessicale]]'' e della ''analisi sintattica'' vera e propria.

Come detto, il primo passo è la generazione di token, o [[analisi lessicale (informatica)|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.

== 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 (informatica)|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.

Line 17 ⟶ 16:

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 ===

{{vedi anche|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 [[Parser top-down|top-down]]'' - Unun 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 [[Parser bottom-up|bottom-up]]'' - Unun 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 [[grammatica libera dal contesto|grammatiche libere dal contesto]] poiché con queste grammatiche si possono scrivere parser veloci ed efficienti.

Line 32 ⟶ 31:

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 [[grammatica dipendente dal contesto|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 ==

* {{FOLDOC}}

* ''Compilers: Principles, TechniquesTechnique, 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 di Unger]]

=== [[Parser bottom-up]] ===

* [[Parser LR]]

** [[Parser SLR]]

** [[ParserGeneratore LALRdi parser]]

* [[Parser di Earley]]

* [[CYK algorithm|Parser CYK]]

* [[Tomita's Algorithm|Parser GLR]]

=== [[Generatore di parser|Generatori di parser]] ===

* [[ANTLR]]

* [[GNU Bison]]

Line 56 ⟶ 48:

* [[JavaCC]]

* [[Yacc]]

* Spirit (Boost)

* [[VisualLangLab]]

== BibliografiaAltri progetti ==

{{interprogetto|preposizione=sul}}

{{FOLDOC}}

* ''Compilers: Principles, Techniques, and Tools''. Aho, Lam, Sethi, Ullman. [[Addison-Wesley]], (2nd Edition) 2006. ISBN 0-321-48681-1

== Voci correlate ==

* [[Augmented transition network]]

== Collegamenti esterni ==

Line 70 ⟶ 56:

* [http://www.MHGSoft.de?Parser TFunctionParser] Un parser matematico esauriente (più di 90 funzioni e operazioni)

* [http://www.ucalc.com/mathparser UCalc Fast Math Parser] Un parser di espressioni, commerciale

* [httphttps://muparserbeltoforion.sourceforge.netde/en/muparser/ muParser] Un parser di espressioni matematiche, open source

* [http://www.cs.vu.nl/~dick/PTAPG.html Parsing Techniques - A Practical Guide] by Dick Grune and Ceriel J.H. Jacobs.

* {{collegamento interrotto|1=[http://www.guidealgoritmi.it/ShowArticle.aspx?ID=3 Operator Precedence Parsing] |data=marzo 2018 |bot=InternetArchiveBot }} Un parser di espressioni matematiche, open source, in linguaggio C

* [http://www.guidealgoritmi.it/ShowArticle.aspx?ID=3 Operator Precedence Parsing] Un parser di espressioni matematiche, open source, in linguaggio C

* [http://www.tule.di.unito.it/ Turin University Parser] Parser del linguaggio naturale, italiano, open source, in linguaggio Common Lisp (di Leonardo Lesmo, Università di Torino)

* [http://nlp.stanford.edu/software/lex-parser.shtml Stanford Parser] Parser di Stanford

{{Portale|informatica}}

[[Categoria:TeorieParsing| della programmazione]]