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

Engenharia de Sistemas e Informática

Ano Lectivo 2002/2003
Informações Gerais
Estrutura e Funcionamento
Objectivos
Avaliação
Programa
Sumários
Software
Trabalhos Práticos
Bibliografia

Esta página contém informação relativa à cadeira de Processamento de Linguagens I a decorrer no ano lectivo 2002-2003 . Processamento de Linguagens I é uma cadeira do 2º Semestre do 3º Ano das licenciaturas em Engenharia de Sistemas e Informática e em Matemática e Ciências da Computação. Referências para páginas de instâncias anteriores podem ser encontradas nos seguintes endereços:

Ano Lectivo 2001-2002: Página
Ano Lectivo 2000-2001: Página
Ano Lectivo 1999-2000: Página

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, gramáticas independentes do contexto e gramáticas de atributos). 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

(18-07-03)
  • Notas Finais: lESI , MCC
  • Os grupos que ficaram de enviar o código fonte dos seus trabalhos práticos (para ser disponibizado nesta página), enviem-me por email o "tar.gz" do projecto.
(21-07-03) Melhoria do Trabalho Prático
  • Sexta-Feira, dia 25 de Julho (sexta-feira)
  • Os grupos devem inscrever-se nos técnicos para reservarem o período para mostrarem o trabalho
  • Caso algum grupo não possa entregar nessa altura, devem contactar um dos docentes de modo a marcar um outro dia para a entrega.
(18-07-03)
  • Notas dos Exames e trabalhos Práticos: lESI , MCC
  • Na 2a Feira será definido o período para apresentarem a melhoria ao 2o. trabalho Prático.

    Nesse dia estaremos cá para mostrar os exames e tirarmos dúvidas sobre o trabalho prático
(23-06-03)
  • Exames de anos anteriores: exame 1 , exame 2 e exame 3

    (notar que estes exames se referem a outra instância da disciplina em que se leccionou gramáticas de atributos com mais detalhe)
  • Aula Teórica do Dr. Marjan Mernik:
    • Slides da aula: slides e gramática de atributos, escrita em LISA, para o exemplo da máquina de calcular: desk.lisa
  • Extras/Melhoria ao Trabalho Prático nº 2:
    • Os grupos podem apresentar os extras ao TP2 de modo a melhorar a respectiva nota até à Época de Recurso (26 de Julho).
    • Em breve será anúnciado nesta página o dia (perto do dia 26 de Julho) em que nós receberemos as melhoria
  • Um artigo (que será apresentado em breve) e que utiliza um dos trabalhos práticos proposto hà dois anos atrás como exemplo de estudo: artigo
(09-06-03) Trabalho Prático nº2: Entrega + Info:
  • A entrega do trabalho prático será feita em:
    • sexta-feira (dia 13 de Junho) - Manhã
    • segunda-feira (dia 16 de Junho) - Tarde
    • terça-feira (dia 17 de Junho) - Manhã
  • Cada grupo deverá reservar uma hora para apresentar o trabalho num desses períodos
  • As folhas para marcação estão disponíveis nos técnicos (junto da sala aberta)
  • Compete ao grupo instalar e mostrar os dois trabalhos a executar nos laboratórios do DI
  • Todos os elementos do grupo têm de estar presente na defesa dos trabalhos práticos
  • Extras ao Trabalho Prático nº 2 :
    • Os extras (e apenas os extras) podem ser apresentados mais tarde (nunca depois da 2a Chamada) em data a combinar directamente com um dos docentes
    • No caso do extra nº1 (combinadores de documentos) é necessário incluir na especificação SSL vários módulos da biblioteca ag_lib (distribuída com as sources C do LRC). Na Makefile que utilizei para gerar a solução do trabalho estão definidos esses módulos. Essa Makefile está disponível aqui Makefile .
    • Os combinadores de documentos usam algumas funções C, definidas no módulo C "docCfiles.c". Este módulo é distribuído com a solução C do trabalho prático. Copiem esse ficheiro para a vossa directoria e alterem a vossa Makefile para o incluir na especificação: Vejam como este módulo C é incluído na especificação na Makefile do link acima.
    • Depois de se definirem as regras para construir um documento abstracto será necessário usar gramáticas de atributos de ordem superior para aceder à reprsentação em LaTeX e HTML do documento criado. Para tal, será necessário falar 5 minutos com um dos docentes para ele explicar como isso é feito.
    • Para utilizar dosi ficheiro diferentes para os estilos e a base de dados bibliográfica, criamos um ficheiro C com uma nova função main evaDoc.c . Este ficheiro está a ser utilizado pela solução C deste trabalho (ver respectiva Makefile acima). Este ficheiro assume o seguinte:
      • Existe uma produção da forma:

        BibTeXStyle : ConsBibTeXStyle (BibStyle Bibtex)

        em que BibTeXStyle é a raiz da gramática abstracta que define a linguagem completa, onde: BibStyle respresenta abstractamente a linguagem de estilos e Bibtex respresenta abstractamente a linguagem BibTex--
      • Existe uma gramática concreta única para ambas as linguagens. Porém, existem (pelo menos) dois não terminais por onde podemos iniciar derivação e que controem árvores abstractas do tipo BibStyle e Bibtex.
