# 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 Revisado de 1973, §2.2.1, §10.1.1
## 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 . 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 .
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 .
Gramáticas-W também foram propostas para utilização na descrição de ações humanas complexas em ergonomia.