Engenharia Gramatical
Sumários
- 1 de Outubro de 2007
- Revisão de alguns conceitos na construção de parsers: análise léxica e análise sintáctica;
- Considerações básicas sobre desempenho na construção de parsers; * Artigo comparativo de abordagens de parsing em Perl
- Exercício de manuseamento de gramáticas (Ficha 01, exerc 1a);
- 9 de Outubro de 2007
- Definição cuidada do objectivo específico deste Módulo: estudar tudo o que tem a ver com:
- uso de Gramáticas na Especificação de Problemas (enfatizando o caso particular da Especificação de Linguagens);
- uso de Gramáticas na construção sistemática dos programas que resolvem os Problemas especificados (enfatizando o caso particular da Geração Automática de Procesadores de Linguagens).
- Leve abordagem ao tema "métricas para aferir a qualidade de uma Gramática" e ao tema "características de uma Linguagem que definem a sua qualidade";
- Introdução à ferramenta UltraGram;
- Utilização do UltraGram para estudar a GIC do Exercício 1 da Ficha Prática 1 (Gf1.1):
- Geração do Autómato Determinista
- Análise estática: dimensão, função de transição e Conflitos
- Análise dinâmica: Stack de Parsing e Árvore de Derivação
- Optimizações na Gramática e implicações na Linguagem; recurso de novo ao UltraGram para avaliar uma série de parâmetros escolhidos para medir a qualidade da Gramática:
- 1ªTransformação: eliminação de Produções Inúteis
- 2ªTransformação: alteração da linguagem (para permitir agrupar as orientações de um orientador).
- 15 de Outubro de 2007
- Elaboração de um relatório sobre métricas de análise/avaliação da qualidade de gramáticas e linguagens;
- Exercícios com a ferramenta UltraGram.
- 22 de Outubro de 2007
- Revisão dos parâmetros usados nas aulas anteriores para avaliar a evolução da qualidade e eficiência das Gramáticas quando se fazem alterações:
- Tamanho da G
- Tamanho do AD LR de reconhecimento
- Tamanho das Tabelas de Parsing
- Tempo de Geração do Parser
- Tempo de acesso à Tabelas de Parsing
- Tempo de Parsing
- Legibilidade de G (para o eng gra que desenvolve)
- Legibilidade/Usabilidade de G (para o user final que a utiliza para conhecer a L)
- Linguagem gerada por G
- Recapitulação/sumário dos Exercícios feitos com a transformação de Gramáticas e da utilização da ferramenta UltraGram para avaliação:
- foram feitas 2 transformações a Gf1.1 (eliminação de PInuteis e Melhoria da Linguagem) mas só a 1ª foi medida (anotando-se na tabela acima o sentido da variação) => refazer o último exercício;
- foram feitas 2 transformações a Gf1.2 (eliminação de PInuteis e Melhoria da Linguagem) mas nenhuma foi medida => refazer todo o exercício.
- Discussão dos relatórios elaborados na aula anterior sobre métricas de análise/avaliação da qualidade de gramáticas com o intuito de reunir a opinão recolhida pelos vários grupos num quadro de consenso geral. Nesta âmbito foram discutidos os seguintes tipos de Métricas:
- de Complexidade ou de Tamanho, tendo sido identificados os seguintes parâmetros:
- #T, #N, #P, #RHS, #Pinuteis, #Alternativas, #Recursividade (ciclos)
- estruturais, tendo sido identificados os seguintes parâmetros:
- Profundidade/Peso da àrvore; Balanceamento da árvore; Recursividade
- Referências Bibliográficas em LaTeX:
- importância das citações na escrita científica: evitar pleonasmos, reconhecimento ao autor, apresentação da base em que se suporta o trabalho, links para a profundar a leitura
- o comando \cite{label} no documento
- a base de dados textual com a bibliografia (fich.bib) no formato @tipo{ label, item=string (, item=string)* }
- o funcionamento cooperativo dos programas LaTeX e BibTeX (e a interacção via fich.aux)
- 29 de Outubro de 2007
- 05 de Novembro de 2007
- Identificaram-se as implicações que as 2 transformações T1 e T2 de Gf1.1 tiveram sobre as características a avaliar sobre gramáticas:
- (C1.1)eficiência na geração: + | -
- (C1.2)eficiência no processamento: + | -
- (C1.3)clareza/legibilidade para manutenção: - | x
- (C2.1)clareza/legibilidade para derivar frases de L: - | x
- (C2.2)características da Linguagem Gerada: x | +
- Relacionaram-se as Métricas propostas por Power e Malloy (M1 a M6) com os Parâmetros definidos na última aula para avaliar Gramáticas, tendo-se concluido que as três primeiras (M1 a M3) correspondiam a métricas por nós previstas enquanto que as três últimas (M4 a M6) teriam ainda de ser incluídas pois medem a dependência entre símbolos; a título de exemplo, para clarificar esta última questão, discutiu-se a diferença entre a recurisvidade directa e indirecta em listas. Assim comparando as 2 alternativas abaixo:
p1: PGList -> PG PGCont
p2: PGCont -> &
p3: | ";" PG PGCont
p1': PGList -> PG PGCont
p2': PGCont -> &
p3': | ";" PGList
verificou-se que a primeira (p1,p2,p3) era preferível por diminuir a dependência entre símbolos.
- Procurou-se identificar a influêndia que cada parâmetro tem sobre as características, em particular ficou clara a importância do comprimento dos Lados Direitos das Produções na eficiência do parsing.
- Foram feitos depois alguns testes com a Ferramenta SLK Parser Generator (http://home.earthlink.net/~slkpg/), gerador de parsers LL, para tentar medir os mesmos indicadores numa situação diferente de Parsing (Top-Down em vez de Bottom-Up), tendo-se de novo recorrido à gramática do 1ºexercício, Gf1.1, a qual teve de ser alterada (como se mostra abaixo) para Eliminar a Recursividade à Esquerda. Desta vez obtiveram-se uma série de métricas úteis para o estudo em curso.
PGs : PGlist .
PGlist : PGlist PG
_epsilon_
PG : IdOrient Tipo CoOrient Aluno ( Titulo ) Inic Fim
IdOrient : ID
Tipo : PHD
MSC
CoOrient : _epsilon_
CO-ORIENT Nome
Aluno : Nome
Titulo : STRING
Nome : STRING
Inic : INI Ano
Fim : _epsilon_
FIM Ano
Ano : NUMBER
- Fez-se ainda uma revisão completa às estrategias de Parsing Top-Down e Bottom-Up:
- Relembrou-se a estrutura e conteúdo das Tabelas LL: N * T -> prod | erro
- Relembrou-se o conteúdo e funcionamento da Stack de Parsing LL, que começa em <S,$> e termina <>
- Relembrou-se a estrutura e conteúdo das Tabelas LR: Q * N -> Q e Q * T -> skip(Q) | red(P) | erro
- Relembrou-se o conteúdo e funcionamento da Stack de Parsing LR, que começa em <> e termina <S,$>
- No fim da aula, apresentou-se o 2ªTrabalho para Casa cujo enunciado se inclui na rubrica Fichas Práticas deste Módulo.
- 12 de Novembro de 2007
- Discutiu-se a resolução (apresentada por um dos grupos) da Ficha Prática III: Transformações da Gramática Gf1.2, aferição das métricas em cada metamorfose e avaliação do impacto de cada transformação (T1, T2 e T3) sobre as características de uma gramática.
- Discussão da aplicação do critério (ou métrica) dito "Fenton's Impurity" para avaliação da Dependencia entre os Símbolos Não-terminais: construção do Grafo e cálculo do factor de Fenton; inclusão de mais um critério (C1.4) que mede a facilidade de modularização e manutenção de uma gramática.
- Continuou-se a trabalhar no segundo tópico do Módulo, Modelação de Sistemas de Informação com Gramáticas, com o início da resolução de um problema concreto: Especificação de um Sistema para Apoio à construção e publicação de Horários (para Alunos, Docentes e Salas) e Sumários das Aulas. Enunciou-se o problema e começou-se a especificar as classes/conceitos: Horários, Horário e Célula do Horário.
- 19 de Novembro de 2007
- Apresentação sumária das várias opções da ferramenta SKL; e breve introdução ao AnTLR e AnTLR-Works.
- Discussão da aplicação do critério (ou métrica) dito "Fenton's Impurity" para avaliação da Dependencia entre os Símbolos Não-terminais.
- Conclusão da resolução de um problema concreto de Modelação de Sistemas de Informação com Gramáticas: Especificação de um Sistema para Apoio à construção e publicação de Horários (para Alunos, Docentes e Salas) e Sumários das Aulas. Continuação da especificação das Classes/conceitos (Sala, Aula, Turno, Disciplina, Aluno, Docente) com a introdução de Invariantes (via Condições Contextuais) e especificação de algumas Operações -- criação de um _Sistema de Gramáticas de 2-Níveis_.
- Simulação e teste das Classes do SI criando uma Parser para reconhecer frases da Linguagem, recorrendo ao AnTLR.
- 26 de Novembro de 2007
- Resolução de um segundo problema concreto de Modelação de Sistemas de Informação com Gramáticas: Sistema de Gestão para apoio ao Atendimento e Triagem de Paciêntes num urgência hospitalar. Especificação das Classes/conceitos (Doentes, Doente, Historial-Clinico, Episódio, Triagem, Lista-Espera) com a introdução de Invariantes (via Condições Contextuais) e especificação de algumas Operações -- criação de um _Sistema de Gramáticas de 2-Níveis_.
- Simulação e teste das Classes do SI criando uma Parser para reconhecer frases da Linguagem, recorrendo ao AnTLR; construção e análise do Grafo de Sucessores (SG) para apreciar a qualidade da especificação.
- Revisão das noções base associadas à especificação da semântica estática (restrições) e dinâmica (tradução) de Linguagens -- estádio 1: Noção de Acção Semântica e de Gramática Tradutora.
- Criação de uma mailing-list; Discussão e Publicação dos critérios de avaliação da UCE30-EL.
- 03 de Dezembro de 2007
- Revisão das noções base associadas à especificação da semântica estática (restrições) e dinâmica (tradução) de Linguagens -- estádio 2: Noção e Definição formal de Gramática de Atributos.
- Resolução do exercício 1.2 da Folha de exercícios 1 para consolidação da matéria sobre GT e AS.
- Início da Resolução do exercício 1.3 da Folha de exercícios 1 para consolidação da matéria sobre GA.
- 10 de Dezembro de 2007
- Revisão das noções base associadas à especificação da semântica estática (restrições) e dinâmica (tradução) de Linguagens -- estádio 2: Noção e Definição formal de Gramática de Atributos.
- Conclusão da Resolução do exercício 1.3 da Folha de exercícios 1 para consolidação da matéria sobre GA.
- Início da Resolução do exercício 2.3 da Folha de exercícios 1 para consolidação da matéria sobre GA.
- 17 de Dezembro de 2007
- Revisão das noções base associadas à especificação da semântica estática (restrições) e dinâmica (tradução) de Linguagens -- estádio 2: Noção e Definição formal de Gramática de Atributos.
- Início da Resolução de um novo exercício (Indice Remissivo) para consolidação da matéria sobre GA -- derivação da GIC Concreta+Abstracta a partir de um exemplo de Txt-Fnt:
- Construção da Lista de Páginas;
- Cálculo do Número de Páginas registadas (entradas);
- Verificação da Ordem Crescente das Páginas;
- Verificação da Inexistência de Palavras Repetidas.
- Construção da tabela (N u T)*(AH u AS)
- Introdução às métricas para Avaliação da Qualidade de uma GA:
- Número de atributos, absoluto, por tipo e em relação ao total de (N u T)
- Complexidade do Tipo dos atributos (atómicos ou estruturados)
- Comprimento dos caminhos dos Grafos de Dependências.
- 07 de Janeiro de 2008
- Revisão das noções base associadas à especificação da semântica estática (restrições) e dinâmica (tradução) de Linguagens -- estádio 2: Noção e Definição formal de Gramática de Atributos.
- Conclusão da Resolução do exercício (Indice Remissivo) para consolidação da matéria sobre GA:
- Construção da Lista alfabética de Palavras associadas à lista de Páginas.
- mostra-se e discute-se abaixo a solução final completa deste exercício:
p1: Index : INDICE Entradas FINDICE
p2: Entradas : Entrada
p3: | Entradas Entrada
p4: Entrada : IdPag ":" LstPals
p5: LstPals : pal
p6: : LstaPals "," pal
p7: IdPag : num
a) criar uma lista de números de páginas
Rp2: Es0.lp = ins(E1.pg, nil)
Rp3: Es0.lp = ins(E2.pg, Es1.lp)
Rp4: E0.pg = IdPag1.pg
Rp7: IdPag0.pg = num1.val
b) contar as Entradas
Rp2: Es0.cnt = 1
Rp3: Es0.cnt = 1 + Es1.cnt
c) garantir que as Páginas aparecem por ordem crescente
Cp3: ( E2.pg > Es1.ult )
Rp2: Es0.ult = E1.pg
Rp3: Es0.ult = E2.pg
d) Garanta que não ha nenhuma Palavra repetida
Sol d1)
Cp3: ( testaRepete(Es1.lpal,E2.lpal) ) //operação mt pesada e desnecessaria
Rp3: Es0.lpal = concat(Es1.lpal,E2.lpal) //operação mt pesada
Rp4: E0.lpal = LstPals2.lpal
Pp5/Rp6: LstPals0.lpal = ins(...)
Sol d2)
Cp5: ( !existe(pal1.val,LstPals0.inlpal) ) //operação mt simples
Cp6: ( !existe(pal2.val,LstPals1.pal) )
Pp5: LstPals0.lpal = ins(pal1.val,LstPals0.inlpal) //operação igual/ simples
Rp6: LstPals0.lpal = ins(pal2.val,LstPals1.lpal); LstPals1.inlpal = LstPals0.inlpal
Rp4: LstPals2.inlpal = Entrada0.inlpal; Entrada0.lpal = LstPals2.lpal
Rp2: Entrada1.inlpal = nil; Entradas0.lpal = Entrada1.lpal
Rp3: Entrada2.inlpal = Entradas1.lpal; Entradas0.lpal = Entrada2.lpal
e) (ignorar restrição da alínea e)criar uma Lista de Pals com uma Lista de Pags
//de novo se coloca a mm situação da Sol d1)
//então vamos avançar logo para a Sol do tipo d2) com AHerdados
Rp4: LstPals2.inpg = IdPag1.pg;
LstPals2.inlpal = Entrada0.inlpal; Entrada0.lpal = LstPals2.lpal
Rp5: LstPals0.lpal = update( mkpair(pal1.val,LstPals0.inpg), LstPals0.inlpal)
//insere o par se Pal não existe, acrescenta Pag a ListaPags se Pal ja existe
Rp6: LstPals0.lpal = update( mkpair(pal2.val,LstPals0.inpg), LstPals1.lpal)
LstPals1.inlpal = LstPals0.inlpal
Rp2: Entradas0.lpal = Entrada1.lpal; Entrada1.inlpal = nil;
Rp3: Entradas0.lpal = Entrada2.lpal; Entrada2.inlpal = Entradas1.lpal
- Início da Resolução de um novo exercício (Descrição de Candidaturas; Dados gerais, Entidades proponentes, Projecto e Fases) para consolidação da matéria sobre GA:
p1: Candidatura : Dados Entidades Proj
p2: Dados : IdCand data Eixo Prog
p3: Entidades : Entid
p4: | Entidades Entid
p5: Entid : CodE
p6: Entid : NOVA CodE Nome Morad Resp
p7: Proj : Desc Inic Fim Fases
p8: Fases : Fase
p9: : Fases Fase
p10: Fase : CodE Desc Inic Fim Custo
p..: Eixo : e1 | e2 | ... en
p..: Prog : p1 | p2 | ... pk
- Verificação do Programa seleccionado em função do Eixo escolhido (nos Dados);
- Tratamento das Entidades -- proponente ja registado (existente na lista das Entidades), ou novo (não existente nessa lista)); identificação das Entidades que participam na Candidatura.
- Sistematização dos esquemas para escolha dos atributos S e H dos simbolos e localização/escrita das regras de cálculo, condições de contexto e regras de tradução (comparação de alternativas).
- Discussão/avaliação das métricas para Avaliação da Qualidade de uma GA:
- Número de atributos, absoluto, por tipo e em relação ao total de (N u T)
- Complexidade do Tipo dos atributos (atómicos ou estruturados)
- Comprimento dos caminhos dos Grafos de Dependências.
- 14 de Janeiro de 2008
- Revisão das noções base associadas à especificação da semântica estática (restrições) e dinâmica (tradução) de Linguagens -- estádio 2: Noção e Definição formal de Gramática de Atributos.
- Conclusão da Resolução do exercício sobre "Descrição de Candidaturas; Dados gerais, Entidades proponentes, Projecto e Fases" para consolidação da matéria sobre GA:
- Cálculo do custo total de um Projecto em função do custo de cada Fase;
- Validação da Entidade Responsável por cada Fase de um Projecto (tem de ser membro da lista de Entidades que integram essa Candidatura).
- Validação do período de duração de cada Fase (tem de estar contido no período total do Projecto).
- Sistematização dos esquemas para escolha dos atributos S e H dos simbolos e localização/escrita das regras de cálculo, condições de contexto e regras de tradução (comparação de alternativas).
- Discussão/avaliação das métricas para Avaliação da Qualidade de uma GA:
- Número de atributos, absoluto, por tipo e em relação ao total de (N u T)
- Complexidade do Tipo dos atributos (atómicos ou estruturados)
- Comprimento dos caminhos dos Grafos de Dependências.
|
|
|
 Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors. Ideas, requests, problems regarding TWiki? Send feedback
|
|
