parsinggrammarll-grammarlr-grammar

Epsilon(ε) productions and LR(0) grammars and LL(1) grammars

At many places (for example in this answer here), I have seen it is written that an LR(0) grammar cannot contain ε productions.

Also in Wikipedia I have seen statements like: An ε free LL(1) grammar is also SLR(1).

Now the problem which I am facing is that I cannot reason out the logic behind these statements.

Well, I know that LR(0) grammars accept the languages accepted by a DPDA by empty stack, i.e. the language they accept must have prefix property. [This prefix property can, however, be dealt with if we assume end markers and as such given any language the prefix property shall always be satisfied. Many texts like Theory of Computation by Sipser assume this end marker to simply their argument]. That being said, we can say (informally?) that a grammar is LR(0) if there is no state in the canonical collection of LR(0) items that have a shift-reduce conflict or reduce-reduce conflict.

With this background, I tried to consider the following grammar:

S -> Aa
A -> ε

enter image description here

canonical collection of LR(0) items

In the above DFA, I find that there is no state which has a shift-reduce conflict or reduce-reduce conflict.

So this grammar should be LR(0) as per my analysis. But it also has ε production.

Isn't this example contradicting the statement:

"no grammar with ε productions can be LR(0)"

I guess if I know the logic behind the above quoted statement then I can understand the concept better.

Actually my main problem arose with the statement :

An ε free LL(1) grammar is also SLR(1).

When I asked one of my friends, he gave the argument that as the LL(1) grammar is ε free hence it is LR(0) and hence it is SLR(1).

But I could not understand his logic either. When I asked him about reasoning, he started sharing post regarding "grammar with ε productions can never be LR(0)"...

But personally I could not think of any logic as to how "ε free LL(1) grammar is SLR(1)". Is it really related to the above property of "grammar with ε productions cannot be LR(0)"? If so, please do help me out.. If not, then should I consider asking a separate question for the second confusion?

I have got my concepts of compiler design from the dragon book by Ullman only. Also the knowledge of TOC from Ullman and from few other texts like Sipser, Linz.

Solution

  • A notable feature of your grammar is that A could just be eliminated. It serves absolutely no purpose. (By "eliminated", I mean simply removing all references to it; leaving productions otherwise intact.)

    It is true that it's existence doesn't preclude the grammar from being LR(0). Similarly, a grammar with an unreachable non-terminal and an ε-production for that non-terminal could also be LR(0).

    So it would be more accurate to say that a grammar cannot be LR(0) if it has a productive non-terminal with both an ε-production and some other productive production. But since we usually only consider reduced grammars without pointless non-terminals, I'm not sure that this additional pedantry serves much purpose.

    As for your question about ε-free LL(1) grammars, here's a rough outline:

    If an ε-free grammar is not LR(0), then there is some state with both a shift and a reduce action. Since the grammar is ε-free, that state was reached by way of a shift or a goto. The previous state must then have had two different productions with the same FIRST set, contradicting the LL(1) condition.