# Why can't we use memoization to parse unambiguous context-free grammars in linear time?

This is a follow-up question to Why is it hard to parse unambiguous context-free grammar in linear time?

I know that Parsing Expression Grammars (PEG) can be parsed in linear time using a packrat parser. Those parser use memoization to accomplish the linear time complexity: basically each non-terminal can be "expanded" at most once at each input position (the result of said expansion being memoized). Since the number of non-terminals is a constant factor in the size of the input, this accounts for the linear time complexity.

Supposedly (according to wikipedia at least), packrat parsers are able to parse many unambiguous context-free grammars.

My question is then: why can't we apply the same memoization principle to parse unambiguous context-free grammars in linear time ? I.e. what are the differentiating factors between PEG and unambiguous CFG that make minimization possible for all PEGs but not for all the CFGs ?

As secondary question: is there a way to easily translate a subset of unambiguous CFG to PEG ?

Also, in this answer, the language of palindromes over alphabet {a, b} is given as example of language for which there is no unambiguous CFG that can be parsed in linear time. Is there a PEG that recognizes this language ? The naive translation won't work due to ordered choice (if one of the alternatives matches, the other alternatives are not attempted, even tough using them might allow for a successful parse of the input). This mailing list entry says it is possible with syntactic predicates, but I don't see how.

-

A memoizing parser for PEGs works in linear time because of two facts:

1. The number of recursive calls that we may need to memoize the result of is linear because it is the product of the input size and the number of nonterminals in the grammar (which for this purpose is considered to be fixed).

2. The result we need to memoize for each call has constant size -- it is just the length of the match for the specified nonterminal that starts at the specified position, if there is any. A PEG match is always unambiguous if it exists at all.

If we try to apply the same principle to general context-free grammars, the second of these properties fails. It is possible for the same nonterminal to match many different substrings that all start at the same point in the string. Potentially, every substring starting at a particular point will match, and each caller will then have to consider all these possibilities. That blows up the running time by a factor of $O(n)$.

-

If we apply dynamic programming to CFGs, we get the CYK algorithm or the Earley algorithm, neither of which have yielded us a linear time algorithm for all unambiguous CFGs.

So, rather than asking 'why can't we use memoization', maybe you should wonder 'how does unambiguity help us if we use memoization?'. Just knowing that any input yields at most one parse tree hardly restricts how complicated the grammar might be, as testified by its undecidability.

What seems a much more reachable target for a linear time algorithm is the class of $NLR(k)$ grammars (see here for a survey on noncanonical parsing methods, which also covers $NLR(k)$). It is undecidable whether a grammar is $NLR(k)$, even for fixed $k$, using essentially the same proof that unambiguity is undecidable. However, it seems a better target, as LR techniques are applicable to an extent: I've already devised an algorithm for these types of grammars - for some grammars, the parse table can be infinitely large, which makes it somewhat unpractical - which parses any such grammar in $O(n)$ time if the table is given, and $O(n^2 f(G))$ time if it computes the table on the fly.

On a side note, the grammar of even palindromes is quite easily parseable in linear time, just not by any commonly employed algorithms - you need an ad-hoc algorithm for it. In fact, this has been the case for any unambiguous grammar thought up so far: ad-hoc linear time algorithms are always available, but a general method is elusive.

-
Interesting. What has always annoyed me when working with grammars tough is that when using restricted classes, it's pretty hard to see if a grammar belongs to that class, or to make up a grammar for your language that falls directly in the class. –  Norswap Jul 15 '12 at 10:37

Also, in this answer, the language of palindromes over alphabet {a, b} is given as example of language for which there is no unambiguous CFG that can be parsed in linear time. Is there a PEG that recognizes this language ? The naive translation won't work due to ordered choice (if one of the alternatives matches, the other alternatives are not attempted, even tough using them might allow for a successful parse of the input). This mailing list entry says it is possible with syntactic predicates, but I don't see how.

This CFG grammar

$$\begin{array}{rl}S ::= & a S a \\ | & b S b \\ | & b b \\ | & a a \end{array}$$

turns out to also be a valid PEG recognizing the same language. The key is to see that in the correct parse, all rules have their begin in the first half of the input. Consider the example input abbaabba: S is matched four times, at positions 0, 1, 2 and 3.

While parsing, it will also match S at position 4 and 5, but it is irrelevant. Matching S at position 4 will make the first alternative for S at position 3 fail, hence the second alternative will be taken, yielding the correct parse.

So matches of S in the second half of the input don't matter, and incorrect matches will only ever happen there.

Things get slightly more tricky if we consider this grammar:

$$\begin{array}{rl}S ::= & a S a \\ | & b S b \\ | & \epsilon \end{array}$$

It can however be converted to this PEG:

$$\begin{array}{rl}S ::= & a X a \\ | & b X b \\ | & \epsilon \end{array}$$ $$\begin{array}{rl}X ::= & a X a \;\&\,. \\ | & b X b \;\&\,. \\ | & \;\&\,. \end{array}$$

The point of the & . in the second rule being to avoid matching S to abba at index 4 instead of matching it to epsilon.

This should normally be applicable to all inputs, let me know if I have made a mistake!

-