On the complexity of LR(k) testing

ABSTRACT

The problem of determining whether an arbitrary context-free grammar is a member of some easily parsed subclass of grammars such as the LR(k) grammars is considered. The time complexity of this problem is analyzed both when k is considered to be a fixed integer and when k is considered to be a parameter of the test. In the first case, it is shown that for every k there exists an O(nk+2) algorithm for testing the LR(k) property, where n is the size of the grammar in question. On the other hand, if both k and the subject grammar are problem parameters, then the complexity of the problem depends very strongly on the representation chosen for k. More specifically, it is shown that this problem is NP-complete when k is expressed in unary. When k is expressed in binary the problem is complete for nondeterministic exponential time. These results carry over to many other parameterized classes of grammars, such as the LL(k), strong LL(k), SLR(k), LC(k), and strong LC(k) grammars.

REFERENCES

• 1: Hunt, H.B. III, Szymanski, T.G. and Ullman, J.D. Operations on sparse relations and efficient algorithms for grammar problems. IEEE Conf. Rec., 15th Ann. Syrup. on Switching and Automata Theory, 1974, pp. 127-132.
• 2: Hartmanis, J. Context-free languages and Turing machine computations. Proc. Syrup. Appl. Math. Vol. 19, Amer. Math. Soc., Providence R.I., 1967, pp. 45-51.
• 3: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 4: Knuth, D.E. On the translation of languages from left to right, lnfo. Contr., 8, 6 (1965), 607-639.
• 5: Korenjak, A.J., and Hopcroft. J.E. Simple deterministic languages. IEEE Conf. Rec., 7th Ann. Syrup. on Switching and Automata Theory, 1966, pp. 36-46.
• 6: Brosgol, B.M. Deterministic translation grammars. TR-3- 74, Center for Research in Computing Technology, Harvard U., 1974 (also Proc. 8th Ann. Princeton Conf. on Inform. Sci. and Systems, 1974, pp. 300-306.
• 7: Younger, D. H. Recognition and parsing of context-free languages in time n 3. Inform. Contr., 10, 2 (1967), 189-208.
• 8: Rosenkrantz, D.J. and Lewis P.M. II Deterministic left corner parsing. IEEE Conf. Rec., llth Ann. Symp. on Switching and Automata Theory, 1970, pp. 139-152.
• 9: Johnson, D.B. and Sethi, R. Efficient construction of LL(1) Parsers. TR-164, Dep. of Computer Sci., Penn State U., State College, Pa., March 1975.

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.4 Processors
          Subjects: Parsing

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing

General Terms:
Languages, Performance, Reliability

Keywords:
LR(k) grammars, NP-complete problems, computational complexity, context-free grammars, parsing