Ambiguous grammar; ambiguity removal; is $A \to AA \mid (A) \mid a$ ambiguous?

1. When is a grammar called ambiguous?

A grammar is called ambiguous when there exists at least one string in its language that has two or more distinct parse trees (equivalently, two different leftmost or two different rightmost derivations).

2. Techniques to remove ambiguity

• Grammar rewriting (precedence/associativity): restructure the grammar with separate levels, e.g. expr → expr + term | term, term → term * factor | factor, so that operators bind with the intended precedence and associativity.
• Parser-tool directives: in YACC/Bison, use precedence declarations %left / %right / %nonassoc to resolve conflicts (e.g. %left '+', %left '*').
• Explicit structure: for left-associative operators use left recursion; for the dangling-else problem use separate matched/unmatched statement nonterminals.
• Caveat: removing ambiguity from an arbitrary grammar is undecidable in general, but for practical expression grammars these techniques work.

3. Justify whether $A \to AA \mid (A) \mid a$ is ambiguous

Yes — this grammar is ambiguous.

The string aaa has two distinct parse trees:

• Tree 1 (grouping as a (a a)): root A → A A, left A → a, right A → A A with children a a:

       A
      / \
     a   A
        / \
       a   a

• Tree 2 (grouping as (a a) a): root A → A A, left A → A A with children a a, right A → a:

       A
      / \
     A   a
   / \
  a   a

Both trees derive the same string aaa with different structure ⇒ the grammar is ambiguous. The root cause is the production $A \to AA$ — two adjacent occurrences of the same nonterminal admit two groupings of any consecutive run of a's.

A fix for this grammar: make the concatenation left- or right-associative explicitly, e.g. $A \to A\,\mathbf{star}$, or add a priority marker — but more importantly, grammar $A\to AA\mid a\mid (A)$ is inherently ambiguous, so a parser generator such as YACC would report a conflict for it. In practice prepend associativity info (%left) or rewrite to an unambiguous grammar such as $A \to A\,\text{cat} \mid (A) \mid a$ with cat a real operator.

$$\boxed{\text{A} \to A A \mid (A) \mid a\ \text{IS ambiguous — the string } aaa \text{ has two parse trees.}}$$