The Complexity of Languages Generated by Attribute Grammars

DOI10.1137/0215005zbMath0589.68055OpenAlexW2134731270MaRDI QIDQ3718173

Joost Engelfriet

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215005

zbMATH Keywords

context-free languagealternationcompilerssemantic domainresource-bounded automatastring-valued attribute grammar

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (9)

Pattern selector grammars and several parsing algorithms in the context- free style ⋮ Complexity characterizations of attribute grammar languages ⋮ On attribute grammars without attribute synthesis ⋮ Independent parallelism in finite copying parallel rewriting systems ⋮ Properties that characterize LOGCFL ⋮ Relating attribute grammars and lexical-functional grammars ⋮ Context-free hypergraph grammars have the same term-generating power as attribute grammars ⋮ Storage products and linear control of derivations ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity

This page was built for publication: The Complexity of Languages Generated by Attribute Grammars