compiler-construction - これはあいまいな文法ですか？

Question

次の文法があいまいであるか、または明確であるかを調べようとしています。

stmt -> IF expr THEN stmt | 一致したStmt

MatchedStmt -> IF expr THEN matchingStmt ELSE stmt | 他の

if-then-else 構造体を実装しています。

exprotherこの質問では気にしないので、終端記号と見なされます。

複数の解析ツリーを持つ文字列を見つけようとしましたが、見つかりません。

手伝ってくれませんか？

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 c3IF 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