Реферат: LL(k) - Грамматики

По отношению к произвольной данной грамматике G возникает ряд естественных вопросов:

(1) Является ли G LL (k)- грамматикой для данного k ?

(2) Существует ли такое k, что G - LL (k)- грамматика?

(3) Так как для LL (1) левые разборы строятся особенно просто, то если G не LL (1)- грамматика, то существует ли эквивалентная ей LL (1)- грамматика G’ , для которой L(G ) = L(G’ )?

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

АЛГ 4: Проверка LL (k)- условия.

Вход: КС- грамматика G =(N ,E ,P ,S ) и целое число k.

Выход: «Да» - если G - LL (k)- грамматика и «Нет» в противном случае.

Метод:

Суть алгоритма сводится к следующему: Для каждого нетерминала, имеющего два или более правила раскрутки вычисляется пересечение первых k- символов всех возможных цепочек раскрутки. Если это множество пусто, то переходят к следующему терминалу, иначе заканчивают со значением «Нет». Если все пересечения пусты - заканчивают со значением «Да». Для получения пересечения двух правил можно воспользоваться записью: (FIRSTk(b` ) ÅkL)Ç(FIRSTk(c` ) ÅkL), где L=FIRSTk(a` ) и a` - цепочка символов после терминала.

[AK1]