Many standard Compiler Design texts mention constructing augmented grammar as first step of LR parsing.

The reason frequently is

  1. It is required in cases where start symbol comes on right hand of any production
  2. It is required when start symbol's RHS have multiple production.

I figured that if in the parse table's action part of very first state of DFA, we provide "success" under entry of '$' we would not require augmented grammar. Is that correct or i am missing something?

Edit: Here is how i think we can declare a parse as success:

Consider S -> .a After we reduce 'a' instead of going to goto(S) from our current state a tTop of stack, we can simply lookahead '$' and output success


Once we have a parsing table, we can parse (or reject) any sentence without any reference to the grammar. So at that point, the fact that the grammar was or was not augmented is essentially moot. (It would be meaningful if there were a user semantic action attached to the augmented start symbol's sole production, but that seems impossible, since the augmented start symbol's production was added automatically, not by the user.)

And it is indeed the case that most parser generators do in fact optimise their parse table by making the shift of the end-of-input marker the accept action, rather than waiting for the augmented start symbol's production to be reduced. With that optimisation, the augmented start symbol is never used in a parser action, so the symbol itself need not exist. If the parser generator augmented the grammar, that augmentation has essentially been undone, except for one little mystery: what is this end-of-input symbol which can be shifted? It doesn't appear in any reducible right-hand side.

Anyway, the point is that it's not parsing which requires an augmented grammar; the augmented grammar is necessary to create the parsing table. The cases where it is necessary are essentially the cases in which there is some non-default reduction action associated with an end-of-input symbol lookahead. That reduction action could only have been correctly added to the parsing table through the analysis of a state which includes the augmented start symbol's production.

(Strictly speaking, as alluded to earlier, the end-of-input symbol can't really exist in the parsing table unless it is present in some right-hand-side in the grammar, and it isn't present until the grammar is augmented; the augmentation not only adds an additional non-terminal, it also adds the end-of-input symbol itself.)

| cite | improve this answer | |
  • $\begingroup$ I am not very sure i get what u are saying...Augmented Start symbol / end of input symbol or for that matter no symbols are placed on stack of LR parser..we push states instead of symbols...pls correct me if i am wrong.. $\endgroup$ – user83335 Sep 8 at 15:31
  • $\begingroup$ If you have a couple of mins pls skim over this so we can be in sync ecomputernotes.com/compiler-design/lr-parsers $\endgroup$ – user83335 Sep 8 at 15:34
  • $\begingroup$ @user83335: That's correct: states are pushed. But a goto action shifts the parser over a non-terminal symbol in the state's items. I probably could have said that more precisely in the answer. From the document you linked: "Goto This function takes a state and grammar symbol as arguments and produces a state." (emphasis added) $\endgroup$ – rici Sep 8 at 15:36
  • $\begingroup$ Small edit made: perhaps it is now clearer. $\endgroup$ – rici Sep 8 at 15:40
  • $\begingroup$ It makes sense now.Tysm for answering :) $\endgroup$ – user83335 Sep 10 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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