Consider now the grammar G

S -> (S + S)
S -> (S * S)
S -> a

Is it ambiguous?

Answer: No because there are disambiguating parentheses and so no left or right recursion.

Can someone explain how the parentheses are disambiguating. I could understand if they were "[" and "(".

Appreciate the help

  • $\begingroup$ Crossposted on math.se math.stackexchange.com/questions/1759611/… $\endgroup$ – Ran G. Apr 28 '16 at 18:16
  • $\begingroup$ Yeah, sorry I'm fairly new is double posting allowed? I thought people here might be better at answering $\endgroup$ – Daniel Apr 28 '16 at 18:45
  • $\begingroup$ Cross-posting (posting on several sites at once) is frowned upon. A moderator will eventually merge both questions. $\endgroup$ – Yuval Filmus Apr 28 '16 at 20:46
  • $\begingroup$ Note that the ambiguity of the related grammar $S\to S+S\mid S*S \mid a$ is not caused by the two operators. Even $S\to S+S\mid a$ is ambiguous: we do not know how $a+a+a$ was derived. Brackets help to distinguish $((a+a)+a)$ from $(a+(a+a))$. See the answer by @YuvalFilmus for full details. $\endgroup$ – Hendrik Jan Apr 29 '16 at 2:48

A grammar $G$ is non-amgibuous if every word in $L(G)$ has a unique parse tree. The simplest way to prove that your grammar non-ambiguous is to prove that $L(S + S),L(S * S),L(a)$ are all distinct (here $L(\alpha)$ is the set of all words that can be generated from the sentential expression $\alpha$); given this, an easy induction shows that $L(G)$ is non-ambiguous.

It is clear that $L(S + S)$ and $L(S * S)$ are disjoint from $L(a)$. To prove that $L(S + S)$ and $L(S * S)$ themselves are disjoint, you can prove by induction that each word generated by $S$ is either $a$ or of the form $(w)$, where $w$ is a well-parenthesized expression (parenthesis close each other correctly), and this gives you a rule for identifying the first and the second $S$ in word generated by $L(S + S)$ and $L(S * S)$; the symbol in between determines whether the word belongs to $L(S + S)$ or to $L(S * S)$.

| cite | improve this answer | |
  • $\begingroup$ This makes more sense to me now, thanks for the answer! $\endgroup$ – Daniel Apr 28 '16 at 21:20

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.