The naive algorithm shares this problem with all other incremental parsing algorithms that maintain connected partial structures.
parsing algorithms based on bottom-up dynamic programming are not applicable because they necessarily compute constituents for substrings that are not prefixes.