LL(1) грамматика для болтаться еще

Question

LL(1) грамматика для болтаться еще

В построении компилятора одна из главных проблем неоднозначности - еще одна проблема. Как уже упоминалось в книге "Компиляторы: принципы, методы и инструменты" Ахо, Лама, Сетхи и Уллмана, грамматика оборванного остального не может использоваться с анализаторами LL(1).

Правда ли, что он не может быть обработан как LL(1)?

3

compiler-construction dangling-else

Источник

user2051818 13 апр '12 в 23:19

1 ответ

Решение

Другие вопросы по тегам compiler-construction dangling-else

user120163 13 апр '12 в 23:32 2012-04-13 23:32 · Accepted Answer · 2012-04-13 23:32

Это правда, он не может быть проанализирован LL(k) или LALR(k) в чистом виде. Проблема состоит в том, что есть две возможные интерпретации висячего другого; это проблема неоднозначности ("else" принадлежит ближайшему "if" или не принадлежит).

Обычно это вылечивают, настаивая только на одной из двух интерпретаций, например, "иначе принадлежит ближайшему, если".

Многие генераторы парсеров могут получить это "случайно"; решение с LL состоит в том, чтобы принять первый работающий синтаксический анализ и сначала попробовать "еще присоединяется к ближайшему". Решение с LR - это "сдвиг на другое", которое легко вызывается простой проверкой действий "сдвига" перед действиями "уменьшения".

Это может стать проблемой только с парсером, который действительно подберет неоднозначные парсеры, такие как GLR. Здесь можно дать внеграмматические подсказки, например, "перейти на другое".