Engenharia de Linguagens (2010/2011)

Engenharia Gramatical

Sumários

31 Maio de 2010

• GraAlEditor, um editor-analisador de Gramáticas:
  • Preparação de um artigo a submeter ao CoRTA2010: discussão dos contributos dos 4 grupos em termos de funcionalidades (visualização incluida, ou não) e da arquitectura;
  • Próxima tarefa: desenvolver a secção especific distribuida a cada grupo.

24 Maio de 2010

• GraAlEditor, um editor-analisador de Gramáticas:
  • Preparação de um artigo a submeter ao CoRTA2010: discussão dos contributos dos 4 grupos, definição dos objectivos do artigo e da sua estrutura (secções e seu conteúdo) e escrita do Abstract;
  • Próxima tarefa: definir e enviar proposta de arquitectura.

17 Maio de 2010

• GraAlEditor, um editor-analisador de Gramáticas:
  • Preparação de um artigo a submeter ao CoRTA2010: foi decidido que cada grupo enviaria por email um Abstract completo em inglês até 5ªf à noite para ser depois feita a fusão (PRH+DCC).

• Introdução às Métricas para Gramáticas de Atributos
  • Métricas de Tamanho:
    • (MTA1) #A = #AS + #AH
    • (MTA2) #RC (regras de cálculo)
    • (MTA3) #CC (condições de contexto)
    • (MTA4) #RT (regras de tradução)
    • (MCA1) FanIN (valor médio considerando os GDLocais a todos as p em P)
    • (MCA2) FanOUT (valor médio considerando os GDLocais a todos as p em P)
  • Métricas de Forma:
    • (MFA1) Complexidade dos Atributos: (#ACompl / #A)
      • #Atributos Atómicos
      • #Atributos Complexos
    • (MFA2) Complexidade das Operações: (#OCompl / (#RT + #CC + #RT))
      • #OSimples
      • #OComplex
    • (MFA3) Esquema de Cálculo I
      • RCpureS (puramente Sintetizado)
      • RCpureI (puramente Herdado)
      • RCmixSI
    • (MFA4) Esquema de Cálculo II
      • RCAgregadas
      • RCNãoAgregadas
    • (MFA5) Esquema das Restrições Contextuais
      • CCTop
      • CCBottom
      • CCCentered
    • (MFA6) Esquema das Regras de Traduçao
      • RTTop
      • RTBottom
      • RTCentered

03 Maio de 2010

• Revisão dos elementos já disponíveis para avaliação dos alunos a este módulo.

• Revisão dos Critérios para avaliar a qualidade das gramáticas, GIC e GA: usabilidade (em termos de leitura, derivação de frases e manutenção); e eficiência (em termos reconhecedor/processor gerado, e geração) e métricas; Discussão da relação das métricas obtidas com a qualidade da linguagem.

• GraAlEditor, um editor-analisador de Gramáticas:
  • Preparação de um artigo a submeter ao CoRTA2010: definição do título, abstratct e estrutura (LaTeX distribuido por email para todos os alunos).

26 Abril de 2010

• GraAlEditor, um editor-analisador de Gramáticas (ficha 3):
  • Discussão dos Trabalhos realizados pelos grupos:
    • André Rocha e Márcio Gomes

19 Abril de 2010

• GraAlEditor, um editor-analisador de Gramáticas (ficha 3):
  • Discussão dos Trabalhos realizados pelos grupos:
    • Daniel Rocha e Jorge Mendes

12 Abril de 2010

• GraAlEditor, um editor-analisador de Gramáticas (ficha 3):
  • Discussão dos Trabalhos realizados pelos grupos:
    • André Santos e Miguel Regedor
    • José Luis Freitas e Helder Silva

15 Março de 2010

• Cálculo das métricas para a gramática do Exemplo 5 :

GIC5T1   (GIC5 sem produções unitárias e usando exBNF)

         p1: PIs --> RESUMO Lst DETALHE Projs '.'
         p2: Lst --> InvPs (';' InvPs)* 
         p3: InvPs --> id LstIds
         p4: LstIds --> id (',' id)*
         p5: Projs --> (Proj '.')+
         p6: Proj --> id str FINANC Entidad num INIC num FIM num
         p7: Entidad --> FCT
         p8:          | GRICES
         p9:          | ADI

GIC5T2   (GIC com a produção p10 modificada para ficra mais curta)
 
         p1: PIs --> RESUMO Lst DETALHE Projs '.'
         p2: Lst --> InvPs
         p3:      | Lst ';' InvPs
         p4: InvPs --> SglInv LstIds
         p5: SglInv --> id
         p6: LstIds --> SglProj
         p7:         | SglProj ',' LstIds
         p8: Projs --> Proj '.'
         p9:        | Projs Proj '.'
         p10: Proj --> SglProj Desc Financiament Period
         p11: Financiament --> FINANC Entidad Valor
         p12: Period --> INIC Ano FIM Ano
         p13: SglProj --> id
         p14: Desc --> str
         p15: Entidad --> FCT
         p16:          | GRICES
         p17:          | ADI
         p18: Ano --> num
         p19: Valor --> num

GIC5T3   (GIC5 permitindo incluir a lista de todos os Membros do projecto)

         p1: PIs --> RESUMO Lst DETALHE Projs '.'
         p2: Lst --> InvPs
         p3:      | Lst ';' InvPs
         p4: InvPs --> SglInv LstIds
         p5: SglInv --> id
         p6: LstIds --> SglProj
         p7:         | SglProj ',' LstIds
         p8: Projs --> Proj '.'
         p9:        | Projs Proj '.'
         p10: Proj --> SglProj Desc FINANC Entidad Valor INIC Ano FIM Ano MEMBROS Membros
         p11: Membros --> SglInv
         p12:          |  SglInv ',' Membros
         p13: SglProj --> id
         p14: Desc --> str
         p15: Entidad --> FCT
         p16:          | GRICES
         p17:          | ADI
         p18: Ano --> num
         p19: Valor --> num

8 Março de 2010

• Cálculo das métricas para a gramática do Exemplo 5:

1 Março de 2010

• Introdução às métricas de forma:
  • Forma da recursividade (F1):
    • Recursividade Directa: X -> α X ou X -> X α
    • Recursividade Indirecta: X -> α Y β e Y -> γ X
    • Recursividade Mista
  • Tipo de recursividade (F2):
    • Recursividade Esquerda: X -> X α
    • Recursividade Direita: X -> α X
    • Recursividade Direita-LL: X -> α Y e Y -> ε | α Y
    • Recursividade Mista
  • Notação (F3):
    • BNF
    • EBNF
    • Misto
• Introdução às métricas lexicográficas
  • Identificadores dos Terminais (T) e Não-Terminais (NT) esclarecedores (L1)
  • Palavras-Peservadas (PR) e Sinais esclarecedores (L2)
  • Identificadores + Literais da Linguagem Flexíveis (L3)
  • Possibilidade de inserir comentários (L4)
    • Comentários inline
    • Comentários blocos
    • Comentários mistos

• Cálculo de Métricas de Forma e Lexicográficas para estudo comparativo de gramáticas:
  • métricas para a Gramática Black, GBla (EG -- Exemplo 1);
  • métricas para a versão original (v0) da Gramática Biblioteca, GBib (EG -- Exemplo 2).

(1) Esclarecedores

(2) Não Esclarecedores

(3) Palavras-Reservadas

(4) Não aplicável

22 Fevereiro de 2010

• Cálculo de métricas para estudo comparativo de gramáticas:
  • métricas para a versão original (v0) da Gramática Biblioteca (2ª coluna da Tabela da aula anterior).
  • métricas para a versão v1 da Gramática Biblioteca, após remoção das produções unitárias.
  • métricas para a versão v2 da Gramática Biblioteca, após alteração para gramática LL(1).
  • métricas para a versão v3 da Gramática Biblioteca, após alteração para uso de notação ex-BNF.
  • métricas para a versão v4 da Gramática Biblioteca, alterada de modo a permitir que cada livro tenha mais de um Autor.
• Conclusão: deixando de lado v4 que altera a Linguagem original, é interessante notar que a gramática menos clara (mais dificl de aprender e manter) é a v1, a qual conduz ao Reconhecedor menor e pt mais eficiente; quanto às outras três (v0, v2 e v3) são muito semelhantes, sendo a versão LL(1) a maior e tv por isso menos "ágil" e a versão ex-BNF um pouco menor e consequentemente mais fácil de usar. Curiosamente, a versão v4 estende a Linguagem original, mantendo uns indicadores de qualidade muito semelhantes aos das suas antecessoras (v0, v2 e v3).

• Gramática da v4

        p0:  Biblioteca   -->  Registos
        p1:  Registos     -->  Registo 
        p2:                |   Registos ',' Registo
        p3:  Registo      -->  '[' REGISTO Descricao  EXISTENCIAS 
                                                    Existencias ']'
        p4:  Descricao    -->  Referencia Tipo Titulo '(' Autores ')' 
                               Editora Ano Catalogo
        ...........
        p28: Autores      -->  Autor
        p29:               |   Autores ','  Autor

• Gramática da v3

        p0:  Biblioteca   -->  Registos
        p1:  Registos     -->  Registo (',' Registo)*
        p2:  Registo      -->  '[' REGISTO Descricao  EXISTENCIAS 
                                                    Existencias ']'
        p3:  Descricao    -->  Referencia Tipo Titulo '(' Autor ')' 
                               Editora Ano Catalogo
        p4:  Referencia   -->  id
        p5:  Tipo         -->  LIVRO
        p6:                 |  CDROM
        p7:                 |  OUTRO
        p8:  Titulo       -->  string
        p9:  Autor        -->  string
        p10: Editora      -->  string
        p11: Ano          -->  num
        p12: Catalogo     -->  BGUM
        p13:                |  ALFA
        p14:                |  OUTRO
        p15: Existencias  -->  LOCAL Local '(' Estados ')'
        p16: Local        --> string 
        p17: Estados      --> Estado (',' Estado)*
        p18: Estado       --> CodigoBarras Disponib
        p19: CodigoBarras --> id
        p20: Disponib     --> ESTANTE
        p21:                | PERMANENTE
        p22:                | EMPRESTADO DataDev
        p23: DataDev      --> Ano '-' Mes '-' Dia
        p24: Mes          --> num
        p25: Dia          --> num

• Gramática da v2

        p0:  Biblioteca   -->  Registos
        p1:  Registos     -->  Registo RegistosAux
        p2:  RegistosAux  --> ',' Registo
        p3:                 |  
        p4:  Registo      -->  '[' REGISTO Descricao  EXISTENCIAS 
                                                    Existencias ']'
        p5:  Descricao    -->  Referencia Tipo Titulo '(' Autor ')' 
                               Editora Ano Catalogo
        p6:  Referencia   -->  id
        p7:  Tipo         -->  LIVRO
        p8:                 |  CDROM
        p9:                 |  OUTRO
        p10: Titulo       -->  string
        p11: Autor        -->  string
        p12: Editora      -->  string
        p13: Ano          -->  num
        p14: Catalogo     -->  BGUM
        p15:                |  ALFA
        p16:                |  OUTRO
        p17: Existencias  -->  LOCAL Local '(' Estados ')'
        p18: Local        --> string 
        p19: Estados      --> Estado EstadosAux
        p20: EstadosAux   --> ',' EstadosAux
        p21:                | 
        p22: Estado       --> CodigoBarras Disponib
        p23: CodigoBarras --> id
        p24: Disponib     --> ESTANTE
        p25:                | PERMANENTE
        p26:                | EMPRESTADO DataDev
        p27: DataDev      --> Ano '-' Mes '-' Dia
        p28: Mes          --> num
        p29: Dia          --> num

• Gramática da v1

        p0:  Biblioteca   -->  Registos
        p1:  Registos     -->  Registo
        p2:                 |  Registos ',' Registo
        p3:  Registo      -->  '[' REGISTO Descricao  EXISTENCIAS  
                                                      Existencias ']'
        p4:  Descricao    -->  id Tipo string '(' string ')' 
                               string num Catalogo
        p5:  Tipo         -->  LIVRO
        p6:                 |  CDROM
        p7:                 |  OUTRO
        p8:  Catalogo     -->  BGUM
        p9:                 |  ALFA
        p10:                |  OUTRO
        p11: Existencias  -->  LOCAL string '(' Estados ')'
        p12: Estados      --> Estado
        p13:                | Estados ',' Estado
        p14: Estado       --> id Disponib
        p15: Disponib     --> ESTANTE
        p16:                | PERMANENTE
        p17:                | EMPRESTADO DataDev
        p18: DataDev      --> num '-' num '-' num

25 Janeiro de 2010

• Discussão da relação das métricas obtidas com a qualidade da linguagem.

• Cálculo de métricas para estudo comparativo de gramáticas:
  • métricas para a Gramática Black, GBla (EG -- Exemplo 1);
  • métricas para a versão original (v0) da Gramática Biblioteca, GBib (EG -- Exemplo 2).

• Conclusão: verificou-se que as gramáticas são sensivelmente do mesmo tamanho (GBla com mais terminais, mas Gbib com mais não-terminais e produções), mas que GBla (com lados direitos mais longos, mais alternativas e com um grafo de dependências mais fechado) é mais complexa que a GBib, sendo esta ultima é mais clara/mais fácil de ler/manter (mais produções unitárias e GD mais simples). Em termos do Reconhecedor, o da segunda (GBib) é um pouco maior (devido a mais NTs e Prods).

18 Janeiro de 2010

• Continuação da definição de critérios para avaliar a qualidade das gramáticas: usabilidade (em termos de leitura, derivação de frases e manutenção); e eficiência (em termos reconhecedor/processor gerado, e geração).
• Critérios definidos em relação a uma Gramática Independente do Contexto (GIC):
  • identificadores dos símbolos
  • nº de símbolos (terminais #T + não terminais #NT)
  • nº de produções (#P)
  • notação (BNF/eBNF)
  • recursividade (Esquerda/Direita, Directa/Indirecta)
  • complexidade em termos de dependências entre símbolos
  • modularidade
• Critérios definidos em relação a uma Gramática de Atributos (GA):
  • identificadores dos símbolos
  • nº de atributos (nº de regras de cálculo)
  • complexidade dos atributos
  • complexidade das acções semânticas
  • nº, complexidade e localização das condições de contexto
  • notação
  • recursividade
  • suporte em gramática concreta/gramática abstracta
  • complexidade em termos de dependências entre símbolos
• Métricas para GIC:
  • Tamanho: #T, #NT, #P, #PU, média do nº de símbolos no lado direito das produções ($RHS_med), nº médio de alternativas para cada símbolo ($Alt_med), número de módulos (#mod), nº dependências entre símbolos usando o grafo de dependências (fan-in, fan-out), tamanho das tabelas de parsing LL(1) = ((N+T)*T), tamanhos das tabelas de parsing LR = (Q*T)+(Q*N), tamanho do recursivo descendente = (#N+#T)
  • Forma:
  • Lexicográficas:

11 Janeiro de 2010

• Discussão sobre técnicas de parsing com base nos relatórios apresentados pelos alunos. Revisão dos conceitos de First, Follow, Lookahead, Parsers Top-Down e Bottom-Up.
• Revisão dos critérios para aferir a Qualidade de Linguagens.
• Introdução aos critérios para aferir a Qualidade das Gramáticas.
• Uma gramática G tem 2 fins: Geradora de Linguagem; e Geradora de um Processador de Linguagem. Enquanto Geradora de Linguagem pretende-se que seja fácil de compreender, derivar e manter. Enquanto Geradora de um Processador pretende-se obter: eficiência do processador gerado; e eficiência do processo de geração.

4 Janeiro de 2010

• Discussão da relevância do ambiente de desenvolvimento (IDE) para a avaliação de uma Linguagem: embora não sendo considerado um critério de aferição de linguagens por não ser uma característica intrínseca e sim um factor externo complementar, reconheceu-se a sua importância neste estudo visto que influencia directamente a utilização da linguagem (um mau IDE não promove a utilização da linguagem e vice-versa). Foram, entretanto, identificadas as seguintes facetas que caracterizam a qualidade de um IDE:
  • editor assistido (orientado pela sintaxe, ou com auto-complete, syntax highlight);
  • editor assistido pela semântica (inteli-sense, snippets);
  • code folding (Definição de Code Folding);
  • compilador/interpretador (rapidez, nível de optimização, tratamento de erros);
  • verificador sintáctico e semântico;
  • debugger;
  • gestor de projectos;
  • controlador de versões;
  • importador/integrador de bibliotecas (se possível, referenciador para bibliotecas);
  • apresentador de dicas e sinópsis e leitor de documentação;
  • possibilidade de configuração e extensibilidade das funcionalidades.

• Continuação da definição de critérios para aferir a Qualidade de Linguagens:
  • CL8 --- Credibilidade/ Fiabilidade (Reliability): type checking, exception handling

MB - Muito Bom, B - Bom, S - Satisfaz, NA - Não Aplicável, N - Não, R - Reduzido

bás - básico, evol - evoluído, impl - implica

I - Imperativo, D - Declarativo, L - Lógico, F - Funcional, S - Scripting, OO - Orientado a Objectos

Extensbilidade:

1. Léxico: aliasing (associar um termo/palavra a outra palavra) --- Extensão ao nível do vocabulário

2. Sintáctico

3. Semântica: linguagem de objectos permite estender a semântica (o uso de bibliotecas contribui para a extensibilidade da linguagem).

14 Dezembro de 2009

• Continuação da definição de critérios para aferir a Qualidade de Linguagens:
  • CL5 --- Extensibilidade
  • CL7 --- Paradigma/Filosofia

MB - Muito Bom, B - Bom, S - Satisfaz, NA - Não Aplicável, N - Não

bás - básico, evol - evoluído, impl - implica

I - Imperativo, D - Declarativo, L - Lógico, F - Funcional, S - Scripting, OO - Orientado a Objectos

Extensbilidade:

1. Léxico: aliasing (associar um termo/palavra a outra palavra) --- Extensão ao nível do vocabulário

2. Sintáctico

3. Semântica: linguagem de objectos permite estender a semântica (o uso de bibliotecas contribui para a extensibilidade da linguagem).

07 Dezembro de 2009

• Aula ocupada com a apresentação, discussão e avaliação do Projecto Integrado (PI) -- 1ªfase.

30 Novembro de 2009

• Continuação da definição de critérios para aferir a Qualidade de Linguagens:
  • CL6 --- Escalabilidade

MB - Muito Bom, B - Bom, S - Satisfaz, NA - Não Aplicável, N - Não

bás - básico, evol - evoluído

23 Novembro de 2009

• Continuação da definição de critérios para aferir a Qualidade de Linguagens:
  • CL2 --- Documentação:
    • definição deste critério: comentários --- in-line, multi-line, DSL em comentário (Aumenta doc e produz manuais --- JavaDoc, MSDN, etc; aumenta robustez e produz provas --- VCGen); meta-informação obrigatória.
  • CL3 --- Unicidade: forma única de escrita.
  • CL4 --- Consistência

MB - Muito Bom, B - Bom, S - Satisfaz

bás - básico, evol - evoluído

16 Novembro de 2009

• Qualidade de gramáticas vs Qualidade de linguagens.
• Critérios para aferir a Qualidade das Linguagens:
  • CL1 -- Expressividade:
    • definição deste critério: facilidade (naturalidade, clareza) com que se exprime uma ideia usando os construtores da linguagem.
    • impacto de CL1 nos quatro dimensões de avaliação: influencia positivamente a aprendizagem, escrita e compreensão sem ter grande impacto no processamento.

• • • Avaliação (comparativa) da expressividade das seguintes linguagens: Basic, Pascal, C, C#, Perl, Prolog, Haskell, XML, LaTeX; discussão da avaliação histórica e dos paradigmas subjacentes.

MB - Muito Bom, B - Bom, S - Satisfaz

9 Novembro de 2009

• Continuação da discussão com os alunos sobre as pesquisas feitas relativas a métricas de gramáticas. Alunos de que apresentaram: Jorge Mendes, André Santos & Miguel Regedor, Márcio Coelho, Paulo Alexandre & Paulo Alexandr e André Rocha.
• Introdução ao conceito de qualidade de gramáticas vs qualidade de linguagens (critérios de avaliação e métricas).
• Definição de Qualidade de uma Linguagem: uma linguagem diz-se com qualidade se a sua legibilidade (em termos de facilidade na aprendizagem, escrita e compreensão) for grande sem degradar a eficiência do processamento.
• Critérios para as Linguagens -- Introdução: CL1 a CL6.

2 Novembro de 2009

• Discussão com os alunos sobre as pesquisas feitas sobre métricas de gramáticas. Alunos de que apresentaram: Jose Luis, Helder Silva, e Daniel Rocha.

26 Outubro de 2009

• Apresentação dos resultados encontrados na pesquisa sobre métricas de gramáticas.
• Revisão da utilização de entradas bibtex num ficheiro latex.
• Resolução do exercício 2, alínea f4.
• Introdução do princípio da Tradução Dirigida pela Semântica e diferenças em relação à Tradução Dirigida pela Sintaxe.
• Introdução ao conceito de Gramáticas de Atributos como tuplo (GIC, A, RC, CC, RT), onde A=Atributos, RC=Regras de Contexto, CC=Condições de Contexto, RT=Regras de Tradução.
• Exemplificação do uso de Gramáticas de Atributos (GA) com a gramática declarations.g

19 Outubro de 2009

• Discussão do duplo papel de uma Gramática, a propósito do Exercício 2 da aula anterior e das suas alíneas a) a c) (comparação com o Exercício 1):
  • a gramática como especificação formal de uma linguagem (papel do utilizador final da linguagem e do engenheiro gramatical);
  • a gramática como especificação formal de um programa, o processador/compilador da linguagem e o recurso a Geradores automáticos de Compiladores (papel do engenheiro gramatical).

• Introdução à noção e relevância do tema Qualidade de Gramáticas (em ambas as vertentes acima identificadas) e da necessidade imperiosa de se definirem Métricas Gramaticais para se poder discutir a qualidade com objectividade.

• Revisão dos conceitos de Parsing Top-Down (Recursivo-Descendente, RD, e LL(1)) e de Parsing Bottom-Up (LR); funções e tabelas de parsing e autómato LR(0) -- resolução das alíneas d) e e) do Exercício 2.

