Automi Finiti, Espressioni Regolari e Analisi Lessicale nella Compilazione

FINITE AUTOMATA e le espressioni regolari

Una macchina a stati finiti o di macchina a stati finiti è un modello matematico di un sistema che accetta una stringa composta da simboli di un alfabeto e determina sé la stringa è la lingua che il controller riconosce.

Formalmente una macchina a stati finiti può essere descritto come una quintupla (S, Σ, T, s, a) quando:

S: è un insieme di stati
È un alfabeto Σ =
T = funzione di transizione
s = stato iniziale
A = insieme degli stati finali o accettare

Forme di rappresentazione del automi a stati finiti

Oltre ad essere in grado di presentare una macchina a stati finiti attraverso la sua definizione formale può essere rappresentata da altre notazioni che sono più comodi e, a volte insipido, le tabelle di transizione più comune, i diagrammi di transizione e le espressioni regolari.

LESSICALE ANALIZZATORE

Il parser ha la funzione principale che la sequenza di caratteri o simboli in alfabeto della lingua e il luogo in categorie conosciuto come unità lessicali. Queste unità sono utilizzate dal parser per determinare sé ciò che è scritto nel programma di origine è grammaticalmente corretta o meno. Alcune delle unità lessicali non sono utilizzati dal parser, ma sono filtrati, con il caso di commenti che documentano il programma ma non usare la grammatica o spazi vuoti che servono a fornire chiarezza alla lettera.

Nella terminologia utilizzata nella costruzione di un parser sono i seguenti:

Pattern .- rappresenta la regola per una sequenza di caratteri è considerata certa unità lessicali.
Lessema .- è il valore attuale di un set di caratteri che soddisfano un modello.
Token .- è il valore associato a una unità lessicale ed è rappresentato come un intero.
.- Caratteri alfabetici sono validi per una sola lingua.
.- Unità lessicali sono le categorie che classificano le stringhe valide in una lingua.

IL RUOLO DELLA analizzatore lessicale
Anche sé il parser è il primo stadio del processo di compilazione non è chi inizia, in quanto ciò rende la sua trasformazione e invia i risultati al parser, che è quello che inizia effettivamente il processo richiedendo un token per l'analizzatore lessicale iniziare a lavorare.
Durante queste fasi è mantenuta una stretta comunicazione con la tabella dei simboli che si concentra informazioni sui soggetti utilizzati nei programmi.

DESCRIZIONE DEL MODELLO
Ci sono 3 modi per descrivere i modelli e sono la descrizione informale che utilizza il linguaggio naturale per descrivere il comportamento della regola lessicale, utilizzando le espressioni regolari e automi a stati finiti come diagrammi di transizione.

SCHEMI DI TRANSIZIONE
Un diagramma di transizione è la rappresentazione grafica di un insieme di stati può essere iniziale, intermedio o finale e può avere una o più uscite per altri Stati.

Gli stati iniziali sono rappresentati da un doppio cerchio e uno zero, l'intermedio da un cerchio e un numero, e termina con un doppio cerchio e l'ultimo numero.
Gli Stati in relazione tra loro con A che hanno un nome che è il carattere o un insieme di caratteri che causano la transizione da uno stato all'altro.

CARATTERISTICHE DEGLI SCHEMI DI TRANSIZIONE
Ogni stato deve essere raggiunta con lo stesso set di caratteri ogni volta che c'è una transizione.
Ogni modello dispone di un selettore di carattere che permette un unico modo per riconoscere il modello da applicare.
Per raggiungere uno stato di accettazione deve essere un passaggio sul personaggio che rompe lo schema di unità lessicali.

DESCRIZIONI INFORMALE di unità lessicali
.- Identifier è una lettera o non seguita da altre lettere, cifre o underscore.
OMMENTI .- iniziano con / * e termina con * / e ciascuno può essere qualsiasi simbolo tranne per la fine del file.
.- EOF indica la fine del file
Errore .- qualsiasi simbolo o conformarsi con le precedenti datori di lavoro.