Complexity of a GLR parser on an ambiguous grammar 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?
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 &amp; 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.