1
$\begingroup$

I am trying to solve the following problem from Aho, et al., Compilers: Principles, Techniques, & Tools (2nd ed.), exercise 2.2.2e:

What language is generated by the following grammar? $S\rightarrow\textbf{a | }S\textbf{ + }S\textbf{ | }S\textbf{ }S\textbf{ | }S\textbf{ * | ( }S\textbf{ )}$

This looks like some combination of infix addition and postfix star operator, along with parenthesis, but I am not sure how to describe this in a clear fashion.

Improve this question
$\endgroup$
  • $\begingroup$ Hint: The language is a familiar one, enough so that it has been given a name. Since you're reading the dragon book, you've almost certainly encountered this particular language before (perhaps with "+" replaced by "$\cup$" or "$\mid$"). $\endgroup$ – Rick Decker Oct 27 '14 at 14:50
  • $\begingroup$ Try to generate a few expressions using this grammar. Here are a few I generated: $aa(a+a^*)^*,a^*,aaaaa,((a))$. $\endgroup$ – Yuval Filmus Oct 27 '14 at 14:51
  • 2
    $\begingroup$ The grammar at hand is a description. What kind of description do you expect? Hint: generate some strings and make an educated guess, then prove it correct. $\endgroup$ – Raphael♦ Oct 27 '14 at 16:44
  • $\begingroup$ Formal languages are just syntax. But they can be used to define the syntax part of a language that has also semantics, for example a programming language. The sentences written in a programming language have meaning. Maybe, the sentences of your language can be given a meaning ... $\endgroup$ – babou Oct 27 '14 at 17:29

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.