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