(30-05-03)
(30-05-03)
  • Ficha nº2 totalmente resolvida : postscript e em sources (ver ficheiro Ficha2.nw)
  • Na distribuição C do LRC estão incluídos vários exemplos de processadores de linguagens e ambientes (gráficos) de programação: Block (falamos na aula), Desk (a linguagem Calculadora) e MicroC.
(23-05-03) Ficha nº2 parcialmente resolvida: ficha21.nw
(23-05-03) LRC:
  • Para instalar o LRC em red-hat 8 ou 9 é necessário usar a versão 6.1 do Boehm' garbage collector (GC).
  • A versão do LRC disponibilizada ontem, estava a usar uma versão anterior do GC. Actualizei hoje o LRC com a última versão do GC. As novas fontes em C do LRC estão disponíveis em: [ lrc.tgz ]
(22-05-03) Trabalho Prático nº2 LRC: Fontes em C
(29-04-03) Aulas teórico práticas: Ficha 2
(29-04-03) Entrega do 1º Trabalho Prático

Regras para a Entrega do Trabalho Prático:
  • O trabalho prático deve ser entregue até, sexta-feira, dia 2 de Maio, à 24 horas
  • A entrega é feita enviando um email único para jas@di.uminho.pt
    • O Assunto (subject) do email tem de ser: PL1 TP1
    • O Conteúdo deverá apenas indicar a constituição do grupo, no formato definido pela seguinte expressão regular: (NUMERO,CURSO,NOME \newline) +
    • Em Anexo (attachment) deverão incluir um ficheiro único que contém o trabalho (ie, o relatório, o código fonte, a makefile, o ficheiro readme, etc). Usem zip ou tar .
    • Por cada dia de atraso na entrega do trabalho será aplicada uma penalização de 1 valor .

      (não adianta alterarem a hora do email, uma vez que onde me encontro são 8 horas mais cedo, e por isso vou estar online até às 24:00)
    • Posteriormente será marcada uma apresentação do trabalho com todos os elementos do grupo presentes
    • O 2º Trabalho Prático será divulgado na próxima semana
(17-04-03) Aula Teórica do Dr. Anthony Sloane
(03-04-03)
  • Sistema LRC
  • Aulas teórico práticas: Ficha
  • Na próxima semana não funcionam os turno teórico-práticos leccionados por João Saraiva. Os alunos desses turnos deverão assistir a uma aula de substituição na Sexta-feira, das 16:00 - 18:00 horas, dia 11 de Abril (sala DI 1.09).
(24-03-03) Trabalho Prático nº1
  • Enúnciado: documento [ pdf ] e literate programming [ noweb ]
  • Para produzir o ficheiro pdf a partir do ficheiro NoWeb fazer:
    • O documento LaTeX/NoWeb utiliza uma base de dados bibliográfica BibTeX. A base de dados bibliográfica necessária está disponível no ficheiro pli.bib
    • Estilo NoWeb necessário para o LaTeX: noweb.sty
    • Extrair o LaTeX: noweave -delay tp1.nw > tp1.tex
    • produzir pdf usando o LaTeX:
      • pdflatex tp1.tex (por exemplo)
      • bibtex tp1.tex
      • pdflatex tp1.tex (actualizar as citações biblio.)
  • Para extrair os módulos C e Lex/Yacc a partir do ficheiro NoWeb fazer:
    • Para extrair um módulo, utiliza-se a ferramenta notangle do NoWeb, em que a opção -R indica qual o fragmento a extrair. Por exmplo, para extrair o fragmento ArvoreAbst.c para o ficheiro com o mesmo nome fazemos: notangle -RArvoreAbst.c tp1.nw > ArvoreAbst.c
    • No caso da makefile temos de garantir que os "tabs" são considerados: notangle -t8 -Rmakefile tp1.nw > makefile
