Engenharia de Linguagens

Engenharia de Linguagens

Engenharia Gramatical 2008/09

Sumários

29 de Setembro de 2008

  • Apresentação da Disciplina 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.

  • Revisão do conceito de Gramática Indepedente de Contexto (GIC) e de Gramática Tradutora (GT); sua definição formal.

  • Apresentação da Ferramenta para geração de compiladores (que será usada ao longo de todo o ano) AnTLR e do ambiente de desenvolvimento associado AnTLRWorks usando o Exemplo 1.

06 de Outubro de 2008

  • Discussão das respostas enviadas pelos alunos às questões Q1 e Q2.

  • Continuação da exploração do Gerador AnTLR usando como base o Exemplo 1: análise do código Java gerado; o algoritmo de parsing com backtracking e sem backtracking mas com o valor de K (para o cálculo do comprimento do LookAhead) explicitado.

  • Conclusão da resolução em AnTLR do Exemplo 1, recorrendo agora a um atributo sintetizado para calcular o comprimento da Lista; teste da solução, quer com a forma recursiva não LL(1), em BNF-puro, da gramática, quer com a versão iterativa, em BNF-extendido; incremento da solução com um novo atributo para cálculo da soma dos valores da lista (os atributos intrínsecos dos Terminais "text", "line" e "column").

Gramática Recursiva não-LL(1) (BNF-puro)

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

Gramática Iterativa (BNF-extendido) --- com resolução em ANTLR

          
options { k=2; }

lista   :   '[' nums ']' { 
                        System.out.println("Soma: " + $nums.soma);
                        System.out.println("Contador: " + $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; };      

  • Inicio da resolução do Exemplo 2: construção de um parser para a gramática da linguagem Lisp (versão iterativa em BNF-extendido).

Gramática Recursiva LL(1) (BNF-puro)

  Lisp     --> SExp 
  SExp     --> num
             | pal
             | "(" SExplist ")"
  SExplist --> SExp SExplist
             | &

Gramática Iterativa (BNF-extendido)
  Lisp   --> SExp;
  SExp   --> num
           | pal
           | "(" SExp* ")"

13 de Outubro de 2008

  • Análise das respostas dadas pelos alunos às questões Q3 e Q4; discussão detalhada sobre os conceitos básicos do parsing Top-Down: condição (de não-ambiguidade) LL(1); Algoritmo Recursivo-Descendente (RD) e Algorimto guiado-por-tabela (iterativo e genérico) LL(1).

  • Continuação da resolução do Exemplo 2:
    • definição dos atributos para resolver a primeira questão: calcular a quantidade de números e palavras da lista
    • definição dos atributos para resolver a segunda questão: construir uma lista plana (todos os elementos ao mesmo nível) com os elementos originais associados ao nível a que aparecem.

20 de Outubro de 2008

  • Análise das respostas dadas pelos alunos à questão Q5 e discussão muito detalhada da solução: sistematização do processo de definição de regras de cálculo em produções iterativas.

  • Continuação da resolução do Exemplo 2:
    • definição dos atributos e condições de contexto para validar a semântica estática da linguagem (neste exemplo, verificar que todos os elementos são do tipo do primeiro elemento da lista); discussão de alternativas para construir os atributos relevantes e para colocar as condições de contexto, mais acima ou mais abaixo na árvore), como se vê nos exemplos seguintes.
    • inicio da geração de código

Como funciona, mas não se deve fazer:
grammar LispCheckFirstBad;
/*
verificar que todos os elementos da lista sejam do mesmo tipo do 1.elemento
*/
@header {
    import java.util.ArrayList;
}

lisp    returns[ArrayList<String> array_out]
@init{ ArrayList<String> array_in = new ArrayList<String>(); }
    :   sExp[array_in]  { String a = $sExp.array_out.get(0);
                  if (a.equals("int") && $sExp.array_out.contains("pal")) {
                    System.out.println("FALSE");
                  }
                  else if (a.equals("pal") && 
                           $sExp.array_out.contains("int")) {
                    System.out.println("FALSE");
                  }
                  else {
                    System.out.println("TRUE: " + a);
                  }
                }
    ;
sExp[ArrayList<String> array_in]    returns [ArrayList<String> array_out]
    :   INT { $array_in.add("int"); $array_out = $array_in;}
    |   PAL { $array_in.add("pal"); $array_out = $array_in; }
    |   '(' 
        ( vez_anterior = sExp[array_in] { 
              $array_in = $vez_anterior.array_out; } )* 
        ')' { $array_out = $array_in; }
    ;

