On the Complexity of LR(k) Testing

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(n(k+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.

CACM December, 1975

Hunt, H. B. III
Szymanski, T. G.
Ullman, J. D.

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

4.12 5.23 5.25

CA751205 JB January 5, 1978  4:28 PM

2702	5	2702
2702	5	2702
2702	5	2702