---

Engenharia de Linguagens (2011/12)

Engenharia Gramatical

Exercícios e Exemplos para as aulas

Exemplo 1:

Considere a linguagem para descrever uma Factura. Sabe-se que uma Factura é composta por um cabeçalho e um corpo, e este é composto por um ou mais movimentos.

A GIC abaixo define formalmente uma primeira versão da linguagem Factura, de acordo com a descrição acima:

      T = { id, str, num}
      N = { Factura, Cabec, Corpo, IdFact, IdE, IdR, ...... }
      S = Factura  
      P = {
            p1:  Factura  --> Cabec Corpo
            p2:  Cabec    --> IdFact IdE IdR
            p3:  IdFact   --> NumFact
            p4:  NumFact  --> id
            p5:  IdE      --> Nome NIF Morada NIB
            p6:  IdR      --> Nome NIF Morada
            p7:  Nome     --> str
            p8:  NIF      --> str
            p9:  Morada   --> str
            p10: NIB      --> str
            p11: Corpo    --> ...
          }

Pede-se então que escreva uma Gramática de Atributos, GA, para

• a) calcular o total por linha e total geral.

• b) estender a linguagem original para permitir mais do que uma factura (calculando os mesmos totais).

• c) modificar a linguagem de modo a suportar inicialmente a descrição do stock (referência, descrição, preço unitário e quantidade em stock); neste caso, cada linha só terá a referência e a quantidade vendida.

• d) estender a semântica da nova linguagem de modo a também actualizar o stock.

Exemplo 2:

A gramática independente de contexto GIC5, abaixo apresentada, define uma linguagem específica (DSL) para apoio à contabilização de todos os Responsáveis por Projetos de I&D (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 3

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 4:

Para apoio a um projecto de Genealogia pretende-se que crie uma linguagem simples (Genea) que permita descrever Famílias. Cada Família será formada pela identificação dos Progenitores (nome próprio e apelido, separados) e pela lista dos filhos (apenas nome próprio).

Em fases posteriores pretende-se que a sua linguagem permita distinguir entre os Progenitores, a Mãe e o Pai, e depois a Data do Nascimento de cada Pessoa bem como a Data do casamento (para que o registo genealógico possa também suportar um projecto de investigação em Demografia Histórica).

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). Essa GIC deve ir sendo sucessivamente transformada para mostrar diferentes formas de definir a mesma linguagem e ainda para fazer a evolução da linguagem inicial, conforme acima pedido.

• b) Perante a GIC escrita, defina um conjunto (o mais completo possível) de validações semânticas que ache necessárias para se obterem frases da linguagem semanticamente corretas.

• c) Para cada uma das validações definidas, identifique a produção (ou produções) onde seja mais eficaz a verificação das mesmas, e
  • construa uma àrvore parcial da gramática onde se consiga desenhar o "cálculo" da informação necessária para escrever as validações
  • escreva as validações usando uma notação mais formal, usando o conhecimento adquirido na alínea anterior

• d) Transforme a GIC numa Gramática Tradutora (GT) para
  • calcular o número de famílias
  • calcular o número de filhos por família
  • calcular o número total de filhos
  • calcular a média de filhos por família
  • imprimir os nomes completos dos filhos (nome próprio + nome mãe + nome pai)

• e) Transforme a GIC numa Gramática Tradutora (GT) para gerar instruções SQL que carreguem para a Tabela "Pessoas" de uma base de dados a informação de cada membro do agregado familiar: Chave, NomeProprio, Apelido, Género (se conhecido); Note que a Chave deve ser gerada pelo seu Processador e que o Apelido dos Filhos deve ser inferido também por esse Processador a partir dos Apelidos dos Progenitores.

• f) Reescreva as GTs anteriores mas agora usando Gramáticas de Atributos (GA).

Exemplo 5:

Pretende-se que crie uma linguagem simples (Lista) que permita escrever uma lista (não vazia) de elementos mistos alfanuméricos e numéricos.

