The Complexity of Languages Generated by Attribute Grammars
Joost Engelfriet · SIAM Journal on Computing · 1986
A string-valued attribute grammar (SAG) has a semantic domain of strings over some alphabet, with concatenation as basic operation. It is shown that the output language (i.e., the range of the translation) of a SAG is log-space reducible to a context-free language.