On the Complexity of LR(k) Testing

Abstract

In this paper we derive upper bounds on the complexity of LR(k) testing both when k is considered to be a fixed integer and also when k is considered to be a parameter of the problem. In the latter case, we show that the lower bounds on the running time of such algorithms depend very strongly on the representation chosen for k. Thus LR(k) testing is NP-complete when k is expressed in unary and complete for nondeterministic exponential time when k is expressed in binary.These results carry over to many other parameterized classes of grammars, such as the LL(k), strong LL(k), SLR(k), LC(k), strong LC(k), BRC(l,k), BC(l,k) and extended precedence (l,k) grammars.