Towards a programming language based on the notion of two-level grammar

AbstractThis paper deals with the problem of computing relations from their abstract non-algorithmic specifications. The formalism under consideration is that of two-level grammars, introduced originally for defining languages. In this formalism the intuitions behind the formal definition can be directly expressed by the grammatical rules, which may have a form close to the statements of natural language. A notion of the relation specified by a two-level grammar is introduced and computability of such relations is discussed. For a class of two-level grammars, called the transparent grammars, an algorithm is outlined for computing the relations specified by the grammars of this class. The transparent grammars turn out to be a generalization of the formalism of Horn clauses, and the algorithm is based on unification. The language generated by a two-level grammar can be used as an additional tool for controlling computations. A transparent two-level grammar can be considered as a non-algorithmic program specifying an input/output relation. The computational algorithm defines an operational semantics of such programs