<p>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$.</p>

<p>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).</p>

<p>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.</p>

<p>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 <a href="https://cstheory.stackexchange.com/questions/7374#18006">answer to a previous question</a>), but reasonning
with the more complex construction of GLR is more obfuscated.</p>

<p>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 <a href="http://www.aclweb.org/anthology-new/P/P89/P89-1018.pdf" rel="nofollow noreferrer">last reference</a> of the <a href="https://cstheory.stackexchange.com/questions/7374">question I answered</a> actually
did that (though I do not recall which general CF parser flavors they
tried).</p>

<p><strong>Answering comments, and sketching a proof:</strong></p>

<p>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.</p>

<p>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 <a href="http://repository.cmu.edu/cgi/viewcontent.cgi?article=2751&amp;context=compsci" rel="nofollow noreferrer">reduction to matrix multiplication</a> as
shown by Leslie Valiant in 1974.  Since then, the theoretical
<a href="http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra" rel="nofollow noreferrer">complexity of these multiplication algorithms</a> 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".</p>

<p>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.</p>

<p>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).</p>

<p>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.</p>

<p>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 <a href="http://www.aclweb.org/anthology-new/P/P89/P89-1018.pdf" rel="nofollow noreferrer">Billot &amp; Lang paper</a> cited above.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-05-21T00:57:20.013Z
Let me clarify things, so maybe you can give a concrete answer.
The worst case grammars look like something S ::= SSS | SS | a, which were introduced by Mark Johnson in the paper "the complexity of glr parsing" to show the worst case O(n^k).

I don't question the general case, but just this simple grammar.
It may indeed be the worst case, but I need proof, using any 
algorithm is fine. I tried this grammar using a GLL parser and
to me it looks like the number of steps is bounded by O(n^2). However, because of left-recursion termination in GLL is pretty hard for me to analyse it.
Wickoo
CC BY-SA 3.0
2014-05-21T01:02:25.237Z
I suggested GLR because I thought maybe it's easier as left-recursion is encoded in the parse table and search space is not affected by that. 
So I can reformulate this question: can someone theoretically, regardless of any algorithm and using some combinatorial formulas and taking sharing into account tell me what's the upper bound of parsing this grammar?
Can you give me reasons in terms of any particular parsing algorithm.
Wickoo
CC BY-SA 3.0
2014-05-21T10:19:57.077Z
I still don't see a concrete answer or a sketch of proof here. You are just giving general facts that I'm aware of. You are right about S ::= S S S that it is used to show o(n^k), as i already said myself. My point was that that grammar is much more ambiguous compared to E ::= E + E. So, you're saying that any ambiguous grammar triggers worst case complexity? My question os that this example seems simpler that worst case and my experiments also show that. Can someone prove it? Or show that it is not the case.
Wickoo
CC BY-SA 3.0
2014-05-21T11:01:40.303Z
The sketch of a proof is: all general CF algorithms walk the whole
forest, because that is what they are built for. Whatever computation
sharing they do is forest sharing. Shared forest representation is
cubic in general, and always so for exponential ambiguity (which is
your case). Hence all those parsers will be cubic on your grammar
example. As I said, this is only a sketch, on which an actual proof
can be built by checking all the claims. Johnson's example is not much
more ambiguous than your: both are exponential and that is all that
matters. The fact you ignore parse trees is irrelevant.
babou
CC BY-SA 3.0
2014-05-21T11:35:03.173Z
You may be right, but I'm not convinced yet by your argument.
How do you define exponential ambiguity? I suggest you run the grammar to see that in practice it doesn't trigger the worst case, but SSS does.
Wickoo
CC BY-SA 3.0
2014-05-21T11:43:41.313Z
Exponential ambiguity = exponential number of parse trees. What difference do you see with SSS, compared to SS. - - - - - - - - - - - - - - -
One way to get a better bound, while retaining the general approach of
these parsing algorithms, would be to find a more compact shared
representation of parse-forests that can be walked as well to simulate
all parse-tree walks. But even then, this would no longer be one of
the classical general CF algorithms. It would be a very interesting
result, though ... but I doubt there is anything to be found.
babou
CC BY-SA 3.0
2014-05-21T11:52:08.923Z
@Ali I do not have the software (and time) to run examples. but there are some figures in the Billot-Lang paper, though probably not enough to actually show that the parsing is cubic. Look at the appendix C.
babou
CC BY-SA 3.0
2014-05-21T13:17:31.073Z
Thanks! Appendix C shows a similar grammar A ::= AA | x named UBDA. I saw a proof in the original Early paper that that this grammar has O(n^3) bound. I redid my experiments, and for very large inputs, 800 a's, I'll get the cubic growth rate. I guess the reason I concluded that it may not be cubic was that its growth was much smaller than SSS, and I ran the experiments for inputs of size 200 which shows the cubic behaviour for SSS but not for E+E,  but still they are both worst case cubic.
Wickoo
CC BY-SA 3.0
2014-05-21T13:34:15.130Z
@Ali Good you succeeded. How did you do your measurements? If you measure execution time, you always have to be careful with small values as they may hide behind system overhead. On the other hand, large values sometimes trigger garbage collection. There are more formal ways of measuring that avoid these pitfalls, but it is sometimes more work, or delicate to set up accurately.
babou
CC BY-SA 3.0
2014-05-21T17:30:23.687Z
I do it in the pretty standard way of measuring the performance of Java programs. Warm up and then average result with throwing out the outliers. I also take the System time instead of nano time to take GC and other noise out (as much as possible). The problem with E + E was it was reaching the n^3 quite late. I basically was doubling the input and measuring if the time was was 8 times bigger, it was much less than 8. The first time I observed 8 was increasing from 400 a's to 800 a's. For the other grammar it is much easier to observe the cubic behaviour and that misleaded me.
Wickoo
CC BY-SA 3.0
2014-05-21T17:58:53.897Z
@Ali This is a bit strange. Maybe there is heavy initialization cost.
Would you mind sending me the times you got for various values of n,
especially those below the 400. Here or at babou(at)inbox.com
babou
CC BY-SA 3.0
2014-05-21T18:48:16.133Z
Sure, the numbers are on my workstation at work. I will send them to you tomorrow.
Wickoo
CC BY-SA 3.0
2014-05-21T00:26:27.573Z
2014-05-21T10:04:40.087Z
2017-04-13T12:32:28.117Z
babou
<p>Let's consider the following expression grammar that is ambiguous:</p>

<p>$E ::= E + E~|~a$</p>

<p>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?</p>

<p>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?</p>

<complexity-classes><parsing>
Complexity of a GLR parser on an ambiguous grammar
Wickoo
# Complexity of a GLR parser on an ambiguous grammar

(Asked by: username_0 on 2014-05-20)

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?

**Tags:** complexity-classes, parsing


---

## 1 answers

