Parsing
Da Wikipedia, l'enciclopedia libera.
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 che esegue questo compito.
Di solito i parser non sono scritti a mano ma generati 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.
Indice |
[modifica] Esempio
L'esempio seguente mostra un caso commune 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 tokens 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 tokens come "12*" o "(3" non verrebbero generati.
L'analisi sintattica propriamente detta riceve in input la sequenza dei token e controlla che i tokens 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 e 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.
[modifica] Tipi di parser
 |
Per approfondire, vedi la voce 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.
[modifica] 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 sensibili al contesto, tuttavia, perdono 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.
[modifica] Voci correlate
[modifica] Parser top-down
- Parser LL
- Parser a discesa ricorsiva
- Parser packrat
- Parser di Unger
[modifica] Parser bottom-up
- Parser LR
- Parser SLR
- Parser LALR
- Parser di Earley
- Parser CYK
- Parser GLR
[modifica] Generatori di parser
[modifica] Riferimenti
Questa voce si basa su materiale disponibile sul Free On-line Dictionary of Computing e il suo utilizzo è regolamentato dalla licenza GFDL.
[modifica] Collegamenti esterni
- 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.
