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").

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

          
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).

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

  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

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; }
    ;

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:

• Lisp.g
• LispTree.g

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)
Fan-int	8/3	(1+5)/2 = 3
Fan-out	4/3	(0+2)/2 = 1
Fan-out/Fan-in	1/2	1/3
Forma de Rec.	Mista	Directa
Notação	BNF	eBNF
Tipo de Rec.	Direita	Implicita

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).

26 de Janeiro de 2009

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

• black.g: black.g