You might want to look into Earley's algorithm or the CYK algorithm, which are two algorithms for deciding whether a string is generated by a context-free grammar. Earley's algorithm runs in time O(n3) for any string of length n regardless of the production rules in the grammar (though the constant term in the big-O notation depends on the grammar), while the CYK algorithm requires that the grammar first be converted to Chomsky normal form to guarantee O(n3) runtime.
Hope this helps!