On the complexity of the circularity test for attribute grammars

ABSTRACT

It 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 circularity test in the sense that the implementation of a general algorithm is not feasible. Another significance of this result is that this is one of the first problems actually arising in practice which has been proven to be of exponential time complexity.

REFERENCES

• 1: D. E. Knuth, Semantics of context free languages, Math. Syst. Th., 2, 127 (1968)
• 2: D. E. Knuth, Correction to {1}, Math. Syst. Th., 5, 95 (1971)
• 3: W. T. Wilner, Declarative semantic definition, Report STAN-CS-233-71, Computer Science Department, Stanford University, 1971
• 4: T. A. Dreisbach, A declarative semantic definition of PL360, UCLA-ENG-7289, Computer Languages Group, Computer Science Department, UCLA, 1972
• 5: A. V. Aho and J. D. Ullman, Translations on a context free grammar, Information and Control, 19,5 (December, 1971)
• 6: P. M. Lewis, II , R. E. Stearns, Syntax-Directed Transduction, Journal of the ACM (JACM), v.15 n.3, p.465-488, July 1968 [doi>10.1145/321466.321477]
• 7: P. M. Lewis , D. J. Rosenkrantz , R. E. Stearns, Attributed translations(Extended Abstract), Proceedings of the fifth annual ACM symposium on Theory of computing, p.160-171, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804047]
• 8: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 9: M. Jazayeri, W. F. Ogden, and W. C. Rounds, On the Complexity of the Circularity Test for Attribute Grammars, Jennings Computing Center Report No. 1148, Case Western Reserve University, Cleveland, Ohio, 1974
• 10: R. M. Karp, Reducibility Among Combinatorial Problems, in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (eds.), Plenum Press, New York 1972
• 11: G. Mager, Writing pushdown acceptors, J. Comp. Syst. Sci. 3, 3(1969)
• 12: Stephen A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal of the ACM (JACM), v.18 n.1, p.4-18, Jan. 1971 [doi>10.1145/321623.321625]
• 13: G. V. Bochmann, Semantics evaluated from left to right, publication No. 135, Départment d'informatique, Université de Montréal, June 1973
• 14: Mehdi Jazayeri, On attribute grammars and the semantic specification of programming languages., 1975