compiler-construction - 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

该语法是模棱两可的，尽管它朝着正确的方向前进:)

这里有一个歧义：

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

由于IF c2 THEN s2 ELSE IF c3 THEN s3可以简化为：

IF c2 THEN matchedStmt ELSE stmt

这是一个matchedStmt。所以它是ELSE s4属于IF c3还是是模棱两可的IF c1。

---

您需要的是matchedStmt在 的两侧完全匹配ELSE，如下所示：

stmt -> matchedStmt | unmatchedStmt

matchedStmt -> IF expr THEN matchedStmt ELSE matchedStmt
            |  other

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