LL parser grammar

У меня есть эта грамматика ниже и пытаюсь выяснить, может ли быть проанализирован с использованием анализатора LL? Если нет, объясните.LL parser grammar

S --> ab | cB 
A --> b | Bb 
B --> aAb | cC 
C --> cA | Aba

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

Но я не уверен, с чего начать и просматривал свой учебник и http://en.wikipedia.org/wiki/LL_parser#Parsing_procedure, но не могу понять или найти какие-либо примеры для подражания. Мне просто нужно увидеть процедуру или шаги, чтобы понять, как делать другие подобные проблемы. Любая помощь приветствуется.

источник

2014-10-22 Jessica Dinh

Если есть левая рекурсия, анализатор LL (k) не может его разобрать. – Mephy

@Mephy: к сожалению, обратное не выполняется - даже если левая рекурсия отсутствует, это может быть не LL (k) –

Вычислить FIRST для всех нетерминалов и проверить, не пересекаются ли FIRST-сеты для альтернатив данного нетерминала. Если все есть, это LL, и если есть какие-то нетерминалы, для которых они нет, это не так. Если есть какие-либо проблемы; правила, вам понадобятся также FOLLOW.

Вычисление FIRST Наборы довольно просты и расскажут вам, является ли грамматика LL (1). Вычисление FIRST _k довольно много, но расскажет вам, является ли грамматика LL (k) для любого конкретного k вы рассчитываете FIRST k комплектов для.

источник

2014-10-22 02:39:13

Итак, первый набор для B является {a, c} и C является {c, b, a } и A - {b, a, c}. Я делаю это правильно? так что теперь будет S? –

@JessicaDinh Да, похоже, вы правильно вычислили FIRST-набор для A, B и C. И поскольку они не пересекаются, грамматика не является LL1-анализируемой. Теперь вы можете продолжать генерировать FIRST-наборы для больших Ks, пока не найдете подходящий K или не сдадитесь. Вам нужно было определить, была ли грамматика LL (1) или LL (K) для любого K? –

LL parser grammar

ответ

Смежные вопросы