Is this an ambiguous grammar or not?

Question

I'm trying to find out if the following grammar is ambiguous or unambiguous:

stmt -> IF expr THEN stmt | matchedStmt

matchedStmt -> IF expr THEN matchedStmt ELSE stmt | other

It implements the if-then-else struct.

expr and other are considered to be terminal symbols, as we don't care about them in this question.

I've been trying to find a string that has more than one parse trees, but I can't.

Can you please help me?

Answer 1

That grammar is ambiguous, although it's heading in the right direction :)

Here's an ambiguity:

IF c1 THEN IF c2 THEN s2 ELSE IF c3 THEN s3 ELSE s4

Since IF c2 THEN s2 ELSE IF c3 THEN s3 can be reduced to:

IF c2 THEN matchedStmt ELSE stmt

which is a matchedStmt. So it's ambiguous whether ELSE s4 belongs to IF c3 or IF c1.

---

What you need is for matchedStmt to be completely matched on both sides of the ELSE, something like this:

stmt -> matchedStmt | unmatchedStmt

matchedStmt -> IF expr THEN matchedStmt ELSE matchedStmt
            |  other

unmatchedStmt -> IF expr THEN stmt
              |  IF expr THEN matchedStmt ELSE unmatchedStmt