Compiladores

Proporcionar ao estudante um contacto aprofundado com as metodologias e técnicas utilizadas na construção de um compilador. 

Procurar tirar partido da complexidade envolvida no processo de construção de compiladores para motivar a modularização de programas e a sua construção optimizada.

Capítulo 1 - Linguagens e processadores

1. Linguagens

1.1. Definição

1.2. Linguagens naturais versus linguagens formais

1.3. Como se especifica uma linguagem

2. Processadores de linguagens

2.1. Definição

2.2. Tarefas de um processador de linguagens

2.3. Estratégias de processamento

2.4. Compiladores

2.5. Assemblers

2.6. Interpretadores

2.7. Tratamento de erros

Capítulo 2 - Linguagens formais

1. Conceitos básicos e notações

2. Gramáticas e linguagens

2.1. Definição de gramática geradora

2.2. Grafos de sintaxe

2.3. Derivação de frases

2.4. Linguagem gerada por uma gramática

2.5. Derivação de formas setenciais

2.6. Reconhecimento de uma frase

2.7. Símbolos anuláveis e símbolos inúteis

2.8. Árvores de derivação

2.9. Recursividade

2.10. Hierarquia de Chomsky

3. Linguagens independentes (livres) do contexto

3.1. Introdução

3.2. Forma normal de Chomsky

3.3. Árvores de derivação

3.4. Gramáticas redundantes

3.5. First, Follow e Lookahead

3.6. Gramáticas do tipo LL(1)

3.7. Gramáticas do tipo LL(k)

3.8.Gramáticas de atributos

4. Linguagens e expressões regulares

5. Gramáticas lineares e linguagens regulares

6. Linguagens sensíveis ao contexto e linguagens com estrutura de frase

Capítulo 3 - Autómatos e respectivas linguagens

1. Autómatos finitos

1.1. Definições

1.2. Representação de um autómato finito

1.3. Reconhecimento de uma frase

1.4. Construção de um AFND a partir de uma expressão regular

1.5. Conversão de um AFND num AFD

1.6. Conversão de uma expressão regular numa gramática regular

2. Autómatos de pilha

2.1. Definição

2.2. Reconhecimento de uma palavra

Capítulo 4 - Análise léxica

1. Definição

2. Métodos

2.1. Tabela de símbolos

2.2. Descrição através de expressões regulares

3. Tratamento de erros

4. Interligação entre os analisadores léxico e sintáctico

5. LEX : um gerador automático de analisadores léxicos

Capítulo 5 - Análise sintáctica

1. Objectivo

2. Estratégias gerais de parsing

3. Análise sintáctica descendente ("top-down")

3.1. Análise recursiva com retrocesso ("backtracking")

3.2. Analisador sintáctico predicativo recursivo

4. Analisador sintáctico predicativo não recursivo - parser LL(1)

5. Construção de tabelas sintácticas predicativas (Tabelas Oráculo)

6. YACC : um gerador de analisadores sintácticos

7. Análise ascendente ("bottom-up")

7.1. Princípios gerais

7.2. Método geral : parser de transição-redução

7.3. Análise sintáctica ascendente LR (parser LR)

7.4. Método SLR(1)

7.5. Método LALR(1)

Capítulo 6 - Análise semântica

1. Objectivo

2. Tradução dirigida pela sintaxe

Capítulo 7 - Geração de código

1. Código intermédio

2. Código final

Compiladores : Princípios, Técnicas e Ferramentas

Alfred V. Aho, Ravi Sethi e Jeffrey D. Ullman

LTC - Livros Técnicos e Científicos Editora, S.A., 1995

ISBN : 85- 216- 1057- 2

Processadores de Linguagens. Da concepção à implementação

Rui Gustavo Crespo

IST Press, 1998

ISBN : 972- 8469- 01- 2

Lex & Yacc

Tony Manson e Doug Brown

O’Reilly & Associates, 1990

ISBN : 0- 937175- 49- 8

Ensino-Aprendizagem

A avaliação será baseada nos seguintes elementos:

