2023
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
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.
- 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
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.
A avaliação consiste num conjunto de testes quinzenais ou duas frequências ou um exame final.
A avaliação consiste num conjunto de testes quinzenais ou duas frequências ou um exame 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)
- Compilers: Principles, Techniques and Tools, Alfred V. Aho, Ravi Sethi e Jeffrey D. Ullman. Addison Wesley, 1986. (1038 páginas)
Equipa Docente (2022/2023 )
- Francisco Manuel Gonçalves Coelho [responsável]