Como funciona e se deve fazer para ficar uma solução elegante e eficiente:
grammar LispCheckFirstGood;
/*
verificar que todos os elementos da lista sejam do mesmo tipo do 
primeiro elemento
*/

lisp    returns[String type_out]
@init{ String type_in = new String(""); }
    :   sExp[type_in]   { System.out.println($sExp.type_out); }
    ;
sExp[String type_in]    returns [String type_out]
    :   INT { if ($type_in.equals("pal") || 
                  $type_in.equals("FALSE: pal")) {
                $type_in = "FALSE: pal";
              }
              else {
                $type_in = "int";
              }
              $type_out = $type_in;
            }
    |   PAL { if ($type_in.equals("int") || 
                  $type_in.equals("FALSE: int")) {
                $type_in = "FALSE: int";
              }
              else {
                $type_in = "pal";
              }
              $type_out = $type_in;
            }
    |   '(' 
        ( vez_anterior = sExp[type_in] { 
              $type_in = $vez_anterior.type_out; } )* 
        ')' { $type_out = $type_in; }
    ;

27 de Outubro de 2008

  • Análise das respostas dadas pelos alunos à questão Q6; discussão detalhada sobre os conceitos básicos da gramática de atributos, distinguindo a dispersão (propagação) de valores pela árvore abaixo (para transmissão de informação contextual de pai para filhos, ou entre irmãos) da síntese do significado da frase (inferindo informação semântica a partir dos valores extraídos da frase através das folhas da árvore de derivação); Reflexão alongada sobre todo o processo de cálculo de atributos, o que levou à formulação das questões Q7 a Q9.

  • Utilização de Literate Programming (LitPrg) na resolução das Fichas Práticas para produção do respectivo relatório (que constituirá o objecto de avaliação neste módulo de EG); apresentação do conceito e do princípio de desenvolvimento subjacente; referência a algumas ferramentas de LitPrg e introdução ao Nuweb; formulação da Q10.

  • Conclusão da resolução do Exemplo 2:
    • definição dos atributos para resolver a última questão, gerar código post-fix para representar um programa Lisp, discussão de alternativas e implementação do processo de tradução.

  • Introdução ao Exemplo 3: processamento de linguagens através da construção explícita e travessias da Árvore de Sintaxe Abstracta (AST)
    • apresentação das facilidades do AnTLR para construção de uma AST durante o parsing.

03 de Novembro de 2008

  • Análise das respostas dadas pelos alunos à questão Q7 a Q10: continuação da discussão sobre cálculo de atributos (inferência de uma ordem parcial, sua totalização para o cálculo sequencial e detecção da independência para o cálculo concorrente); questões práticas associadas à utilização de programas gerados automaticamente; distinção clara entre escrever um documento que expões um problema e discute a sua resolução através do desenvolvimento de um programa (Literate Programming) próprio do acto de escrever um programa e o comentar detalhadamente (incluindo alguma meta-informação nos comentários, como é o caso do JavaDoc).

  • Processamento de Linguagens através da construção explícita de uma Árvore de Sintaxe Abstracta (AST) e suas travessias
    • Continuação do estudo das facilidades do AnTLR para construção de uma AST durante o parsing -- ilustração através da aplicação de vários operadores ao Exemplo 2 (Linguagem Lisp).
    • Exploração da facilidade anterior para fazer o slicing sintático da Árvore de Derivação ('Parsing Tree') concreta e completa do texto-fonte.
    • Introdução às Tree-Grammars para definir Travessias à AST que a processam -- construção de Sistemas de Produção (sistena de regras Condição-Reacção, por pattern-matching nos nodos da árvore) para transformação do texto-fonte.

  • Continuação da resolução do Exemplo 3: elaboração da CFG (GIC) com os comandos SQL escolhidos por cada grupo.

Ficheiros utilizados na aula:

10 de Novembro de 2008

  • Sistematização da utilização de Gramáticas Tradutoras (GT) vs Gramáticas de Atributos (GA); cálculo de atributos on-the-fly (durante o parsing) e cálculo a-posteriori através de travessias à árvore. Ainda na utilização de GAs, discussão da utilização da Tradução Dirigida pela Semântica conjugada com a construção da Árvore de sintaxe abstracta.

  • Discussão sobre a forma de construir um relatório. Cada relatório deverá ser composto por:
    • Introdução
    • Problema a resolver e Objectivos
    • Análise
    • Concepção da Solução
    • Implementação
    • Conclusão

  • Continuação da resolução do Exemplo 3: elaboração da CFG (GIC) com os comandos SQL escolhidos por cada grupo; construção da respectiva AST e início da definição de transformações.

