Gramatica van Wiingaarden (de asemenea, vB-gramatica sau B-gramatica ) este o gramatică cu două niveluri care oferă o modalitate de a defini gramatici potențial infinite printr-un număr finit de reguli. Formalismul a fost inventat de Adrian van Wiingaarden pentru a defini unele dintre constrângerile sintactice care anterior trebuiau formulate în limbajele naturale, în ciuda naturii lor fundamental sintactice. Aplicațiile tipice sunt manipularea genului și numărului în limbaje naturale și formularea corectă a identificatorilor în limbaje de programare.
Metoda a fost utilizată și dezvoltată în definirea limbajului de programare ALGOL 68 . Acesta este un exemplu de clasă mai largă de gramatici afixate.
O gramatică B constă dintr-un număr finit de metareguli care sunt folosite pentru a deriva reguli de inferență (potențial infinite) dintr-un număr finit de hiperreguli. Definiția metaregulilor este limitată la o gramatică fără context. Hyperrules limitează contextele permise la un nivel superior. În esență, substituția consecventă utilizată în procesul de inferență este echivalentă cu procesul de unificare, de exemplu din limbajul Prolog, așa cum a menționat Alan Colmeroe.
Înainte de limbajul ALGOL 68 , ALGOL 60 a fost oficializat prin formulare Backus-Naur fără context. Apariția unor noi gramatici sensibile la context pe două niveluri a prezentat o dificultate pentru unii cititori ai „Raportului final” despre ALGOL 68 în 1968. Ulterior, raportul final a fost editat de Weingaarden și colegii săi și publicat ca „Raport editat” pe ALGOL 68 în 1973.
Gramaticile B se bazează pe ideea de a completa simbolurile non-terminale ale gramaticilor COP cu atribute (sau afixe ) care transmit informații între nodurile arborelui de analiză și sunt folosite pentru a restricționa sintaxa și a specifica semantica. Această idee era binecunoscută la acea vreme, în special Donald Knuth a vizitat comitetul de dezvoltare ALGOL 68 în timpul dezvoltării propriei sale versiuni. [1] O caracteristică interesantă a gramaticilor B este relația lor strictă cu atributele șirurilor date de o gramatică CF, în care concatenarea este singura operație posibilă. În gramaticile de atribute, atributele pot fi de orice tip și li se poate aplica orice operație.
După ce au fost introduse în raportul Algol 68, gramaticile B au fost considerate prea puternice și nerestricționate pentru utilizare practică. Parțial influențat de modul în care au fost aplicate, raportul editat al lui Algol 68 conținea o gramatică mult mai lizibilă, păstrând în același timp formalismul propriu-zis al gramaticii B.
În acest moment, a devenit clar că gramaticile B erau într-adevăr prea puternice. Sunt Turing-complete, ceea ce face imposibilă deloc analizarea lor: problema verificării dacă un șir dat poate fi generat de o gramatică B dată este de nerezolvat din punct de vedere algoritmic. Utilizarea lor ar trebui să fie strict restricționată pentru utilizarea în analize sau traduceri automate. Au fost dezvoltate versiuni limitate și modificate ale gramaticii B pentru a rezolva această problemă, în special
Anthony Fisher a scris un parser pentru o clasă mare de gramatici B [1] Arhivat la 14 decembrie 2007 la Wayback Machine .
Dick Grune a creat un program C care generează tot felul de reguli de inferență pentru o gramatică cu două niveluri [2] .
Aplicațiile gramaticilor cu afix extins menționate mai sus pot fi considerate aplicații ale gramaticilor B, deoarece gramaticile PA sunt destul de apropiate de ele.
Gramaticile B au fost, de asemenea, propuse pentru utilizare pentru a descrie acțiuni umane complexe în ergonomie.