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

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

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

Метод:

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

[AK1]