How to intuitively come up with an example for an ambiguous grammar and how to make that grammar unambiguous?

Question

I don't get how to intuitively come up with an example for an ambiguous grammar.

Let's take as an example this grammar:

Declaration ::= Type D ;
         Type ::= "int" | "char"
         D ::= "*" D
            |  D "[" number "]"
            |  D "(" Type ")"
            |  "(" D ")"
            |  name

I am told outright that this grammar is ambiguous. What is expected of me is to find one example that proves that it is. What I'm interested is what is the thought process that allows you to find an example. Our teacher just gave us one example that would show that we would obtain two different derivation tree like:

int *foo[5];  has two derivation tree

            Declaration              Declaration
             /    |   \               /    |   \
           Type   D    ;            Type   D    ;
            |    / \                 |    / \____
           int  *   D               int  /   \ \ \
                   / \____              D    [ 5 ]
                  /   \ \ \            / \
                 D    [ 5 ]           *   D
                 |                        |
                foo                      foo

However I have no idea how he thought to himself that int*foo[5] would be the example before doing the trees. It all boils down to how they did it without trial and error?

How to make that grammar unambiguous? I was also given the task to make the above grammar unambiguous. However I don't know yet again what is the intuition behind making it unambiguous.

They gave us this solution:

 Declaration ::= Type D ;
       Type ::= "int" | "char"
       D ::= "*" D
          |  "(" D ")" D'
          |  name D'
       D' ::= "[" number "]" D'
           |  "(" Type ")" D'
           |  empty               <== empty string

There must be a pattern in all of this. What it is? What is the general method to solve this type of problem regardless of which grammar is given?

Answer 1

The simple way of seeing this class of ambiguities is to observe that if two right-hand sides for the same non-terminal overlap, then they could be applied in either order:

 D ::=     "*" D
    |          D "[" number "]"

The overlap is pretty clear:

 "*" D "[" number "]"

Another example, where a right-hand side can overlap with itself:

E ::= E "+" E

Overlap:

      E "*" E
            E "*" E
      -------------
      E "*" E "*" E

The solution is to remove the overlap by introducing a new non-terminal for one of the overlapping uses. Here's my solution to the ambiguity in your grammar:

Declaration ::= Type D ;
Type ::= "int" | "char"
D ::= "*" D
   E
E ::= E "[" number "]
   |  E "(" Type ")"
   |  "(" D ")"
   |  name

Which productions you decide to shift to the new non-terminal is not arbitrary; it will define which of the competing parses is correct for the language you are designing. There is no universal answer to that question, so it cannot be done algorithmically.

Note: The clumsy solution you have been provided with is probably because your lesson is being mixed with a discussion of top-down parsing. My grammar, though unambiguous, is not suitable for top-down parsing because it is left-recursive. However, the resulting parse tree reflects the syntactic structure of the declaration.