Van-Wijngaarden-Grammatik
Eine Van-Wijngaarden-Grammatik (auch: vW-Grammatik oder W-Grammatik) ist eine Zweistufengrammatik aus der Compilerprogrammierung, eine Art von formaler Grammatik, die es möglich macht, mit einer endlichen Menge von Regeln potentiell unendliche Grammatiken zu definieren.
Anwendung bei ALGOL 68
Adriaan van Wijngaarden erfand diese Technik und benutzte sie bei der Definition der Programmiersprache Algol 68, um einige syntaktische Forderungen streng definieren zu können, die man bis dahin in natürlicher Sprache hatte formulieren müssen – z. B. dass Bezeichner in ihrem Geltungsbereich nicht mehrfach deklariert sind und dass der Gebrauch der Bezeichner mit ihrer Deklaration übereinstimmt.
Eine Van-Wijngaarden-Grammatik besteht aus einer endlichen Menge von Metaregeln, die dazu verwendet werden, aus einer endlichen Menge von Hyperregeln beliebig viele Produktionsregeln abzuleiten. Hyperregeln beschränken die zulässigen Kontexte auf der oberen Stufe. Wie Alain Colmerauer feststellte, ist die konsistente Substitution, die im Ableitungsprozess verwendet wird, im Wesentlichen äquivalent zur Unifikation, wie sie in Prolog stattfindet.
Andere Anwendungen
Es wurde festgestellt, dass Zweistufengrammatiken auch außerhalb ihres ursprünglichen Anwendungsfeldes von Nutzen sein können.
Anthony Fisher versuchte, einen Parser für allgemeine W-Grammatiken zu konstruieren.[1]
Es ist vorgeschlagen worden, die Methode in der Ergonomie zur Beschreibung komplexer menschlicher Handlungen zu verwenden.
Vom Security-Experten Eric Filiol wurde in einer formalen Definition von metamorphen Computerviren ein Vergleich zur Zweistufengrammatik und Van-Wijngaarden-Grammatik hergestellt.[2]
Quellenangaben
- Homepage von Anthony Fisher
- Eric Filiol: Metamorphism, Formal Grammars and Undecidable Code Mutation. In: International Journal of Computer Science 2, 2007, 1, ISSN 1306-4428, S. 70–75.