Parsing: differenze tra le versioni

Versione delle 22:31, 12 mag 2013

Versione delle 18:14, 28 ago 2013

Riga 1:

In [[informatica]], il '''parsing''' o '''analisi sintattica''' è il processo atto ad analizzare uno stream continuo in [[input]] (letto per esempio da un file o una tastiera) in modo da determinare la sua struttura grammaticale grazie ad una data [[grammatica formale]]. Un '''parser''' è un [[programma (informatica)|programma]] che esegue questo compito.

Di solito i parser non sono scritti a mano, ma generati attraverso dei [[generatore di parser|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 (informatica)|interprete]] o di un [[compilatore]].

Riga 7:

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.

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

Line 17 ⟶ 18:

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.