ESERCIZI SU ANALISI LESSICALE
3/2/2023

18/9/2020

15/6/2020

Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

3 Febbraio 2023

Si consideri la seguente grammatica (scritta in ANTLR)
prg : ’let’ dec ’in’ stm ;
dec : (’int’ Id ’;’)+ ;
exp : Integers | Id | exp ’+’ exp ;
stm : (Id ’=’ exp ’;’)+

dove
• gli Integers sono sequenze non vuote di cifre prefissate dal segno + o -;
• gli Id sono gli identificatori (sequenze non vuote di caratteri);
Esercizi
1. (punti 2) completare l’input di ANTLR con le regole per l’analizzatore lessicale che riguardano
Integers e Id;

2. (punti 9) dare tutte le regole di inferenza per verificare l’uso di identificatori non inizializ-
zati. Ad esempio let int x; int y; in x = 3 + y ; `e un programma erroneo secondo

l’analisi semantica. L’analisi semantica ritorna anche informazioni sull’o↵set degli identifica-
tori (vedi punto 4);

3. (punti 4) verificare, scrivendo l’albero di prova, che il programma seguente sia correttamente
tipato:
let int x; int y; in y = 5 ; x = 3 + y ;

4. (punti 9) definire il codice intermedio per tutti i costrutti del linguaggio, in particolare allo-
cando lo spazio necessario sulla pila per memorizzare i valori degli identificatori (che occupano

sempre 4 byte).

Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

16 Settembre 2022

Esercizio 1 (6 punti) Si definisca un analizzatore lessicale in ANTLR che accetta sequenze di token
che a loro volta sono stringhe (non vuote) sull’alfabeto a, b che contengono un numero pari di
occorrenze di b.
Esercizio 2. (9 punti) Definire le regole di tipo per le dichiarazioni D di un linguaggio e la cui
sintassi `e:

E ::= id | id(A)
A ::= id | id, A
F ::= T id | T id, F
D ::= T id | T id(F){ E } | T id ; D | T id(F){ E } ; D

Il linguaggio ammette ricorsione ma non mutua ricorsione. Il linguaggio non ha sottotipaggio.
Scrive l’albero di prova di

T1 x ; T1 f(T2 y){ x } ; T3 g(T3 z){ g(z) }

Esercizio 3. (9 punti) Il comando case3 E (v1:E1) (v2:E2) (E3) valuta l’espressione E; se il
suo valore `e v1 allora calcola E1, se il suo valore `e v2 allora calcola E2, altrimenti calcola E3 (E,
E1, E2 ed E3 sono espressioni – non contengono il comando break).
1. Definire la funzione code gen che prende in input una espressione case3 e genera il codice
intermedio (il risultato di una espressione si trova sempre in un registro $A0);
2. Come verifica, si generi il codice di
case3 (x+y)
(1: case3 (x) (0: x + y) (1: x+1) (y+1))
(2: y - x)
(0)
(le variabili x ed y si trovano ad o↵set 0 e +4 del frame pointer $FP.)
Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

20 Dic2mbre 2021

Esercizio 1 (6 punti). Sia L il linguaggio sull’alfabeto {a, b, c, d} costituito
da sequenze (non vuote) di token della forma ↵d

dove ↵ `e una qualunque

stringa non vuota che contiene {b, c} e

`e una qualunque stringa non vuota
che contiene {a, c}. Ad esempio ccdc bdc `e una sequenza di token valida,
mentre cc ada `e sbagliata. Si definisca in ANTLR l’analizzatore lessicale per
tokens in L senza utilizzare gli operatori * o +.
Esercizio 2 (8 punti). I seguenti sono potenziali regole di tipo per il
costrutto let in un linguaggio con sottotipaggio (<:). Dire quali regole
sono corrette e quali sbagliate. Per quelle sbagliate dare (a) un codice che
dovrebbe essere tipabile e non lo `e; (b) un codice che `e tipabile e invece non
dovrebbe essere.
1.
` e : T0

` e0 : T00 T0 <: T
` let T x = e in e0 : T00
2.
` e : T0