A partir dai, especifique um Processador para:

• a) calcular o número total de elementos da lista, o número de inteiros e o somatório dos números;
• b) calcular o somatório dos números, mas só após a ocorrência da palavra "soma";
• c) adicionar os números após a ocorrência da palavra "soma" e subtrair após a palavra "subtrai".

Exemplo 6:

Considere a gramática independente de contexto (GIC), abaixo apresentada, que define uma linguagem específica para descrever a lista de compras a fazer numa manhã de sábado de sol em Braga com vista a repor o stock do frigorifico e da despensa.

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

         p0:  Compras      -->  LISTA PARA data LCs
         p1:  LCs          -->  Setor '.'
         p2:                |   LCs  Setor '.'
         p3:  Setor        -->  IdSetor Cs
         p4:  IdSetor      -->  MERCEARIA | FRUTARIA | TALHO | PEIXARIA | PADARIA
         P5:  Cs           -->  Item
         p6:                |   Cs ';' Item
         p7:  Item         -->  Prod Marca Qt Unid
         p8:  Prod         -->  id
         p9:  Qt           -->  num
         p10: Marca        -->  &
         p11:               |   string
         p12: Unid         -->  KG | L | M | DZ | UNI

Tendo em conta esta GIC, utilize o AntLR e a seguinte gramática (Compras.g) para desenvolver as seguintes questões:

• Defina os atributos, regras de cálculo e regras de tradução necessários para: contar e imprimir o total de items distintos a comprar em cada setor do mercado municipal.

• Defina os atributos, regras de cálculo e regras de tradução necessários para determinar e imprimir o total de quilos (explicitados) a carregar para casa.

• Defina os atributos, regras de cálculo e condições de contexto necessários para garantir que: não se repetem setores na mesma lista de compras. Caso essa regra seja violada, deve ser emitida uma mensagem de erro

Exemplo 7

Referente ao exercício 1 do 1º Teste de EG (2011/2012), segue a especificação de uma possível Gramática em AntLR (Conferencias.g) e um possível texto de entrada para a mesma.

Nesta base, pretende-se que, em AntLR (usando atributos) se resolvam os seguintes pedidos para um analisador semântico:

• Verificar que o primeiro e último dia da conferência estão de acordo com a data de duração da conferência;

• O número de dias explicitados é igual ao número de dias compreendidos na data de duração da conferência;

• Para cada sessão, verificar que
  • não há comunicações a iniciar à mesma hora;
  • há um espaçamento temporal, X, equivalente entre as comunicações;
  • a comunicação inicial começa à hora indicada como o início dessa sessão;
  • a última comunicação termina X unidades de tempo antes da hora de fecho da sessão;

• O 1º autor de uma comunicação a decorrer numa sessão nunca é moderador da mesma;

e se produzam os seguintes dados estatísticos:

• Número de autores distintos;

• Número de comunicações por sessão;

• Média de autores por comunicação (não contemplar sessões do tipo PAINEL);

• Lista de comunicações por autor.

Exemplo 8

Em AntLR, pode-se construir uma árvore de sintaxe abstrata (AST) a partir de uma gramática concreta , usando regras de reescrita e de criação de árvores. Os seguintes ficheiros mostram como usando o exemplo da linguagem C (simplificada: Cmb ):

• Combined Grammar -- Gramática Concreta do Cmb com construção da árvore;
• Tree Grammar -- Estrutura da AST de Cmb com exemplo de uso de atributos;
• Run em Java -- Programa em Java para percorrer a AST e produzir resultados;

Dados estes 3 elementos, pretende-se que se criem semelhantes (um ficheiro para cada alínea) para:

• Fazer alteração à gramática base para suportar funções;
• Construir uma Tabela de Símbolos (para facilitar a tarefa, podem usar esta implementação de Tabela de Símbolos ) ;
• Fazer análise Semântica usando a tabela de símbolos;
• Fazer tradução do texto fonte Cmb para código máquina;
• ... (to be continued)