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?

  • $\begingroup$ Do you mean all prefixes or truly all substrings? $\endgroup$ – reinierpost Sep 12 '12 at 12:18
  • $\begingroup$ Of course you can: the trivial algorithm just tries to parse all $\frac{n(n-1)}{2}$ substrings. So I guess you want to do it faster, and that's interesting. Maybe one can empower one of the (fast) string matching algorithms with the LR automaton? $\endgroup$ – Raphael Sep 12 '12 at 21:56

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy