complexityofparser

Question

Consider the following statements:-

S1 : for LL(1) parsing of n tokens ,time complexity in the best case is O(n) and worst case is O(n4) .

S2 : for LR parsing of n tokens ,time complexity in the best case is O(n) and worst case is O(n3) .

which of the following statements are true?

a)Only S1 is correct.

b)Only S2 is correct.

c) Both S1 and S2 is correct.

d)Neither S1 nor S2 is correct.

Answer 1

First let us know about the 1st statement :

The best case corresponds to the case when the grammar is an S grammar ..

S- grammar means :

A grammar where all productions are of the form  A --> TV* and also there is a restriction that (A,T) pair is used at most once considering the entire set of productions of the grammar..This is also known as linear parsing grammar.

S - grammar is a subset of LL(1) grammars as all LL(1) does not follow the 2nd restriction of S grammar which is concerning (A,T) pair..So the best case of LL(1) will be when it is an S grammar..

So in this case we will have best case of O(n) , where n is the number of tokens..

The worst and general case corresponds to dynamic programming solution which takes O(n⁴) for left recursive grammars and O(n³) for right recursive grammar..So worst case is O(n⁴)  ..

Hence statement 1 is true..

[Reference : https://en.wikipedia.org/wiki/Top-down_parsing ] 

Now let us come to second statement..

LR grammars on the other hand are more efficient than LL(1) grammars..

 Knuth proved that LR parsers were the most general-purpose parsers possible that would still be efficient in the worst cases.

"LR(k) grammars can be efficiently parsed with an execution time essentially proportional to the length of the string."

For every k≥1, "a language can be generated by an LR(k) grammar if and only if it is deterministic [and context-free], if and only if it can be generated by an LR(1) grammar."

So for LR grammars we have both best and worst case complexity of O(n) ..So statement 2 is false actually..

Hence A) option is correct ..

Comments

@Habibkhan

As per this https://pdfs.semanticscholar.org/c406/47d79f07b0eb0f01ee58e72ae0999094a7ac.pdf

 

---

https://gateoverflow.in/91761/parsers-complexity

However for bottom up parser using the CYK algorithm , we will get upper bound of O(n³) whatever the CFG be (either left recursive or right recursive)..

@Habibkhan

Sir ..For bottom up parser worst case is O(n^3)

SO how LR(k) can do it in O(n)

---

"LR grammars we have both best and worst case complexity of O(n) .."

I'm not  getting this.

Becoz Lr(K) parser follow  in best case o (n) and worst case it should be o (n^3). (Same as Membership Algorithm in CFG)

Please correct me if I'm wrong.