Say I have an LR grammar G and a string w. I know that I can check if w is in the language of G in linear time. But what if w itself is not in the language of G, but I want to find all substrings of w that are in the language of G? And can I get parse trees for those substrings? What would be the time complexity for these things?
migrated from stackoverflow.com Sep 12 '12 at 12:09
This question came from our site for professional and enthusiast programmers.
You can do this in $O(n^2)$ time using an advanced version of Earley. See this answer for this advanced version.
This algorithm can parse any $LR(k)$ grammar in linear time. While doing so, it also parses all prefixes of the string (if no lookahead is used - for lookahead you would need to also perform actions that would be performed at end-of-string tokens) and puts 'I am finished' items in item sets whose index corresponds to an index in the string at which a prefix was recognized to be in the language.
We can therefore start this algorithm at every position in the string, parsing the remainder of the string, for a total running time of $O(n^2)$. As we can have $O(n^2)$ matches, this is in a sense optimal.
You could also change the algorithm and run it once: you can insert an 'I've started here' item at every index, and then parse the string running the Early version only once. This may be faster in practice, but I'm not sure what its running time would be.
Note that recovering a parse forest from an Earley parse is not the simplest thing in parsing. The above algorithm probably needs augmenting if you also want all the parses of the substrings (rather than just what substrings match). Note that on grammars that are not $LR(\pi)$ for some regular partition $\pi$ (which includes all $LR(k)$ languages), the above algorithm may not run in quadratic time.