Engenharia de Linguagens

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
    • Definição dos Critérios para Caracterização de uma Gramática como geradora de programas (processadores/compiladores):
      • eficiência na geração
        • tempo geração
        • tamanho/complexidade das EDs usadas
      • eficiência no processamento (na compilação)
        • tempo Parsing
        • tamanho/complexidade das Tabelas, ou mecanismos, de decisão.
      • clareza/legibilidade para manutenção (perspectiva do EG)
    • Definição dos Critérios para Caracterização de uma Gramática como geradora de linguagens:
      • clareza/legibilidade para derivar frases de L (perspectiva do end-user)
      • características da Linguagem Gerada [mos07]:
        • expressividade
        • abstracção
        • compreensibilidade e documentação???
        • unicidade
        • consistência
        • extensibilidade ???
        • segurança (+comp)
        • realizabilidade (+comp)
        • eficiência dos programas (comp)
        • sinergia (comp)
        • ortogonalidade (comp)
    • Definição dos Parâmetros a medir para avaliar estas características (no âmbito da Geração de Programas):
      • tamanho de G: #T, #N, #P, #Pinuteis, #RHS, #Alt/N, #AltMedia
      • tipo de Recursividade
      • tamanho das Tabelas + tempo Decisão (acesso às Tabs ou aos Casos):
        • tamanho do AD-LR (#Q) ª tamanho Tab-LL
    • Repetição dos Exercícios feitos sobre a transformação de Gramáticas e a utilização da ferramenta UltraGram para avaliação:
      • foram feitas 2 transformações a Gf1.1 (eliminação de PInuteis e Melhoria da Linguagem) de modo a registar em Tabela Comparativa o valor de todos os indicadores (parâmetros) escolhidos para caracterizar o Tamanho de G 
                        Gf1.1v1 | Gf1.1v2 | Gf1.1v3 | Gf1.1v3'
          #T:    12        12        12        12
          #N:    11         5        13         6
          #P:    15         9        18        11
          #PI:    6         0         6         0
          RHS (min,max,med):
               0,9,1.9  0,10,2.3  0,8,1.8   0,9,2.0
          Alt (min,max,med)
                2,2,2   ......
          Alt/N: 8/11      8/5       10/13     10/6

          TRec:  LRec     .......

          #Q:    28        22        32        25
    • Foram feitos depois alguns testes com a Ferramenta ProGrammar (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 a a gramática do 1ºexercício, Gf1.1, a qual teve de ser alterada (como se mostra abaixo) para Eliminar a Recursividade à Esquerda. Infelizmente este exercício, para além de mostrar que o ProGrammar? detectava logo a Recursividade à Esquerda e que, não havendo conflitos, mostrava o processo de parsing e de construção da AD, não trouxe grande ajuda nas medições pretendidas porque não mostrava as tabelas. 
             PGs ::=   PGlist "." ;
       PGlist ::= PG [ {";" PGList } ];
       PG ::= IdOrient Tipo CoOrient Aluno "("Titulo")" Inic Fim;
       IdOrient ::= alpha ;
       Tipo ::= "PHD" | "MSC" ;
       CoOrient ::= [ "CO-ORIENT" Nome ] ;
       Aluno ::= Nome ;
       Titulo ::= string;
       Nome ::= string;
       Inic ::= "INI" Ano ;
       Fim ::= [ "FIM" Ano ] ;
       Ano ::= numeric ;
       string ::= quotedstring;
    • Foi introduzido um outro Tópico do Módulo: modelação de sistemas de informação com Gramáticas.
  • 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.