Parsing table size (bottom-up)

Question

I've seen a comparison between sizes of parsing tables constructed for ambiguous and unambiguous grammar (of the same language). The one created for ambiguous was significantly smaller. The used parser was SLR(1).

I would like to ask you, is it always true that the size of parsing tables (of the bottom-up parser) representing an ambiguous grammar is always smaller than parsing tables of corresponding unambiguous grammar? Obviously assuming that conflicts are resolved correctly.

I have done some research, but I cannot find any proof or answer to this question.

Answer 1

It is not always the case. Consider the classic grammars for the language of balanced parentheses

The unambiguous one has 5 states in the SLR(1) automaton.

S -> '(' S ')' S | \epsilon

At the same time, ambiguous grammar has 6 states in the SLR(1) automaton.

S -> S S | '(' S ')' | \epsilon 

Thus the table size for the ambiguous grammar is greater than the table size for the unambiguous grammar.

The same is true about two grammars for the a+ language: S -> a S | a and S -> S S | S S S | a.