The intrinsically exponential complexity of the circularity problem for attribute grammars

ABSTRACT

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 semantics for all possible sentences (programs) in fact will be well defined. It is proved that this problem is, in general, computationally intractable. Specifically, it is shown that any deterministic algorithm which solves the problem must for infinitely many cases use an exponential amount of time. An improved version of Knuth's circularity testing algorithm is also given, which actually solves the problem within exponential time.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 3: Aho, A.V., and Ullman, J.D. Translations on a context-free grammar. Inform. Contr. 19, 5 (Dec. 1971), 439-475.
• 4: Gregor V. Bochmann, Semantic evaluation from left to right, Communications of the ACM, v.19 n.2, p.55-62, Feb. 1976 [doi>10.1145/359997.359999]
• 5: 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]
• 6: Dreisbach, T.W. A declarative semantic definition of PL360. UCLA-ENG-7289, Computer Languages Group, Computer Sci. Dep., UCLA, 1972.
• 7: Susan L. Gerhart, Correctness-preserving program transformations, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.54-66, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512983]
• 8: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 9: Mehdi Jazayeri, On attribute grammars and the semantic specification of programming languages., 1975
• 10: Knuth, D.E. Examples of formal semantics. Symposium on Semantics of Algorithmic Languages, Lecture Notes in Mathematics, Vol. 188, Springer-Verlag, New York, 1971.
• 11: Knuth, D.E. Semantics of context free languages. Math. Syst. Th. 2 (1968), pp. 127-145; correction to article in Math. Syst. Th. 5 (1971), p. 95.
• 12: 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]
• 13: Mager, G. Writing pushdown acceptors. J. Comp. Syst. Sci. 3 (1969), 276-318.
• 14: A. R. Meyer, WEAK MONADIC SECOND ORDER THEORY OF SUCCESSOR IS NOT ELEMENTARY-RECURSIVE, Massachusetts Institute of Technology, Cambridge, MA, 1973
• 15: D. Neel , M. Amirchahy, Semantic attributes and improvement of generated code, Proceedings of the 1974 annual conference, p.1-10, January 1974 [doi>10.1145/800182.810373]
• 16: Petrick, S.R. Semantic interpretation in the REQUEST system. IBM Res. Rep. RC 4457, July, 1973.
• 17: Wilner, W.T. Declarative semantic definition. Rep. STAN- CS-233-71, Computer Sci. Dep., Stanford U., 1971.
• 18: Wilner, W.T. Formal semantic definition using synthesized and inherited attributes. In Formal Semantics of Programming Languages, Courant Computer Science Symposium 2, R. Rustin (Ed.), Prentice-Hall, Englewood Cliffs, N.J., 1972.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Languages, Reliability

Keywords:
attribute grammars, circularity problem, computational complexity, context-free grammars, exponential time, semantics