Parsing
Da Wikipedia, l'enciclopedia libera.
In informatica, il parsing è 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. Il termine parsabile (in inglese parseable) è genericamente applicato al testo o ai dati che possono essere parsati.
Il parsing trasforma il testo in input in una struttura dati, genericamente un albero, il quale è visitabile per ulteriori operazioni e che cattura la gerarchia implicita dell'input. Genericamente, i parsers operano in due fasi, prima identificano i token presenti nell'input (l'analisi lessicale, compito genericamente svolto dall'analizzatore lessicale), ed infine costruiscono un albero di parsing dai tokens ricavati (l'analisi sintattica).
Indice |
[modifica] Linguaggi umani
In alcune traduzioni automatiche e nei sistemi di elaborazione del linguaggio naturale, i testi sono parsati da programmi. Purtroppo le frasi del linguaggio umano non son facilmente parsate dai programmi poiché nella struttura del linguaggio umano ci sono molte ambiguità
[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 context-free poiché con queste grammatiche si possono scrivere parser veloci ed efficienti. Tuttavia le grammatiche context-free sono limitate nella loro espressivita poiché possono descrivere un numero limitato di linguaggi. 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. Altre grammatiche più potenti, tuttavia, perdono in efficienza. Di conseguenza è una strategia comune quella di creare dei parser "rilassati" (con minori vincoli) per le grammatiche context-free le quali accetteranno un superinsieme dei costrutti del linguaggio in considerazione (quindi potrebbero accettare alcuni costrutti non validi); in seguito questi costrutti non ricercati possono essere filtrati dall'output. Genericamente è semplice definire una grammatica context-free che includa tutti i costrutti del linguaggio desiderato; mentre è spesso impossibile creare una grammatica context-free che accetti solo i costrutti desiderabili. I parser genericamente non sono scritti a mano ma generati attraverso dei generatori di parser.
[modifica] Visione generale del processo di parsing
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.
Il primo passo è la generazione di token, o parsing 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.
Il prossimo passo è l'analisi sintattica (in inglese syntax analysis), la quale si occupa di controllare che i tokens formino delle espressioni permesse. Questo lavoro è genericamente eseguito attraverso una grammatica context-free, 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 parsers
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:
- Top-down parsing - 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. Gli LL parsers sono esempi di parsers top-down.
- Bottom-up parsing - 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. Gli LR parsers sono esempi di parsers bottom-up.
Un'altra importante distinzione è quella tra parsers che generano per leftmost derivation o per rightmost derivation (vedi grammatiche context-free). I parser LL genereranno una derivazione leftmost e i parser LR una derivazione rightmost (benché spesso al contrario).
[modifica] Esempi di parsers
[modifica] Parsers top-down
Tra i parsers che usano il top-down parsing:
- Recursive descent parser
- LL parser
- Packrat parser
- Unger parser
[modifica] Parsers bottom-up
Tra i parsers che usano il bottom-up parsing:
- LR parser
- SLR parser
- LALR parser
- Canonical LR parser
- GLR parser
- Earley parser
- CYK parser
- Tomita parser
[modifica] Voci correlate
- ANTLR
- Chart parser
- Compiler-compiler
- GNU bison
- GNU flex
- SableCC
- JavaCC
- Yacc
- Lex
- Lexing
- pass
- Spirit parser framework
- Shallow parsing
[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.
