Van-Wijngaarden-Grammatik

aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 1. Dezember 2020 um 07:32 Uhr durch imported>Wegner8(113297) (Verhalten zur Chomsky-Hierarchie?).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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

  1. Homepage von Anthony Fisher
  2. Eric Filiol: Metamorphism, Formal Grammars and Undecidable Code Mutation. In: International Journal of Computer Science 2, 2007, 1, ISSN 1306-4428, S. 70–75.

Weblinks