[x : T] ` e0 : T00 T <: T0
` let T x = e in e0 : T00

3.
` e : T0

[x : T0
] ` e0 : T00 T0 <: T
` let T x = e in e0 : T00

Nel caso in cui nessuna regola sia corretta, (i) dare la regola giusta e (ii)
controllare che i codici di prima siano correttamente tipabili/non tipabili.
Esercizio 3 (10 punti). Definire la funzione code gen per
1. la dichiarazione di funzione void come: void f(T x){ S } ;
2. l’invocazione di funzione f(e) (e `e una espressione).
(Attenzione che `e consentito l’accesso alle variabili globali)
Quindi, assumendo che l’etichetta che corrisponde alla seguente funzione
fact sia fact label, scrivere il codice per
int x = 1 ;
void fact(int n){
if (n >= 0) { x = x*n ; fact(n-1) } ;
}
fact(10) ;
Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

18 Settembre 2020

Nota Bene. Quando avete terminato, fare una foto a tutto il compito col cellulare usando una ap-
plicazione che esegue scansioni, tipo CamScanner, e inviarla per email a cosimo.laneve@unibo.it .

Esercizio 1 (punti 6) Gli identificatori di un linguaggio di programmazione devono iniziare e
terminare con “ ” e tra questi due caratteri ci possono essere solo lettere maiuscole e cifre (in
qualunque ordine) con il vincolo che il numero di lettere e quello delle cifre sia sempre pari. Definire
l’analizzatore lessicale per questi identificatori in ANTLR.
Esercizio 2 (punti 9) Si consideri la seguente grammatica:
S -> S B | y
B -> B x | A x
A -> z | z S y
1. verificare, costruendo la tabella che la grammatica non `e LL(1);
2. modificare la grammatica per renderla LL(1) e dimostrarlo costruendo la tabella.
Esercizio 3 (punti 9) Si consideri il comando iterativo
loop k {S}

dove k `e una costante intera. Quando k > 0, questo comando itera esattamente k volte il corpo S.
Quando k  0 il comando non fa niente.
1. Scrivere la cgen per questo comando;
2. generare il codice intermedio per
loop 34 { x = x+1 ; loop 25 { y = x+y ;} }
assumendo che x sia ad o↵set 4 del record di attivazione corrente e y sia ad o↵set 4 del record
di attivazione dell’ambiente statico immediatamente esterno.
Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

15 Giugno 2020

Nota Bene. Alla fine del compito, fare una foto a tutto il compito col
cellulare e inviare le foto per email a cosimo.laneve@unibo.it .

Esercizio 1 (6 punti). Definire un analizzatore lessicale in ANTLR che ac-
cetta sequenze di token che a loro volta sono stringhe non vuote sull?alfabeto

{a, b} per cui non ci sono mai due occorrenze di b consecutive. Ad esempio
a abaa b aaaab `e un input riconosciuto.
Esercizio 2 (7 punti). Data la grammatica (le lettere minuscole sono
simboli terminali, A `e il simbolo iniziale)

S ! Aa | bAc |Bc | bBa
A ! aA | "
B ! bB | "

Verificare se la grammatica `e LL(1) costruendo l’opportuna tabella. Nel
caso non lo sia, esiste un k per cui essa `e LL(k)? Motivare la risposta.
Esercizio 3 (10 punti). Definire la funzione code gen per il comando

for id := E to E’ do S

La semantica del for `e: (1) si calcolano il valore delle espressioni E e E’ e
siano esse v e v0

; (2) quindi si inizializza id a v e si esegue S se id  v0
; (3)

dopo l’esecuzione di S, si incrementa id e si riverifica se id  v0

. L’iterazione

termina quando id > v0
.

Si applichi tale regola al comando

for x := y to z do z := x+1

assumendo che le variabili x e y si trovino nel record di attivazione corrente

ad o↵set 8 e 12 del $fp, mentre z si trovi nell’ambiente statico immediata-
mente precedente a o↵set 8.

Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

19 Settembre 2019

Esercizio 1 (6 punti). Definire un analizzatore lessicale in ANTLR che ac-
cetta sequenze di token che a loro volta sono stringhe non vuote sull’alfabeto

a, b, c, per cui le occorrenze di a (se ci sono) precedono le occorrenze di b e
di c (se ci sono) e le occorrenze di b precedono quelle di c (se ci sono). Ad
esempio a abbc bcc c `e un input riconosciuto.
Esercizio 2 (9 punti). Si assuma di avere un linguaggio object oriented.

1. Definire la regola semantica per l’overriding, ossia la regola che per-
mette di tipare

class A { ...
T1 m (T2 x) { ...}
...}
class B extends A { ...
T3 m (T4 x) { ...}
...}
[Suggerimento: definire la regola di tipo per il costrutto class B
extends A, assumendo, per semplicit`a che B abbia esattamente un
metodo. Fare i due casi che il metodo sia sovrascritto oppure no]
2. Definire anche la funzione checkDecs che implementa la regola del
punto precedente.
Esercizio 3 (9 punti). Definire la funzione code gen per il comando

whileTre E do { C } { C’ } od

che (1) calcola E e sia v il suo valore; (2) se v = 0 allora termina, altrimenti
se v `e un multiplo di 3 esegue C, altrimenti esegue C’.
Quindi applicare le regole di sopra al comando
whileTre (x+y) { y := y+1; x := x-2 } { x= x-1 } od
assumendo che la variabile x si trovi ad o↵set +4 del frame pointer $fp,
mentre la variabile y si trova nell’ambiente statico immediatamente esterno
all’ambiente corrente e a o↵set +8.
Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

4 Luglio 2019
Esercizio 1 (6 punti). Dato l’input di ANTLR
start : (BINDIGIT PIU DIGIT)+ ;
PIU : ’+’ ;
BINDIGIT : (’0’ | ’1’)+ ;
DIGIT : (’0’..’9’)+ ;
WS : (’ ’ | ’\t’ | ’\n’ | ’\r’ ) -> skip ;
Dire cosa accade quando l’input da analizzare `e (motivare le risposte):
a) 1+1
b) 1+2+3
Esercizio 2 (8 punti). Si assuma di avere un linguaggio con sottotipi (e relazione di
sottotipo <:).
1. Definire la regola semantica per l’invocazione x.m(E) dove x `e un oggetto, m un metodo
ed E una espressione.
2. Scrivere l’albero di derivazione per l’espressione x.m(y.n(z.f)) ; quando l’ambiente
`e [x 7! Cx, y 7! Cy, z 7! Cz]. Quali sono le condizioni per cui l’espressione di sopra `e
ben tipata?
Esercizio 3 (10 punti). Definire la funzione code gen per le espressioni booleane

E and E E or E not E
Quindi applicare le regole definite all’espressione
x and (y or not z)

assumendo che le variabili x e y si trovino ad o↵set +4 e +8 del frame pointer $fp, mentre
la variabile z si trova nell’ambiente statico immediatamente esterno all’ambiente corrente e
a o↵set +8.
Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

5 Giugno 2019

Esercizio 1. Definire un analizzatore lessicale in ANTLR che accetta sequenze
di token che a loro volta sono stringhe sull’alfabeto a, b, c, che contengono
esattamente una e una sola occorrenza di a ed una e una sola occorrenza di
b.

Esercizio 2. Data la grammatica (le lettere minuscole sono simboli termi-
nali)

A ! Ba | C
B ! AA
C ! Cc | b

1. Trasformarla, rimuovendo la (mutua) ricorsione sinistra;
2. verificare se la grammatica ottenuta `e LL(1) costruendo l’opportuna
tabella.
Esercizio 3. Define the function code gen for the statement

