Newsgroup: it.comp.lang.pascal
Titolo: Analizzatore lessicale di espressioni

PROGETTO: Analizzatore lessicale di espressioni
Il primo passo di un compilatore/esecutore o di un qualsiasi programma che deve elaborare sequenze non banali di dati è l'analisi lessicale. 
Nell'esempio l'input è una sequenza di assegnazioni di espressioni aritmetiche a delle variabili. Ad esempio, una sequenza come questa seguente: 
alfa = 32;
beta = -41;
x    = alfa * beta;
y    = (alfa * beta + x) / x * alfa + beta.
Osserviamo che gli elementi atomici che compongono l'input sono dei caratteri, ma che è possibile individuare delle sequenze di caratteri che, dal punto di vista semantico (ovvero, dal punto di vista del significato di ciò che si sta analizzando) costituiscono unità distinte. La prima riga dell'esempio sopra mostrato deve essere decomposto nelle sequenti parti 
alfa
=
32
;
 
ed interpretare la stringa alfa come il nome di una variabile, il carattere = come il simbolo speciale che separa il nome della variabile dalla espressione che gli si vuole assegnare, la stringa 32 come il numero intero corrispondente, il carattere ; come il simbolo che indica la fine della prima assegnazione (ovvero della prima coppia variabile-espressione). 
I token
--------
Il compito dell'analizzatore lessicale è quello di suddividere la stringa di input in token, ovvero, di raggruppare i caratteri dell'input in modo da formare le unità di significato atomiche in cui è conveniente decomporre l'input. 
Chiaramente, i token in cui suddivedere l'input dipendono dal tipo di testo che si deve analizzare. Nel nostro caso, gli elementi che possiamo individuare sono: 
Identificatori
--------------- 
corrispondenti ai nomi delle variabili. Per semplicità, supponiamo che gli identificatori possano contenere solo caratteri alfanumerici, comincino per un carattere alfabetico e che maiuscolo/minuscolo sia significativo (overro, alfa, aLFa, AlfA ed ALFA sono identificatori diversi). 
Costanti numeriche
------------------- 
si tratta di sequenze composte da cifre numeriche (da caratteri nel'intervallo 0..9). Di cosequenza, i numeri con segno (ed in particolare i numeri negativi) sono decomposti in coppie formate dal simbolo speciale corrispondente al segno e dalla parte numerica vera e propria. 
Simboli speciali
----------------- 
sono i simboli corrispondenti alle parentesi e agli operatori aritmetici che compaiono nelle espressioni, il carattere ; che separa le assegnazioni, il carattere . che indica la fine della sequenza; il carattere =. Si osservi che nel nostro caso tutti i simboli speciali sono formati da un solo carattere. Riassumendo, i simboli speciali sono: 
( ) + - * / = ; . 
In generale, uno o più spazi bianchi possono apparire tra una qualsiasi coppia di token. Gli spazi bianchi non sono però obbligatori. Ad esempio, nell'ultima assegnazione della sequenza dell'esempio 1 non c'è nessuno spazio bianco tra la coppia di token ( e alfa, come non c'è nessuno spazio bianco tra la coppia di token x e ). Inoltre, tale assegnazione è equivalente a 
y=(alfa*beta+x)/x*alfa+beta.
 
dove non ci sono spazi bianchi tra i token. Possiamo quindi dire che gli spazi bianchi tra token devono essere ignorati, anche se, si osservi che le due stringhe alfa beta e alfabeta corrispondono a cose molto diverse, il primo ad una sequenza di due idenficatori alfa e beta, il secondo ad un unico identificatore alfabeta. 
Nota. Input contenenti sequenze del tipo alfa beta non sono possibili in sequenze di assegnazioni corrette. Questo errore non è però legato alla costruzione di token errati, ma al modo in cui i token sono concatenati--ovvero, si tratta di un errore sintattico. L'analizzatore lessicale non si deve curare di scoprire situazioni di questo tipo, sarà a livello di analisi sintattica che l'errore verrà rilevato. 
Come rappresentare i token 
Supponiamo di utilizzare la seguente struttura dati Pascal per memorizzare i token. 
type token = record 
               tipo: integer;
               id: string;
               val: integer;
             end;
