Two-level Grammar as a Functional Programming Language
Balanjaninath Edupuganty · The Computer Journal · 1989
A two-level grammar consists of two context-free grammars interacting in a manner such that their combined computing power is equivalent to that of a Turing Machine. We show that two-level grammar can be used as a functional programming where the two-level grammar notation is the syntax of the language. Two-level grammar programs as represented are actually high-level descriptions of recursive functions, with one level of the grammar specifying the function domains and the second level defining the function evaluation rules. A general algorithm to interpret two-level grammars is given to make two-level grammar programs executable. The primary advantages of two-level grammar over other functional programming languages are (1) the capability for data and procedural abstraction provided by the different levels of the grammar and (2) the structured form of natural language which is used as the two-level grammar syntax, making two-level grammar programs very readable.