В примере есть две грамматики:
Неоднозначность:
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. Требуется хотя бы один знак «а», но любое число «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»).