### Answer by username_1 on 2014-05-21. Score: 3 | Accepted answer

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](https://cstheory.stackexchange.com/questions/7374#18006)), 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](http://www.aclweb.org/anthology-new/P/P89/P89-1018.pdf) of the [question I answered](https://cstheory.stackexchange.com/questions/7374) 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](http://repository.cmu.edu/cgi/viewcontent.cgi?article=2751&context=compsci) as
shown by Leslie Valiant in 1974. Since then, the theoretical
[complexity of these multiplication algorithms](http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra) 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](http://www.aclweb.org/anthology-new/P/P89/P89-1018.pdf) 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.

> **Comments:**
> **username_0**: Let me clarify things, so maybe you can give a concrete answer. The worst case grammars look like something S ::= SSS | SS | a, which were introduced by Mark Johnson in the paper "the complexity of glr parsing" to show the worst case O(n^k).  I don't question the general case, but just this simple grammar. It may indeed be the worst case, but I need proof, using any  algorithm is fine. I tried this grammar using a GLL parser and to me it looks like the number of steps is bounded by O(n^2). However, because of left-recursion termination in GLL is pretty hard for me to analyse it.  
> **username_0**: I suggested GLR because I thought maybe it's easier as left-recursion is encoded in the parse table and search space is not affected by that.  So I can reformulate this question: can someone theoretically, regardless of any algorithm and using some combinatorial formulas and taking sharing into account tell me what's the upper bound of parsing this grammar? Can you give me reasons in terms of any particular parsing algorithm.  
> **username_0**: I still don't see a concrete answer or a sketch of proof here. You are just giving general facts that I'm aware of. You are right about S ::= S S S that it is used to show o(n^k), as i already said myself. My point was that that grammar is much more ambiguous compared to E ::= E + E. So, you're saying that any ambiguous grammar triggers worst case complexity? My question os that this example seems simpler that worst case and my experiments also show that. Can someone prove it? Or show that it is not the case.  
> **username_1**: The sketch of a proof is: all general CF algorithms walk the whole forest, because that is what they are built for. Whatever computation sharing they do is forest sharing. Shared forest representation is cubic in general, and always so for exponential ambiguity (which is your case). Hence all those parsers will be cubic on your grammar example. As I said, this is only a sketch, on which an actual proof can be built by checking all the claims. Johnson's example is not much more ambiguous than your: both are exponential and that is all that matters. The fact you ignore parse trees is irrelevant.  
> **username_0**: You may be right, but I'm not convinced yet by your argument. How do you define exponential ambiguity? I suggest you run the grammar to see that in practice it doesn't trigger the worst case, but SSS does.  
> **username_1**: Exponential ambiguity = exponential number of parse trees. What difference do you see with SSS, compared to SS. - - - - - - - - - - - - - - - One way to get a better bound, while retaining the general approach of these parsing algorithms, would be to find a more compact shared representation of parse-forests that can be walked as well to simulate all parse-tree walks. But even then, this would no longer be one of the classical general CF algorithms. It would be a very interesting result, though ... but I doubt there is anything to be found.  
> **username_1**: @Ali I do not have the software (and time) to run examples. but there are some figures in the Billot-Lang paper, though probably not enough to actually show that the parsing is cubic. Look at the appendix C.  
> **username_0**: Thanks! Appendix C shows a similar grammar A ::= AA | x named UBDA. I saw a proof in the original Early paper that that this grammar has O(n^3) bound. I redid my experiments, and for very large inputs, 800 a's, I'll get the cubic growth rate. I guess the reason I concluded that it may not be cubic was that its growth was much smaller than SSS, and I ran the experiments for inputs of size 200 which shows the cubic behaviour for SSS but not for E+E,  but still they are both worst case cubic.  
> **username_1**: @Ali Good you succeeded. How did you do your measurements? If you measure execution time, you always have to be careful with small values as they may hide behind system overhead. On the other hand, large values sometimes trigger garbage collection. There are more formal ways of measuring that avoid these pitfalls, but it is sometimes more work, or delicate to set up accurately.  
> **username_0**: I do it in the pretty standard way of measuring the performance of Java programs. Warm up and then average result with throwing out the outliers. I also take the System time instead of nano time to take GC and other noise out (as much as possible). The problem with E + E was it was reaching the n^3 quite late. I basically was doubling the input and measuring if the time was was 8 times bigger, it was much less than 8. The first time I observed 8 was increasing from 400 a's to 800 a's. For the other grammar it is much easier to observe the cubic behaviour and that misleaded me.  
> **username_1**: @Ali This is a bit strange. Maybe there is heavy initialization cost. Would you mind sending me the times you got for various values of n, especially those below the 400. Here or at username_1(at)inbox.com  
> **username_0**: Sure, the numbers are on my workstation at work. I will send them to you tomorrow.  

---