for id:= E to E0 do S

(E ed E0 sono espressioni, S sono comandi) con le assunzioni di codifica
fatte a lezione. La semantica del for `e la seguente.
1. vengono calcolati i valori di E e di E0 e siano essi v e v0
;

2. si inizializza id a v;
3. si verifica se id `e minore di v0

; se il risultato `e vero si va a 4, altrimenti

si esce;
4. si esegue S, alla fine di S si incrementa id e si ritorna a 3.
Quindi applicare la funzione al codice

for i := y to z do y := y-z

assumendo che le variabili i e z si trovano ad o↵set +4 e +8 e del frame

pointer $fp, mentre la variabile y si trova nell’ambiente statico immedi-
atamente esterno all’ambiente corrente e a o↵set +4 (l’ambiente statico `e


14/2/2019

5/6/2019

18/9/2020
Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

14 Febbraio 2019

Esercizio 1 Si definisca un analizzatore lessicale in ANTLR che accetta se-
quenze di token che a loro volta sono stringhe (non vuote) sull’alfabeto a, b

che contengono un numero dispari di occorrenze di a.

Esercizio 2. Data la grammatica (le lettere minuscole sono simboli termi-
nali)

S ! Ab | Bc
A ! aA0
A0 ! d | "
B ! aB0
B0 ! d | "

