$L(G)$ is the set of all p-expressions
Let an operator mean either $+$ or $*$. In order to characterize the strings generated by $G$, we may observe the number of operators and the number of $a$'s in a string.
Call a string $w$ over alphabet $\{a, +, *\}$ a p-expression if
- $w$ is non-empty, and
- there are at least as many operators as $a$'s in each proper suffix of $w$ while there are one less operators than $a$'s in $w$. (In particular, $w$ ends with an operator and starts with two $a$'s unless $w=a$.)
Claim: $L(G)$ is the set of all p-expressions.
Proof: Use structural induction. This is an easy exercise for the readers.
$G$ is unambiguous
Proof: Let us show that $w\in L(G)$ has a unique parse tree using induction on $|w|$.
- Base case, $|w|=1$. Then $w$ must be $a$. $S\to a$ is the only derivation for $w$.
- As induction hypothesis, assume the proposition is true for $|w|\le n$.
Let $|w|=n+1$. WLOG, suppose $w$ ends with $+$. So the first step in the derivation for $w$ must be $$S\to SS+.$$
Let $w_1$ be the string produce by the first $S$ on the right hand side and $w_2$ be the string produced by the second $S$ so that $w=w_1w_2+$. Note that $w_1, w_2\in L(G)$.
Scanning $w_1w_2+$ from right to left character by character, let us track the difference of the number of operators and the number of $a$'s scanned. The claim above implies the last scanned character of $w_2$ must be the character at which that difference have dropped to 0 for the first time.
So $w_2$ is determined uniquely by $w$. Hence $w_1$ is also determined uniquely by $w$.
By induction hypothesis, there is a unique parse tree for $w_1$ and for $w_2$. Hence, there is a unique parse tree for $w$. $\quad\checkmark$
Inspect $G$ reversed
Here is another way to show $G$ is unambiguous, which may appear simpler for readers with more experience.
Let $G^r$ be $G$ with production rules reversed, i.e.,
$$G^r=(\{a,+, *\}, \{S\}, \{S\to +SS, S\to *SS, s\to a\}, \{S\}).$$
It is easy to see that $G$ is unambiguous iff $G^r$ is unambiguous.
With some simple routine computation, we can obtain the $LL(1)$ parsing-table of $G^r$,
$$\begin{array} {|c|c|c|c|}\hline
&{\\\$} &+ & * & a \\\hline
S & &S\to +SS &S\to *SS & S\to a \\\hline
\end{array}$$
As an $LL(1)$ grammar, $G^r$ is unambiguous. Hence, $G$ is ambiguous as well.
More generally, we can prove that a context-free grammar is unambiguous if all production rules end with different terminals.
An exercise
Prove $(\{0, 1,+, *\},$ $\{S, B\},$ $\{S\to SS+,$ $S\to SS*,$ $S\to
B,$ $B\to 0B,$ $B\to 1B,$ $B\to 0,$ $B\to 1\},$ $\{S\})$ is an unambiguous grammar.