Processamento de Linguagens e Compiladores
Matemática e Ciências da Computação

2005/2006
Equipa Docente e Horário
Estrutura e Funcionamento
Objectivos
Avaliação
Programa
Fichas Teórico-Práticas
Software
Contribuições dos Alunos
Notas & Exames
Trabalhos Práticos
Sumários
Bibliografia

Esta página contém informação relativa à cadeira de Processamento de Linguagens e Compiladores a decorrer no ano lectivo 2005-2006 . Processamento de Linguagens e Compiladores é uma cadeira do 2º Semestre do 2º Ano da licenciatura em Matemática e Ciências da Computação.

Esta página está a ser gerada a partir de um documento XML, por uma ferramenta que utiliza os métodos de programação leccionados neste curso (eg, expressões regulares, autómatos finitos e gramáticas independentes do contexto). A partir da especificação XML é produzida esta página, bem como a sua representação em LaTeX. O formato LaTeX dá origem aos seguintes documentos em postscript e pdf: [ ps ] , [ pdf ]

Novidades e Avisos

(27-07-06)
  • As notas da época de recurso estão disponíveis.
  • Os alunos podem consultar os exames na 6a feira (dia 28 de Julho).
(17-07-06)
  • As notas finais estão disponíveis.
  • Possíveis soluções dos trabalhos práticos (apresentadas pelos alunos) estão disponíveis na secção Contribuições dos Alunos
(14-07-06)
  • As notas da duas chamadas da época normal de exames estão disponíveis.
  • Os enunciados dos exames estão também disponíveis
  • Os exames podem ser consultados na próxima segunda-feira (dia 17)
  • As notas dos testes práticos serão disponibilizadas na segunda-feira (tl como se pode ler em baixo...)
(27-06-06)
  • Pela quantidade de emails que tenho recebido a perguntar quando é o dia 19, vejo que esta página está a ser acedida frequentemente. Já agora acedam também à página seguinte que permite ver resultados de análise de performance de várias linguagens de programação (cerca de 50) e dos seus compiladores: The Computer Language Shootout Benchmarks
  • Sim ! O ghc e a linguagem Haskell está com uma performance bem à frente do Java e cada vez mais próxima da linguagem C (gcc) ! !
  • BTW, este concurso não está a ser organizado pelas pessoas das linguagens funcionais...
  • Depois de todos os alunos terem consultado esta página as notas serão afixadas :-)
(16-06-06)
  • As notas da apresentação/defesa dos Trabalhos Práticos já estão disponíveis.
  • As notas dos testes práticos serão disponibilizadas na 2a feira (19 de Junho)
(05-06-06)
(30-05-06)
  • Uma nova versão do Gram2C está disponível . Apaguem a versão antiga e instalem esta nova versão.
  • Esta nova versão tem na directoria de Exemplos o exemplo List estudado hoje nas aulas. Re-utilizem a Makefile e vejam como o código C gerado é incluído no lex e yacc
  • Os apontamentos sobre as regras de conversão de Gramáticas Abstractas para C estão disponíveis em pdf e em ficheiro fonte
    • Vejam o exemplo Block, especialmente como o yacc cria a Árvore Abstracta que respresenta uma frase. No trabalho prático terão de criar uma Árvore Abstracta que repesenta BC--.
(26-05-06)
  • O 2º trabalho prático já está disponível.
  • Na secção de software está disponibilizado algum software necessário na resolução deste trabalho.
(28-04-06)
(28-04-06)
  • A Fichas Teórico-Prática nº7 já está disponível.
  • Um exemplo de um scanner escrito directamente em Haskell está disponível em scanner.hs
  • Exemplos de scanners escrito em Lex estão disponíveis nos apontamentos Especificação e Processamento de Linguagens (ver bibliografia)
(12-04-06)
  • O 1º trabalho prático já está disponível.
(11-04-06)
  • A Fichas Teórico-Prática nº6 já está disponível.
  • As regras de conversão de expressões regulares em autómatos finitos não deterministas estão disponíveis em conversaoRegExp2Ndfa.pdf.
(25-03-06)
  • As Fichas Teórico-Práticas nº4 e nº5 já estão disponíveis.
(20-03-06)
  • A Ficha Teórico-Prática nº3 já está disponível.
(13-03-06)
  • A Ficha Teórico-Prática nº2 já está disponível.
(06-03-06)
  • A Ficha Teórico-Prática nº1 já está disponível.
(01-03-06)
  • Aula teórica de substituição: 5ª Feira, dia 2 de Março, 10:00, sala DI 0.04
(27-02-06)
  • A página da disciplina está no "ar".

