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:
-- -- 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
Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.