I'm studying (for self-betterment - I don't go to school) the 2nd edition of Compilers: Principles, Techniques and Tools by Aho et al. I'm not sure how to do Exercise 2.4.1 (b), which is to construct a recursive-descent parser, starting with the grammar:

$S\to S(S)S \mid \epsilon$.

It seem to me that the simpler grammar

$S\to (S)S \mid \epsilon$

can generate the same language as the given grammar, and if that's the case, I can construct a parser for it in a similar manner to the example that was shown in the previous section, without difficulty. Is that the right approach? (Keep in mind that I'm only in chapter 2, at around page 70 of this 1000+ page book, so the solution shouldn't be too "advanced".)

  • 2
    $\begingroup$ Indeed it's the same language. And you can't really deal with that left $S$ without altering the grammar, so this should be a correct way. $\endgroup$ – Karolis Juodelė Jun 18 '14 at 20:00
  • $\begingroup$ @KarolisJuodelė in that case the original grammar is ambiguous, and the parse will reflect only one possible derivation. That might not be enough $\endgroup$ – vonbrand Jun 19 '14 at 8:23
  • 1
    $\begingroup$ Thanks for the replies. @vonbrand The original grammar is clearly ambiguous. But if I understand correctly, that doesn't necessarily prevent us from being able to check whether a particular string could be derived from it. Is that right? $\endgroup$ – Aky Jun 19 '14 at 12:09
  • 1
    $\begingroup$ @Aky, it depends on what you want. If it is just to check membership in the language, it is clearly enough. If you need a particular derivation (or all of them, as may be) it isn't. $\endgroup$ – vonbrand Jun 19 '14 at 12:22
  • 1
    $\begingroup$ @vonbrand Given how (not so) far I am into the book, I don't think I'm expected to show anything besides membership. So I'm happy with that. $\endgroup$ – Aky Jun 19 '14 at 12:25

Your Answer

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

Browse other questions tagged or ask your own question.