Преобразование двусмысленной грамматики в однозначную

Ответ 1

Пример состоит из двух грамматик:

Неоднозначное:

E → E + E | E ∗ E | (E) | a

Однозначный:

E → E + T | T
T → T ∗ F | F
F → (E) | a

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

• Оператор '*' связывается более жестко, чем оператор '+'.
• Оба оператора '*' и '+' остаются ассоциативными.

Без внешней информации нет способа сделать преобразование.

С внешней информацией мы можем сказать, что:

a * a + b * b

сгруппирован, как если бы он был написан:

(a * a) + (b * b)

а не как:

a * ((a + b) * b)

Второе предполагает, что '+' связывается более жестко, чем '*', и что операторы связываются справа налево, а не слева направо.

Комментарий

Как бы ассоциативность появилась на картинке для таких примеров, как:

    S → aA | Ba
    A → BA | a
    B → aB | epsilon

Это двусмысленная грамматика, и как это сделать, чтобы превратить ее в однозначную?

Интересно, "epsilon" - это ε, пустая строка; пусть анализировать грамматику в обоих направлениях.

ε - пустая строка

Правило для B говорит, что B - либо пустая строка, либо a, за которой следует действительный B, что равно бесконечно длинной строке 0 или более a.

Правило для A означает, что A является либо a, либо a B, за которым следует a. Таким образом, бесконечно длинная строка может быть A тоже. Таким образом, для грамматики нет способа выбрать, является ли строка a либо A, либо B.

И правило для S не помогает; S - либо a, за которым следует бесконечно длинная строка a или бесконечно длинная строка a, за которой следует a. Он требует по крайней мере одного a, но любое число a от одного вверх в порядке, но грамматика не имеет оснований для выбора между левой и правой альтернативами.

Итак, эта грамматика по своей сути неоднозначна и не может, по моей оценке, быть однозначной; это, безусловно, нельзя сделать однозначным без другой информации, не имеющейся у нас.

ε не является пустой строкой

Как насчет того, если ε не является пустой строкой?

• B является либо ε, либо aε.
• A является либо a, либо a, а затем a (поэтому либо a, либо aε, либо aaε).
• Либо: S - это a, за которым следует A (следовательно, aa, aaε или aaaε)
• Или: S - это B, за которым следует a (следовательно, εa или aεa).

В этом случае грамматика недвусмысленная, поскольку она стоит (хотя и не обязательно LR (1)). Ясно, что многое зависит от значения "эпсилон" в комментарии/вопросе.

Ассоциативность

Я не думаю, что ассоциативность влияет на эту грамматику. Он обычно вступает в игру с инфиксными операторами (такими как "+" в "a + b" ).

Ответ 2

Из Википедии (на Распознавание неоднозначных грамматик):

Некоторые двусмысленные грамматики могут быть преобразованы в однозначные грамматики, но общая процедура для этого невозможна, так как не существует алгоритма для обнаружения неоднозначных грамматик.

Чтобы придумать вторую грамматику, вам нужно найти грамматику

• Эквивалент первому: оба генерируют один и тот же язык
• Unamiguous: для каждого предложения языка дерево разбора уникально