Specifica di Grammatiche - Gian Franco...

Esercizio 1Specificare la definizione regolare relativa ai simboli lessicali intconst (costante intera) e id (identificatore), sulla base dei seguenti vincoli:

• Una costante intera con più di una cifra non può iniziare con uno zero;

• Una costante intera diversa da zero è opzionalmente qualificata da un segno (parte integrante della costante);

• Un identificatore inizia con un carattere alfabetico ed è seguito da una sequenza (anche vuota) di caratteri alfanumerici, eventualmente separati da caratteri underscore '_';

• In un identificatore, non sono ammesse sequenze di due o più underscore consecutivi e l’underscore non può terminare l’identificatore.

Linguaggi di Programmazione Esercizi Lessico 1

Esercizio 1

Specificare la definizione regolare relativa ai simboli lessicali intconst (costante intera) e id (identificatore), sulla base dei seguenti vincoli:

• Una costante intera con più di una cifra non può iniziare con uno zero;

• Una costante intera diversa da zero è opzionalmente qualificata da un segno (parte integrante della costante);

• Un identificatore inizia con un carattere alfabetico ed è seguito da una sequenza (anche vuota) di caratteri alfanumerici, eventualmente separati da caratteri underscore '_';

• In un identificatore, non sono ammesse sequenze di due o più underscore consecutivi e l’underscore non può terminare l’identificatore.

Linguaggi di Programmazione Esercizi Lessico

lettera ® [A-Za-z]cifra ® [0-9]alfanum ® lettera | cifracifra-iniziale ® [1-9]segno ® + | -intconst ® segno? (cifra-iniziale cifra*) | 0id ® lettera alfanum* ( _ alfanum+)*

2

Esercizio 2Specificare la definizione regolare relativa ai simboli lessicali realconst (costante reale) e id (identificatore), sulla base dei seguenti vincoli:

• Una costante reale si compone di una parte intera (obbligatoria) ed una parte decimale (opzionale);

• La parte intera è separata dalla parte decimale (se espressa) da un punto;

• Una costante reale include il segno '-' se negativa (ma non il segno '+', se positiva);

• La parte intera con più di una cifra non può iniziare con uno zero;

• Un identificatore inizia con un carattere alfabetico ed è seguito da una sequenza (anche vuota) di caratteri alfanumerici;

• Un identificatore non può essere più lungo di quattro caratteri.


Esercizio 2Specificare la definizione regolare relativa ai simboli lessicali realconst (costante reale) e id (identificatore), sulla base dei seguenti vincoli:

• Una costante reale si compone di una parte intera (obbligatoria) ed una parte decimale (opzionale);

• La parte intera è separata dalla parte decimale (se espressa) da un punto;

• Una costante reale include il segno '-' se negativa (ma non il segno '+', se positiva);

• La parte intera con più di una cifra non può iniziare con uno zero;

• Un identificatore inizia con un carattere alfabetico ed è seguito da una sequenza (anche vuota) di caratteri alfanumerici;

• Un identificatore non può essere più lungo di quattro caratteri.


lettera ® [A-Za-z]cifra ® [0-9]alfanum ® lettera | cifracifra-iniziale ® [1-9]segno ® '-'intero ® cifra-iniziale cifra* | 0decimale ® cifra+

realconst ® segno? intero ('.' decimale)?id ® lettera alfanum? alfanum? alfanum?

4

Esercizio 3

Specificare la definizione regolare relativa al simbolo lessicale indirizzo, che rappresenta l'indirizzo civico di una persona, come nei seguenti esempi:

L'indirizzo deve rispettare i seguenti vincoli lessicali:

• La prima riga specifica il nome (in generale, uno o più nomi) e il cognome (uno solo) della persona;

• La seconda riga specifica la via (unico nome preceduto dalla keyword Via) e il numero civico;

• La terza riga specifica il CAP e la città (eventualmente composta da più nomi);

• Ogni elemento sulla stessa riga è separato dal successivo mediante un blank;

• Ogni riga è separata dalla successiva mediante un newline;

• Ogni identificatore (nome, cognome, indirizzo, città) inizia con una maiuscola ed è seguito da una o più minuscole;

• Un nome (o più) della persona può essere abbreviato dal primo carattere seguito dal punto;

• Il numero civico è composto da non più di 3 cifre e non può iniziare con una sequenza di zeri;

• Il CAP è composto da cinque cifre.


Angelo B. RossiVia Europa 14525100 Brescia

Angelo B. Matteo RossiVia Africa 1227100 Pavia

T. BianchiVia Asia 264123 Bastia Franca

5

Esercizio 3

Specificare la definizione regolare relativa al simbolo lessicale indirizzo, che rappresenta l'indirizzo civico di una persona, come nei seguenti esempi:


Angelo B. RossiVia Europa 14525100 Brescia

Angelo B. Matteo RossiVia Africa 1227100 Pavia

T. BianchiVia Asia 264123 Bastia Franca

blank ® ' 'newline ® '\n'maiuscola ® [A-Z]minuscola ® [a-z]cifra ® [0-9]nonzero ® [1-9]id ® maiuscola minuscola+

