Prove that following grammar is ambiguous; S → a | S + S | S S | S* | ( S ) Prove that the following grammar is ambiguous; S → a | S + S | S S | S* | ( S )
checking ambiguity in grammar. the subject of this question is compiler construction and automation. would you please help me find the answer we only have to figure out whether its ambiguous or not
To show the grammar is ambiguous, you must find a string derived by the grammar which has two or more distinct parse trees. I think we have a few options here. One that should work is S + S*:
                   S
                  /
                 /
   S            S--+
  /            / \
 /            /   \
S--+         S     S
 \            \
  \            \
   S--S         *
    \            
     \
      *

These derivations are fundamentally different (not just different orderings of the same derivation) and so the string S + S* is fundamentally ambiguous. Does it mean (S + S)* or does it mean S + (S*)?