Это двусмысленная грамматика или нет?

Я пытаюсь выяснить, является ли следующая грамматика неоднозначной или однозначной:

stmt -> ЕСЛИ выражение ТО stmt | matchedStmt

matchedStmt -> IF expr THEN matchedStmt ELSE stmt | разное

Он реализует структуру if-then-else.

expr и other считаются терминальными символами, так как в этом вопросе они нас не интересуют.

Я пытался найти строку с более чем одним деревом синтаксического анализа, но не могу.

Не могли бы вы мне помочь?


compiler-construction grammar ambiguity context-free-grammar
person Sofia    schedule 13.11.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Эта грамматика неоднозначна, хотя движется в правильном направлении :)

Вот двусмысленность:

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
person rici    schedule 13.11.2013
comment
Теперь ясно! Я пытался выяснить, неоднозначна она или нет, найдя строку, созданную двумя деревьями синтаксического анализа, как я сделал для первой грамматики, и не смог. Я думал, что это единственный способ доказать, что это неоднозначно, но, да, мы можем сказать то же самое о ELSE s4, что не очевидно, где это совпадает. Огромное спасибо! :) - person Sofia; 14.11.2013