Nella quale i campi sono utilizzati nel seguente modo: 
Il campo tipo contiene un codice numerico che identifica univocamente il token, oppure il valore -1 in caso di errore (ovvero, in caso di lettura di un simbolo speciale che non compare tra quelli ammessi, ad esempio, !). Il fatto che ogni simbolo speciale sia formato da un solo carattere, ci permette di associare come codice di ciascun simbolo speciale il numero d'ordine del corrispondente carattere. Per quanto riguarda i codici di identificatori e numeri invece, basta scegliere due valori che non interferiscono con i precendenti; in particolare, fissiamo 1 per gli identificatori e 2 per i numeri. 
Il campo id viene utilizzato nel caso in cui il token è un identificatore, per memorizzare la stringa dell'identificatore. 
Il campo val viene utilizzato nel caso in cui il token è un numero, per memorizzare il valore del numero. 
La procedura nexttoken 
La procedura principale che si deve scrivere è la 
  procedure nexttoken(var tk: token);
che scandisce l'input alla ricerca del token successivo e ritorna i dati del token nella variabile tk passata per riferimento. 
La procedura deve anche gestire il caso in cui non c'è più alcun token da leggere dato che si è giunti alla fine del file di input (oppure, ci sono solo spazi bianchi prima della fine del fine). Per gestire correttamente questa situazione, si consiglia di assumere che il valor di tipo 0 indichi il token vuoto e che questo è il valore di ritorno della procedura nexttoken nel caso in cui nessun token sia presente prima della fine del file di input. Un'altra possibilità è quella di trasformare la nexttoken in una funzione 
  function nexttoken(var tk: token): boolean;
che ritorna true nel caso in cui venga effettivamente letto un token dal file di input e false nel caso in cui ci si trovi alla fine del file e non ci siano altri token da leggere. Si sconsiglia di gestire la fine file mediante chiamate di eof esterne alla nexttoken. 
Ovviamente, la nexttoken può richiamare altre procedure. In particolare si consiglia di scrivere la 
  procedure getnum(var n: integer);
che si aspetta di trovare in input una sequenza di cifre (ovvero, un numero senza segno) e converte tale sequenza nel corrispondente valore intero (da ritornare in n). Tale procedura termina la lettura dell'input non appena il numero termina (ovvero appena incontra un carattere che non è una cifra). 
E di scrivere la 
  procedure getid(var id: string);
