05 02 13

Page 1

Linguaggi Formali e Compilatori (Formal Languages and Compilers) prof. S. Crespi Reghizzi, prof. Angelo Morzenti (prof. Luca Breveglieri) Prova scritta - 5 febbraio 2013 - 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 RAGIONEVOLE A VVISO - A P AR TIRE DALLA SESSIONE ESTIV A (GIUGNO 2013), GLI ESERCIZI DI ANALISI SIN- T A TTICA ANDRANNO AFFRONT A TI SECONDO LA TEORIA ELR / ELL -L AT E O R I ALR / LL NON SAR `AP I `U AMMESSA - SI VEDA IL SITO WEB DEL CORSO PER MA TERIALE DIDA TTICO E INFORMAZIONI 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 possedere 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 il tergo del foglio; `e vietato allegare nuovi fogli o sostituirne di esistenti. •Tempo: Parte I (teoria): 2h.15m - Parte II (esercitazioni): 60m 1 Espressioni regolari e automi finiti 20% 1. Dato l’alfabeto ternario{ a, b, c}, si consideri l’automa nondeterministicoA seguen- te: 3 1 2A → ← a b b a c Si risponda alle domande seguenti: (a) Tramite il…