Generalized Context-Free Grammars
Leiden University, Leiden, The Netherlands, (1996)Abstract
We consider several language generating formalisms from the literature,
such as string-valued attribute grammars with only s-attributes,
parallel multiple context-free grammars, relational grammars and
top-down tree-to-string transducers, of which we have chosen the
OnlyS string-valued attribute grammars to be our vantage point. We
prove that OnlyS string-valued attribute grammars, parallel multiple
context-free grammars and relational grammars generate the same class
of languages, and we prove that every language accepted by an OnlyS
string-valued attribute grammar is the image of a top-down tree-to-string
transducer. The main result of this thesis is the proof of equivalence
of the special string-valued attribute grammars, the multiple context-free
grammar, the special relational grammar and the finite copying top-down
tree-to-string transducer. In order to prove these equivalences,
definitions of some of these formalisms have been slightly modified,
and normal forms have been (re)defined and proven
Description
Attribute Grammar