Open AccessOn Defining Semantics by Means of Extended Attribute Grammars
Author(s) -
Ole Lehrmann Madsen
Publication year - 1983
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v12i109.6524
Subject(s) - l attributed grammar , computer science , tree adjoining grammar , parse tree , parsing , context sensitive grammar , attribute grammar , programming language , denotational semantics , operational semantics , rule based machine translation , indexed grammar , s attributed grammar , combinatory categorial grammar , natural language processing , theoretical computer science , semantics (computer science) , context free grammar
The possibilities for defining predicate transformers, denotational semantics, and operational semantics by means of extended attribute grammars are treated. The approach to operational semantics consists of a set of attribute grammar rules that specifies the possible transformations upon a given program. A proposal for defining the domains of an attribute grammar within the formalism is given. It is also shown how an attribute grammar may be reformulated as a tree rewriting system. Finally an efficient evaluator that works for all attribute grammars (including some circular ones) is described. This evaluator constructs during a left-to-right scan of a linear representation of the parse tree (a right-parse) a directed (acyclic) graph that represents the values of the attributes at the root of the parse tree. The parse tree itself need not be constructed. During a (recursive) scan of this graph the attribute values may be evaluated.