---

Engenharia de Linguagens

Engenharia Gramatical 2008/09

Exercícios e Exemplos para as aulas

Exemplo 1: Escreva, em notação AnTLR, 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;

Acrescente Acções Semânticas (e depois Atributos) para calcular o Comprimento da Lista.

Exemplo 2: Escreva, em notação AnTLR, uma Gramática para a famosa linguagem funcional Lisp(1) que:

• aceite uma Lista de Números;
• gere o respectivo Parser com o AnTLR;
• teste o parser com o Debugger visual do AnTLRWorks;

Acrescente Atributos para:

• calcular a quantidade de números e palavras da lista;
• construir uma lista plana (todos os elementos ao mesmo nível) com os elementos originais associados ao nível a que aparecem;
• verificar que todos os elementos da lista sejam do mesmo tipo do 1ºelemento
• gerar código post-fix(2) como se a SExp fosse calculada numa máquina de stack.

(1) Considere para este exemplo que a gramática de uma Symbolic Expression (na qual assenta a linguagem Lisp) escrita numa notação geral (livre) é:

      T = { num, pal, "(", ")" }
      N = { SExp, SExplist }
      S = SExp
      P = {
            p1: SExp     --> num
            p2: SExp     --> pal
            p3: SExp     --> "(" SExplist ")"
            p4: SExplist --> SExp SExplist
            p5: SExplist --> &
          }

(2) Considere que o código-máquina a gerar (para traduzir as S-Expressions para uma máquina de stack) é uma Linguagem Assembly simples apenas com as 3 instruções seguintes:

    LAB pal   // LABel significa que o operando 'pal' é uma constante 
              // alfanumérica (identificador)
    CONS num  // CONS significa que o operando 'num' é uma constante 
              // numérica
    OPER op   // OPER significa que o operando 'op' é um operador

Para melhor compreender o que se pretende, mostra-se abaixo o resultado de processar duas frases válidas da Linguagem Lisp:

    (defun quad x (mul x x))           
              ==> LAB quad, LAB x, LAB x, LAB x, OPER mul, OPER defun
    (let res (add (mul 1 2)(div 8 4))) 
              ==> LAB res, CONS 1, CONS 2, OPER mul, CONS 8, CONS 4, 
                           OPER div, OPER add, OPER let

Exemplo 3: Nos tempos que correm, a utilização da linguagem SQL (Structured Query Language) é comummente aceite na comunidade informática para a interrogação de bases de dados. São várias as ferramentas que fazem uso desta linguagem: SQL Server, MySQL, Apache Derby, etc.

A gramática da linguagem SQL não é mais do que uma lista de comandos. Pretende-se neste exercício que implemente a gramática da linguagem SQL com pelo menos 4 comandos à sua escolha. Em relação aos comandos escolhidos, pode simplificar a sua sintaxe real, incluindo apenas a parte obrigatória (p.ex., no SELECT pode omitir a parte ORDER-BY ou GROUP-BY).

Depois de implementar a sua gramática, recorrendo ao AnTLR, pretende-se que:

• Construa a Árvore de Sintaxe Abstracta (ASA, ou em inglês AST) utilizando o mecanismo próprio do ANTLR;
• Depois de ter a AST, deverá:
  • construir a Tabela de Identificadores (TabId) constituída pelos nomes das Tabelas e pelos nomes dos Campos
  • gerar uma S-Expr (Lisp) a partir da árvore (uma espécie de pretty-print da AST).

Exemplo 4:

• Análise da Qualidade da Gramática de uma Linguagem para Gestão Científica II (Projectos de Investigação): enunciado

Questões colocadas nas aulas

Q1:

• (2008.09.29) "Explique porque se constata, ao fazer debug visual no AnTLRWorks, que o parser gerado pelo AnTLR é Top-Down?"

Q2:

• (2008.09.29) "O que é preciso acrescentar à Gramática da Lista de Números, do Exemplo 1, para calcular o comprimento da lista (ou contar os seus elementos)?"

Q3:

• (2008.10.06) "Porque é que, após analisar o código produzido pelo ANTLR, se pode afirmar que o Parser gerado é um recursivo-descendente (RD) e não um LL?"

Q4:

• (2008.10.06) "Porque é que a declaração dos atributos numa gramática AnTLR devia ser introduzida pela palavra-reservada 'synthesizes' e não 'returns' ?"

Q5:

