Как определить, является ли язык LL(1) LR(0) SLR(1)

StackOverflow https://stackoverflow.com/questions/475949

Вопрос

Есть ли простой способ определить, является ли грамматика LL(1), LR(0), SLR(1)...просто глядя на грамматику, не проводя какого-либо сложного анализа?

Например:Чтобы решить, является ли грамматика BNF LL(1), вам необходимо вычислить наборы First и Follow, что в некоторых случаях может занять много времени.

Есть ли у кого-нибудь идеи, как сделать это быстрее?Любая помощь будет очень признательна!

Это было полезно?

Решение

Для начала немного педантичности.Вы не можете определить, является ли язык является LL(1) от проверки грамматики, вы можете делать утверждения только о грамматика сам.Вполне возможно писать грамматики, отличные от LL(1), для языков, для которых существует грамматика LL(1).

С этим в сторону:

  • Вы можете написать синтаксический анализатор грамматики и заставить программу сначала вычислять грамматику, а затем следить за наборами и другими свойствами.В конце концов, это большое преимущество грамматик BNF: они понятны машине.

  • Проверьте грамматику и найдите нарушения ограничений различных типов грамматики.Например:LL(1) допускает правую, но не левую рекурсию, поэтому грамматика, содержащая левую рекурсию, не является LL(1).(Для других грамматических свойств вам придется потратить некоторое время на определения, потому что я сейчас не могу вспомнить ничего другого из головы :).

Другие советы

Отвечая на ваш главный вопрос:Для очень простой грамматики можно определить, является ли она LL(1), не создавая наборы FIRST и FOLLOW, например

A → A + A | а

не является LL(1), а

A → A | беременный

является.

Но когда вы станете более сложным, вам нужно будет провести некоторый анализ.

A → B | а
Б → А + А

Это не LL(1), но это может быть не сразу очевидно.

Грамматические правила арифметики быстро становятся очень сложными:

выражение → термин { '+' термин }
срок → фактор { '*' фактор }
Фактор → номер | '(' expr ')'

Эта грамматика обрабатывает только умножение и сложение, и уже не сразу понятно, является ли эта грамматика LL(1).Это все еще возможно оценить, просматривая грамматику, но по мере роста грамматики это становится все менее осуществимым.Если мы определяем грамматику для всего языка программирования, почти наверняка потребуется сложный анализ.

Тем не менее, есть несколько очевидных явных признаков того, что грамматика не соответствует LL(1) — например, A → A + A выше — и если вы найдете какой-либо из них в своей грамматике, вы будете знать, что ее необходимо переписать. если вы пишете парсер рекурсивного спуска.Но нет быстрого способа проверить, что грамматика является ЛЛ(1).

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

Прямо из книги «Составители:Принципы, методы и инструменты» Ахо и др.ал.

Страница 223:

Грамматика G — это LL(1). если и только если всякий раз, когда A -> альфа | бета являются двумя различными произведениями группы G, выполняются следующие условия:

  1. Для отсутствия терминала «а» выполните оба действия. альфа и бета выводить строки, начинающиеся с «а»
  2. Максимум один из альфа и бета может получить пустую строку
  3. Если бета может достичь пустого перехода через ноль или более переходов, тогда альфа не выводит строку, начинающуюся с терминала в FOLLOW(A).Аналогично, если альфа может достичь пустого перехода через ноль или более переходов, тогда бета не выводит строку, начинающуюся с терминала в FOLLOW(A)

По сути, это вопрос проверки того, что грамматика проходит тест на попарную непересекаемость, а также не включает левую рекурсию.Или, более кратко, леворекурсивная или неоднозначная грамматика G не может быть LL(1).

Проверьте, является ли грамматика неоднозначной или нет. Если это так, то грамматика не является LL (1), потому что нет никакой неоднозначной грамматики LL (1).

да, есть ярлыки для ll (1) грамматики

1) если A - > B1 | B2 | ....... | Bn     затем первое (B1) пересечение, первое (B2) пересечение .first (Bn) = пустое множество, тогда это будет 1 (1) грамматика

2) если A - > B1 | epsilon      затем B1 пересечение следовать (A) пустое множество

3) если G - любая грамматика такая, что каждый нетерминал выводит только одно произведение, то грамматика - это LL (1) 

p0 S' → E
p1 E → id
p2 E → id ( E )
p3 E → E + id
  • Создайте LR(0) DFA, набор FOLLOW для E и таблицы действий/перехода SLR.
  • Это грамматика LR(0)?Докажите свой ответ.
  • Используя таблицы SLR, покажите этапы (сдвиги, сокращения, принятие) синтаксического анализа LR:
    id ( id + id )
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top