Departamento de Informática (UM)

Teoria das Linguagens e Compilação

14922 [ME80ME8002006773]

[Mestrado em Engenharia Física - Física da Informação]

S1

Pedro Manuel Rangel Santos Henriques

Objetivos

O conteúdo programático proposto é talhado item a item para fornecer todo o suporte concetual e teórico que permite ao aluno desenhar e especificar linguagens através de instrumentos formais como sejam gramáticas e expressões regulares e ainda lhe permite usar essas especificações para gerar automaticamente os programas necessários para reconhecer e processar as frases dessas linguagens.
Assim acredita-se firmemente que, com os elementos fornecidos, os alunos poderão adquirir em um semestre as capacidades identificadas como objetivo de aprendizagem desta UC.

Programa

1. Introdução ao Processamento de Linguagens: noção de Linguagem e de Gramática, Interpretador versus Compilador; Arquitetura de um processador de linguagens: análise léxica, análise sintática e análise semântica.
2. Linguagens Regulares e Análise Léxica; Especificação de linguagens regulares com expressões regulares; Reconhecimento de linguagens especificadas com expressões regulares: o conceito de autómato; Conversão de Expressões Regulares em Autómatos Finitos Determinísticos; A ferramenta GAWK como Sistema de Produção; Flex como gerador de autómatos.
3. Análise Sintática: Linguagens e Gramáticas Independentes de Contexto; Estrutura e funcionamento de um parser; Parsing Top-Down: o Recursivo-descendente e LL (1); Parsing Bottom-UP: LR(0) e SLR (1); Utilização da ferramenta Yacc como gerador de parsers Bottom-UP. 4. Análise Semântica e Transformação especificada via Gramáticas Tradutoras (GT) ---Tradução Dirigida pela Sintaxe; o Gerador de Compiladores Yacc.

Bibliografia

Santos, P.R., Langlois, T. (2014). Compiladores – Da Teoria à Prática, FCA.

Crespo, R. G. (1998). Processadores de Linguagens: da concepção à implementação, IST-Press.

Aho, Sethi, Ullman (1986). Compiler Principles, Techniques and Tools, Addison-Wesley.

Waite, W. (1993), An Introduction to Compiler Construction, HarperCollin College Publishers.

Grune, D., Reeuwijk, K., Bal. H. E., Ceriel, Jacobs, J. H., Langendoen, K. (2012). Modern Compiler Design, 2nd. edition, Springer.

Cooper, K. C., Torczon, L. (2011). Engineering a Compiler, 2nd. edition, Elsevier/Morgan-Kaufmann.

Appel, A. W., Palsberg, J. (2002). Modern Compiler Implementation in Java, Cambridge University Press.

Appel, A. W., Ginsburg, M. (2004). Modern Compiler Implementation in C, Cambridge University Press.

Pittman, Peters (1992). The Art of Compiler Design: theory and pratice, Prentice-Hall.

Brown, D., Levine, J., Mason, T., (2012). Lex & Yacc, 2nd Edition, Unix Programming Tools, O’Reilly.

Resultados da aprendizagem

- Especificar linguagens de domínio específico através de gramáticas
- Desenvolver processadores para essas linguagens com base na respetiva gramática
- Extrair dados de um texto com base em regras de produção (padrão-ação) baseadas em expressões regulares
- Transformar qualquer texto num outro formato com base em regras de produção (padrão-ação) baseadas em expressões regulares
- Usar programas que produzem programas com base em especificações formais (geradores de analisadores léxicos e de compiladores)
- Adquirir conhecimentos sobre autómatos como modelos formais de máquinas de estado e base de reconhecedores de frases guiados por tabela
- Utilizar ferramentas genéricas de informática em ambiente Linux baseadas em expressões regulares, em garfos ou outras.

Método de avaliação

A avaliação da aprendizagem envolve: um trabalho de desenvolvimento experimental, em grupo, consubstanciando uma componente de carácter individual. Tanto a componente individual como a de grupo têm limite de execução temporal bem definido, nunca excedendo o período lectivo.
A classificação final é dada por:

- 40% componente prática de grupo
- 60% componente individual.
É exigida avaliação positiva em ambas as componentes

Funcionamento

Turno: TP 1; Docente: Sofia Guilherme Rodrigues Santos; Dep.: DI; Horas: 30.