Gramáticas de Van Wijngaarden

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.

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".

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

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.

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.

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^[1]. 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.

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.

• Gramática de Atributos