Métodos de Programação III

O conceito de Autómato Não-Determinista e da Linguagem gerada pelo AND
As funções de epsilon-closure, de caminho e de aceitação de uma frase
A sua modelação e implementação em Haskell
A utilização de ANDs para modelar sistemas reais do tipo "Máquina de Transição de Estados"

Aulas P de 2005/10/17

Tópicos:

Conversão de Autómatos Não-Deterministas em Autómatos Deterministas
Resolução da Ficha TP nuº 4

Resumo:

No final desta aula prática, os alunos devem ter ficado a saber, ou consolidado conhecimentos da última aula, relativos a:

O conceito de conversão de um AND para AD
A sua modelação e implementação em Haskell

Aulas P de 2005/10/24

Tópicos:

Cálculo Parcial de Programas aplicado à Especialização de Reconhecedores de Linguagens (funções dfaaccept e ndfaaccept baseados em Autómatos Deterministas e Não-Deterministas
Início da Resolução da Ficha TP nuº 6

Resumo:

No inicío da aula, fez-se uma revisão completa e muito detalhada a toda a matéria estudada até à data (ERs, DfAs e NDfAs e conversões entre eles) e sua relação, ligando cada tópico a cada uma das 5 fichas TP propostas. Chamou-se a atenção para o facto da Ficha 5 (que trata da conversão ER para NDfA) ter sido trabalhada apenas a nível das aulas T (mas estar na mesma disponível na página da disciplina).
Para consolida tudo isso, desenvolveu-se com cuidado e detalhe o exercício 1 fa Ficha 6, no quadro e faz a respectiva implementação em haskell para validar e comparar reconhecedores.

Na segunda parte da aula, discutiu-se o conceito de Partial Evaluation e o seu significado prático quando aplicada à especialização de programas com vista a obter versões mais eficientes (PE e optimização de programas).
Foram vistos alguns casos práticos e falou-se nos Geradores de Compiladores.
Começou-se a fazer o 2º exercício da Ficha 6: especialização da função dfaaccept.

Aulas P de 2005/10/31

Tópicos:

Cálculo Parcial de Programas aplicado à Especialização de Reconhecedores de Linguagens (funções dfaaccept e ndfaaccept baseados em Autómatos Deterministas e Não-Deterministas
Autómatos Deterministas Reactivos - introdução ao conceito e sensibilização
Conclusão da Resolução da Ficha TP nuº 6 e Início da Resolução da Ficha TP nuº 7

Resumo:

No inicío da aula, relembrou-se o importante conceito de Partial Evaluation (introduzido na aula anterior) e o seu significado prático quando aplicada à especialização de programas com vista a obter versões mais eficientes (PE e optimização de programas) e concluiram-se os exercícios 2 e 3 da Ficha 6 relativos à especialização das funções dfaaccept / dfawalk e ndfaaccept / ndfawalk.

Na segunda parte da aula, foi discutido o conceito de autómato reactivo, tendo-se procurado variados casos práticos (do nosso quotidiano) para ilustrar a potencialidade da ideia.
Antes de se começar a resolver as 2 alíneas do 1º exercício da Ficha 7, falou-se do método de programação baseado em autómatos reactivos e na estratégia simples de programação a ele associada: divisão do problema no modelo como máquina de transição de estados e seu enriquecimento com acções semânticas.

Aulas P de 2005/11/07

Tópicos:

Autómatos Deterministas Reactivos - o conceito e a aplicação
Conclusão da Resolução da Ficha TP nuº 7

Resumo:

Toda esta aula foi usada para reforçar o conceito de autómato reactivo, tendo-se procurado analisar com detalhe e modelar os problemas que faltavam da Ficha 7 -- exercícios 3, 4 e 5.
Para os dois últimos casos, em que não era dado o autómato, avaliaram-se abordagens alternativas em que uma complica o autómato (em número de estados e transições) mas é muito simples do ponto de vista semântico, e outra usa um autómato mais pequeno (com número de estados fixo, independente das alternativas) mas sobrecarrega a tarefa nas acções semânticas.
Ainda se falou novamente (devido à importância que o assunto tem no âmbito da disciplina) do método de programação baseado em autómatos reactivos e na estratégia simples de programação a ele associada: divisão do problema no modelo como máquina de transição de estados e seu enriquecimento com acções semânticas.

Aulas P de 2005/11/14

Tópicos:

Autómatos Deterministas Reactivos - sua implementação em Haskell
Resolução da Ficha TP nuº 8
(acesso à ficha resolvida)
Gramáticas Independentes de Contexto - introdução ao conceito básico e sua utilidade como Método de Programação
Introdução da Resolução da Ficha TP nuº 9

Resumo:

Grande parte desta aula foi ocupada com a discussão (através da resolução dos exercícios propostos na Ficha 8) da utilização de Monades como forma de implementar numa linguagem funcional (Haskell, no caso) os autómatos reactivos construídos nas duas últimas aulas para resolver os exercícios da Ficha TP 7.
Nesse sentido foram analisadas 4 situaações diferentes (a 1ª só retórica): utilização de Monades sem acções semânticas; utilização de Monades para realizar apenas operações de IO (escritas) aquando das transições; utilização de Monades para definir o estado do sistema (com um ou mais valores) e alterar esse estado; e ainda, utilização de Monades mistos, isto é, com estado e operações de IO.
Na parte final da aula introduziu-se a Ficha 9, tendo-se essencialmente discutido a importância das GIC na modulação de problemas em que um tratamento puramente sequencial, linear, do texto de entrada não é suficientemente poderoso para os resolver. Deu-se especial destaque à importância do novo conceito de símbolo não-terminal.

Aulas P de 2005/11/21

Tópicos:

Gramáticas Independentes de Contexto - definições formais básicas e introdução à escrita de GIC
Resolução da Ficha TP nuº 9 (problemas 1.1 a 1.4)

Resumo:

Pegando no 1º exercício da Ficha 9, relembrou-se a definição formal de GIC e introduziram-se as várias definições básicas que serão depois úteis para resolver a Ficha 10 (onde se faz a respectiva imlememtação em Haskell): gramática incompleta ou mal-formada; gramática ambígua; símbolos anuláveis, deriváveis e acesséveis (símbolos inúteis).
Procedeu-se então a escrita de várias gramáticas a partir de: expressões regulares; exemplos de frases válidas; e descrição da linguagem pretendida. Deu-se especial destaque à importância da estrutura das frases pretendidas e ao conceito de símbolo não-terminal.

Aulas P de 2005/11/28

Tópicos:

Gramáticas Independentes de Contexto - escrita de GIC e sua implementação em Haskell
Conclusão da Resolução da Ficha TP nuº 9 (problemas 1.4 e 1.5)
(acesso à ficha resolvida)
Resolução da Ficha TP nuº 10
(acesso à ficha resolvida)

Resumo:

Com base nos exercícios já resolvidos da Ficha 9, procedeu-se à escrita de mais algumas gramáticas a partir da descrição da linguagem pretendida e de exemplos de frases válidas. Deu-se especial destaque à importância da estrutura das frases pretendidas e ao conceito de símbolo não-terminal.
Concluída a Ficha 9, procedeu-se ao estudo cuidado da sua implementação em Haskell, analisando os exercícios propostos na Ficha 10 (tipo de dados "Cfg" e principais operadores para processar as componentes de uma GIC).

Aulas P de 2005/12/05

Tópicos:

Gramáticas Independentes de Contexto - implementação de GIC em Haskell e operações sobre elas: First, Follow e LookAhead
Conclusão da Resolução da Ficha TP nuº 10 e início da Resolução da Ficha nuº 11
(acesso à ficha resolvida)

Resumo:

Concluída a Ficha 10 (tipo de dados "Cfg" e principais operadores para processar as componentes de uma GIC) discutiram-se os conceitos fundametais para o cálculo das Tabelas de Parsing LL(1): lookahead, first e follow. Fez então 1 primeiro exercício no quadro e apontou-se para a respectiva implementação Haskell (Ficha 11).

Aulas P de 2005/12/12

Tópicos:

Gramáticas Independentes de Contexto - implementação de GIC em Haskell e operações sobre elas: First, Follow e LookAhead; construção da Tabela de Parsing (tabela de decisão) LL(1).
Discussão da Resolução das Fichas nuº 11 e 12

Resumo:

Nesta aula continuou-se a discussão sobre os conceitos fundamentais para o cálculo das Tabelas de Parsing LL(1): lookahead, first e follow. Fizeram-se alguns exercícios, no quadro, e apontou-se para a respectiva implementação Haskell (Fichas 11 e 12).

author: prh@di.uminho.pt;
Last modified: 14 de Dezembro de 2005