Objetivo e resultados da aprendizagem

Processamento de Linguagens / Compiladores

 

Os principais objetivos desta Unidade Curricular são:

- 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.

No final da Unidade Curricular o estudante deve ser capaz de,

- conceber compiladores;

- Conceber, planear, desenhar e implementar processadores de linguagens segundo determinadas regras lexicais e sintácticas;

- Conceber e implementar em software as várias etapas relacionadas com compiladores;

- Perceber os detalhes internos das linguagens de programação e dos seus compiladores.

 

Programa

Processamento de Linguagens / Compiladores

 

Resumido

Capítulo 1. Linguagens e processadores

Capítulo 2. Linguagens formais

Capítulo 3. Autómatos e respectivas linguagens

Capítulo 4. Análise léxica

Capítulo 5. Análise sintáctica

Capítulo 6. Análise semântica

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

Detalhado

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 sentenciais

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. FLEX : um gerador automático de analisadores léxicos

Capítulo 5 - Análise sintática

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

 

Bibliografia

Processamento de Linguagens / Compiladores

 

"Compiladores : Princípios, Técnicas e Ferramentas", 1995

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

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

ISBN: 85- 216- 1057- 2

 

"Processadores de Linguagens. Da concepção à implementação", 1998

Rui Gustavo Crespo

IST Press

ISBN : 972- 8469- 01- 2

 

"Lex & Yacc", 1990

Tony Manson e Doug Brown

O’Reilly & Associates

ISBN : 0- 937175- 49- 8

 

Avaliação

Processamento de Linguagens / Compiladores

 

A avaliação no período de Aprendizagem consiste no seguinte:

- 2 Testes escritos (Frequências): 15 valores (7 + 8)

- 1 Trabalho prático: 5 valores

Aprendizagem = Testes escritos + Trabalho prático

em que,

- Presença nas aulas inferior a 75%   ==>   Reprovado e Não Admitido a Exame

- Trabalho prático < 1,5 (em 5)   ==>   Reprovado e Não Admitido a Exame

- Aprendizagem < 5,5 (em 20)   ==>   Reprovado e Não Admitido a Exame

- Aprendizagem >= 9,5 (em 20)   ==>   Aprovado e Dispensado de Exame

- Outros casos   ==>   Reprovado e Admitido a Exame

 

Exame = Teste escrito + Trabalho prático

em que,

- Teste escrito: 15 valores

- Trabalho prático (realizado durante o período de Aprendizagem): 5 valores

 

Datas dos testes

Processamento de Linguagens / Compiladores

 

 Tipo

Data

Hora

Salas

Enunciado

Resolução

Trabalho

07-01-2018

23:59

-

Download

-

Frequência 1

13-11-2017

18:00

6.01 - 6.05

Download

Download

Frequência 2

11-12-2017

18:00

-

Download

Download

Trabalho prático:

1. Deverá ser entregue em formato digital e enviado via e-mail para cbarrico@di.ubi.pt os seguintes documentos:

- Relatório (em pdf)

- Código (em flex/lex e em linguagem C)

2. Ficheiros de dados disponíveis (texto) para testes:

Endereços URL

 

Classificações obtidas

Processamento de Linguagens / Compiladores

 

Ano letivo 2017/2018 (necessita de senha de acesso)

Presenças

Trabalhos práticos

Frequência 1

Frequência 2 (Os testes podem ser consultados na aula teórica da próxima semana)

Aprendizagem

Exame Época Normal

Exame Época Recurso

 

Apontamentos

Processamento de Linguagens / Compiladores

 

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ática (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)

 

Folhas práticas

Processamento de Linguagens / Compiladores

 

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

Ficheiros de dados disponíveis

Texto1.txt

InteirosReais.txt

NumerosTelefone.txt

Resolução de exercícios da folha prática "Análise léxica":

Exercício 16.b)

Exercício 16.d)

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

Testes (enunciados e resoluções)

Ano Lectivo

Tipo

Enunciado

Resolução

2009-2010

Frequência 1

Download

Download

2009-2010

Frequência 2

Download

Download

2009-2010

Exame 1

Download

Download

2009-2010

Exame 2

Download

Download

 

 

 

 

2010-2011

Frequência 1

Download

Download

2010-2011

Frequência 2

Download

Download

2010-2011

Exame Normal

Download

Download

2010-2011

Exame Recurso

Download

Download

 

Horário

Processamento de Linguagens / Compiladores

 

Horas

Segunda

Sala

Terça

Sala

Quarta

Sala

Quinta

Sala

Sexta

Sala

8

  

 

 

 

 

 

 

 

 

 

9

 

 

EI-TE

6.3

EI-PL2

6.13

 

 

 

 

10

 

 

EI-TE

6.3

EI-PL2

6.13

 

 

 

 

11

 

 

ATEND

G-4.2

EI-PL1

6.13

 

 

 

 

12

 

 

ATEND

G-4.2

EI-PL1

6.13

 

 

 

 

13

 

 

  

  

 

 

 

 

 

 

14

 

 

 

 

 

 

 

 

 

 

15

 

 

 

 

 

 

 

 

 

 

16

ATEND

G-4.2

 

 

 

 

 

 

 

 

17

ATEND

G-4.2

 

 

 

 

 

 

 

 

18