---

Engenharia de Linguagens (2009/10)

Engenharia Gramatical

Exercícios e Exemplos para as aulas

Exemplo 5:

A gramática independente de contexto GIC5, abaixo apresentada, define uma linguagem específica (DSL) para apoio à contabilização de todos os PIs de um dado grupo de investigação, permitindo descrever cada projecto concluído ou em andamento dentro do grupo, financiado pela FCT, pelo GRICES ou pela ADI. O Símbolo Inicial é PIs, os Símbolos Terminais são escritos em minúsculas (pseudo-terminais), ou em maiúscula (palavras-reservadas), ou entre apóstrofes (sinais de pontuaçãao) e a string nula é denotada por &; os restantes serão os Símbolos Não-Terminais.

         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
         p11: SglProj --> id
         p12: Desc --> str
         p13: Entidad --> FCT
         p14:          | GRICES
         p15:          | ADI
         p16: Ano --> num
         p17: Valor --> num

sabendo-se ainda que os símbolos terminais variáveis e os comentários válidos são definidos pelas seguintes expressões regulares:

         num : [0-9]+
         id : [a-zA-Z]+
         str : \"[^"]*\"
         comentario1 : "%".*

Afira a qualidade de GIC5 calculando todas as métricas estudadas (tamanho, forma, lexicográficas).

Pretende-se repetir a avaliação da 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):

• (GIC5T1) reescreva a gramática eliminando todas as produções unitárias e a recursividade (à custa de usar notação ex-BNF);
• (GIC5T2) por questões de legibilidade e outras razões, não é desejável ter produções tão longas (com tantos símbolos do lado direito), como a p10 acima. Modifique a gramática G de modo a permitir reescrever p10 da seguinte forma:

         p10: Proj --> SglProj Desc Financiament Period

• (GIC5T3) complete a gramática G para permitir incluir na descrição detalhada de cada projecto (símbolo Proj) a lista de todos os seus membros (sigla dos investigadores que nele colaboram);

Exemplo 4:

Repita o mesmo exercício do Exemplo 3 para medição e aferição de qualidade aplicado à sua gramática do Exemplo 1.

Exemplo 3:

Considere a gramática independente de contexto abaixo apresentada no Exemplo 2, designada por GIC2, e calcule as métricas dos 3 tipos de modo a poder pronunciar-se sobre a qualidade da GIC em causa.

Repita o mesmo exercício de medição e aferição de qualidade para as gramáticas GIC2T1, GIC2T2, GIC2T3, GIC2T4 e GIC2T5 obtidas da original (GIC2) por aplicação das sequintes transformações:

• (T1) remova todas as produções unitárias;
• (T2) transforme a gramática em LL(1);
• (T3) reescreva a gramática usando ex-BNF, de modo a eliminar toda a recursividade directa ou indirecta;
• (T4) reescreva a gramática de modo a permitir que a derivação do símbolo Descrição na produção p4 seja assim:

   
             p4:  Descricao    -->  IdentObra '(' Autor ')' IdentEdicao
   

• (T5) altere a gramática de modo a permitir que cada livro tenha mais de um Autor.

-- -- PedroRangelHenriques - 23 Jan 2010 - 23 Jan 2010

Exemplo 2:

A gramática independente de contexto, GIC, abaixo apresentada, define uma linguagem específica para descrever os livros e CDs disponíveis numa biblioteca e os estados que lhe são associados (livres ou emprestados), à semelhança do que acontece nas bibliotecas da UM.

O Símbolo Inicial é Biblioteca, os Símbolos Terminais são escritos em maiúsculas (pseudo-terminais) ou em maiúscula entre apostrofes (palavras-reservadas e sinais de pontuação), e a string nula é denotada por &; os restantes (sempre em minúsculas) serão os Símbolos Não-Terminais.

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

Neste contexto e após analisar a GIC dada, responda às alíneas seguintes.

• a) Escreva uma Frase válida da linguagem gerada pela GIC dada, mostrando a respectiva Árvore de Derivação.

