Linguagens Formais e Autómatos › 43343

código no paco
43343
área científica
Informática / Ciência e Tecnologia da Programação
créditos
6
escolaridade
ensino teórico (T) - 3 horas/semana
ensino prático e laboratorial (PL) - 2 horas/semana
idioma(s) de lecionação
a inserir brevemente
objectivos

A unidade curricular aborda teoria das linguagens, tendo como objetivo dotar o estudante com a capacidade de projetar e implementar tradutores dirigidos pela sintaxe, incluindo a construção de compiladores. Pretende-se que o aluno adquira:

  • Capacidade de trabalhar com linguagens regulares, incluindo a manipulação de modelos computacionais usados para as descrever e reconhecer, nomeadamente as expressões regulares, autómatos finitos e gramáticas regulares.

  • Capacidade de trabalhar linguagens independentes do contexto, quer na sua interpretação, quer no projeto.

  • Capacidade de distinguir análise lexical e análise sintática.

  • Capacidade de projetar e implementar tradutores dirigidos pela sintaxe, incluindo compiladores.

competências

Pretende-se que o aluno adquira as seguintes competências:

  • Capacidade de trabalhar com linguagens regulares, incluindo a manipulação de modelos computacionais usados para as descrever e reconhecer, nomeadamente as expressões regulares, autómatos finitos e gramáticas regulares.

  • Capacidade de trabalhar linguagens independentes do contexto, quer na sua interpretação, quer no projeto.

  • Capacidade de distinguir análise lexical e análise sintática.

  • Capacidade de projetar e implementar tradutores dirigidos pela sintaxe, incluindo compiladores.

conteúdos

A unidade curricular aborda teoria das linguagens, tendo como alvo o projeto e implementação de tradutores dirigidos pela sintaxe, incluindo a construção de compiladores. Apresenta-se a seguir a lista dos tópicos cobertos.

Introdução aos processadores de linguagens

Linguagens

  • Noções básicas
  • Operações sobre linguagens
  • Representação e classificação das linguagens

Linguagens regulares

  • O papel do analisador lexical

  • Expressões regulares

  • Autómatos finitos: deterministas, não deterministas e generalizados

  • Gramáticas regulares

  • Equivalência entre expressões regulares, autómatos finitos e gramáticas regulares

Gramáticas independentes do contexto e análise sintática

  • O papel do analisador sintático

  • Gramáticas independentes do contexto

  • Projeto de gramáticas

  • Análise sintática descendente

  • Análise sintática ascendente

Traduções dirigidas pela sintaxe

  • Atributos e acções semânticas

  • Definições dirigidas pela sintaxe

  • Árvores sintáticas abstratas

  • Análise semântica

Geração de código

  • Geração de código intermédio

avaliação

A avaliação baseia-se em duas provas escritas e em dois trabalhos práticos. As provas escritas avaliam a compreensão das matérias dadas enquanto que os trabalhos práticos avaliam a capacidade dos alunos usarem os conhecimentos adquiridos na construção de tradutores dirigidos pela sintaxe.

No cálculo da nota final, os exames escritos e os trabalhos práticos têm o mesmo peso, 50% cada um.

requisitos

Atendendo aos assuntos cobertos, conhecimentos sobre os seguintes tópicos são desejáveis: teoria dos conjuntos, noções sobre grafos, indução matemática. Para a boa realização dos trabalhos práticos, competências de programação e de estruturas de dados são essenciais.

metodologia

Nas aulas teóricas expõe-se a matéria e trabalham-se exemplos de aplicação. As aulas práticas decorrem em laboratório de computadores e são, em primeiro lugar, usadas para introduzir as ferramentas de programação e, em seguida, utilizadas para auxiliar no desenvolvimento dos trabalhos práticos.

A avaliação é dividida em duas componentes, uma teórica e outra prática. As duas componentes têm o mesmo peso (50%) na determinação da nota final. A componente teórica pretende avaliar a compreensão das matérias dadas. É realizada através de duas provas escritas, decorrendo uma a meio do semestre e outra no fim. A componente prática pretende avaliar a capacidade dos alunos usarem os conhecimentos adquiridos na construção de tradutores dirigidos pela sintaxe. É concretizada através de dois trabalhos práticos, realizados em grupo de 4 a 5 elementos.

bibliografia base
Apontamentos de linguagens formais e autómatos / Artur Pereira / 2007 Fundamentals of the theory of computation: principles and practice / Raymond Greenlaw, James Hoover / 1998 Compilers : principles, techniques, and tools / Alfred Aho, Ravi Sethi, Jeffrey Ullman / 1986
bibliografia recomendada
  • Alfred Aho, Monica Lam, Ravi Sethi e Jeffrey Ullman, Compilers : principles, techniques, and tools, 2nd edition, 2007.

  • Pedro Reis Santos e Thibault Langlois; Compiladores: da teoria à prática, 2014.

  • Raymond Greenlaw e James Hoover, Fundamentals of the theory of computation, 1998.

  • Artur Pereira, Apontamentos de Linguagens Formais e Autómatos, 2008-2015.

  • John E. Hopcroft e Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, 1979.

Este sítio web utiliza cookies sem recolher informação pessoal que permita a identificação dos utilizadores. Ao navegar neste sítio está a consentir a sua utilização.saber mais
Para que esta página funcione corretamente deve ativar a execução de Javascript. Se tal não for possível, algumas funcionalidades poderão estar limitadas.