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

В примере есть две грамматики:

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

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

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

Интересно, равно ли «эпсилон» ε, пустая строка; давайте проанализируем грамматику в обоих направлениях.

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

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

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

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

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

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

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

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

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

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

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