On the complexity of LL(k) testing

摘要

The problem of testing whether or not a context-free grammar possesses the LL(k) property is studied. For each fixed integer k ⩾ 0, the problem is shown to be solvable in nondeterministic time 0(n), and simultaneously in deterministic space 0(n) and in deterministic time 0(nk+1), where n is the size of the grammar in question. These upper bounds represent an improvement by a factor of n upon those obtained by the linear time-bounded reduction of LL(k) testing to LR(k) testing. The results are an implication of a new method for constructing canonical LL(k) parsers, which can be regarded as a dual of Knuth's method for constructing canonical LR(k) parsers. This parser construction method also implies a new subclass of LL(k) grammars, called LALL(k) grammars, which constitute a dual class of the LALR(k) grammars. The problem of testing whether or not a grammar is LALL(k) is shown to be PSPACE-complete for each fixed k ⩾ 2.