БНФ Грамматика Двусмысленность

Question

Я недавно думал о следующем БНФ

A -> x | yA | yAzA

where x,y,z are terminals.

Я почти уверен, что эта грамматика неоднозначна, но как сделать ее однозначной?

Answer 1

Грамматика неоднозначна, если конкретная строка может иметь более одного дерева разбора.На вашем языке строка yyxzx может иметь любое из этих двух деревьев разбора:

    A                  A
   / \                /|\`\
  y   A              y A z A
     /|\`\            / \   \
    y A z A          y   A   x
      |   |              |
      x   x              x

Поэтому грамматика неоднозначна.

Это на самом деле эквивалентно пресловутому "if / then /else "двусмысленность в C-подобных языках, где y=if, z=else и x=statement.http://en.wikipedia.org/wiki/Dangling_else. Я бы порекомендовал проверить эту страницу, чтобы узнать, как обойти эту проблему.