A complexity theory of grammar problems

ABSTRACT

The close relationship between programming language syntax, context-free grammars (abbreviated cfgs), parsing, and compiling is well-known and is extensively discussed in [1]. Unfortunately, many of the problems about programming languages, one might wish to solve, are equivalent to undecidable grammar problems. Two especially important such problems are (1) the emptiness of intersection problem, i.e. determining if the intersection of the languages generated by a pair of grammars is empty, and (2) the grammar class membership problem, i.e. determining for a fixed class of grammars r and a grammar G, if G is an element of T.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 2: K. Culik, II and R. Cohen, LR-regular grammars&emdash; an extension of LR(k) grammars, JCSS 7, 1(1973), 66-96.
• 3: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 4: H.B. Hunt, III and T.G. Szymanski, Complexity metatheorems for context-free grammar problems, Princeton University Computer Science Technical Report 187, July 1975 (also submitted for publication).
• 5: J. Hartmanis , J. E. Hopcroft, An Overview of the Theory of Computational Complexity, Journal of the ACM (JACM), v.18 n.3, p.444-475, July 1971 [doi>10.1145/321650.321661]
• 6: K. Culik, II and R. Cohen, LR-regular grammars—an extension of LR(k) grammars, JCSS 7, 1 (1973), 66-96.
• 7: Thomas Gregory Szymanski, Generalized bottom-up parsing., 1973
• 8: W.F. Ogden, unpublished note, December 1974.
• 9: Robert McNaughton , Seymour A. Papert, Counter-Free Automata (M.I.T. research monograph no. 65), The MIT Press, 1971
• 10: A.J. Korenjak and J.E. Hopcroft, Simple deterministic languages, IEEE Conference Record of 7th Annual Symposium on Switching and Automata Theory October 1966, 36-46.
• 11: M.A. Harrison and I.M. Havel, Strict deterministic grammars, JCSS 7, 3(1973), 237-277.
• 12: H.B. Hunt, III and J.L. Rangel, Decidability of equivalence, containment, intersection, and separability of context-free languages, Center for Research in Computing Technology TR 19-75, Harvard University, Cambridge, Massachusetts, October 1975.
• 13: D.E. Knuth, A characterization of parenthesis languages, Inf. and Control, 11(1967), 269-289.
• 14: H.B. Hunt, III, T.G. Szymanski, and J.D. Ullman, Operations on sparse relations and efficient algorithms for grammar problems, Proc. 15th Annual IEEE Symp. on Switching and Automata Theory, October 1974, 127-132.
• 15: Harry B. Hunt, III , Thomas G. Szymanski , Jeffrey D. Ullman, On the complexity of LR(k) testing, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.130-136, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512990]
• 16: B.M. Brosgol, Deterministic translation grammars, Ph.D. thesis, Harvard University, Cambridge, Massachusetts, 1974.
• 17: Charles Nicholas Fischer, On parsing context free languages in parallel environments., 1975
• 18: T.G. Szymanski and J.H. Williams, Non-canonical extensions of bottomup parsing techniques, to appear in SIAM Journal on Computing.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Algorithms, Languages, Theory