17 de Novembro de 2008

  • Discussão breve (a propósito da Q11) do Tratamento de Erros num Compilador. Referência a cada uma das fases:
    • Detecção (implícita nos algorítmos de cada uma das 3 etapes de Análise;
    • Sinalização do erro: localização, diagnóstico e terapia;
    • Correcção (os modelos formais de correcção) e Recuperação (Ponto-de-Recomeço e Terminais-Fidedignos).

  • Continuação da resolução do Exemplo 3: elaboração da CFG (GIC) com os comandos SQL escolhidos por cada grupo; construção da respectiva AST e início da definição de transformações.

  • Linguagens Visuais, VisualLISA:
    • Exemplificação dos Editores/compiladores gerados automaticamente com o Devil: VisualTopicMaps e VisualDRAW;
    • Apresentação e Testes com a Linguagem Visual para especificação de Gramáticas de Atributos, VisualLISA;
    • Resposta a um inquérito sobre a "usabilidade" deste editor.

24 de Novembro de 2008

  • A propósito da Q12, continuação da discussão mais aprofundada sobre Tratamento de Erros no Processamento de Linguagens e mais específicamente num Compilador:
    • ainda, Correcção versus Recuperação.
    • referência a Editor Sensível ao Contexto e Editor Guiado pela Sintaxe.

  • Continuação da resolução do Exemplo 3: elaboração da CFG (GIC) com os comandos SQL escolhidos por cada grupo; construção da respectiva AST e início da definição de transformações.

  • Linguagens Visuais, VisualLISA:
    • Definição de Linguagem Visual e Gramática Visual; exemplo da gramática da VisualLISA? em notação PLG (Picture Layout Grammar).
    • Breve introdução ao sistema gerador de Editores/Reconhecedores de Linguagens Visuais, DEVIL (Development Environment for Visual Languages), baseado no Eli e no gerador de compiladores para gramática de atributos LIGA.
    • Apresentação da especificação completa da Linguagem VisualLIGA incluindo a sintaxe, semântica estática, geração de código e o editor.

15 de Dezembro de 2008

  • A propósito da Q14, Q15 e Q16 continuação da discussão aprofundada sobre Tratamento de Erros no Processamento de Linguagens (mais específicamente num Compilador), bem como sobre Edição Assistida:
    • erros de run-time (versus erros em compile-time).
    • discussão do binómio Editor Sensível ao Contexto e Editor Guiado pela Sintaxe.

  • Introdução à Qualidade de Linguagens (QL) e Qualidadade de Gramáticas (QG); Métricas:
    • Discussão sobre critérios para Avaliar a QG e a QL.
    • Critérios apresentados para avaliar a QG:
      • Legibilidade da gramática (identificadores, documentação, meta-linguagem),
        • como formalismo que descreve uma linguagem,
        • como especificação de um processador;
      • Características da linguagem gerada pela gramática
      • Portabilidade da gramática (nas 2 perspectivas acima);
      • Adaptabilidade (para Evolução da Linguagem);
      • Eficiência como suporte à Geração Automática dum Processador para a respectiva Linguagem (tempo+memória);
      • Eficiência do Reconhecedor (Processador) gerado com base nessa gramática(tempo+memória).
    • Critérios apresentados para avaliar a QL:
      • Legibilidade dos textos (programas) escritos nessa linguagem;
      • Expressividade;
      • Abstracção;
      • Consistência;
      • Unicidade;
      • Documentação;
      • Extensibilidade / Adaptabilidade;
      • Escalabilidade.
    • Métricas de Tamanho relativas à gramática:
      • Numero de Terminais (#T)
      • Numero de Não-Terminais (#NT)
      • Numero de Produções (#P)
      • Numero de Produções Inuteis (#PI)
      • Numero Médio de Alternativas para um NT ($Alt-med)
      • Comprimento Médio do RHS de cada Produção ($RHS-med)

05 de Janeiro de 2009

  • Dado faltar um grande número de alunos, não foram discutidas as últimas questões Q17 e Q18.

  • Para colmatar a discussão sobre o tratamento de erros (recuperação) e preparar as métricas relativas à qualidade das gramáticas, foi feita uma introdução muito sucinta ao conceito de Autómato Determinista de Parsing LR(0) e ao processo de construção:
    • exemplo apresentado: Aut-LR(0) da linguagem Lisp (Exemplo 2);
    • exemplo proposto para fazer para a próxima aula (ver Q19).

  • Introdução à Qualidade de Linguagens (QL) e Qualidadade de Gramáticas (QG); Métricas:
    • Métricas de Tamanho ao Parser:
      • Numero de Funções do Parser RD (#NT+#T)
      • Dimensão da Tabela de Parsing LL(1) (#NT*(#T+1))
      • Dimensão da Tabela de Parsing LR(0) (#Q*(#T+1) + #Q*#NT)
    • Métricas de Forma:
      • Forma de Recursividade (Directa, Indirecta, Mista)
      • Tipo de Recursividade (Esq, Dir, Dir-LL, Mista, Implicita)
      • Notação (BNF, exBNF, Mista)
      • Factor de Coesão -- Dependência entre Símbolos (FanOut? / FanIn? )

12 de Janeiro de 2009

  • Construção do Autómato Determinista de Parsing LR(0) para a gramática do Exercício 4.
  • Cálculo das métricas de tamanho para duas variantes da gramática Lisp (Lispv1.g e Lispv2.g) anteriomente apresentadas na aula (BNF/EBNF).
    Métrica Lisp (v1) Lisp (v2)
    #NT 3 2
    #T 4 4
    #P 6 4
    #PI 0 0
    $Alt-med 2 2
    $RHS-med 1.3(3) 1.5

  • Estudo do impacto de cada uma das variantes quanto à legibilidade de G como geradora de L e quanto à legibilidade em termos de manutenção. Relativamente às duas versões da gramática do Lisp apresentadas, os alunos concordaram que a 2ª versão era mais legível e mais fácil de manter do que a 1ª.

Métrica Lisp (v1) Lisp (v2)
Forma de Rec. Mista Directa
Tipo de Rec. Direita Implicita
Notação BNF eBNF
Fan-int 8/3 (1+5)/2 = 3
Fan-out 4/3 (0+2)/2 = 1
Fan-out/Fan-in 1/2 1/3

19 de Janeiro de 2009

  • Introdução das métricas lexicográficas:
    • ML1 --- identificadores dos símbolos N U T, podendo tomar um dos seguintes valores: abreviado/extenso e esclarecedor/não esclarecedor.
    • ML2 --- ortografia das palavras reservadas e sinais, podendo tomar um dos seguintes valores: abreviado/extenso e esclarecedor/não esclarecedor.
    • ML3 --- ortografia dos terminais-variáveis, podendo tomar um dos seguintes valores: flexivel, rígido.
    • ML4 --- comentários, podendo tomar um dos seguintes valores: inline, bloco, misto, meta-informação.

  • Cálculo das métricas de forma e lexicográficas para as duas variantes da gramática Lisp anteriomente apresentadas na aula (BNF/EBNF).

Métrica Lexicográfica Lisp (v1) Lisp (v2)
ML1 Abreviado/Esclarecedor Abreviado/Esclarecedor
ML2 NA NA
ML3 Rigidos Rigidos
ML4 NA NA

26 de Janeiro de 2009

  • Cálculo das métricas do Exercício 4.

Métrica PIs PIs(v2) PIs(v3)
ML1 Abreviado/Não Esclarecedor Abreviado/Não Esclarecedor Abreviado/Não Esclarecedor
ML2 Não Abreviado/Não Esclarecedor Não Abreviado/Não Esclarecedor Não Abreviado/Não Esclarecedor
ML3 Rigidos Rigidos Rigidos
ML4 Linha Linha Linha
       
Forma Directa Directa Directa
Tipo Mista Mista Mista
Notação BNF BNF BNF
FanIn 36/12    
FanOut 3/2    
FanIn/FanOut 0,5    
       
#T 14 14 14
#NT 12 14 14
#P 17 20 19
#PI 5 6 5
$Alt-Med 17/12 20/14 = 1.43 19/14=1.36
$RHS-Med 37/17 43/20 = 2.15 39/19=2.11
       
#Tam-RD 26 28 28
#Tam-LL 180 210 210
#Tam-LR 918 1160 1044


r30 - 23 Sep 2009 - 10:52:57 - JoseFaria
This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback
Syndicate this site RSSATOM