Как определить, является ли язык LL (1) LR (0) SLR (1)
На этот ответ уже ответили в этом комментарии , который также ссылается на Угловые документы , описывающие, как этого достичь.
6 ответов
Во-первых, немного педантизма. Вы не можете определить, является ли язык языком LL (1), проверяя его на наличие грамматики, вы можете только утверждать о самой грамматике . Вполне возможно написать грамматику без LL (1) для языков, для которых существует грамматика LL (1).
С этим по-другому:
-
Вы можете написать синтаксический анализатор для грамматики и иметь программу, которая сначала вычислит и будет следовать наборам и другим свойствам для вас. В конце концов, это большое преимущество грамматик БНФ, они машинно понятны.
-
Проверьте грамматику и найдите нарушения ограничений различных типов грамматики. Например: LL (1) допускает правую, но не левую рекурсию, поэтому грамматика, содержащая левую рекурсию, не является LL (1). (Что касается других грамматических свойств, вам придется потратить некоторое время на определения, потому что я не могу вспомнить что-либо еще в моей голове:).
В ответ на ваш главный вопрос: для очень простой грамматики можно определить, является ли она LL (1), без построения наборов FIRST и FOLLOW, например
A & rarr; А + А |
не является LL (1), а
A & rarr; а | b
is.
Но когда вы усложняете ситуацию, вам нужно провести некоторый анализ.
A & rarr; Б | a
B & rarr; A + A
Это не LL (1), но это может быть не сразу очевидно
Грамматические правила для арифметики быстро становятся очень сложными:
expr & rarr; термин {'+' термин}
термин & rarr; фактор {'*' фактор}
фактор & rarr; номер | '(' expr ')'
Эта грамматика обрабатывает только умножение и сложение, и уже не сразу ясно, является ли грамматика LL (1). Все еще можно оценить это, просматривая грамматику, но с ростом грамматики это становится менее осуществимым. Если мы определим грамматику для всего языка программирования, почти наверняка потребуется сложный анализ.
Тем не менее, есть несколько очевидных признаков того, что грамматика не является LL (1) & mdash; как A & rarr; A + A выше & mdash; и если вы сможете найти что-то из этого в своей грамматике, вы будете знать, что ее нужно переписать, если вы пишете парсер рекурсивного спуска. Но нет ярлыка для проверки того, что грамматика равна LL (1).
Одним из аспектов, «является неоднозначным язык / грамматика», является известный неразрешимый вопрос , например, Пост-переписка и , решение проблем .
Проверьте, является ли грамматика неоднозначной или нет. Если это так, то грамматика не является LL (1), потому что нет никакой неоднозначной грамматики LL (1).
у вас есть ярлыки для ll (1) грамматики
1) если A-> B1 | B2 | ....... | Bn, то первое (B1) пересечение, первое (B2) пересечение. first (Bn) = пустое множество, затем будет ll (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 )