CODEWITHSUNDEEP
compiler-constructiongrammarcontext-free-grammarambiguity
Sofia
Sofia

Reputation: 11

Is this an ambiguous grammar or not?

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?

Upvotes: 0

Views: 1425

Answers (1)

rici
rici

Reputation: 241931

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

Upvotes: 2

Related Questions