1- Equipa Docente e Horário

  • João Saraiva

    Teóricas: MCC T1 2ª Feira - 14:00-15:00 sala CP2-102
    T2 4ª Feira - 11:00-12:00 sala CP3-103
    Teórica-Prática: MCC TP1 2ª Feira - 15:00-16:00 sala ? ?
    MCC TP2 4ª Feira - 09:00-10:00 sala CP3 205
    Prática: MCC P1 3ª Feira - 09:00-11:00 sala DI 1.09
    Dúvidas MCC 3ª Feira - 14:00-18:00
  • Tiago Alves

    Prática: MCC P2 3ª Feira - 11:00-13:00 sala DI 1.09
    Dúvidas MCC ? ? ?
2- Estrutura e Funcionamento

Exposição da matéria fundamental -- motivação, conceitos, definições, métodos e justificações -- a nível das aulas teóricas. Resolução de exercícios de consolidação, a nível das aulas teórico-práticas, no quadro. Realização no computador, no contexto das aulas práticas, de exercícios práticos e pequenos projectos. Resolução extra aulas de dois trabalhos concretos de aplicação, recorrendo às linguagens de programação Haskell e C.
3- Objectivos

É objectivo deste curso levar os alunos a:
  • Compreender os conceitos de análise e geração automática de programas.
  • Aprofundar os conceitos de Gramática Independentes do Contexto e a sua utilização na especificação e no desenvolvimento de processadores de linguagens formais.
  • Analisar e compreender as diferentes técnicas de parsing: "Top-Down" e "Bottom-Up"
  • Analisar e compreender as tarefas de unparsing/pretty priting, análise de nomes, optimização e geração de código.
  • Reforçar a aptidão dos alunos para desenvolver programas correctos e eficientes.
4- Avaliação

A Avaliação tem uma componente teórica e uma componente prática, ambas obrigatórias.

De acordo com o regulamento actualmente em vigor na UM, a nota teórica (NT) será obtida através da realização de 1 prova individual escrita . Essa prova tem as instâncias a seguir indicadas (um aluno só poderá fazer melhoria na época de recurso):
  • Exame, realizado na 1ª chamada da época normal, no fim do 1º semestre
  • Exame, realizado na 2ª chamada da época normal, no fim do 1º semestre
  • Exame, realizado na época de recurso
A componente prática será formada por 2 componentes
  • 2 trabalhos práticos ( P1 e P2 ) a realizar durante o semestre
  • Duas provas individuais escrita ( PE ) sobre os trabalhos práticos com 15 minutos de duração. Esta prova escrita será realizada imediatamente depois da entrega dos trabalhos práticos.
A nota prática ( NP ) será obtida de acordo com a seguinte fórmula:
NP = P1 * 0.4 + P2 * 0.4 + PE * 0.2
A nota final será determinada de acordo com a seguinte fórmula:

NF = ( NT + NP )/2
Exige-se 8 valores como nota mínima em cada uma das partes.
5- Programa

  • Processamento de Linguagens Formais
    • Conceitos e exemplos
    • Arquitectura dos Processadores de Linguagens
  • Análise Léxica de Linguagens Formais
    • Conceitos e suas tarefas
    • Especificação via Expressões Regulares
    • Construção de Analisadores Léxicos basedos em Autómatos Finitos
    • Geração Automática de Analisadores Léxicos
      • Breve Introdução ao sistema Lex
  • Análise Sintática de Linguagens Formais
    • Conceitos e suas tarefas
    • Especificação da Estrutura de Linguagens via Gramáticas Independentes do Contexto
      • Gramáticas/Estruturas Concretas versus Gramáticas/Estruturas Abstractas
    • Representação de Gramáticas no Paradígma Imperativo
      • De Gramáticas Concrectas para Especificações em Yacc
        • Breve Introdução ao sistema Yacc
      • De Gramáticas Abstractas para Tipos de Dados Estruturados em C
    • Técnicas de Parsing
      • Parsers Top-Down
      • Parsers Bottom-Up
  • Análise Semântica de Linguagens Formais
    • Conceitos e Tarefas
    • Implementação de Analisadores Semânticos: Problemas e Soluções
      • Analisadores Semânticos baseados em Multiplas Travessias na Estrutura Abstracta da Linguagem
      • "Colagem" de Travessias: A solução Imperativa versus Funcional
6- Fichas Teórico-Práticas

As fichas a realizar em cada aula prática são disponibilizadas nesta secção. As fichas estarão disponíveis na sexta-feira da semana anterior à aula a que se destinam.
  • Ficha Teórico-Prática nº 1: Expressões Regulares
  • Ficha Teórico-Prática nº 2: Autómatos Finitos Deterministas
  • Ficha Teórico-Prática nº 3: Autómatos Finitos Não Deterministas
  • Ficha Teórico-Prática nº 4: > Conversão de Autómatos Finitos Não Deterministas em Deterministas
  • Ficha Teórico-Prática nº 5: Conversaõ de Expressões Regulares em Autómatos Finitos Não Deterministas
  • Ficha Teórico-Prática nº 6: Lex: Um gerador de Analisadores Léxicos
  • Ficha Teórico-Prática nº 7: Gramáticas Independentes do Contexto em Haskell
  • Ficha Teórico-Prática nº 8: Propriedades de Gramáticas Independentes do Contexto
  • Ficha Teórico-Prática nº 9: Gramáticas Independentes do Contexto em Yacc
    • (disponível em breve)
  • Ficha Teórico-Prática nº 10: Árvores de Sintaxe Abstractas em C
