A worst case of circularity test algorithms for attribute grammars
Abstract
References
Index Terms
- A worst case of circularity test algorithms for attribute grammars
Recommendations
On exponential-time completeness of the circularity problem for attribute grammars
Attribute grammars (AGs) are a formal technique for defining semantics of programming languages. Existing complexity proofs on the circularity problem of AGs are based on automata theory, such as writing pushdown acceptor and alternating Turing ...
The intrinsically exponential complexity of the circularity problem for attribute grammars
Attribute grammars are an extension of context-free grammars devised by Knuth as a mechanism for including the semantics of a context-free language with the syntax of the language. The circularity problem for a grammar is to determine whether the ...
On the complexity of the circularity test for attribute grammars
POPL '75: Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languagesIt is shown that both the upper and the lower bounds on the time complexity of the circularity test for Knuth's attribute grammars are exponential functions of the size of the grammar description. This result implies the "intractability" of the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Check for updates
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 302Total Downloads
- Downloads (Last 12 months)57
- Downloads (Last 6 weeks)13
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in