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



Я не понял, как однозначная грамматика получается из неоднозначной грамматики? Рассмотрим пример на сайте: Пример . Как была получена грамматика, меня смущает.

Кто-нибудь может проводить меня ?

117   2  

2 ответов:

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

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

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').

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

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

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

  1. эквивалентно первому: оба порождают один и тот же язык
  2. однозначно: для каждого предложения язык, дерево синтаксического анализа является уникальным
    Ничего не найдено.

Добавить ответ:
Отменить.