Gramáticas de Van Wijngaarden

Uma gramática de van Wijngaarden (também conhecida por gramática-vW ou gramática-W (W-grammar) é uma gramática em dois níveis que fornece uma técnica para definir potencialmente infinitas gramáticas, em um número finito de regras.

O formalismo foi inventado por Adriaan van Wijngaarden para definir com rigor algumas restrições sintáticas que anteriormente tinham que ser formuladas em linguagem natural, apesar de seu conteúdo ser essencialmente sintático. As aplicações típicas são o tratamento de gênero e número em sintaxes de linguagem natural e a boa definição de identificadores em linguagens de programação.

A técnica foi utilizada e desenvolvida na definição da linguagem de programação ALGOL 68. É um exemplo da larga classe de gramáticas aumentadas.

Visão global

Uma gramática-W consiste de um conjunto finito de meta-regras, que são usadas para derivar (possivelmente infinitamente muitas) regras de produção de um conjunto finito de Hyper-regras. Meta-regras são restritas as definidas por uma gramática livre de contexto. Hyper-regras restringem os contextos admissíveis ao nível superior. Essencialmente, as substituições consistentes, utilizadas no processo de derivação são equivalentes a unificação, como em Prolog, como foi observado por Alain Colmerauer.

Exemplos em Algol 68

Antes de ALGOL 68 a linguagem ALGOL 60 foi formalizada usando a forma, livre de contexto, de Backus-Naur. E assim o aparecimento de novas gramáticas de dois níveis, sensíveis ao contexto, apresentavam um desafio para alguns leitores do ALGOL 1968 ALGOL 68 "Final Report". Posteriormente, o relatório final foi revisto por Wijngaarden e seus colegas, e publicado como o ALGOL 1973 68 "Revised Report".

ALGOL 68, como no Relatório Final 1968 § 2.1

a) program : open symbol, standard prelude,
     library prelude option, particular program, exit,
     library postlude option, standard postlude, close symbol.
b) standard prelude : declaration prelude sequence.
c) library prelude : declaration prelude sequence.
d) particular program :
     label sequence option, strong CLOSED void clause.
e) exit : go on symbol, letter e letter x letter i letter t, label symbol.
f) library postlude : statement interlude.
g) standard postlude : strong void clause train

ALGOL 68 como no Relatório Revisado de 1973, §2.2.1, §10.1.1

program : strong void new closed clause

A) EXTERNAL :: standard ; library ; system ; particular.
B) STOP :: label letter s letter t letter o letter p.

a) program text : STYLE begin token, new LAYER1 preludes, 
       parallel token, new LAYER1 tasks PACK, 
       STYLE end token.
b) NEST1 preludes : NEST1 standard prelude with DECS1, 
       NEST1 library prelude with DECSETY2, 
       NEST1 system prelude with DECSETY3, where (NEST1) is
       (new EMPTY new DECS1 DECSETY2 DECSETY3).
c) NEST1 EXTERNAL prelude with DECSETY1 : 
       strong void NEST1 series with DECSETY1, go on token ; 
       where (DECSETY1) is (EMPTY), EMPTY.
d) NEST1 tasks : NEST1 system task list, and also token, 
       NEST1 user task PACK list.
e) NEST1 system task : strong void NEST1 unit.
f) NEST1 user task : NEST2 particular prelude with DECS, 
       NEST2 particular program PACK, go on token, 
       NEST2 particular postlude, 
       where (NEST2) is (NEST1 new DECS STOP).
g) NEST2 particular program : 
       NEST2 new LABSETY3 joined label definition
       of LABSETY3, strong void NEST2 new LABSETY3
       ENCLOSED clause.
h) NEST joined label definition of LABSETY : 
       where (LABSETY) is (EMPTY), EMPTY ; 
       where (LABSETY) is (LAB1 LABSETY1), 
          NEST label definition of LAB1, 
          NEST joined label definition of$ LABSETY1. 
i) NEST2 particular postlude :
       strong void NEST2 series with STOP.

Implementações

Analisador sintático (parser) yo-yo para gramáticas de van Wijngaarden com gramáticas de exemplo para expressões, eva, sal e a linguagem de programação Pascal [1]. O padrão atual ISO 7185 para a Pascal usa a Forma de Backus–Naur estendida.

História

Gramáticas-W são baseadas na ideia de fornecer aos símbolos não-terminais de gramáticas livres de contexto atributos (ou afixos) que passam informações entre os nodos da árvore sintática usados para restringir a sintaxe e especificar a semântica. Essa ideia era bem conhecido na época; por exemplo, Donald Knuth visitou o comitê de projeto de ALGOL 68 enquanto desenvolvia sua própria versão de sua gramática de atributos. Bastante peculiar para gramáticas-W foi seu tratamento rigoroso de atributos como cadeias de caracteres (strings), definidas por uma gramática livre de contexto, em que a concatenação é única operação possível; em gramáticas de atributos, os atributos podem ser de qualquer tipo de dados, e qualquer tipo de operação pode ser aplicado a eles.

Após a sua introdução no relatório Algol 68, as gramáticas-W foram consideradas amplamente como demasiado poderosas e sem restrições para serem práticas. Isso foi em parte uma consequência da forma como tinham sido aplicadas; o relatório revisado de Algol 68 continha uma gramática muito mais legível, sem modificar o formalismo da gramatica-W.

Entretanto, ficou claro que as gramáticas-W são de fato muito poderosas.

Elas são Turing completo, o que torna impossível a análise sintática, de um modo geral: é um problema indecidível decidir se uma dada cadeia de caracteres (string) pode ser gerada por uma dada gramática-W. Seu uso deve ser seriamente limitado quando usado para análise e tradução automática. Variantes restritas e modificadas de gramáticas-W foram desenvolvidas para resolver esta questão, por exemplo:

• Gramáticas estendidas, aplicadas na descrição de gramáticas de linguagem natural, tais como Inglês e Espanhol.
• Sistemas-Q, também aplicados na área de processamento da linguagem natural.
• A série de linguagens CDL, usadas na construção de compiladores para linguagens de programação.

Aplicações além de ALGOL 68

Anthony Fisher escreveu um analisador sintático para uma vasta classes de gramáticas-W [2].

Dick Grune criou um programa em linguagem C que poderia gerar todas as possíveis produções de uma gramática de dois níveis [3].

Gramáticas-W também foram propostas para utilização na descrição de ações humanas complexas em ergonomia.

Ver também

• Gramática de Atributos

Ligações externas

• Uso noAlgol68
• Tutorial introdutório por Steven Pemberton.