0
$\begingroup$

I know how to verify whether grammar is LR(0) or not. But this particular case is little tricky and hence the question.

Grammar:

$SL \rightarrow SL ; S \space | \space \epsilon$

$S \rightarrow s$

(Note: $SL$ is single non-terminal.)

Now, LR(0) automaton for this grammar is as follow:

enter image description here

Now my question is whether to consider entry $start \rightarrow SL.$ in $State_1$ as SR conflict.

Because I previously came to know that we don't consider conflicts due to augmented production.

Thanks.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

You haven't actually augmented the grammar. The augmented grammar has the production $$start\to SL\;\$$$

With that change, state 1 is not a reduction state and there is no conflict.

If you did not intend to augment the grammar, then it is not $LR(0)$, because the language does not have the prefix property. But that's not very useful, so normally we augment grammars, turning the language $L$ into $L\$$, where $\$$ is a symbol not in the the alphabet for $L$. Clearly the augmented language has the prefix property.

There's a reasonable explanation with references on Wikipedia.

Improve this answer
$\endgroup$
4
  • $\begingroup$ But we use $start \rightarrow SL$ as augmentation rule. Don't we? And we reduce by this production when the lookahead symbol is $\$$ in case of SLR, LALR and CLR. So is it different for LR(0). $\endgroup$
    – Vimal Patel
    Commented Feb 5, 2020 at 3:33
  • $\begingroup$ Wikipedia mentions augmentation rule like one in your answer but some other reference like Compilers: Principles, Techniques, and Tools (2nd Edition) by Ullman mentions it like $start \rightarrow SL $. And I think here this distinction makes the grammar lr(0) or non-lr(0) if you use different augmentation rule. $\endgroup$
    – Vimal Patel
    Commented Feb 5, 2020 at 3:53
  • 2
    $\begingroup$ @vimal: yes, the presentation in the Dragon book is a bit confusing. If you look at the actual algorithm for constructing an SLR parsing table (algorithm 4.8 in the edition I have, but I think yours has different numbering) you'll see that the augmented rule is handled specially. First, it's excluded from being a reduction in 2b, and then in 2c it's treated as though $\$$ were in the lookahead, although with an "accept" action rather than a shift. Those special case rules are exactly the same as augmenting the rule with $\$$ and then treating the reduction as an accept rather than the shift... $\endgroup$
    – rici
    Commented Feb 5, 2020 at 4:15
  • 1
    $\begingroup$ In practice, that saves a state. But it complicates the exposition. Since the Dragon Book was written for practitioners rather than theoreticians, the pragmatic approach is justifiable, I suppose. But the usual way of writing augmentation rules seems simpler. $\endgroup$
    – rici
    Commented Feb 5, 2020 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.