2
$\begingroup$

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

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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*)?

$\endgroup$
2
$\begingroup$

A grammar is ambiguous if it can generate a string in more than two ways, i.e. a string generated by the grammar does not have a unique parse tree.

The grammar you have can generate the string a + a + a by the following parse trees.

          S             S
        / | \         / | \
       /  |  S       S  |  \
      /   |  |       |  |   \
     /    |  |       |  |    \
    S     |  |       |  |     S
  / | \   |  |       |  |   / | \
 S  |  S  |  |       |  |  S  |  S
 |  |  |  |  |       |  |  |  |  |
 a  +  a  +  a       a  +  a  +  a

This shows that the grammar is ambiguous.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.