nome ® id | maiuscola\.num ® nonzero cifra? cifra?cap ® cifra cifra cifra cifra cifraindirizzo ® nome (blank nome)* blank id newline Via blank id blank num newline cap (blank id)+

6

Esercizio 4

Specificare la definizione regolare relativa ad una tabella (non vuota), in cui ogni riga rappresenta nome, cognome e codice fiscale di una persona, come nel seguente esempio,

sulla base dei seguenti vincoli lessicali:

• Nome e cognome iniziano con una lettera maiuscola, seguita da una o più lettere minuscole;

• Il codice fiscale, composto da lettere maiuscole e cifre, è suddiviso in quattro parti: tre lettere per il cognome, tre lettere per il nome, la data di nascita (due cifre per l'anno, una lettera per il mese, giorno del mese compreso tra 01 e 31) ed una stringa alfanumerica di cui il primo carattere e l'ultimo sono lettere mentre i tre caratteri intermedi sono cifre;

• Nome e cognome sono seguiti da uno spazio;

• Ogni riga, ad eccezione dell'ultima, è seguita da un newline.


Luigi Rossi ROSLGI84L14M634UAnna Bianchi BCIANN92A07H584XEnrico Verdi VRDERC67M13S124Y

Esercizio 4

Specificare la definizione regolare relativa ad una tabella (non vuota), in cui ogni riga rappresenta nome, cognome e codice fiscale di una persona, come nel seguente esempio:


maiuscola ® [A-Z]minuscola ® [a-z]cifra ® [0-9]spazio ® ' 'newline ® '\n'id ® maiuscola minuscola+

anno ® cifra ciframese ® maiuscolagiorno ® 0 [1-9] | [1-2] [0-9] | 3 [0-1]cf ® maiuscola maiuscola maiuscola maiuscola maiuscola maiuscola anno mese giorno maiuscola cifra cifra cifra maiuscolapersona ® id spazio id spazio cf tabella ® persona (newline persona)*

Luigi Rossi ROSLGI84L14M634UAnna Bianchi BCIANN92A07H584XEnrico Verdi VRDERC67M13S124Y

Esercizio 5

Specificare la definizione regolare relativa ad una lista (anche vuota) di elementi, in cui ogni elemento è unidentificatore o un numero, come nel seguente esempio,


• Un identificatore inizia con una lettera ed è seguito da almeno due caratteri alfanumerici.

• Un numero è composto da una parte intera (una o più cifre) ed opzionalmente da una parte decimale (un punto seguito da due cifre); la parte intera con più di una cifra non può iniziare con uno zero; un numero può avere un segno negativo (ma non positivo).

• Gli elementi della lista sono separati tra loro da una virgola e da uno spazio.


[a2b, 25, 0, AAzxy, 0.12, 13.00, stella, 100, S289aa, 123.65, zeta]

Esercizio 5

Specificare la definizione regolare relativa ad una lista (anche vuota) di elementi, in cui ogni elemento è un identificatore oun numero, come nel seguente esempio,


• Un identificatore inizia con una lettera ed è seguito da almeno due caratteri alfanumerici.

• Un numero è composto da una parte intera (una o più cifre) ed opzionalmente da una parte decimale (un punto seguito da due cifre); la parte intera con più di una cifra non può iniziare con uno zero; un numero può avere un segno negativo (ma non positivo).

• Gli elementi della lista sono separati tra loro da una virgola e da uno spazio.


[a2b, 25, 0, AAzxy, 0.12, 13.00, stella, 100, S289aa, 123.65, zeta]

lettera ® [a-zA-Z]nonzero ® [1-9]cifra ® 0 | nonzerospazio ® ' 'punto ® '.'alfanum ® lettera | cifraid ® lettera alfanum alfanum alfanum*intero ® 0 | nonzero cifra*num ® -? intero (punto cifra cifra)?elem ® id | numlista ® [ (elem (, spazio elem)*)? ]

Esercizio 6

Specificare la definizione regolare relativa ad una lista (anche vuota) di tuple, in cui ogni elemento di una tupla può essere una stringa, un numero intero, un numero reale o una costante booleana, come nel seguente esempio,


• Ogni tupla (racchiusa tra parentesi) contiene almeno due elementi, separati tra loro da una virgola.

• Le tuple non hanno separatori tra loro.

• Una stringa (anche vuota) è delimitata da due doppi apici e può contenere caratteri alfanumerici, spazi e doppi apici (per evitare ambiguità, questi ultimi devono essere preceduti dal backslash).

• Un numero intero diverso da zero non può iniziare con la cifra 0.

• Un numero reale ha una parte intera ed una parte decimale, separate da un punto.

• La parte intera diversa da zero di un numero reale non può iniziare con la cifra 0.

• I numeri possono essere preceduti dal segno.


[("alfa",+10,12.34,true)("\"beta\"",false)("Gamma 25",0.12,false)]

Esercizio 6

Specificare la definizione regolare relativa ad una lista (anche vuota) di tuple, in cui ogni elemento di una tupla può essere una stringa, un numero intero, un numero reale o una costante booleana, come nel seguente esempio:


[("alfa",+10,12.34,true)("\"beta\"",false)("Gamma 25",0.12,false)]

lettera ® [a-zA-Z]nonzero ® [1-9]cifra ® 0 | nonzeropunto ® '.'apici ® '"'alfanum ® lettera | cifrastringa ® apici (alfanum | spazio | '\'apici)* apiciintero ® (+|-)?(0 | nonzero cifra*)reale ® intero punto cifra+

booleano ® true | falseelemento ® stringa | intero | reale | booleanotupla ® '('elemento (,elemento)+')'lista ® '['tupla*']'

Esercizio 7

Specificare la definizione regolare relativa ad un insieme (anche vuoto) di identificatori, come nel seguenteesempio,


• ogni identificatore è separato dal successivo da una virgola seguita da uno spazio;

• un identificatore inizia con una lettera maiuscola ed è seguito da zero o più caratteri alfanumerici;

• un identificatore può includere caratteri underscore;

• un underscore non può seguire un altro underscore e nemmeno essere l'ultimo carattere dell'identificatore.


{Alfa, Beta22, Gamma_1_delta, Luna_Sole_stelle, Xilofono_1_2_345_omega}

Esercizio 7

Specificare la definizione regolare relativa ad un insieme (anche vuoto) di identificatori, come nel seguenteesempio,


• ogni identificatore è separato dal successivo da una virgola seguita da uno spazio;

• un identificatore inizia con una lettera maiuscola ed è seguito da zero o più caratteri alfanumerici;

• un identificatore può includere caratteri underscore;

• un underscore non può seguire un altro underscore e nemmeno essere l'ultimo carattere dell'identificatore.


{Alfa, Beta22, Gamma_1_delta, Luna_Sole_stelle, Xilofono_1_2_345_omega}

maiuscola ® [A-Z]minuscola ® [a-z]lettera ® maiuscola | minuscolacifra ® [0-9]underscore ® '_'spazio ® ' 'alfanum ® lettera | cifraid ® maiuscola ((underscore ? alfanum)+)*insieme ® '{' (id (, spazio id)*) ? '}'

Esercizio 8

Specificare la definizione regolare relativa ad una lista (anche vuota) di record composti da tre elementi: una parola, un numero (senza segno) ed un insieme (anche vuoto, eventualmente disomogeneo) di parole o numeri,


• Non è ammessa spaziatura;

• Una parola è composta da caratteri alfanumerici ed underscore (questi ultimi non possono essere consecutivi, né iniziare o terminare la parola);

• Un numero può essere un intero o un reale (con parte decimale obbligatoria);

• Non sono ammessi numeri con prefisso di zeri non significativi.


[(sole,10,{}),(12_beta, 0.12,{0,12.35,21}),(Gamma_1_2_tre,128.09,{luna,2_stelle})]

Esercizio 8

Specificare la definizione regolare relativa ad una lista (anche vuota) di record composti da tre elementi: una parola, un numero (senza segno) ed un insieme (anche vuoto, eventualmente disomogeneo) di parole o numeri:


[(sole,10,{}),(12_beta, 0.12,{0,12.35,21}),(Gamma_1_2_tre,128.09,{luna,2_stelle})]

lettera ® [a-zA-Z]nonzero ® [1-9]cifra ® 0 | nonzerounderscore ® '_'punto ® '.'alfanum ® lettera | cifraparola ® alfanum+ (underscore alfanum+)*intera ® 0 | (nonzero cifra*)decimale ® cifra+

numero ® intera (punto decimale)?atomo ® parola | numeroinsieme ® { (atomo ( , atomo)*)? }record ® '(' parola, numero, insieme ')'lista ® '[' (record ( , record)*)? ']'

Esercizio 9

Specificare la definizione regolare relativa ad una lista (anche vuota) di numeri complessi, come nel seguente esempio:


• Un numero complesso è rappresentato da una coppia (parte reale, parte immaginaria);

• Ognuna delle due parti è rappresentata da un numero, eventualmente con segno, avente una parte intera, opzionalmente una parte decimale (almeno una cifra) e, infine, opzionalmente una parte esponenziale (rappresentata da E seguita da un intero, eventualmente con segno);

• La parte intera non contiene zeri non significativi;

• Il linguaggio è libero dal formato: ogni elemento lessicale (numero, parentesi, virgola) può essere separato dagli altri mediante spazi bianchi e/o tab e/o newline.


[ (1, 24.66),(0.12, +3) ( 1.845, 1.23E20 ) , (33E4, 26.80E3) ]

Esercizio 9

Specificare la definizione regolare relativa ad una lista (anche vuota) di numeri complessi, come nel seguente esempio:


[ (1, 24.66),(0.12, +3) ( 1.845, 1.23E20 ) , (33E4, 26.80E3) ]

spazio ® ' ' | '\t' | '\n' | enonzero ® [1-9]cifra ® 0 | nonzeropunto ® '.'intera ® 0 | (nonzero cifra*)decimale ® cifra+

intera_con_segno ® (+|-)? interaesponenziale ® E intera_con_segno numero ® intera_con_segno (punto decimale)? esponenziale?complesso ® spazio '(' spazio numero spazio , spazio numero spazio ')' spaziolista ® spazio '[' (complesso (, complesso)*)? ']' spazio

Esercizio 10

Specificare la definizione regolare relativa ai seguenti simboli lessicali di un linguaggio di programmazione:

• Identificatore: stringa alfanumerica, di lunghezza compresa tra due e quattro caratteri, che inizia con una lettera e termina con una cifra;

• Costante intera: sequenza di cifre priva di zeri non significativi;

• Costante stringa (anche vuota): racchiusa tra doppi apici e contenente qualsiasi carattere diverso da doppi apici e newline;

• Costante booleana: true o false;

• Commento: stringa di caratteri che inizia con # e termina con newline.


Esercizio 10


• Identificatore: stringa alfanumerica, di lunghezza compresa tra due e quattro caratteri, che inizia con una lettera e termina con una cifra;

• Costante intera: sequenza di cifre priva di zeri non significativi;

• Costante stringa (anche vuota): racchiusa tra doppi apici e contenente qualsiasi carattere diverso da doppi apici e newline;

• Costante booleana: true o false;

• Commento: stringa di caratteri che inizia con # e termina con newline.


lettera ® [A-Za-z]minuscola ® [a-z]nonzero ® [1-9]cifra ® 0 | nonzeroalfanum ® lettera | cifranewline ® '\n'id ® lettera alfanum? alfanum? cifraintconst ® nonzero cifra* | 0strconst ® \"(~[\n\"])*\"boolconst ® true | falsecommento ® #(~\n)*\n

Esercizio 11


• Commento: stringa (non vuota) di caratteri che inizia con -- e termina con newline;

• Costante intera: sequenza di cifre priva di zeri non significativi, con segno opzionale;

• Costante reale: costituita da una parte intera (obbligatoria, priva di zeri non significativi), un punto ed una parte reale (opzionale, priva di zeri non significativi), con segno opzionale;

• Identificatore: sequenza di caratteri alfanumerici, eventualmente separati dal carattere underscore, il quale però non può stare né all'inizio né alla fine dell'identificatore, e nemmeno dopo un altro underscore.


Esercizio 11


• Commento: stringa (non vuota) di caratteri che inizia con -- e termina con newline;

• Costante intera: sequenza di cifre priva di zeri non significativi, con segno opzionale;

• Costante reale: costituita da una parte intera (obbligatoria, priva di zeri non significativi), un punto ed una parte reale (opzionale, priva di zeri non significativi), con segno opzionale;

• Identificatore: sequenza di caratteri alfanumerici, eventualmente separati dal carattere underscore, il quale però non può stare né all'inizio né alla fine dell'identificatore, e nemmeno dopo un altro underscore.


lettera ® [A-Za-z]nonzero ® [1-9]cifra ® 0 | nonzeronewline ® '\n'dot ® '.'underscore ® '_'commento ® -- (~newline)+ newlineintconst ® (+|-)? (nonzero cifra* | 0)realpart ® cifra* nonzerorealconst ® intconst dot realpart?id ® lettera+ (underscore lettera+)*

Esercizio 12


• Commento: stringa (non vuota) di caratteri che inizia con e termina con un tab oppure con un newline;

• Costante intera: sequenza di cifre priva di zeri non significativi, con segno opzionale per numeri diversi da 0;

• Identificatore: sequenza illimitata di caratteri alfanumerici, che inizia con due lettere e termina con dueo tre cifre.


Esercizio 12


• Commento: stringa (non vuota) di caratteri che inizia con e termina con un tab oppure con un newline;

• Costante intera: sequenza di cifre priva di zeri non significativi, con segno opzionale per numeri diversi da 0;

• Identificatore: sequenza illimitata di caratteri alfanumerici, che inizia con due lettere e termina con dueo tre cifre.


lettera ® [A-Za-z]nonzero ® [1-9]cifra ® 0 | nonzerotab ® '\t'newline ® '\n'commento ® -- (~(newline | tab))+(newline | tab)intconst ® ((+|-)? (nonzero cifra*)) | 0id ® lettera lettera alphanum* cifra cifra cifra?

Esercizio 13

Specificare la definizione regolare relativa ad un assegnamento di una variabile con una espressione aritmetica che coinvolge altre variabili e numeri, come nel seguente esempio:


• L'assegnamento è specificato su una sola linea e termina con un newline;

• Ogni elemento nell'assegnamento è separato dal successivo (se esiste) da uno spazio;

• Una variabile è una stringa alfanumerica, di lunghezza massima di tre caratteri, che inizia con una lettera;

• I numeri sono interi senza segno e senza zeri non significativi.


a12 = b + C3 D2s * 24 / z + 1

Esercizio 13

Specificare la definizione regolare relativa ad un assegnamento di una variabile con una espressione aritmetica che coinvolge altre variabili e numeri, come nel seguente esempio:


• L'assegnamento è specificato su una sola linea e termina con un newline;

• Ogni elemento nell'assegnamento è separato dal successivo (se esiste) da uno spazio;

• Una variabile è una stringa alfanumerica, di lunghezza massima di tre caratteri, che inizia con una lettera;

• I numeri sono interi senza segno e senza zeri non significativi.


lettera ® [A-Za-z]nonzero ® [1-9]cifra ® 0 | nonzeroalfanum ® lettera | cifraspazio ® ' 'newline ® '\n'num ® nonzero cifra* | 0id ® lettera alfanum? alfanum?operando ® id | numoperatore ® '+' | '-' | '*' | '/' assegnamento ® id spazio = spazio operando (spazio operatore spazio operando)* newline

a12 = b + C3 D2s * 24 / z + 1

Esercizio 14

Specificare la definizione regolare relativa ad una tabella (non vuota), in cui ogni riga rappresenta codice, nome, quantità e prezzo di un prodotto, come nel seguente esempio,


• Il codice è una sequenza di quattro cifre che non può iniziare con zero;

• Il nome inizia con una lettera maiuscola, seguita da una o più lettere minuscole;

• La quantità è un numero intero maggiore di zero e minore di 100;

• Il prezzo è un numero maggiore di zero, con parte decimale di due cifre, senza zeri non significativi nella parte intera.

• Ogni elemento nella riga è separato dal successivo da uno spazio;

• Ogni riga, ad eccezione dell'ultima, è separata dalla successiva da un newline.


8892 Sedia 4 28.501366 Tavolo 1 125.753244 Lampada 2 74.00

Esercizio 14Specificare la definizione regolare relativa ad una tabella (non vuota), in cui ogni riga rappresenta codice, nome, quantità e prezzo di un prodotto, come nel seguente esempio,


• Il codice è una sequenza di quattro cifre che non può iniziare con zero;

• Il nome inizia con una lettera maiuscola, seguita da una o più lettere minuscole;

• La quantità è un numero intero maggiore di zero e minore di 100;

• Il prezzo è un numero maggiore di zero, con parte decimale di due cifre, senza zeri non significativi nella parte intera.

• Ogni elemento nella riga è separato dal successivo da uno spazio;



maiuscola ® [A-Z]minuscola ® [a-z]nonzero ® [1-9]cifra ® 0 | nonzerospazio ® ' 'newline ® '\n'nome ® maiuscola minuscola+

codice ® nonzero cifra cifra cifra quantita ® nonzero cifra?prezzo ® nonzero cifra* '.' cifra cifra | 0 '.' (nonzero cifra | cifra nonzero) prodotto ® codice spazio nome spazio quantita spazio prezzotabella ® prodotto (newline prodotto)*

8892 Sedia 4 28.501366 Tavolo 1 125.753244 Lampada 2 74.00

Esercizio 15

Specificare la definizione regolare relativa ad una tabella (non vuota), in cui ogni riga rappresenta codice, descrizione, dimensioni e peso di un prodotto, come nel seguente esempio:


• Il codice inizia con tre cifre e termina con due lettere maiuscole, ma non può iniziare con uno zero.

• La descrizione è composta da una stringa non vuota di lettere minuscole, eventualmente separate da spazi. Nel caso in cui esistano spazi (e solo in tal caso), è richiesto l'uso dei doppi apici.

• Le dimensioni sono espresse da una terna di numeri interi (diversi da zero) racchiusa tra parentesi tonde, qualificati dall'unità di misura (mm o cm) e separati da uno spazio;

• Il peso si compone di una parte intera (diversa zero) ed opzionalmente da una parte decimale composta da una o due cifre. La parte decimale non può terminare con uno zero. Il peso è qualificato dall'unità di misura (g o Kg).

• Ogni elemento nella riga è separato dal successivo con uno spazio.



324AX pila (2cm 8mm 1cm) 25g158CE "lampada da tavolo" (20cm 18cm 28cm) 1.55Kg208SG sedia (40cm 45cm 80cm) 6Kg652PL "temperino in legno" (6mm 8cm 6mm) 22.5g

Esercizio 15

Specificare la definizione regolare relativa ad una tabella (non vuota), in cui ogni riga rappresenta codice, descrizione, dimensioni e peso di unprodotto, come nel seguente esempio:


324AX pila (2cm 8mm 1cm) 25g158CE "lampada da tavolo" (20cm 18cm 28cm) 1.55Kg208SG sedia (40cm 45cm 80cm) 6Kg652PL "temperino in legno" (6mm 8cm 6mm) 22.5g

maiuscola ® [A-Z]minuscola ® [a-z]apici ® \"nonzero ® [1-9]cifra ® 0 | nonzerospazio ® ' 'newline ® '\n'intero ® nonzero cifra* decimale ® '.' cifra? nonzeroundim ® [mc]m unpeso ® K?gcodice ® nonzero cifra cifra maiuscola maiuscolaparola ® minuscola+

descrizione ® parola | (apici parola (spazio parola)+ apici) dimensione ® intero undimdimensioni ® '(' dimensione spazio dimensione spazio dimensione ')'peso ® intero decimale?prodotto ® codice spazio descrizione spazio dimensioni spazio pesotabella ® prodotto (newline prodotto)*

Esercizio 16

Specificare la definizione regolare relativa ai simboli identifier e num, sulla base dei seguenti vincoli lessicali:

• Un identifier è composto da almeno tre caratteri alfanumerici, ha un prefisso (non vuoto) di lettere edun suffisso (anche vuoto) di cifre, come nei seguenti esempi: alfa, ab3, abc, a34, M240, Lt2, gH27, z32158.

• Un num è una costante (senza segno) intera o reale. Nel primo caso, non sono inclusi zeri non significativi. Nel secondo caso, sia la parte intera che la parte decimale (composta da almeno una cifra) non include zeri non significativi, come nei seguenti esempi: 0, 2, 10, 124, 0.2, 12.01, 345.3456700001


Esercizio 16

Specificare la definizione regolare relativa ai simboli identifier e num, sulla base dei seguenti vincoli lessicali:

• Un identifier è composto da almeno tre caratteri alfanumerici, ha un prefisso (non vuoto) di lettere edun suffisso (anche vuoto) di cifre, come nei seguenti esempi: alfa, ab3, abc, a34, M240, Lt2, gH27, z32158.

• Un num è una costante (senza segno) intera o reale. Nel primo caso, non sono inclusi zeri non significativi. Nel secondo caso, sia la parte intera che la parte decimale (composta da almeno una cifra) non include zeri non significativi, come nei seguenti esempi: 0, 2, 10, 124, 0.2, 12.01, 345.3456700001


lettera ® [A-Za-z]nonzero ® [1-9]cifra ® 0 | nonzerointero ® nonzero cifra* | 0decimale ® '.' cifra* nonzeronum ® intero decimale?identifier ® lettera+ (lettera lettera | lettera cifra | cifra cifra) cifra*

Esercizio 17

Dato un alfabeto S = {a, b, c}, si chiede di specificare l'espressione regolare delle stringhe che contengonoal più due b non consecutivi.


Esercizio 17

Dato un alfabeto S = {a, b, c}, si chiede di specificare l'espressione regolare delle stringhe che contengonoal più due b non consecutivi.


(a | c)* | (a | c)* b (a | c)* | (a | c)* b (a | c)+ b (a | c)*

Esercizio 18

Dato un alfabeto S = {a, b, c}, si chiede di specificare l'espressione regolare delle stringhe che contengonoesattamente tre b separati fra loro da altri caratteri.


Esercizio 18

Dato un alfabeto S = {a, b, c}, si chiede di specificare l'espressione regolare delle stringhe che contengonoesattamente tre b separati fra loro da altri caratteri.


(a | c)* b (a | c)+ b (a | c)+ b (a | c)*

Esercizio 19

Specificare la definizione regolare relativa ai simboli parola e numero, sulla base dei seguenti vincoli lessicali:

• Una parola è composta da almeno tre caratteri alfanumerici, ha un prefisso (non vuoto) di lettere ed un suffisso (non vuoto) di cifre, come nei seguenti esempi: sole25, k25, M55, K200, kL5, Aa2, w123456789.

• Un numero è una costante intera o reale, opzionalmente preceduta dal segno. Se intera, non sono inclusi zeri non significativi. Se reale, sia la parte intera che la parte decimale (composta da almeno due cifre) non include zeri non significativi, come nei seguenti esempi: 0, 2, +0, +10, 124, 0.24, 15.07, 123.450009.


Esercizio 19

Specificare la definizione regolare relativa ai simboli parola e numero, sulla base dei seguenti vincoli lessicali:

• Una parola è composta da almeno tre caratteri alfanumerici, ha un prefisso (non vuoto) di lettere ed un suffisso (non vuoto) di cifre, come nei seguenti esempi: sole25, k25, M55, K200, kL5, Aa2, w123456789.

• Un numero è una costante intera o reale, opzionalmente preceduta dal segno. Se intera, non sono inclusi zeri non significativi. Se reale, sia la parte intera che la parte decimale (composta da almeno due cifre) non include zeri non significativi, come nei seguenti esempi: 0, 2, +0, +10, 124, 0.24, 15.07, 123.450009.


lettera ® [A-Za-z]nonzero ® [1-9]cifra ® 0 | nonzerosegno ® + | -intero ® segno? (nonzero cifra* | 0)decimale ® '.' (cifra+ nonzero | cifra 0)numero ® intero decimale?parola ® lettera+ (lettera | cifra) cifra+

Esercizio 20

Specificare la definizione regolare relativa ai simboli name e number, sulla base dei seguenti vincoli lessicali:

• Un name, comprendente almeno cinque caratteri alfanumerici di cui almeno due lettere e almeno duecifre, è diviso in due parti, di cui la prima solo di lettere e la seconda solo di cifre, come nei seguenti esempi: alba25, Yk1123, mhp60, wQ201, odissea2001.

• Un number è composto necessariamente da una parte intera (opzionalmente preceduta dal segno), opzionalmente seguita da una parte decimale. Entrambe le parti non includono zeri non significativi. Èopzionalmente presente come suffisso anche una parte esponenziale, composta dal carattere E seguito da una parte intera (l'esponente) diversa da zero e senza zeri non significativi, come nei seguenti esempi: 0, 3, +0, +20, 347E12, 0.7E3, 12.09, -431.990002E+21.


Esercizio 20

Specificare la definizione regolare relativa ai simboli name e number, sulla base dei seguenti vincoli lessicali:

• Un name, comprendente almeno cinque caratteri alfanumerici di cui almeno due lettere e almeno duecifre, è diviso in due parti, di cui la prima solo di lettere e la seconda solo di cifre, come nei seguenti esempi: alba25, Yk1123, mhp60, wQ201, odissea2001.

• Un number è composto necessariamente da una parte intera (opzionalmente preceduta dal segno), opzionalmente seguita da una parte decimale. Entrambe le parti non includono zeri non significativi. Èopzionalmente presente come suffisso anche una parte esponenziale, composta dal carattere E seguito da una parte intera (l'esponente) diversa da zero e senza zeri non significativi, come nei seguenti esempi: 0, 3, +0, +20, 347E12, 0.7E3, 12.09, -431.990002E+21.


lettera ® [A-Za-z]nonzero ® [1-9]cifra ® 0 | nonzerosegno ® + | -intero ® segno? (nonzero cifra* | 0)decimale ® '.' cifra* nonzeroesponente ® E segno? nonzero cifra*number ® intero decimale? esponente?name ® lettera lettera+ (lettera | cifra) cifra+ cifra

Esercizio 21

Specificare la definizione regolare relativa al simbolo identificatore, composto da lettere, cifre e underscore, come nei seguenti esempi: alfa, a25, a_bc_def, alfa_beta_1_23_456, xy_zwq10_658_20. Gli underscore non possono iniziare ne terminare l'identificatore, e nemmeno essere accostati l'uno all'altro. Il prefisso (non vuoto) dell'identificatore non può contenere cifre. Il suffisso (anche vuoto) dell'identificatore non può contenere lettere.


Esercizio 21

Specificare la definizione regolare relativa al simbolo identificatore, composto da lettere, cifre e underscore, come nei seguenti esempi: alfa, a25, a_bc_def, alfa_beta_1_23_456, xy_zwq10_658_20. Gli underscore non possono iniziare ne terminare l'identificatore, e nemmeno essere accostati l'uno all'altro. Il prefisso (non vuoto) dell'identificatore non può contenere cifre. Il suffisso (anche vuoto) dell'identificatore non può contenere lettere.


lettera ® [A-Za-z]cifra ® [0-9]prefisso ® lettera+ (_ lettera+)*suffisso ® cifra* (_ cifra+)*identificatore ® prefisso suffisso

Esercizio 22

Dato un alfabeto composto dai tre caratteri x, y, z, specificare l'espressione regolare delle stringhe che contengono due o tre y non consecutivi.


Esercizio 22

Dato un alfabeto composto dai tre caratteri x, y, z, specificare l'espressione regolare delle stringhe che contengono due o tre y non consecutivi.


(x | z)* y (x | z)+ y (x | z)* ((x | z)+ y (x | z)*)?

Esercizio 23

Specificare la definizione regolare relativa ad una tabella (anche vuota), in cui ogni riga contiene i dati di una persona descritta da nome (anche più di uno), cognome (anche più di uno), via, numero civico (massimo 3 cifre, non inizia con 0), città (composta eventualmente da più nomi) e provincia (identificata dalla sigla tra parentesi), come nel seguente esempio:

È richiesto che la specifica sia conforme alla spaziatura e alla punteggiatura indicata nell'esempio.


Andrea Lorenzi, Via Italia 135, Urago Mincio (PV)Rita Sandra De Benedetti, Via Alberelle 8, Panoramico (BG)Angelo Rinaldi, Via Sentieri 18, Monte Alto Toscano (GR)

Esercizio 23

Specificare la definizione regolare relativa ad una tabella (anche vuota), in cui ogni riga contiene i dati di una persona descritta da nome (anche più di uno), cognome (anche più di uno), via, numero civico (massimo 3 cifre, non inizia con 0), città (composta eventualmente da più nomi) e provincia (identificata dalla sigla tra parentesi), come nel seguente esempio:

È richiesto che la specifica sia conforme alla spaziatura e alla punteggiatura indicata nell'esempio.


Andrea Lorenzi, Via Italia 135, Urago Mincio (PV)Rita Sandra De Benedetti, Via Alberelle 8, Panoramico (BG)Angelo Rinaldi, Via Sentieri 18, Monte Alto Toscano (GR)

maiuscola [A-Z]minuscola [a-z]nonzero [1-9]cifra nonzero | 0numero nonzero cifra? cifra?spazio ' 'newline '\n'ident maiuscola minuscola+

idents ident (spazio ident)*

riga idents , spazio Via spazio idents spazio numero , spazio idents spazio '(' maiuscola maiuscola ')'tabella riga (newline riga)* | e

Esercizio 24

Specificare la definizione regolare relativa al simbolo parola, composto da lettere e cifre. Le cifre non possono iniziare ne terminare l'identificatore, e devono sempre essere separate fra loro. Il prefisso (non vuoto) della parola non può contenere minuscole. Il suffisso (eventualmente vuoto) della parola non può contenere maiuscole, come nei seguenti esempi: CASA, Sole, C9alfa, SOLE2LUNA5STELLA4cometa6m,AB7CDEalfa3beta4gamma.


Esercizio 24

Specificare la definizione regolare relativa al simbolo parola, composto da lettere e cifre. Le cifre non possono iniziare ne terminare l'identificatore, e devono sempre essere separate fra loro. Il prefisso (non vuoto) della parola non può contenere minuscole. Il suffisso (eventualmente vuoto) della parola non può contenere maiuscole, come nei seguenti esempi: CASA, Sole, C9alfa, SOLE2LUNA5STELLA4cometa6m,AB7CDEalfa3beta4gamma.


maiuscola ® [A-Z]minuscola ® [a-z]cifra ® [0-9]prefisso ® maiuscola+ (cifra maiuscola+)*suffisso ® minuscola* (cifra minuscola+)*parola ® prefisso suffisso

Esercizio 25

Dato un alfabeto { x, y, z }, specificare l'espressione regolare di tutte e sole le stringheche non iniziano con una x, includono almeno due y e non contengono y consecutivi.


Esercizio 25

Dato un alfabeto { x, y, z }, specificare l'espressione regolare di tutte e sole le stringheche non iniziano con una x, includono almeno due y e non contengono y consecutivi.


z* (z (x | z)* )? y (x | z)+ y (x |z)* ((x | z)+ y (x |z)* )*

Esercizio 26

Dato un alfabeto { a, b, c, d }, specificare l'espressione regolare di tutte e sole le stringhe che non iniziano con c e nemmeno con d, includono o due o tre c, non contengono c consecutivi, e non terminano con c.


Esercizio 26

Dato un alfabeto { a, b, c, d }, specificare l'espressione regolare di tutte e sole le stringhe che non iniziano con c e nemmeno con d, includono o due o tre c, non contengono c consecutivi, e non terminano con c.


(a | b)+ (a | b | d)* c (a | b | d)+ c (a | b | d)+ (c (a | b | d)+)?

Esercizio 27

Specificare la definizione regolare relativa ad una tabella non vuota in cui ogni riga descrive uno studente in termini di nome (eventualmente più di uno) cognome (eventualmente più di uno), data di nascita (giorno-mese-anno) e matricola, come nel seguente esempio:

sulla base dei seguenti vincoli lessicali:• Nome e cognome iniziano con una lettera maiuscola, la quale è seguita da una o più

lettere minuscole;• Nella data di nascita, il giorno è compreso tra 01 e 31, il mese tra 01 e 12, l'anno tra 00

e 99;• La matricola è composta da quattro o cinque cifre;

• Ogni elemento della riga (ad eccezione dell'ultimo) è seguito da uno spazio;

• Ogni riga (ad eccezione dell'ultima) è seguita da un newline.


Angelo Albini 250295 8734Linda Sofia Crespi Arnoldi 141197 10451Matteo Giuliano Gatti 020796 9800Serena Giulia Antonia Re 230594 7543

Esercizio 27

Specificare la definizione regolare relativa ad una tabella non vuota in cui ogni riga descrive uno studente in termini di nome (eventualmente più di uno) cognome (eventualmente più di uno), data di nascita (giorno-mese-anno) e matricola, come nel seguente esempio:


Angelo Albini 250295 8734Linda Sofia Crespi Arnoldi 141197 10451Matteo Giuliano Gatti 020796 9800Serena Giulia Antonia Re 230594 7543

maiuscola ® [A-Z]minuscola ® [a-z]cifra ® [0-9]nonzero ® [1-9]spazio ® ' 'newline ® '\n'id ® maiuscola minuscola+

anno ® cifra ciframese ® 0 nonzero | 1 [0-2]giorno ® 0 nonzero | [1-2] cifra | 3 [0-1]nascita ® giorno - mese - annomatricola ® cifra cifra cifra cifra cifra?studente ® id (spazio id)+ spazio nascita spazio matricolatabella ® studente (newline studente)*

Esercizio 28

È dato l'alfabeto S = { a, b }. Specificare l'espressione regolare di tutte e sole le stringhe che non iniziano con ab.


Esercizio 28

È dato l'alfabeto S = { a, b }. Specificare l'espressione regolare di tutte e sole le stringhe che non iniziano con ab.


e | a | b | (aa | ba | bb) .*

Esercizio 29

Dato l’alfabeto Σ = {1, 2, 3}, specificare l’espressione regolare di tutte e sole le stringhe che non iniziano con due cifre uguali.


Esercizio 29

Dato l’alfabeto Σ = {1, 2, 3}, specificare l’espressione regolare di tutte e sole le stringhe che non iniziano con due cifre uguali.


ε | . | (1~1 | 2~2 | 3~3) .*

Esercizio 30

Dato l’alfabeto Σ = {0,1,2,3,4,5,6,7,8,9}, specificare la definizione regolare del simbolo lessicale numpari, in cui ogni stringa del linguaggio rappresenta un numero naturale pari (incluso lo zero) privo di zeri non significativi.


Esercizio 30

Dato l’alfabeto Σ = {0,1,2,3,4,5,6,7,8,9}, specificare la definizione regolare del simbolo lessicale numpari, in cui ogni stringa del linguaggio rappresenta un numero naturale pari (incluso lo zero) privo di zeri non significativi.


cifra ® [0-9]nonzero ® [1-9]cifrapari ® [02468]numpari ® cifrapari | nonzero cifra* cifrapari

Specifica di Grammatiche - Gian Franco...

Documents

Transcript of Specifica di Grammatiche - Gian Franco...