- Oggetto:
- Oggetto:
Linguaggi Formali e Traduttori
- Oggetto:
Formal Languages and Compilers
- Oggetto:
Anno accademico 2022/2023
- Codice dell'attività didattica
- MFN0603
- Docenti
- Jeremy James Sproston (Corso A + Turno 2)
Gian Luca Pozzato (Corso B)
Viviana Patti (Turno 1 + Turno 3)
Luigi Di Caro (Turno 4) - Corso di studi
- [008707] Laurea in Informatica
- Anno
- 2° anno
- Periodo didattico
- Primo semestre
- Tipologia
- Caratterizzante
- Crediti/Valenza
- 9 CFU - Numero di ore - Number of hours: 48 (in aula) + 30 (in laboratorio)
- SSD dell'attività didattica
- INF/01 - informatica
- Modalità di erogazione
- Tradizionale
- Lingua di insegnamento
- Italiano
- Modalità di frequenza
- Facoltativa
- Tipologia d'esame
- Scritto più orale obbligatorio
- Prerequisiti
-
Familiarità con i concetti fondamentali della logica, della teoria degli insiemi e della progettazione di algoritmi iterativi e ricorsivi. Capacità di programmare in linguaggi ad alto livello.
Insegnamenti propedeutici (forniscono le competenze attese in ingresso): Programmazione I; Programmazione II; Architettura degli elaboratori; Matematica Discreta e Logica.The student must be acquainted with the basic concepts of logic, set theory and with iterative and recursive algorithm design. The student must also be able to program in high-level languages
Preparatory Courses (providing the expected entry skills): Programmazione I; Programmazione II; Architettura degli elaboratori; Matematica Discreta e Logica. - Oggetto:
Sommario insegnamento
- Oggetto:
Obiettivi formativi
L'insegnamento ha l'obiettivo di fornire le nozioni fondamentali relative alla specifica di linguaggi formali e alla traduzione di programmi. Sebbene il corso presenti queste nozioni nel contesto specifico della progettazione e realizzazione di compilatori, i concetti, i formalismi, le metodologie e le tecniche presentate trovano applicazione in un'ampia gamma di contesti in cui si richiede la specifica, la comprensione e la traduzione di informazioni strutturate. La parte teorica dell'insegnamento è affiancata da attività pratiche mirate a illustrare l'applicazione concreta delle suddette tecniche allo sviluppo di programmi per l'analisi di dati strutturati e di altri programmi. La padronanza dei concetti e degli strumenti riguardanti linguaggi formali e traduttori rientra fra gli Obiettivi formativi dell'area informatica di base del CdS in Informatica (L31).The course aims to provide students with fundamental notions related to the specification of formal languages and to the translation of programs. Although the course presents these notions in the specific context of compiler design and implementation, the presented concepts, formalisms, methodologies and techniques are applicable in a wide variety of contexts in which the specification, understanding and translation of structured data are necessary. The theoretical part of the course is paired with practical activities aimed at illustrating the concrete application of the aforementioned techniques to the development of programs for the analysis of structured data and other programs. Obtaining skills regarding the concepts and tools regarding formal languages and translators forms part of the "Obiettivi formativi specifici del CdS in Informatica (L31)".- Oggetto:
Risultati dell'apprendimento attesi
Comprensione e acquisizione della terminologia tecnica del settore. Conoscenza delle metodologie fondamentali per la descrizione della sintassi di linguaggi formali (ad esempio i linguaggi di programmazione) e di alcune tecniche di analisi sintattica e traduzione; capacità di utilizzare tali conoscenze per lo sviluppo di sistemi software. Conoscenza e padronanza degli strumenti di base per la progettazione di traduttori.CONOSCENZA E CAPACITÀ DI COMPRENSIONE. Acquisizione di conoscenze teoriche e applicative relative a linguaggi formali e traduttori.
CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE. Acquisizione dell’abilità di applicare conoscenza teorica di linguaggi formali e traduttori alla soluzione di problemi pratici relativi alla traduzione di programmi.
AUTONOMIA DI GIUDIZIO. Acquisizione delle capacità per la valutazione delle correttezza della progettazione di traduttori per linguaggi di programmazione e per valutare l’efficacia della loro implementazione e funzionamento.
ABILITÀ COMUNICATIVE. Acquisizione della capacità di utilizzare framework precise per ragionare di linguaggi formali (automi a stati finiti, grammatiche) e traduttori (definizioni dirette dalla sintassi, schemi di traduzione).
CAPACITÀ DI APPRENDIMENTO. Acquisizione di capacità di imparare e autovalutarsi, sia rispetto a problemi teorici sia rispetto a problemi pratici, in un modo autonomo.
Understanding and acquisition of the technical terminology of the field. Knowledge of the fundamental methodologies for the description of the syntax of formal languages (for example, programming languages) and of techniques for syntactical analysis and translation; ability to use such knowledge for the development of software systems. Knowledge and mastery of the basic tools for the development of translators.KNOWLEDGE AND UNDERSTANDING Acquisition of theoretical and applicative skills concerning formal languages and translators.
APPLYING KNOWLEDGE AND UNDERSTANDING Acquisition of the ability to apply theoretical knowledge of formal languages and translators to the solution of practical problems concerning the translation of programs.
MAKING JUDGEMENTS Acquisition of skills for assessing the correctness of designs for translators for simple languages, and for judging the effectiveness of their implementation and operation
COMMUNICATION SKILLS Acquisition of the ability to use precise, unambiguous frameworks for reasoning about formal languages (finite-state automata, grammars) and translators (syntax-directed definitions, syntax-directed translation schemes).
LEARNING SKILLS Acquisition of the ability to learn and carry out self-assessment, with regard to both theoretical and practical problems, in an autonomous manner.
- Oggetto:
Modalità di insegnamento
L’insegnamento è suddiviso in una parte di teoria (48 ore) e una parte di laboratorio (30 ore). La parte di teoria consiste in un ciclo di lezioni erogate con l'ausilio di slide, note, lavagne (fisiche o virtuali), editor per lo sviluppo di codice. Le lezioni sono accompagnate da sessioni interattive dedicate a chiarimenti, esempi ed approfondimenti sui contenuti del corso. La parte di laboratorio consiste in una serie di esercizi relativi all'applicazione pratica dei concetti trattati nella parte di teoria e forniscono agli studenti l'esperienza necessaria per affrontare l'esercitazione finale, che richiede la realizzazione di un traduttore per un semplice linguaggio di programmazione.The course is divided into a theoretical part (48 hours) and a laboratory part (30 hours). The theoretical part consists of a series of lessons supported by the use of slides, notes, blackboards (physical or virtual), editors for the development of code. The lessons will be accompanied by interactive sessions dedicated to the presentation of examples, and to the clarification and further exploration of the course contents. The laboratory part of the course consists of a series of exercises relative to the practical application of the concepts considered in the theoretical part of the course, and offer the students the necessary experience to complete the final exercise, which requires the completion of a traduttore for a simple programming language.- Oggetto:
Modalità di verifica dell'apprendimento
L'esame dell'insegnamento consiste di due prove obbligatorie.- Prova scritta composta di domande di natura teorica ed esercizi su tutto il programma del corso.
- Prova di laboratorio, consistente nella presentazione e discussione di del progetto, che riguarda lo sviluppo e l'implementazione di un traduttore per un semplice linguaggio di programmazione.
Gli esiti di entrambe le suddette prove sono espressi in trentesimi. Per superare le prove, è necessario ottenere un voto di almeno 18 su 30 in entrambe. Per sostenere la prova di laboratorio è necessario prima aver superato la prova scritta. Il voto complessivo per l'insegnamento è ottenuto facendo una media pesata tra il voto della prova scritta e il voto della prova di laboratorio, dove il peso della prova scritta è il doppio di quello della prova di laboratorio. A richiesta, e comunque per ottenere la lode, è possibile sostenere una prova orale integrativa. Le prove devono essere superate nella stessa sessione d'esame.
The exam of the course consists of two obligatory tests.- Written test, composed of questions of a theoretical nature and exercises on the entire programme of the course.
- Test of the laboratory part of the course, which consists of the presentation and discussion of a project regarding the development and implementation of a translator for a simple programming language.
The results of each of the aforementioned tests are expressed in marks out of 30. To pass the tests, it is necessary to obtain a mark of at least 18 out of 30. In order to take the test of the laboratory part of the course, the written test must first be passed. The final mark for the course is obtained by a weighted average between the mark for the written test and the mark for the laboratory test, where the written test has twice the weight of the laboratory test. Students can also ask to take a supplementary oral exam, which must be taken to obtain the maximum grade of 30 cum laude. The tests must be passed within the same exam session.
- Oggetto:
Programma
- Nozioni di base di linguaggi formali
- Automi a stati finiti
- Espressioni regolari
- Proprietà dei linguaggi regolari
- Grammatiche libere
- Automi a pila
- Proprietà dei linguaggi liberi
- Analisi sintattica top-down
- Traduzione diretta dalla sintassi
- Generazione di codice intermedio
- Basic notions of formal languages
- Finite-state automata
- Regular expressions
- Properties of regular languages
- Context-free grammars
- Pushdown automata
- Properties of context-free languages
- Top-down parsing
- Syntax-directed translation
- Intermediate code generation .
Testi consigliati e bibliografia
- Oggetto:
- Libro
- Titolo:
- Automi, Linguaggi e Calcolabilità
- Anno pubblicazione:
- 2018
- Editore:
- Pearson
- Autore:
- J. E. Hopcroft, R. Motwani, J. D. Ullman
- Note testo:
- Le due edizioni precedenti sono ugualmente valide.
- Obbligatorio:
- No
- Oggetto:
- Libro
- Titolo:
- Compilatori: Principi, tecniche e strumenti
- Anno pubblicazione:
- 2019
- Editore:
- Pearson
- Autore:
- A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman
- Note testo:
- Le edizioni precedenti sono ugualmente valide.
- Obbligatorio:
- No
- Oggetto: