Complexity of a GLR parser on an ambiguous grammar

Question

Let's consider the following expression grammar that is ambiguous:

$E ::= E + E~|~a$

Although GLR parsing (recognition actually, I'm not interested in parse tree creation) is worst case $O(n^3)$, but how does a GLR parser behaves on this grammar that is not worst-case?

I suspect the complexity is $O(n^2)$ or close to it. Can anyone reason about the complexity of this grammar in a generalized setting like GLR that explores all the paths?

Answer 1

This example grammar is worst case ambiguity, unless I do not understand what you mean by worst case ambiguity. Why do you think it should not be? Try to analyse $a+a+a+a+a$.

It's time complexity is $O(n^3)$ with any general CF parser, such as CKY, Earley, GLR, GLL, etc. However, you need only $O(n^2)$ space if you do not keep parse-tree information (though I would have to check how you manage not to keep it in GLR ... it may require minor modification).

But then, if you are not interested in parse-trees, but only in recognition, you should forget ambiguities, and just change it for a regular grammar that recognizes the same language, in linear time.

Reasonning with GLR is a bit of a pain. But you can do it easily enough with CKY. There is no essential difference in principle (see the second part of my answer to a previous question), but reasonning with the more complex construction of GLR is more obfuscated.

Alternatively, take the code of a GLR parser, and add counters in proper places. Then run a few example and you will see that it checks with $O(n^3)$. The last reference of the question I answered actually did that (though I do not recall which general CF parser flavors they tried).

Answering comments, and sketching a proof:

Regarding worst case grammar, you suggest $S \rightarrow SSS \mid SS \mid a$ given in a paper by Mark Johnson. I do not have the paper handy, but my guess is that he uses the $S \rightarrow SSS$ rule to show that the complexity will $O(n^4)$ unless specific steps are taken to binarize this rule (there are actually 2 ways to do it). The reason is that the polynomial complexity exponent can be the length of the longest right hand side (RHS), at least in non terminals. So he deliberately uses a RHS with 3 non-terminals. Your example grammar does not have that problem, and in that sense you can indeed consider that it is not as bad. Johnson's example would be even worse with a RHS of length 4, or more.

I questioned your "not a worst case" statement because, it is easy to bring time complexity down to $O(n^3)$ by binarization of right-hand sides, which is straightforward and changes the trees only in an obvious and very readable way. However, in the current state of the art, you cannot go below $O(n^3)$, unless you use very complex recognition techniques that do not give you parse trees and are based on a reduction to matrix multiplication as shown by Leslie Valiant in 1974. Since then, the theoretical complexity of these multiplication algorithms has gone down fron the $O(n^{2.807})$ of Strassen algorithm to $O(n^{2.373})$ of Williams algorithm, though those faster than Strassen are unusable in practice. It is not known (afaik) whether this bound can be brought down further. These bounds can certainly apply to your grammar, as well as they do to all others, but I would not call it "parsing".

Going back to the more classical parsing algorithms, I guess one can give a common proof based on the following remark: all classical parsing algorithms are based on the (non-deterministic) pushdown automaton (PDA) model (it is not always very visible, but it is always there). The deterministic algorithms, like precedence, LR(k) or LL(k) and their variants are just deterministic PDAs built in some systematic way (when possible), that correspond to a technique using the grammar to walk the (unique) parse-tree as efficiently as possible. These techniques are limited to subclasses of CF grammars and languages.

The general context-free parsing algorithms can handle all CF grammars and languages. They are usually built using the very same techniques, but the consruction accepts that there may be conflicts in the the steps to be applied. These conflicts are simply non-deterministic choices. But the construction is basically the same as in the deterministic case. That means that the resulting non-deterministic PDA can walk all possible parse-trees, sometimes having to walk parse-tree fragments that do not belong to a full parse-tree (for example in unambiguous CF languages that are not deterministic).

So these algorithms walk all parse-trees, independently of whether they actually produce these parse-trees as output. There may be exponentially many (even sometimes infinitely many) such parse trees. The General CF parsers use a tabular (dynamic programming / memoization) technique to share computation, in order to do the work a bit faster. They all use the same tabular technique (from an abstract point of view) and get all the same worst case complexity $O(n^3)$. They may however differ on some example, for example if a grammar falls in the domain wherhe one PDA construction gives a dterministic PDA, while another does not. But they all have $O(n^3)$ time complexity when there are exponentially many parse trees as in your example.

I do not believe I ever encountered a parsing algorithm that does not fall in this schematic description (up to some bells and whistles). This is essentially the basis of the work in the Billot & Lang paper cited above.

Now, as I said, if you are not interested in parse-tree, you can always modify one of these algorithms to do better in some cases. For example, as I said, the rules $S \rightarrow SS \mid a$ could be noticed by the recognizer (no longer parser) construction technique, and replaced by the simpler rules $S \rightarrow aS \mid a$. But then it is no longer the same "parsing" algorithm.

For an analysis of tree sharing into forests and the effect on parsing complexity, you may want to read "Observations on Context Free Parsing" by Beau Sheil In Statistical Methods in Linguistics, 1976:71-109. The point is that all general CF parsing algorithms walk this shared forest completely. And it has size $O(n^3)$ for your example grammar.