Was (wer) ist LR1 grammar - definition

In computer science, Van Wijngaarden grammars (also vW-grammars or W-grammars) are a formalism for defining formal languages invented by Adriaan van Wijngaarden for the purpose of defining the ALGOL 68 programming language. The resulting specification remains its most notable application.

W-grammars are two-level grammars: they are defined by a pair of grammars, that operate on different levels:

• the hypergrammar is an attribute grammar, i.e. a set of context-free grammar rules in which the nonterminals may have attributes; and
• the metagrammar is a context-free grammar defining possible values for these attributes.

The set of strings generated by a W-grammar is defined by a two-stage process:

1. within each hyperrule, for each attribute that occurs in it, pick a value for it generated by the metagrammar; the result is a normal context-free grammar rule; do this in every possible way;
2. use the resulting (possibly infinite) context-free grammar to generate strings in the normal way.

The consistent substitution used in the first step is the same as substitution in predicate logic, and actually supports logic programming; it corresponds to unification in Prolog, as noted by Alain Colmerauer.

W-grammars are Turing complete; hence, all decision problems regarding the languages they generate, such as

• whether a W-grammar generates a given string
• whether a W-grammar generates no strings at all

are undecidable.

Curtailed variants, known as affix grammars, were developed, and applied in compiler construction and to the description of natural languages.

Another curtailed version of W-grammars is Prolog, the logic programming language.