12 Outubro de 2009

• Introdução da notação AnTLR e comparação com a escrita de gramáticas em Lex/Yacc.
• Escrita em notação AnTLR de uma Gramática para uma linguagem que:
  • aceite uma Lista de Números;
  • gere o respectivo Parser com o AnTLR;
  • teste o parser com o Debugger visual do AnTLRWorks;
  • inclua Acções Semânticas e Atributos para calcular a Soma dos números na lista e Comprimento da Lista.
• Discussão das diferenças entre o formato BNF e EBNF e comparação das respectivas árvores de derivação.
• Discussão das diferenças entre Recursividade à Esquerda e Recursividade à Direita.

   Lista --> "[" Nums "]"
   Nums  --> int
           | int',' Nums

          
lista   :   '[' nums ']' { 
                       System.out.println("Soma: " + $nums.soma +
                                        "\nContador: " + $nums.conta); 
        }
   ;

nums   returns [int soma, int conta=0]
   :   a = INT    { 
                              $soma = Integer.parseInt($a.text); 
                              $conta++; 
                           }
                (',' b = INT { $soma += Integer.parseInt($b.text); 
                               $conta++; 
                             }
                )*
   ;
            
INT   :   ('+' | '-')? ('0'..'9')+
   ;
            
WS   :   (' ' | '\t' | '\n' | '\r') { channel=HIDDEN; };      

28 de Setembro de 2009

• 1. Apresentação da UCE30-EL e em particular do Módulo de EG:
  • Apresentação da Equipe Docente, dos Objectivos e do modo de Funcionamento e Avaliação;
  • Introdução e Motivação para a área de Processamento de Linguagens e para o desenvolvimento baseado em Gramáticas e em Geradores de Compiladores.

• 2. Revisão do conceito de Linguagem e sua relação com Gramática:
  • Apresentação dos critérios a observar quando se faz o design de uma Linguagem:
    • Satisfação dos Requisitos pedidos no enunciado
    • Satisfação das Restrições explicitadas no enunciado
    • Procura de Legibilidade
    • Procura de Simplicidade na utilização para escrever frases.
  • Resolução do Exemplo1: desenho de uma Linguagem

• 3. Revisão do conceito de Gramática Indepedente de Contexto (GIC) e de Gramática Tradutora (GT); sua definição formal.
  • Resolução do Exemplo2 (inicio, discussão do enunciado): leitura e análise de uma Gramática