Zweistufengrammatik

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 Anwedungsfeldes 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

1. ↑ Homepage von Anthony Fisher
2. ↑ Filiol, Eric: Metamorphism, Formal Grammars and Undecidable Code Mutation. 2007.

Weblinks

• Anwendung der vW-Grammatik in ALGOL 68