Analizzatore lessicale: differenze tra le versioni

Versione delle 10:00, 12 mar 2011

Versione delle 12:34, 7 mag 2011

Riga 1:

Un '''Analizzatoreanalizzatore lessicale''', a volte chiamato '''scanner''' o '''lexer''', è un programma, o un parte di un programma (vedi [[compilatore|compilatori]] e [[parsing|parsersparser]]), che si occupa di [[analisi lessicale (informatica)|analizzare lessicalmente]] un dato input, genericamente il [[codice sorgente]] di un programma.

Quindi il compito di un analizzatore lessicale è di analizzare uno stream di caratteri in input e produrre in uscita uno stream di tokens''token''.

Il ''token'' è un elemento che ha un tipo e un valore, ''[[lessema'']].

I tokens''token'' costituiscono gli elementi base su cui andrà ad operare un [[analizzatore sintattico]].

L'individuazione di tokens''token'' all'interno di uno stream di caratteri è effettuata attraverso "[[pattern"]] (schemi, modelli).

== Funzionamento ==

Come scritto prima l'analizzatore lessicale individua i tokens''token'' attraverso i patternspattern, prendiamo ad esempio questi patternspattern:

<code>

cifra = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0

Riga 16:

</code>

Dove il simbolo <code>|</code> indica l'[[operatore ''or''logico]] inglese OR, l'alternativa.

Il simbolo ''*'', asterisco, indica che l'elemento che lo precede può essere ripetuto zero o più volte.

Riga 25:

<code>123 + 141 / 725</code>

Ci aspetteremo che l'output sia formato dai seguenti tokens''token'':

{|

! Tipo ''token''

! Lessema (valore del ''token'')

|-

| numero

Riga 48:

Da notare come gli spazi bianchi vengano saltati.

Per effettuare questo lavoro gli analizzatori lessicali si basano su un [[automa a stati finiti deterministico]]. Si parte da uno stato iniziale, e ci si sposta negli altri stati in base al carattere in ingresso sino a quando non si raggiunge uno stato di accettazione nel quale si può inviare il ''token'' in output.

Ad esempio per il nostro modello avremmo un automa simile al seguente:

[[Immagine:analizzatorelessicale1.png]]

Si inizia dallo stato iniziale (1), e in base al carattere in arrivo ci si può spostare allo stato 2 o al 4. Se arriva una cifra ci si sposterà al 2, e rimarremmo qui finché non arriva qualcosa di diverso da una cifra, in tal caso passeremo allo stato 3. In questo stato, stato di riconoscimento, produrremmo il ''token'', in questo caso di tipo numero, e lo invieremo in uscita. Dopo il riconoscimento si tornerà allo stato iniziale sempre con lo stesso valore di prima.

Nel caso del nostro esempio, <code>123 + 141 / 725</code>, gli spostamenti tra gli stati sarebbero stati i seguenti:

Riga 80:

| +

| 3

| Produci ''token'' di tipo Numero e valore 123

|-

| +

Riga 88:

| +

| 4

| Produci ''token'' di tipo Operatore e valore +

|-

| 1

Riga 108:

| /

| 3

| Produci ''token'' di tipo Numero e valore 141

|}

e cosi via...

== Costruzione di un analizzatore lessicale ==

Un analizzatore lessicale può essere scritto a mano, ma questo comporterebbe un grosso impiego di tempo. In aiuto ai programmatori vengono strumenti di generazione automatica di lexer, quale ad esempio [[Lex]]. Altri strumenti di generazione di analizzatori lessicali sono integrati nei [[generatore di parser|generatori di parsers''parser'']].

==Voci correlate==