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):
Reduza a gramática G eliminando as produções inúteis.
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
Altere a gramática G para agrupar numa única descrição todas as orientações do mesmo Orientador.
Notas e Links úteis