2024

Autómatos e Linguagens de Programação

Nome: Autómatos e Linguagens de Programação
Cód.: INF13195L
6 ECTS
Duração: 15 semanas/156 horas
Área Científica: Informática

Língua(s) de lecionação: Português
Língua(s) de apoio tutorial: Português, Inglês
Regime de Frequência: Presencial

Objetivos de Desenvolvimento Sustentável

Objetivos de Aprendizagem

- Discutir máquinas de estados finitos.
- Construir ou Definir uma expressão regular e uma GLC para representar ou um AFD para aceitar/gerar uma linguagem especificada; Converter entre representações equivalentes.
- Determinar o lugar de uma linguagem na hierarquia de Chomsky, os principais problemas nas definições de sintaxe
- Usar gramáticas formais para especificar a sintaxe de linguagens, ferramentas declarativas para gerar analisadores e scanners.
- Definir uma semântica formal e uma árvore de sintaxe abstrata para uma linguagem pequena.
- Explicar como os programas que processam outros programas tratam os outros programas e as vantagens de ter representações de programas que não sejam strings de código-fonte.
- Escrever um programa para processar alguma representação de código.

Conteúdos Programáticos

1. Palavras, Linguagens e Expressões
Alfabetos, Palavras e Linguagens; Expressões Regulares
2. Autómatos Finitos
Autómatos Finitos Deterministas; Computação Não Determinista; Eliminação do Não Determinismo; Minimização e Composição de AFD; O Pumping Lemma
3. Gramáticas e Autómatos de Pilha
4. Análise Sintática
Análise Sintática e Limpeza de uma Gramática; Gramáticas LL(k) e LR(k)
5. Representação e Execução de Programas
Árvore de Sintaxe Abstrata; Análise Semântica; Tabela de símbolos; Análise de nomes; Sistemas de tipos; Verificação e inferência de tipos; Suporte para um Interpretador

Métodos de Ensino

Aulas Teóricas com apresentação de conteúdos, explicação de aplicações e ilustração de exemplos. Aulas práticas com resolução de exercícios e desenvolvimento de exemplos.

Avaliação

A avaliação contínua consiste em duas frequências (10 valores cada; 20 valores total = 100% da nota final).

A avaliação final consiste na realização de um exame (20 valores = 100% da nota final).

Bibliografia

- Languages and Machines: An Introduction to the Theory of Computer Science, 2 ed. Thomas A. Sudkamp. Addison Wesley, 1997. (320 páginas)

- Compilers: Principles, Techniques and Tools, Alfred V. Aho, Ravi Sethi e Jeffrey D. Ullman. Addison Wesley, 1986. (1038 páginas)

Equipa Docente

Voltar