Ao longo desta dissertação, faz-se o estudo de uma área (processamento de documentos) e identifica-se um problema em particular (semântica estática dos documentos). Para a resolução desse problema seguem-se duas abordagens, cada uma delas suportada por um formalismo, nomeadamente: Gramáticas de Atributos (abordagem gramatical, no Capítulo 9) e CAMILA (abordagem algébrica no Capítulo 8).
Para facilitar a discussão apresentada nesses capítulos e outras referências ao longo da dissertação, optou-se por introduzir brevemente os referidos formalismos (conceitos básicos e notação) no presente capítulo: Gramáticas de Atributos (Secção 2.1) e CAMILA (Secção 2.2).
Uma gramática de atributos é um formalismo muito divulgado e utilizado pela comunidade dos compiladores para especificar a sintaxe e a semântica das linguagens [Hen92].
Introduzidas por Knuth [Knu68], as gramáticas de atributos surgiram como uma extensão das gramáticas independentes de contexto (GIC), permitindo a definição local (sem a utilização de variáveis globais) do significado de cada símbolo num estilo declarativo.
Os símbolos terminais têm atributos intrínsecos (que descrevem a informação léxica a cada um deles associada). Por outro lado, os símbolos não-terminais são associados com atributos genéricos, através dos quais se poderá sintetizar informação semântica (subindo na árvore de sintaxe abstracta, das folhas para a raiz), ou herdar informação semântica (descendo na árvore de sintaxe abstracta, do topo para as folhas), permitindo referências explícitas a dependências de contexto.
Seja G, uma gramática independente de contexto definida como um tuplo G=<T,N,S,P>, onde:
T representa o conjunto de símbolos terminais (o alfabeto).
N é o conjunto de símbolos não-terminais.
S é o símbolo inicial, ou axioma: S ∈ N.
P é o conjunto de produções, ou regras de derivação, cada uma com a forma:
A → &dgr;, A ∈ N e &dgr; ∈ (T U N)*
que representaremos neste documento como:
X0 → X1 X2 ... Xn
Para cada regra de derivação p ∈ P existe uma árvore de sintaxe cuja raiz é X0, o não-terminal do lado esquerdo e, os seus n descendentes são os Xi com n ≥ i ≥ 1, correspondentes aos símbolos do lado direito. A árvore de sintaxe abstracta respectiva é aquela na qual se retiram os nodos que correspondem a palavras reservadas, só ficando os que representam símbolos com carga semântica.
Dada uma frase f de LG, a linguagem gerada pela gramática G, designa-se por Árvore de Sintaxe (AS), ou Árvore de Derivação , a árvore cuja raiz é o axioma S da gramática e cuja fronteira (as folhas) é composta pelos símbolos terminais que, uma vez concatenados da esquerda para a direita, formam a frase inicial. A Árvore de Sintaxe Abstracta (ASA) obtém-se colando as respectivas sub-árvores abstractas correspondentes a cada uma das regras de derivação p ∈ P seguidas para derivar a frase a partir do axioma S.
Uma gramática de atributos (GA) é um tuplo GA=<G,A,R,C>, onde:
G é uma GIC que segue a definição dada acima.
A é a união dos A(X) para cada X ∈ (T U N) e representa o conjunto de todos os atributos (cada um com um nome e um tipo); os atributos dos símbolos terminais chamam-se intrínsecos e o seu valor não precisa de ser calculado, provém da análise léxica; para cada não-terminal X, o conjunto dos respectivos atributos A(X) divide-se em dois subconjuntos: os atributos herdados AH(X) e os atributos sintetizados AS(X).
R é a união dos Rp, o conjunto das regras de cálculo dos valores dos atributos para cada produção p ∈ P.
C é a união dos Cp, o conjunto das condições de contexto para cada produção p ∈ P.
Seja p uma produção de uma GIC (p ∈ P), Rp o respectivo conjunto de regras de cálculo e Cp o respectivo conjunto de condições de contexto. Neste contexto:
Xi.a, i ≥ 0, representa o atributo a associado ao símbolo X que ocorre na posição i da produção p.
uma regra de cálculo, r ∈ Rp, é uma expressão da forma Xi.a = ƒun( ..., Xj.b, ... ) com:
a ∈ AS(X0) V a ∈ AH(Xi), i > 0
b ∈ AH(X0) V b ∈ AS(Xj), j > 0
ƒun é uma função do tipo Va (o tipo do atributo a)
uma condição de contexto, c ∈ Cp, é um predicado da forma: pred( ..., Xi.a, ... ), i ≥ 0
Dada uma frase de LGA, a linguagem gerada pela gramática de atributos GA, seja ASA a correspondente Árvore de Sintaxe Abstracta, como definido acima. Originalmente, cada nodo da árvore é etiquetado com o símbolo gramatical correspondente e o identificador da produção aplicada para o derivar.
Suponhamos, agora, que cada nodo é enriquecido com os atributos, herdados ou sintetizados, associados àquele símbolo.
Uma Árvore de Sintaxe Abstracta Decorada (ASAD) é a ASA inicial depois de passar pelo processo de cálculo dos atributos, que vai associar aos atributos de cada nodo um valor do tipo apropriado. Para que seja uma ASAD válida é ainda necessário que todas as condições de contexto associadas às produções correspondentes aos nodos da árvore, sejam satisfeitas (cujo valor seja verdadeiro para os valores actuais dos atributos).
Para ilustrar estes conceitos apresenta-se o exemplo seguinte que especifica uma gramática de atrbutos para o reconhecimento e conversão de datas.
Exemplo 2-1. Uma gramática de atributos para tratamento de datas
Neste exemplo, especifica-se uma linguagem para a definição de datas em formato português antigo (dd.mm.aaaa) e especifica-se também a respectiva conversão para o formato europeu (aaaa.mm.dd) com validação completa.
Assim, e atendendo às definições acima apresentadas tem-se:
T = { int, "/" }
N = { Data, Dia, Mes, Ano }
S = Data
P = { p1, p2, p3, p4 }
AS(Data) = { trad: string }
AS(Dia) = { val: string }
AH(Dia) = { limite: int }
AS(Mes) = { nome: string; limite:int }
AH(Mes) = { ano: int }
AS(Ano) = { val: string; ano: int }
AIntr(num) = { val: int }
p1: Data -> Dia "/" Mes "/" Ano
Rp1: Data.trad = junta("%s.%s.%s",Ano.val,Mes.nome,Dia.val)
Dia.limite = Mes.limite
Mes.ano = Ano.ano
p2: Dia -> num
Rp2: Dia.val = tostr(num.val)
Cp2: ((num.val >= 1) e (num.val <= Dia.limite))
p3: Mes -> num
Rp3: Mes.nome = convertenome(num.val)
Mes.limite = ultimodia(num.val,Mes.ano)
Cp3: ((num.val >= 1) e (num.val <= 12))
p4: Ano -> num
Rp4: Ano.val = tostr(num.val)
Ano.ano = num.val
Cp3: (num.val >= 1) A gramática de atributos é um formalismo declarativo para especificar linguagens. Porém a gramática de atributos pode também ser usada para a construção (manual ou automática) de processadores para as linguagens especificadas (compiladores, tradutores, etc). Assim como da GIC se retira toda a informação para desenvolver o analisador léxico e o analisador sintático (parser), também das regras de cálculo e condições de contexto se pode extrair informação necessária para implementar a análise semântica.
A análise semântica, implementada segundo este paradigma da tradução dirigida pela semântica [1] [Hen92], é constituída por duas grandes tarefas aplicadas a cada um dos nodos da ASAD:
o cálculo do valor das ocorrências dos atributos
a validação das condições contextuais associadas a cada nodo da ASAD
Este cálculo faz-se aplicando as funções descritas explicitamente na gramática de atributos sob a forma de regras de cálculo (conjunto Rp). De igual forma, a validação realiza-se avaliando os predicados também explicitamente especificados na forma de condições de contexto (conjunto Cp).
As regras de cálculo, ao definirem o valor de uma ocorrência de atributo em função dos valores de outras ocorrências de atributos, induz imediatamente dependências entre estes. Estas dependências têm de ser identificadas pois irão influenciar a ordem de cálculo, na medida em que devem ser respeitadas para que uma função seja sempre invocada com os argumentos instanciados com os valores correctos. A determinação da ordem de cálculo é uma tarefa complexa (cresce exponencialmente em tempo e espaço relativamente ao número de atributos) que é executada pelo sistema gerador do compilador. Na prática, o problema é contornado introduzindo a noção de classes gramaticais para as quais se desenvolveram algoritmos de ordenação mais eficientes [Hen92].
Além disso, dada a quantidade de ocorrências de atributos que podem surgir numa ASAD (muitos deles tomando valores em tipos estruturados), o processo de cálculo consome grande parte do tempo total da compilação. Por causa deste factor temporal, surgiu o conceito de cálculo incremental dos atributos no contexto de compiladores que são activados em simultâneo com editores estruturados. Nesses ambientes, o compilador tem de ser reactivado (para reanalisar o texto) cada vez que é feita uma alteração a esse texto-fonte. O cálculo incremental (conceito também existente nas "folhas de cálculo") tem por objectivo a minimização do esforço dispendido na análise semântica para que o processo de edição/compilação seja mais rápido. A ideia é manter-se, em tempo real, a informação sobre as dependências entre atributos de modo a que, após uma alteração qualquer na ASA, se identifiquem os atributos associados aos símbolos que foram alterados e aqueles que deles dependem e se calculem apenas esses valores, sendo conservados todos os restantes.
Como foi dito, para desenvolver parte do trabalho apresentado nesta dissertação (Capítulo 9), recorreu-se a este formalismo. Para implementar os protótipos, recorreu-se a um ambiente de geração de compiladores incrementais baseado em Gramáticas de Atributos: o Synthesizer Generator [RT89a, RT89b, Ram93], que se apresenta na secção seguinte.
Após ter sido introduzido o conceito de Gramáticas de Atributos, apresenta-se agora o Synthesizer Generator (SGen) como uma ferramenta que permite gerar automaticamente editores estruturados associados a compiladores incrementais.
O SGen é uma ferramenta que tem por objectivo implementar editores dirigidos pela sintaxe de uma dada linguagem. Estes são gerados a partir de uma especificação formal escrita na linguagem do SGen, a SSL ("Synthesizer Specification Language").
A SSL é uma linguagem funcional que foi pensada e concebida para a especificação de acções semânticas num compilador. Muitos dos ingredientes necessários para o efeito são suportados nativamente na linguagem: manipulação da árvore de derivação, tipos de dados estruturados pensados para suportar tarefas comuns num compilador como por exemplo a gestão de uma tabela de símbolos, etc.
O SGen foi desenvolvido na Universidade de Cornell, Estados Unidos, por Thomas Reps e Tim Teitelbaum [RT89a, RT89b]. Surgiu como o sucessor do "Cornell Program Synthesizer" [TR81], que era basicamente um editor de PL/I com um compilador e um interpretador incremental.
Este sistema começou a ser desenvolvido em 1981 e, devido ao sucesso que alcançou, em 1990, o projecto termina no meio académico e continua numa empresa constituída para o efeito, GrammaTech, Inc.
Os editores gerados pelo SGen trazem algumas vantagens ao desenvolvimento de programas e outras especificações do género, pois:
seguem o paradigma da compilação incremental, que acaba por ser a sua maior potencialidade.
o editor gerado pelo SGen faz a análise léxica, a análise sintática e a análise semântica em simultâneo com a edição, podendo ainda, como efeito lateral, realizar o processamento da informação reconhecida até ao momento.
o conhecimento da sintaxe da linguagem permite que o próprio editor dê um feedback imediato ao seu utilizador, guiando-o e dispensando-o de conhecer a sintaxe concreta.
o conhecimento da semântica da linguagem pode ser usado para transformar a informação, incrementalmente, durante a edição (reescrita de ramos da ASA).
a possibilidade de dotar o editor com o conhecimento estrutural e sintático de uma dada linguagem faz com que estes editores sejam óptimos meios de normalização de escrita de programas ou documentos. Por exemplo, dotando um editor com o conhecimento estrutural de uma carta é possível pôr as pessoas de uma empresa a escrever cartas com a mesma estrutura.
o editor gerado pode ainda ser configurado para ter janelas extra onde são mostradas vistas transformadas da árvore de sintaxe abstracta ("unparsing rules"); normalmente estas vistas correspondem às várias gerações de código realizadas pelo compilador.
Um compilador desenvolvido em SGen tem a mesma estrutura de um compilador genérico, tendo portanto os mesmos módulos, só que além destes tem outros relacionados com a interface e a edição estruturada.
A especificação de um editor estruturado em SSL compreende vários módulos: sintaxe abstracta (onde se especifica a sintaxe da linguagem à custa apenas dos elementos estruturais com valor semântico), sintaxe concreta (onde se especifica toda a sintaxe da linguagem; é este módulo que é usado para carregar ficheiros externos no editor), atributos (onde se declaram os atributos e se especificam as suas equações de cálculo) e, por fim, as regras de "unparsing" (onde se especifica de que maneira queremos ver a informação sintetizada na árvore de sintaxe abstracta decorada; para cada transformação pretendida da informação sintetizada iremos ter um destes módulos).
Para exemplos concretos, o leitor poderá consultar as referências fornecidas ou ainda, duas teses de mestrado recentemente desenvolvidas nesta linha de investigação [Lop98, Sou98].
| [1] | Nome que atribuímos por oposição ao paradigma da tradução dirigida pela sintaxe. |