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

Question

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

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

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

Answer 1

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

С этим из пути:

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

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

Answer 2

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

A & rarr; А + А | а

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

A & rarr; а | б

есть.

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

A & rarr; Б | а
B & rarr; A + A

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

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

expr & rarr; term {'+' term}
термин & rarr; фактор {'*' фактор}
фактор & rarr; номер | '(' expr ')'

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

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

Answer 3

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

Страница 223:

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

1. Если нет терминала "a", то и alpha , и beta получают строки, начинающиеся с "a"
2. Не более одного из alpha и beta могут получить пустую строку
3. Если beta может достичь пустого перехода через ноль или более переходов, то alpha не извлекает строку, начинающуюся с терминала в FOLLOW (A). Аналогично, если alpha может достичь пустого перехода через ноль или более переходов, то beta не извлекает строку, начинающуюся с терминала в FOLLOW (A)

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

Answer 4

Один аспект, «это неоднозначность языка / грамматики», это известный неразрешимый вопрос , такой как Почтовая переписка и прекращение проблем.

Answer 5

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

Answer 6

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

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

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

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

Answer 7

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 )