• (2008.10.18) Considere a gramática da linguagem Lisp definida na última aula (download aqui) para responder à seguinte questão.
  Substituindo a produção p4: sExpr -> '(' sExpr* ')' por p4: sExpr -> '(' sExpr sExpr+ ')' como procederia ao cálculo do atributo soma?

Q6:

• (2008.10.20) "Porque é que o termo PROPAGAR 'expressa correctamente' o conceito de herança em Gramáticas de Atributos (GAs)?"

Q7:

• (2008.10.27) "Os atributos podem ou não ser calculados de uma forma concorrente?"

Q8:

• (2008.10.27) "Qual o princípio das GAs que um neto não pode herdar directamente de um(a) avô(ó)?"

Q9:

• (2008.10.27) "Qual o inconveniente de alterar código automaticamente gerado?"

Q10:

• (2008.10.27) "Qual a diferença de atitude entre JavaDoc (princípio) e Literate Programming?"

Q11:

• (2008.11.10) "Qual a diferença entre definir o ';' como Parte integrante dum Comando, ou como Terminador de Comando ? e se for como Separador de Comandos ?"

Q12:

• (2008.11.17) "Porque os compiladores actuais e reais não fazem correcção de erros?"

Q13:

• (2008.11.17) "Prove, com o autómato LR(0), a diferença entre as seguintes situações: ';' como terminador e ';' como parte integrante do comando."

Q14:

• (2008.11.24) "Porque é que o compilador não é um processo interactivo?"

Q15:

• (2008.11.24) "Qual o ganho extra que advém do uso de editores sensíveis ao contexto? Diga também qual a diferença entre Editor Sensível ao Contexto e Editor Guiado pela Sintaxe."

Q16:

• (2008.11.24) "Qual a diferença entre um compilador à la Pascal e um compilador à la C no que diz respeito ao tratamento de erros em run-time?"

Q17:

• (2008.12.15) "Porque é que os Editores Dirigidos pela Sintaxe quase não se utilizam actualmente?"

Q18:

• (2008.12.15) "Proponha uma estrutura para construir a Tabela de Identificadores a usar no processamento das Linguagens Orientadas a Objectos."

Q19:

• (2009.01.05) Constrúa o Aut-LR(0) para a gramática (GIC) do Exemplo 4.

Q20:

• (2009.01.05) Aplique todas as Métricas de Tamanho e de Forma já estudadas à GIC da linguagem Lisp (ver Exemplo 2).

Q21:

• (2009.01.26) Explique porque, na prática, se usam 2 gramáticas para a mesma linguagem.

Q22:

• (2009.01.26) Calcule as Métricas Lexicográficas e de Forma para as linguagens C, Pascal e XML, usando as gramáticas disponíveis no UltraGram.

Fichas Práticas para resolver fora das aulas

Ficha I (Data de Entrega: 2008.11.10 --- relatório em Literate Programming)

• Geração de um Processador para Gestão Científica (Teses e Orientadores): enunciado

Ficha II: Faça um relatório detalhado, recorrendo ao Literate Programming, sobre o Exercício 3 descrito acima.

Ficha III (Data de Entrega: 2009.02.05 --- relatório em Literate Programming):

• Pesquise na Internet o que há sobre Métricas para Avaliação da Qualidade em Gramáticas e Linguagens; integre no seu relatório um capítulo específico (mas claro e bem estruturado) sobre o estudo feito.
• Avaliação da Qualidade de Gramáticas; Métricas

Retome a Gramática da DSL GCI apresentada no enunciado da Ficha I e estude a sua qualidade avaliando as Métricas que foram ensinadas nas aulas.

Pretende-se repetir a avaliação da sua qualidade depois de efectuar cada uma das 3 transformações abaixo (as alterações são não-cumulativas, isto é, são independentes e realizadas sempre sobre a gramática original):

• (T1)

Reduza a gramática G eliminando as produções inúteis.

• (T2)

Altere a gramática G de modo a simplificar o lado direito da produção p3, permitindo escrevê-lo na forma:

    p3:  Pg       -->  IdOrient DescOrientac Periodo

• (T3)

Altere a gramática G para agrupar numa única descrição todas as orientações do mesmo Orientador.

Notas e Links úteis

• AnTLR
• Literate Programming
• Construção de árvores em AnTLR
• Versão do AnTLRworks com suporte de Debug de Tree Grammars

---