# How to describe the language generated by S → a | S + S | S S | S * | ( S )

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.

• 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$"). – Rick Decker Oct 27 '14 at 14:50
• Try to generate a few expressions using this grammar. Here are a few I generated: $aa(a+a^*)^*,a^*,aaaaa,((a))$. – Yuval Filmus Oct 27 '14 at 14:51
• 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. – Raphael Oct 27 '14 at 16:44
• 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 ... – babou Oct 27 '14 at 17:29