Semantics of context-free languages

DE Knuth - Mathematical systems theory, 1968 - Springer
DE Knuth
Mathematical systems theory, 1968Springer
Abstract “Meaning” may be assigned to a string in a context-free language by defining
“attributes” of the symbols in a derivation tree for that string. The attributes can be defined by
functions associated with each production in the grammar. This paper examines the
implications of this process when some of the attributes are “synthesized”, ie, defined solely
in terms of attributes of the descendants of the corresponding nonterminal symbol, while
other attributes are “inherited”, ie, defined in terms of attributes of the ancestors of the …
Abstract
“Meaning” may be assigned to a string in a context-free language by defining “attributes” of the symbols in a derivation tree for that string. The attributes can be defined by functions associated with each production in the grammar. This paper examines the implications of this process when some of the attributes are “synthesized”, i.e., defined solely in terms of attributes of thedescendants of the corresponding nonterminal symbol, while other attributes are “inherited”, i.e., defined in terms of attributes of theancestors of the nonterminal symbol. An algorithm is given which detects when such semantic rules could possibly lead to circular definition of some attributes. An example is given of a simple programming language defined with both inherited and synthesized attributes, and the method of definition is compared to other techniques for formal specification of semantics which have appeared in the literature.
Springer