These elementary pieces are specially designed to satisfy two useful properties: First, each elementary piece can be stored using an amount of space that does not depend on the length of w. Second, elementary pieces can be shared among different derivations of w under G. The algorithm then uses dynamic programming to construct and store in a multidimensional parsing table all possible elementary pieces pertaining to the derivations of w under G. From such a table one can directly check whether w ∈ L(G).
despite the fact that the number of derivations of w under G can grow exponentially with the length of w, the two properties of elementary pieces allow the algorithm to run in time polynomial in the length of w. the runtime is not bounded by a polynomial function in the size of G, as should be expected from the hardness results reported in Section 3.1.