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

Пример имеет две грамматики:

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

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

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

I интересно, является ли "Эпсилон" ε, пустой строкой; давайте проанализируем грамматику в обоих направлениях.

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

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

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

Ε-это не пустая строка

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

• B-это либо ε, либо ae.
• A - это либо a, либо B, за которым следует a (таким образом, либо a, либо ae, либо aae).
• либо: S - это a, за которым следует A (отсюда aa, aae или aaae)
• или: S - Это B, за которым следует a (отсюда ea или aea).

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

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

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