• b) Altere a gramática de modo a permitir que cada livro tenha mais de um Autor.

• c) O par de produções p1/p2 define uma lista com recursividade à esquerda. Altere esse par para usar recursividade à direita e mostre, através das árvores de derivação, a diferença entre ambos os esquemas iterativos.

• d) (TPC)Escreva as funções de um parser RD-puro (recursivo-descendente) para reconhecer o Símbolo Estado e seus derivados.

• e) (TPC)Construa o estado inicial do autómato LR(0) pra gramática dada e os estados que dele saiem.

• f) Transforme a GIC dada numa gramática tradutora, GT, reconhecível pelo AnTLR, para:
  • calcular e imprimir: o número de registos; e o número de livros existentes para cada registo.
  • o número total de livros com estado RESERVADO/PERMNENTE/ESTANTE.
  • identificar e listar por ordem alfabética os títulos dos livros.
  • verificar se não existem registos com a mesma referência.

• g) repita a alinea anterior usando agora uma gramática de atributos, GA, recorrendo também ao AnTLR, para gerar o processador, criando primeiro uma árvore de sintaxe abstracta (ASA).

Exemplo 1:

Black é uma jovem empresa portuguesa que desenha, produz e comercializa tudo para Góticos, desde vestimentas, meias e sapatos até adereços e tatuagens.

A Black quer ter um sitio WWW, como agora é moda, mas que seja alimentado facilmente por eles (cada época que a colecção é alterada) sem contudo saberem nada de HTML, nem terem eles de montar o site. Para isso pretende-se definir uma nova Linguagem que permita à Black descrever a sua colecção. Além da data da última actualização, a linguagem deverá permitir descrever acessórios e vestimentas.

No caso de se tratar de um acessório, além da referência e descrição, deverá ser possível incluir o url para uma ou mais imagens (opcional), o tipo do acessório (bracelete, colar, bolsa, anel, piercing); o seu preço e o material de que é feito (pele, cabedal, tecido, metal).

No caso de se tratar de vestimenta, deverá ser possível diferenciar entre Para Ele e Para Ela. Além da referência e descrição da vestimenta, deverá ser incluído o url para uma ou mais imagens, o tipo da vestimenta (vestido, calça, t-shirt), o preço e os tamanhos disponíveis (XS, S, M, L, XL).

Após ler o enunciado acima, pede-se que:

• a) Escreva então uma Gramática Independente de Contexto, GIC, que especifique a Linguagem pretendida (note que o estilo da linguagem (mais ou menos verbosa) e o seu desenho são da sua responsabilidade).

• b) Transforme a GIC acima em notação do AnTLR e gere um parser para reconhecer frases válidas da linguagem que criou e para detectar os erros em frases inválidas.

Questões colocadas nas aulas

Q1:

• (2009-10-19) Investigue o que existe sobre métricas para avaliar a qualidade de gramáticas (apresente na próxima aula uma síntese das referências que encontrou).

Fichas Práticas para Avaliação (a resolver fora das aulas)

F4:

• Escreva uma pequena monografia em formato de artigo, e entregue para efeitos de avaliação, sobre Editores Estruturais (structure-editors) e Editores Orientados pela Sintaxe (syntax-directed editors): resumo do conceito, abordagens e estado actual (nível académico e comercial).

F3:

• Desenvolva um sistema (GraAlEditor) para edição, visualização e medição de gramáticas. Nesse sistema deve implementar os várioa parametros de aferição e as várias métricas estudadas.

F2:

• Escreva uma pequena monografia em formato de artigo, e entregue para efeitos de avaliação, sobre Parsing: resumo do conceito, abordagens e algoritmos.

F1:

• O resultado da investigação solicitada na Q1 acima, deve ser escrito em formato de artigo e entregue (após apresentação oral na aula) para efeitos de avaliação --- Classe Latex para formatar o documento a apresentar: llncs2e.zip

Notas e Links úteis

• AnTLR
• Literate Programming
• Construção de árvores em AnTLR

---