Van Wijngaarden grammar
A Van Wijngaarden grammar (also: vW grammar or W grammar ) is a two -level grammar from compiler programming , a type of formal grammar that makes it possible to define potentially infinite grammars with a finite set of rules.
Use with ALGOL 68
Adriaan van Wijngaarden invented this technique and used it when defining the programming language Algol 68 in order to be able to strictly define some syntactic requirements that had previously had to be formulated in natural language - e.g. B. that identifiers are not declared more than once in their area of application and that the use of the identifier corresponds to its declaration.
A Van Wijngaarden grammar consists of a finite set of meta rules that are used to derive any number of production rules from a finite set of hyper rules . Hyper-rules restrict the permitted contexts on the upper level. As Alain Colmerauer noted, the consistent substitution used in the derivation process is essentially equivalent to the unification used in Prolog .
Other uses
It has been found that two-level grammars can also be useful outside of their original field of application.
Anthony Fisher tried to construct a parser for general W-grammars.
It has been proposed to use the method in ergonomics to describe complex human actions .
Security expert Eric Filiol made a formal definition of metamorphic computer viruses in comparison to the two-stage grammar and Van Wijngaarden grammar.
References
- ↑ Anthony Fisher's homepage
- ↑ Eric Filiol: Metamorphism, Formal Grammars and Undecidable Code Mutation . In: International Journal of Computer Science 2, 2007, 1, ISSN 1306-4428 , pp. 70-75.