20 06 11

Page 1

Linguaggi Formali e Compilatori (Formal Languages and Compilers) prof. S. Crespi Reghizzi, prof. Angelo Morzenti (prof. Luca Breveglieri) Prova scritta - 20 giugno 2011 - Parte I: Teoria CON SOLUZIONI - A SCOPO DIDA TTICO LE SOLUZIONI SONO MOL TO ESTESE E COM- MENT A TE V ARIAMENTE - NON SI RICHIEDE CHE IL CANDIDA TO SVOLGA IL COMPITO IN MODO AL- TRETT ANTO AMPIO, BENS `I CHE RISPONDA IN MODO APPROPRIA TO E A SUO GIUDIZIO RAGIONEVO LE NOME: MATRICOLA: FIRMA: ISTRUZIONI - LEGGERE CON ATTENZIONE: • L’esame si compone di due parti: – I (80%) Teoria: 1. espressioni regolari e automi finiti 2. grammatiche libere e automi a pila 3. analisi sintattica e parsificatori 4. traduzione sintattica e analisi semantica – II (20%) Esercitazioni Flex e Bison • Per superare l’esame l’allievo deve sostenere con successo entrambe le parti (I e II), in un solo appello oppure in appelli diversi, ma entro un anno . • Per superare la parte I (teoria) occorre dimostrare di posse dere conoscenza sufficiente di tutte le quattro sezioni (1-4), rispondendo alle domande obbligatorie. • `E permesso consultare libri e appunti personali. • Per scrivere si utilizzi lo spazio libero e se occorre anche i l tergo del foglio; ` e vietato allegare nuovi fogli o sostituirne di esistenti. • Tempo: Parte I (teoria): 2h.30m - Parte II (esercitazioni): 45m 1 Espressioni regolari e automi finiti 20% 1. `E data l’espressione regolare R seguente: R = ( a | b )+ ( b | c)+ ( a | c )∗ Si risponda alle domande seguenti: (a) Si scrivano la stringa pi` u breve ambigua e quella pi` u br eve non ambigua del linguaggio L(R). (b) Usando il metodo Berri-Sethi (BS), si ricavi un automa de terministico A che accetta il linguaggio L(R). (c) (facoltativa) Si minimizzi il numero degli stati dell’a utoma A. 2 Soluzione (a) Ciascuna…