Parsing

In informatica, il parsing è il processo di 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).

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à

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.

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.

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

Esempi di parsers

Parsers top-down

Tra i parsers che usano il top-down parsing:

Parsers bottom-up

Tra i parsers che usano il bottom-up parsing:

Voci correlate

Riferimenti

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.

Informatica

Gourt Home::Gourt :: Parsing