On Generalization of Attribute Grammars
Yutaka Kikuchi, Takuya Katayama · Systems and Computers in Japan · 1996
Abstract An attribute grammar is a formal system consisting of a context‐free grammar together with semantic rules, which enables us to describe not only the syntax but also the semantics of language. The limited framework of attribute grammar, however, is not conducive to expansion of the system and the many ambiguous definitions of attribute grammar make it difficult to examine its formal nature. We propose a generalized attribute grammar based on the following two grammatical viewpoints: the use of type‐0 grammars in place of the basic, context‐free grammars. relaxation of the restrictions of semantic rules. The generalization is a formal system that allows us to define computation derived from the attribute grammars. We can also use the generalization as a framework for discussing abstract characteristics of the attribute grammars. This paper provides a formal definition and classification of general attribute grammars. We define the semantics of general attribute grammars by using semantic functions whose inputs are structures derived from the underlying grammar and whose outputs are attributed structures. We provide classifications of general attribute grammars based on the abstract properties of semantic functions. We regard general attribute grammars as constraint satisfaction systems. Traditional attribute grammars are restricted in that underlying grammars are context free and semantic rules are solved by unidirectional local propagation.