Si dimostri, costruendo l’opportuna tabella, che la grammatica `e LL(1). Nel
caso in cui non lo sia, verificare se esiste k tale che la grammatica `e LL(k).
Motivare la risposta.
Esercizio 3. Definire la funzione CheckDecs(D, vtable, ftable) quando
D `e una sequenza di dichiarazioni di un linguaggio (senza subtyping) e la cui
sintassi `e:
D ::= T id | T id(T0 id0

){ E } | T id ; D | T id(T0 id0
){ E } ; D
E possibile utilizzare ` CheckExp(E, vtable, ftable) senza doverla definire.
Le altre funzioni devono essere tutte definite.
Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

5 Giugno 2019

Esercizio 1. Definire un analizzatore lessicale in ANTLR che accetta sequenze
di token che a loro volta sono stringhe sull’alfabeto a, b, c, che contengono
esattamente una e una sola occorrenza di a ed una e una sola occorrenza di
b.

Esercizio 2. Data la grammatica (le lettere minuscole sono simboli termi-
nali)

A ! Ba | C
B ! AA
C ! Cc | b

1. Trasformarla, rimuovendo la (mutua) ricorsione sinistra;
2. verificare se la grammatica ottenuta `e LL(1) costruendo l’opportuna
tabella.
Esercizio 3. Define the function code gen for the statement

for id:= E to E0 do S

(E ed E0 sono espressioni, S sono comandi) con le assunzioni di codifica
fatte a lezione. La semantica del for `e la seguente.
1. vengono calcolati i valori di E e di E0 e siano essi v e v0
;

2. si inizializza id a v;
3. si verifica se id `e minore di v0

; se il risultato `e vero si va a 4, altrimenti

si esce;
4. si esegue S, alla fine di S si incrementa id e si ritorna a 3.
Quindi applicare la funzione al codice

for i := y to z do y := y-z

assumendo che le variabili i e z si trovano ad o↵set +4 e +8 e del frame

pointer $fp, mentre la variabile y si trova nell’ambiente statico immedi-
atamente esterno all’ambiente corrente e a o↵set +4 (l’ambiente statico `e

accessibile attraverso il registro $al).
Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

19 Dicembre 2019

Esercizio 1 (6 punti) Scrivere le definizioni formali di nullable, first, e
follow per grammatiche LL(1).
Esercizio 2 (10 punti) In un linguaggio di programmazione i programmi Prg
sono definiti da questa sintassi
Prg ::= Fun* Stm
Fun ::= Type Id ”(” FPar ”)” = Stm