che si aspetta di trovare un identificatore, lo legge e ne ritorna il nome in id. 
Si consiglia inoltre di utilizzare funzioni come le getch e ungetch per la scansione dell'input, in modo da garantire che: 
al momento della chiamata di getnum e getid, quello che si deve cercare di leggere è un numero (il prossimo carattere di input è una cifra numerica) o un identificatore (il prossimo carattere di input è un carattere alfabetico). 
la getnum e la getid consumino tutti e soli i caratteri dell'input del numero e dell'identificatore che devono leggere. Ad esempio, se la getnum viene chiamata quando in input si trova una sequenza che comincia per 
234+alfa*... 
allora la getnum deve consumare solo 234 dalla sequenza di input e garantire che dopo il token 234 sia correttamente riconosciuto il token +. Analogamente, la getid che verrà chiamata dopo aver acquisito +, dovrà consumare solo alfa e garantire la successiva acquisizione di *. 
Nota. La soluzione che si basa sulle funzioni getch e ungetch non è l'unica possibile, nè c'è un unico modo di usare correttamente le suddette funzioni. L'importante è che la soluzione adottata gestisca correttamente i casi particolari discussi precedentemente. Come ulteriore aiuto, si verifichi attentamente che getid non perda il primo carattere dell'identificatore che deve leggere e che getnum non perda la prima cifra del numero da leggere. 
Cosa si deve fare 
Il programma da realizzare deve dividere in token il testo contenuto in un file di nome dati.txt che si trova nella stessa directory del programma in esecuzione. Si fa notare che, il nome del file di input non può essere cambiato e che il programma deve funzionare indipendentemente dalla directory in cui si trova. 
In questa parte del progetto, non interessa verificare che i token siano organizzati in maniera sintatticamente corretta: a livello lessicale si arriva ad un errore solo nel caso in cui si trova un token non valido. 
Come risultato, il programma deve stampare su righe separate i token che compongono l'input, nell'ordine in cui appaiono in input. In particolare, 
per i simboli speciali, si deve stampare il corrispondente carattere; 
per gli identificatori, si deve stampare il codice corrispondente (ovvero, 1) e la stringa dell'identificatore; 
per i numeri, si deve stampare il codice corrsipondente (ovvero, 2) ed il suo valore. 
Dato che i programmi verranno verificati automaticamente, si richiama l'attenzione sul fatto che l'output deve corrispondere esattamente alla descrizione precedentemente fornita. Per maggiore chiarezza, si riporta in appendice l'output che ci si attende dalla analisi lessicale dell'esempio 1. 
Esempio di output 
1 alfa
= 
2 32
;
1 beta 
= 
-
2 41
;
1 x
=
1 alfa
*
1 beta
;
1 y
= 
(
1 alfa
* 
1 beta 
+ 
1 x
) 
/ 
1 x 
*
1 alfa
+ 
1 beta
.
----------------------------------------------
Virgilio Mail - Il tuo indirizzo E-mail gratis
http://mail.virgilio.it
-- 
Posted from [212.216.176.199] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

> PROGETTO: Analizzatore lessicale di espressioni
e che cosa vuoi???? Che ti si faccia il progettino??? Col cazzo!
Cercati Tp Lex e Tp Yacc e leggiti il manuale; poi prendi il libro Griongio
Bruno: Linguaggi formali e compilatori, studiatelo (dopo aver letto il
manuale, eh!) e a quel punto sei in gredo di fare l'esercizio

Non è che per caso segui le lezioni di Panconesi alla Sapienza alla Facoltà
di informatica ????????????
^_____^

E' più chiara la tua spiegazione di quella del professore!!! :-)
Grazie!!!
Cmq getid è stupidissima....
Daniele.

 Cmq getid è stupidissima....
confermo , è molto simile al progetto di prog. 1, se lo avessi ricontrollato
a dovere telo posterei..... sai non mi va di fare figuracce!!!

 a dovere telo posterei..... sai non mi va di fare figuracce!!!
Una domanda:
come fai terminare il file?
Con un carattere ben preciso oppure fai un controllo sul buffer per evitare
il problema che l'ultimo carattere eventualmente giusto non venga
visualizzato?
Daniele.

La mia č una soluzione ricorsiva :faccio scorrere il buffer, se trova un
carattere lettera lo inserisce nella stringa IDENTIFICATORE, se invece č un
altro carattere faccio un controllo sulla stringa: se questa č vuota allora
continuo a scorrere; se invece non č vuota, vuol dire che sono arrivato alla
fine della stringa e la stampo. Tutto questo sotto il controllo di un WHILE
iniziale:
        while not eof (testo) do begin..
NB: la stringa identificatore deve essere scritta tutta su una riga ,
altrimenti se viene spezzata (tipo IDENT<a capo>IFICATORE) viene
interpretata come 2 identificatori, perchč anche se non si vedono i
caratteri tipo <a capo> , <tab> , <fine testo> ci sono e vengono letti.
PS : **mi sembra** che Panconesi abbia detto che il testo finiva con un
PUNTO , ma per essere piů generale ho usato EOF.
ciao ciao ^____^


Infatti ieri ha dato il punto come operatore!
Cmq anche io ho fatto come te, solo con un cicle repeat-until(eof)!
Grazie, Daniele.

ma cosě non si perde l'ultimo carattere? ciao.
steve

 ma cosě non si perde l'ultimo carattere? ciao.
Si ma faccio un ltimo controllo appena uscito dalla procedura...
Daniele.