(17-03-03) Apontamentos sobre Gramáticas Abstractas em C:
(18-02-03) A página da disciplina está no "ar".

1- Informações Gerais

A cadeira de Processamento de Linguagens I é leccionada aos curso de Lincenciatura em Matemática e Ciências da Computação e Licenciatura em Engenharia de Sistemas e Informática, especialização em Tecnologias do Software.
  • Engenharia de Sistemas e Informática
    • Código: RT 5306O4
    • Ano/Semestre: 3º Ano / 2º Semestre
    • Escolaridade: 2 Teóricas + 2 Teórico-Práticas
  • Matemática e Ciências da Computação
    • Código: RT 7006N7
    • Ano/Semestre: 3º Ano / 2º Semestre
    • Escolaridade: 2 Teóricas + 2 Teórico-Práticas

1.1- Equipa Docente e Horário

  • João Saraiva

    Teóricas: LESI/MCC T1 2ª Feira - 11:00-12:00 sala CP2-203
    T2 5ª Feira - 10:00-11:00 sala CP2-103
    Teórica-Prática: LESI TP1 3ª Feira - 08:00-10:00 sala DI 0.03
    Teórica-Prática: MCC TP2 5ª Feira - 14:00-16:00 sala DI 1.09
    Dúvidas LESI/MCC 3ª Feira - 16:00-18:00
  • José João Almeida

    Teórica-Prática: MCC TP1 4ª Feira - 11:00-13:00 sala DI 1.09
    Teórica-Prática: LESI TP2 5ª Feira - 17:00-19:00 sala DI 0.03
    Dúvidas LESI/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 e no computador. Realização, no computador, extra aulas de trabalhos concretos de aplicação, recorrendo a ferramentas como Lex/Yacc e o sistema LRC .
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"
  • Aprender uma nova metodologia de programação: Programação baseada em Gramática de Atributos e a sua utilização na especificação e desenvolvimento de processadores de linguagens formais.
  • Aprender o conceito de ambiente de programação e a sua especificação via gramáticas de atributos
  • Relacionar gramáticas de atributos com programação funcional "lazy".
  • 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 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 2º semestre
  • Exame, realizado na 2ª chamada da época normal, no fim do 2º semestre
  • Exame, realizado na época de recurso
A componente prática seré formada por 2 trabalhos para realização em grupo, sendo entregues acompanhados de um relatório sucinto e discutidos em frente ao computador: A nota prática será a média aritmética das classificações obtidas nos 2 trabalhos avaliados. A nota final será determinada de acordo com a seguinte fórmula:

NotaFinal = NotaTeorica * 0.50 + (NotaPratica - Delta / 2) * 0.50

sendo Delta = | NT - NP |

Exige-se 8 valores como nota mínima em cada parte.
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
    • Especificação da Semântica de Linguagens via Atributos
      • Programação com Atributos
      • Gramáticas de Atributos
      • Geração Automática de Analisadores Semânticos a partir de Gramáticas de Atributos
        • O Sistema de Gramáticas de Atributos LRC

          Geração de analisadores semânticos na linguagem C e Haskell
      • De Gramáticas de Atributos para Programas Circulares "Lazy"
  • Ambientes de Programação
    • Introdução e Exemplos
    • Especificação de Ambientes de Programação via Gramáticas de Atributos
    • Especificação do Interface via Gramáticas de Atributos
    • Geração de Ambientes de Programação no Sistem LRC
6- Sumários

7- Software

Neste curso será utilizado o seguinte software:
8- Trabalhos Práticos

  • Trabalho Prático nº1: Ver secção novidades e aviso
  • Trabalho Prático nº2:
Bibliografia

  • Alfred V. Aho and Ravi Sethi and Jeffrey D. Ullman Compilers: Principles, Techniques and Tools Addison-Wesley 1986
  • 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
  • João Saraiva, Matthijs Kuiper and Pedro Henriques Tutorial on Language-based Environments [PS] 2000
  • Thomas Reps and Tim Teitelbaum The Synthesizer Generator Reference Manual third edition Edicao Springer Verlag 1989
  • Brian Kernighan and Dennis Ritchie The C Programming Language Prentice Hall 1988
Pagina mantida por:

João Saraiva

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

Last Change on Thu Jul 31 19:29:06 2003