02 10 12

Page 1

Linguaggi Formali e Compilatori (Formal Languages and Compilers) prof. S. Crespi Reghizzi, prof. Angelo Morzenti (prof. Luca Breveglieri) Prova scritta - 2 ottobre 2012 - Parte I: Teoria CON SOLUZIONI -AS C O P OD I D A T T I C OL ES O L U Z I O N IS O N OM O L T OE S T E S EEC O M - MENT A TE V ARIAMENTE - NON SI RICHIEDE CHE IL CANDIDA TO SVOLGA IL COMPITO IN MODO AL- TRETT ANTO AMPIO, BENS`IC H ER I S P O N D AI NM O D OA P P R O P R I A T OEAS U OG I U D I Z I OR A G I O N E V OLE NOME: MATRICOLA: FIRMA: ISTRUZIONI - LEGGERE CON ATTENZIONE: •L’esame si compone di due parti: –I( 8 0 % )T e o r i a : 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. •`Ep e r m e s s oc o n s u l t a r el i b r iea p p u n t ip e r s o n a l i . •Per scrivere si utilizzi lo spazio libero e se occorre anche i lt e r g od e lf o g l i o ;` ev i e t a t o allegare nuovi fogli o sostituirne di esistenti. •Temp o: Parte I (teoria): 2h.15m - Parte I I (esercitazioni): 60m 1E s p r e s s i o n i r e g o l a r i e a u t o m i fi n i t i20% 1. I linguaggiL′eL′′sono definiti tramite le espressioni regolariR′eR′′seguenti: R′= ( (ab|b)∗a )∗ R′′= ( b(ba|aa)∗)+ Si risponda alle domande seguenti: (a) Si elenchino le stringhe di lunghezza ≤3a p p a r t e n e n t iac i a s c u n od e il i n g u a g g i . (b) Si costruisca un automa finito Ache riconosce…