2
$\begingroup$

I was reading the LR() parsers from the Dragon Book where I came across these lines:

To construct canonical LR(0) collection for a grammar, we define an augmented grammar and 2 functions, CLOSURE and GOTO.

for example say if we have a grammar like-->

S → BB
B → cB/d

Then in augmented grammar we define it as

S' → S

S → BB

B → cB/d

In the dragon book the reason for this is mentioned as,

The purpose of this new starting state production is to indicate the parser when it should stop parsing and announce the acceptance of the input. That is acceptance occurs when only when the parser is about to reduce S' → S

I am unable to understand what this even means and how this augmented grammar is useful for parsing. Any help will be highly appreciated.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ If you don't understand what that means I'd suggest going back in the book and re-read every section you don't fully understand. I think the books explanation is clear and I couldn't say it better myself. $\endgroup$
    – orlp
    Sep 4, 2019 at 8:32
  • $\begingroup$ @yuval any answer from u will be very helpful, as you can explain topics in a fluid manner. $\endgroup$
    – Turing101
    Sep 4, 2019 at 12:19

1 Answer 1

Reset to default
3
$\begingroup$

The augmented grammar adds a new starting non-terminal $S'$ with the sole production $S' \to S$. This helps in detecting acceptance: If you reduce by this particular production (to the non-terminal $S'$), you are accepting. To reduce to the start non-terminal of the original grammar tells you nothing, it might appear on some right hand side.

Improve this answer
$\endgroup$

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.