- 2 provas escritas: 6 valores (T1) + 8 valores (T2)

- Trabalhos práticos: 6 valores (TP)

- Presença nas aulas práticas (PP) : 50% presenças no mínimo (*)

(*) Esta regra não se aplica aos alunos que estejam abrangidos pelo estatuto de trabalhador-estudante (devidamente comprovado nos Serviços Académicos).

A nota final será obtida à custa da seguinte expressão:

NotaFinal = T1 + T2 + TP

em que 

- PP < 50%  ==>  Reprovado e Não Admitido a Exame

- TP < 2  ==>  Reprovado e Não Admitido a Exame

- NotaFinal < 6  ==>  Reprovado e Não Admitido a Exame

- T1 + T2 < 6  e  NotaFinal >= 6  ==>  Reprovado e Admitido a Exame

- NotaFinal >= 10  e  T1 + T2 >= 6  e  TP >= 2  e  PP >= 50%  ==>  Aprovado e Dispensado de Exame

Exame

A avaliação será baseada nos seguintes elementos :

- Prova escrita: 14 valores

- Trabalhos práticos: 6 valores (realizados durante o semestre)

Aulas teóricas

Capítulo 1 - Linguagens e processadores (apontamentos) (slides)

Capítulo 2 - Linguagens formais (apontamentos) (slides)

Capítulo 3 - Autómatos e respectivas linguagens (apontamentos) (slides)

Capítulo 4 - Análise léxica (apontamentos) (slides)

Capítulo 5 - Análise sintáctica (apontamentos) (slides)

Capítulo 6 - Análise semântica (apontamentos) (slides)

Capítulo 7 - Geração de código (apontamentos) (slides)

Ferramentas usadas nas aulas práticas (download)
Geradores automáticos de analisadores léxicos (LEX/FLEX) e sintáticos (YACC/BISON):

- Introdução ao FLEX

- LEX − A Lexical Analyzer Generator

- FLEX - Version 2.5 (1995)

- A Compact Guide To LEX & YACC

- YACC - Yet Another Compiler-Compiler

- BISON - Version 1.5 (1995)

- BISON - Version 2.4.1 (2009)

Links importantes

- Make - a tutorial

- Compilers Lecture Notes

- The Lex & Yacc Page

- A Compact Guide to Lex & Yacc

- Modern Compiler Implementation in C

- Lex and YACC primer/HOWTO

- Flex : Version 2.5 (1995)

Folha 1 - Linguagens formais

Folha 2 - Autómatos e respectivas linguagens

Folha 3 - Análise léxica

Folha 4.1 - Análise sintáctica descendente

Folha 4.2 - Análise sintáctica ascendente

Folha 5 - Análise semântica

Folha 6 - Geração de código

Testes do ano lectivo 2009/2010

Frequência 1  +  Resolução

Frequência 2  +  Resolução

Exame 1 

Exame 2

Construção de um analisador léxico e um sintático

Enunciado

Autómato

Código em C (texto + documento)

Código em LEX & YACC (texto + documento)

Ficheiros para teste: Fich_1, Fich_2

Enunciado do Trabalho Prático

Testes (enunciados e resoluções)

Ano Lectivo	Tipo	Enunciado	Resolução
1999-2000	Trabalho Prático	Download	Download
1999-2000	Frequência	Download	Download
1999-2000	Exame Normal	Download	Download
1999-2000	Exame Recurso	Download	Download
2001-2002	Frequência	Download	Download
2001-2002	Exame Normal	Download	Download
2002-2003	Frequência	Download	Download
2002-2003	Exame Normal	Download	Download
2002-2003	Exame Recurso	Download	Download

Horas	Segunda	Sala	Terça	Sala	Quarta	Sala	Quinta	Sala	Sexta	Sala
8
9
10
11	LFC-PL3	6.25	LFC-PL1	6.25
12	LFC-PL3	6.25	LFC-PL1	6.25
13
14			LFC-TE	6.18
15			LFC-TE	6.18
16
17	LFC-PL2	6.25
18	LFC-PL2	6.25
19