Parsing: differenze tra le versioni

Versione delle 00:08, 12 mag 2014

Versione attuale delle 19:16, 20 feb 2025

(31 versioni intermedie di 24 utenti non mostrate)

Riga 1:

InL''''analisi [[informatica]],sintattica''' ilo '''''parsing''''' ooppure '''analisi sintatticaparsificazione''' è ilun processo attoche adanalizza analizzareun uno streamflusso continuo indi [[input]]dati (lettoin per esempio da un file o una tastiera)ingresso, in modo da determinare la correttezza della sua struttura grammaticale grazie ad una data [[grammatica formale]]. UnIl termine '''parser'parsing'' èproviene undal [[programmaLingua (informatica)latina|programmalatino]] ''pars'' ("parte"), che esegueindica una parte di un discorso questopiù compitoampio.

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.

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.

==Descrizione==

Line 12 ⟶ 10:

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 25 ⟶ 23:

* ''Analisi [[Parser bottom-up|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 ===

Line 33 ⟶ 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 bottom-up]] ===

* [[Parser LR]]

** [[Parser SLR]]

** [[ParserGeneratore LALRdi parser]]

* [[Parser di Earley]]

* [[CYK algorithm]]

* [[Tomita's Algorithm]]

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

* [[ANTLR]]

* [[GNU Bison]]

Line 62 ⟶ 48:

* [[JavaCC]]

* [[Yacc]]

* Spirit (Boost)

== Altri progetti ==

* [[VisualLangLab]]

{{interprogetto|preposizione=sul}}

== Collegamenti esterni ==

Line 69 ⟶ 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

Line 78 ⟶ 64:

{{Portale|informatica}}

[[Categoria:TeorieParsing| della programmazione]]