2023
Automata and Programming Languages
Name: Automata and Programming Languages
Code: INF13195L
6 ECTS
Duration: 15 weeks/156 hours
Scientific Area:
Informatics
Teaching languages: Portuguese
Languages of tutoring support: Portuguese, English
Regime de Frequência: Presencial
Sustainable Development Goals
Learning Goals
- Discuss finite state machines.
- Design or Generate a deterministic finite state machine, a regular expression and a context-free grammar to accept or represent a specified language; Convert among equivalently powerful notations.
- Determine a languages place in the Chomsky hierarchy, key issues in syntax definitions.
- Use formal grammars to specify the syntax of languages, declarative tools to generate parsers and scanners.
- Give a formal semantics and an abstract syntax tree for a small language.
- Explain how programs that process other programs treat the other programs as their input data and the benefits of having program representations other than strings of source code.
- Write a program to process some representation of code.
- Design or Generate a deterministic finite state machine, a regular expression and a context-free grammar to accept or represent a specified language; Convert among equivalently powerful notations.
- Determine a languages place in the Chomsky hierarchy, key issues in syntax definitions.
- Use formal grammars to specify the syntax of languages, declarative tools to generate parsers and scanners.
- Give a formal semantics and an abstract syntax tree for a small language.
- Explain how programs that process other programs treat the other programs as their input data and the benefits of having program representations other than strings of source code.
- Write a program to process some representation of code.
Contents
1. Words, Languages and Expressions
Alphabets, Words and Languages, Regular Expressions
2. Finite automata
Deterministic Finite Automata, Non-deterministic computing, Elimination of Non-Determinism, Minimization and Composition of DFA, The Pumping Lemma
3. Grammars and Push-down Automata
4. Syntax analisys
Syntactic Analysis and Clean Grammars, LL(k) and LR(k) Grammars
5. Representation and Execution of Programs, Abstract Syntax Tree, Semantic Analysis, Table of symbols, Name Analysis, Type systems, Checking and Inference Types, Support for a Interpreter
Alphabets, Words and Languages, Regular Expressions
2. Finite automata
Deterministic Finite Automata, Non-deterministic computing, Elimination of Non-Determinism, Minimization and Composition of DFA, The Pumping Lemma
3. Grammars and Push-down Automata
4. Syntax analisys
Syntactic Analysis and Clean Grammars, LL(k) and LR(k) Grammars
5. Representation and Execution of Programs, Abstract Syntax Tree, Semantic Analysis, Table of symbols, Name Analysis, Type systems, Checking and Inference Types, Support for a Interpreter
Teaching Methods
Theoretical classes with presentation of contents, explanation of applications and illustration of examples. Practical classes with resolution of exercises and development of examples.
The assessment consists of a set of biweekly or two-frequency tests or a final exam.
The assessment consists of a set of biweekly or two-frequency tests or a final exam.
Teaching Staff
- Francisco Manuel Gonçalves Coelho [responsible]
