Analizzatore lessicale: differenze tra le versioni

Versione delle 12:08, 8 giu 2006

Versione attuale delle 11:37, 31 dic 2024

(32 versioni intermedie di 28 utenti non mostrate)

Riga 1:

{{F|programmazione|febbraio 2013}}

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

Un '''analizzatore lessicale''' ({{Inglese|'''lexer'''}} o '''''scanner''''') è un programma che effettua l'[[analisi lessicale]] di un dato testo, generalmente il [[codice sorgente]] di un programma, producendo da esso una sequenza di ''[[Token (testo)|token]]''.

Il ''token'' è un elemento che ha un nome e un valore, tipicamente il [[lessema]] ma può trattarsi anche di un insieme di informazioni elementari come il tipo del numero o il punto del programma in cui è definito. I ''token'' costituiscono gli elementi base su cui andrà ad operare un [[analizzatore sintattico]].

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

== Funzionamento ==

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

L'individuazione di ''token'' all'interno di un flusso di caratteri è effettuata attraverso modelli, definiti attraverso delle [[espressioni regolari]]. I seguenti sono un esempio di questi modelli:

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

L'individuazione di tokens all'interno di uno stream di caratteri è effettuata attraverso ''pattern'', in italiano modelli.

=== Funzionamento ===

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

<code>

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

numero = cifra cifra*

operatore = + | - | x | /

</code>

dove il simbolo <code>|</code> indica la [[disgiunzione logica]] OR, mentre l'asterisco indica che l'elemento che lo precede può essere ripetuto zero o più volte.

Dove il simbolo | indica l' ''or'' inglese, l'alternativa.

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

Il modello sopra specifica che una cifra è un numero da 1 a 0, mentre un numero è composto da una o più cifre; un operatore è invece il segno più, meno, per e diviso. Secondo questo modello, la stringa <code>123 + 141 / 725</code> produrrà la seguente sequenza di ''token'', trascurando gli spazi.

Dai modelli sopra riportati abbiamo che una cifra può essere 1 o 2 o 3 .. e così via; un numero è composto da almeno una cifra, e può essere seguito da più cifre. Gli operatori sono quelli classici della matematica.

{|

! Tipo

! Lessema (valore)

|-

| numero

| 123

|-

| operatore

| +

|-

| numero

| 141

|-

| operatore

| /

|-

| numero

| 725

|}

Per effettuare questo lavoro gli analizzatori lessicali si basano su un [[automa a stati finiti deterministico]], strettamente collegati alle [[espressioni regolari]]. 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 uscita. Ad esempio per il nostro modello avremmo un automa simile al seguente:

Se noi diamo in input all'analizzatore lessicale la seguente espressione:

[[File:Automa di un analizzatore lessicale.png]]

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

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.

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

<table>

<tr><th>Tipo token</th><th>Lessema (valore del token)</th></tr>

<tr><td>numero</td><td>123</td></tr>

<tr><td>operatore</td><td>+</td></tr>

<tr><td>numero</td><td>141</td></tr>

<tr><td>operatore</td><td>/</td></tr>

<tr><td>numero</td><td>725</td></tr>

</table>

Nell'esempio precedente, <code>123 + 141 / 725</code>, gli spostamenti tra gli stati sarebbero stati i seguenti:

Da notare come gli spazi bianchi vengano saltati.

{| border="1"

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.

! Carattere

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

! Stato attuale

! Azione

|-

| 1

| 1

| Vai a stato (2)

|-

| 2

| 2

| Vai a stato (2)

|-

| 3

| 2

| Vai a stato (2)

|-

| +

| 2

| Vai a stato (3)

|-

| +

| 3

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

|-

| +

| 1

| Vai a stato (4)

|-

| +

| 4

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

|-

| 1

| 1

| Vai a stato (2)

|-

| 4

| 2

| Vai a stato (2)

|-

| 1

| 2

| Vai a stato (2)

|-

| /

| 2

| Vai a stato (3)

|-

| /

| 3

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

|}

e così via...

== Costruzione di un analizzatore lessicale ==

[[Immagine:analizzatorelessicale1.png]]

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 ''parser'']].

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:

<table border="1">

<tr><th>Carattere</th><th>Stato Attuale</th><th>Azione</th></tr>

<tr><td>1</td><td>1</td><td>Vai a stato (2)</td></tr>

<tr><td>2</td><td>2</td><td>Vai a stato (2)</td></tr>

<tr><td>3</td><td>2</td><td>Vai a stato (2)</td></tr>

<tr><td>+</td><td>2</td><td>Vai a stato (3)</td></tr>

<tr><td>+</td><td>3</td><td>Produci token di tipo Numero e valore 123</td></tr>

<tr><td>+</td><td>1</td><td>Vai a stato (4)</td></tr>

<tr><td>+</td><td>2</td><td>Produci token di tipo Operatore e valore +</td></tr>

<tr><td>1</td><td>1</td><td>Vai a stato (2)</td></tr>

<tr><td>4</td><td>2</td><td>Vai a stato (2)</td></tr>

<tr><td>1</td><td>2</td><td>Vai a stato (2)</td></tr>

<tr><td>/</td><td>2</td><td>Vai a stato (3)</td></tr>

<tr><td>/</td><td>3</td><td>Produci token di tipo Numero e valore 141</td></tr>

</table>

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

==Voci correlate==

*[[Analisi lessicale (informatica)]]

*[[Analisi sintattica]]

*[[Compilatore]]

{{Portale|informatica}}

*[[Parsing]]

[[Categoria:Analisi lessicale]]

[[Categoria:Programmazione]]

[[en:Syntax analysis]]