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

Ответ 1

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

С учетом этого:

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

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

Ответ 2

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

A → A + A | а

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

A → a | б

есть.

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

A → B |
B → A + A

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

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

expr → term {'+' term}
term → фактор {'*' factor}
фактор → номер | '(' expr ')'

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

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

Ответ 3

Один аспект, "язык/грамматика неоднозначный", известный неразрешимый вопрос, например Post post и halting проблемы.

Ответ 4

Прямо из книги "Составители: принципы, методы и инструменты" от Aho, et. и др.

Страница 223:

грамматика G является LL (1) тогда и только тогда, когда, когда A → alpha | бета - два разных произведения G, выполняются следующие условия:

• Для терминалов "a" не выполняются строки alpha и beta, начинающиеся с "a"
• В большинстве случаев альфа и бета могут выводить пустую строку
• Если бета может достигать пустого перехода через ноль или более переходов, то альфа не выводит ни одной строки, начинающейся с терминала в FOLLOW (A). Аналогично, если альфа может достичь пустого перехода через ноль или более переходов, то бета не выводит ни одной строки, начинающейся с терминала в FOLLOW (A)

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

Ответ 5

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

Ответ 6

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

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

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

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

Ответ 7

p0 S' → E
p1 E → id
p2 E → id ( E )
p3 E → E + id

• Создайте LR (0) DFA, FOLLOW, установленный для E и таблиц SLR/goto.
• Является ли это грамматикой LR (0)? Докажите свой ответ.
• Используя таблицы SLR, покажите шаги (сдвиги, сокращения, принятие) анализа парсера LR:
  id ( id + id )