dove Type possono essere solamente int e bool, FPar sono i parametri formali,
cio`e sequenze anche vuote del tipo Type1 Id1, ··· , Typen Idn, e Stm `e la categoria
sintattica dei comandi (lo Stm in Prg `e il main). Definire

1. le regole di inferenza per analizzare programmi con mutua ricorsione [Sug-
gerimento: servono due regole, una per costruire l’ambiente iniziale con

tutti i tipi delle funzioni, l’altra per analizzare il programma;
2. definire lo pseudocodice per CheckProg che implementa le regole di sopra;
3. fornire l’albero di prova per il programma

int f(int x) = return (g(x,x) + 1) ;
int g(int u, int v) = return(f(u+v)) ;
print(f(1)+g(2,3)) ;

assumendo i vincoli di tipo standard per i comandi e le espressioni (quelli
visti a lezione).
Esercizio 3 (8 punti)
1. Definire la funzione code gen per il termine do S while E che esegue
S, quindi controlla E e se essa `e vera riesegue S, altrimenti l’esecuzione
termina.
2. Come verifica, si generi il codice di
do do ( x:= x+1 ; y:= y+x ) while (x>y) while (y<x+z)
dove le variabili x, y e z si trovano ad o↵set +4 e +8 e +12 del frame pointer
FP.
Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

19 Febbraio 2020

Esercizio 1 (7 punti). Data la grammatica (le lettere minuscole sono
simboli terminali, A `e il simbolo iniziale)
A ! BC
B ! aB | "
C ! CbB | c

Riscrivere la grammatica rimuovendo la ricorsione sinistra e verificare se la
grammatica `e LL(1) costruendo l’opportuna tabella. Nel caso non lo sia,
esiste un k per cui essa `e LL(k)? Motivare la risposta.
Esercizio 2 (7 punti). I seguenti sono potenziali regole di tipo per il
costrutto let in un linguaggio con sottotipaggio (<:). Dire quali regole
sono corrette e quali sbagliate. Per quelle sbagliate dare (a) un codice che
dovrebbe essere tipabile e non lo `e; (b) un codice che `e tipabile e invece non
dovrebbe essere.
1.
` e : T0

` e0 : T00 T0 <: T
` let T x = e in e0 : T00
2.
` e : T0

[x : T] ` e0 : T00 T <: T0
` let T x = e in e0 : T00

3.
` e : T0

[x : T0
] ` e0 : T00 T0 <: T
` let T x = e in e0 : T00

Nel caso in cui nessuna regola sia corretta, (i) dare la regola giusta e (ii)
controllare che i codici di prima siano correttamente tipabili/non tipabili.
Esercizio 3 (10 punti). Definire la funzione code gen per
1. la dichiarazione di funzione void come: void f(T1 x, T2 y){ S } ;
2. l’invocazione di funzione f(e, e0

) (e, e0 sono espressioni).

Quindi, assumendo che l’etichetta che corrisponde alla seguente funzione
fact sia fact label, scrivere il codice per
int x = 1 ;
void fact(int n, int z){
if (n == 0) x = z ;
else fact(n-1, z*n) ;
}

28/5/2021

9/7/2021

Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

18 Settembre 2020

Nota Bene. Quando avete terminato, fare una foto a tutto il compito col cellulare usando una ap-
plicazione che esegue scansioni, tipo CamScanner, e inviarla per email a cosimo.laneve@unibo.it .

Esercizio 1 (punti 6) Gli identificatori di un linguaggio di programmazione devono iniziare e
terminare con “ ” e tra questi due caratteri ci possono essere solo lettere maiuscole e cifre (in
qualunque ordine) con il vincolo che il numero di lettere e quello delle cifre sia sempre pari. Definire
l’analizzatore lessicale per questi identificatori in ANTLR.
Esercizio 2 (punti 9) Si consideri la seguente grammatica:
S -> S B | y
B -> B x | A x
A -> z | z S y
1. verificare, costruendo la tabella che la grammatica non `e LL(1);
2. modificare la grammatica per renderla LL(1) e dimostrarlo costruendo la tabella.
Esercizio 3 (punti 9) Si consideri il comando iterativo
loop k {S}

dove k `e una costante intera. Quando k > 0, questo comando itera esattamente k volte il corpo S.
Quando k  0 il comando non fa niente.
1. Scrivere la cgen per questo comando;
2. generare il codice intermedio per
loop 34 { x = x+1 ; loop 25 { y = x+y ;} }
assumendo che x sia ad o↵set 4 del record di attivazione corrente e y sia ad o↵set 4 del record
di attivazione dell’ambiente statico immediatamente esterno.
Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

28 Maggio 2021

Nota Bene. Quando avete terminato, fare una foto a tutto il compito col cellulare usando una ap-
plicazione che esegue scansioni, tipo CamScanner, e inviarla per email a cosimo.laneve@unibo.it .

I programmi di un linguaggio di programmazione sono blocchi Dec Stm dove
• Dec sono sequenze di dichiarazioni di identificatori interi (int);
• Stm sono sequenze di comandi che possono essere
– assegnamenti di una espressione Exp a una variabile;
– iterazioni while (la guardia del condizionale `e una espressione intera, la semantica `e
quella di C).
• Exp possono essere costanti intere, identificatori o espressioni con somma.
Esercizi
1. (punti 6) definire l’input completo di ANTLR per la grammatica del linguaggio di sopra;
2. (punti 9) dare tutte le regole di inferenza per verificare il corretto uso degli identificatori

(identificatori non dichiarati o di dichiarazioni multiple) e per gestire gli o↵set nella gener-
azione di codice.

3. (punti 9) definire il codice intermedio per tutti i costrutti del linguaggio, in particolare per il
programma. Ricordate che la cgen prende come input anche l’ambiente/tabella dei simboli
nei vari nodi dell’albero sintattico. Fate attenzione alla gestione degli accessi al record di
attivazione.
Generare il codice intermedio per il codice
int x; int z;
x = 4; z = x+5; while (z + 3){ z = z+x ; while (x){ x = x+1; } }
Corso di Laurea Magistrale in Informatica
Compito di Compilatori e Interpreti

9 Luglio 2021

Nota Bene. Quando avete terminato, fare una foto a tutto il compito col cellulare usando una ap-
plicazione che esegue scansioni, tipo CamScanner, e inviarla per email a cosimo.laneve@unibo.it .

I programmi di un linguaggio di programmazione sono blocchi { Dec Stm } dove
• Dec sono sequenze di dichiarazioni di identificatori interi con inizializzazioni, cio`e Dec :
(’int’ X ’=’ Exp ’;’)* ;
• Stm sono sequenze di comandi. Cio`e
Stm : ( X ’=’ Exp ’;’ | ’if’ ’(’ Exp ’)’ ’\{’ Stm ’\}’ ’else’ ’\{’ Stm ’\}’
| Stm Stm )* ;
• la sintassi delle espressioni Exp `e:

Exp : Exp ’+’ Exp | Exp ’-’ Exp | X | N ;

dove N sono i naturali, e X sono gli identificatori.
Esercizi
1. (punti 6) trasformare la grammatica delle espressioni in modo da eliminare la ricorsione
sinistra. Quindi verificare, costruendo l’opportuna tabella, che la grammatica ottenuta sia
LL(1). [Assumere che N ed X siano simboli terminali.]
2. (punti 9) dare tutte le regole di inferenza per verificare se un identificatore contiene un
numero pari o un numero dispari, il corretto uso degli identificatori (identificatori non dichiarati
o di dichiarazioni multiple) e per gestire gli o↵set nella generazione di codice. Per quanto
riguarda, la verifica pari/dispari, assumere di avere un test sulle costanti Is oe(n) che ritorna
p se n `e pari, d se `e dispari. Inoltre si ricordi che la somma/di↵erenza di due pari o di due
dispari `e pari, mentre la somma/di↵erenza di un pari e un dispari `e dispari. Quando non si
`e in grado di determinare se un identificatore `e pari o dispari allora quell’ identificatore ha
valore > (quando uno degli argomenti della somma `e > allora il risultato `e >. Fare attenzione
al comando condizionale.
Scrivere l’albero di prova per
{ int x = 1; int z = x + 3; if (x+1) { z = x+z; } else {z = x+1; x = z-1 ;}

3. (punti 9) definire il codice intermedio per tutti i costrutti del linguaggio, in particolare allo-
cando lo spazio necessario sulla pila per gestire i blocchi.