7- Software

O seguinte software utilizado/recomendado nesta disciplina está já disponível:
  • Expressões Regulares: O sistema HaLeX está disponível na página oficial do sistema HaLeX.html e em HaLeX_1.1.tgz .
  • Gramáticas Independentes do Contexto: O Sistema HaGLR: Disponível em breve.
  • Árvores de Síntaxe Abstractas: Sistema Gram2C: Um Gerador de Árvores Abstractas em C
    • O Gram2C utiliza o Bohem's Garbage Collector (ver abaixo)
    • Este gestor de memória é distribuído com o Gram2C (logo, instalando o Gram2C, instala-se também o gc ! )
    • código fonte: Gram2C.tgz
  • Máquinas Virtuais:
    • MSP - Um máquina de assembly muito simples:
      • O Simulador WinMSP: WinMSP.tgz
      • O WinMSP é distribuído em binário para o SO Windows. Para o executar em Linux devem instalar o sistema wine : Wine
      • Regras de Conversão de esturturas condicionais e ciclicas para MSP: msp.ps
    • SPIM - A MIPS32 Simulator
  • Gestão de Memória: O Gestor de Memória Boehm-Demers-Weiser para C/C + +
  • Literate Programming: O Sistema de Literate Programming NoWeb
8- Contribuições dos Alunos

Soluções dos trabalhos práticos apesentados:
9- Notas & Exames

O enunciado( em versão electrónica) dos exames propostos neste ano lectivo foram: Os resultados finais obtidos pelos alunos estão disponíveis aqui .

Os resultados finais incluindo a época de recurso estão disponíveis aqui .
10- Trabalhos Práticos

Os trabalhos práticos propostos são os seguintes:
  • Trabalho Prático nº 1: Processador de Gramáticas
  • Trabalho Prático nº 2: Um Interpretador da Linguagem BC--
Os resultados dos trabalhos práticos estão disponíveis aqui .
11- Sumários

A definir
Bibliografia

  • Andrew W. Appel Modern Compiler Implementation in C: basic techniques Cambridge University Press 1997
  • Andrew W. Appel Modern Compiler Implementation in ML: basic techniques Cambridge University Press 1997
  • Alfred V. Aho and Ravi Sethi and Jeffrey D. Ullman Compilers: Principles, Techniques and Tools Addison-Wesley 1986
  • João Saraiva Language Processing (with a Functional Flavour) DI/UM 1ª Edicao 2000
  • João Saraiva Especificação e Processamento de Linguagens DI/UM 1ª Edicao [PS] [HTML] 1995
  • William M. Waite and Lynn R. Carter An Introduction to Compiler Construction Harper Collins 1993
  • Thomas Niemman A Compact Guide to Lex & Yacc [PDF] [HTML]
  • M. E. Lesk and E. Schmidt Lex - A Lexical Analyzer Generator. Computing Science Technical Report No. 39, Bell Laboratories, Murray hill, New Jersey [PDF] 1975
  • Stephen C. Johnson Yacc: Yet Another Compiler Compiler Computing Science Technical Report No. 32, Bell Laboratories, Murray hill, New Jersey [PDF] 1975
  • John Levine, Tony Mason and Doug Brown lex & yacc O'Reilly & Associates, Inc 1992
  • João Saraiva HaLeX: A Haskell Library to Model, Manipulate and Animate Regular Languages ACM Workshop on Functional and Declarative Programming in Education (FDPE/PLI'02), Pittsburgh, USA, [PS] [HTML] 2002
  • John Hopcroft, Rajeev Motwani and Jeffrey Ullman Introduction to Automata Theory, Languages and Computation Addison-Wesley 2nd Edition Edicao [HTML] 2001
  • R. Floid and R. Beigel The Language of Machines: An Introduction to Computability and Formal Languages Computer Science Press 1994
    • Repeated Key FB94
  • S.P.Jones, et al Report on the Programming Language Haskell 98 [HTML] [PS] [PDF] 1999
  • R. Bird Introduction to Functional Programming using Haskell Prentice Hall 1998
  • S. Thompson Haskell - The Craft of Functional Programming Addison-Wesley 2ª Edicao 1999
  • N. Jones, C. Gomard and P. Sestoff Partial Evaluation and Automatic Program Generation Prentice Hall [HTML] 1993
  • E. Horowitz and S. Sahni Fundamentos de Estruturas de Dados Editora Campus 1984
Pagina mantida por:

João Saraiva

jas@di.uminho.pt		 Page produced by a Tool generated by LRC from the XML document pagina_plc.xml

Last Change on Thu Jul 27 11:40:28 2006