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

ОПР: Пусть G =(N ,E ,P ,S ) - КС-грамматика. Определим FOLLOWk(b` ) как множество терминальных символов, которые могут встречаться после нетеминала, являющегося аргументом функции.

ТРМ: КС-грамматика G =(N ,E ,P ,S ) является LL (1)-грамматикой тогда и только тогда, когда для двух различных правил A ®b` и A ®c` пересечение FIRST1(b` FOLLOW1(A))ÇFIRST1(c` FOLLOW1(A)) пусто при всех AÎN . (Без ДКВ ).

Теорему можно выразить следующим : по первому символу после нетерминала необходимо выбрать применимое правило - следовательно эти символы различны и пересечение пусто. Эта теорема может применяться к LL (k)- грамматикам, но не всегда выполняться. Грамматики для которых выполняется теорема называются сильными, таким образом все LL (1) грамматики - сильные. Необходимо так же заметить что каждая LL (k)- грамматика однозначна, поэтому если имеется неоднозначная грамматика - то она не LL (k). Имеется неразрешимая проблема распознавания, существует ли для данной КС-грамматики G , не являющейся LL (k), эквивалентная ей LL (k)- грамматика. Однако в ряде случаев такое преобразование возможно. Применяется два способа:

Первый способ - устранение левой рекурсии .

ПРМ: Пусть G - грамматика S ®S a|b которая не является LL- грамматикой. Заменим правила на следующие:

S ®bS`

S` ®aS` |e

получив при этом эквивалентную LL (1)- грамматику.

Другой способ - левая факторизация .

ПРМ: Рассмотрим LL (2)- грамматику G с двумя правилами S ®aS |a. В этих двух правилах «вынесем влево за скобки» символ a, записав их в виде S ®a(S |e ). Иными словами, мы считаем что операция конкатенации дистрибутивна относительно операции выбора альтернативы (обозначаемой вертикальной чертой). Заменим эти правила на :

S ®aA

A®S |e

тем самым получим эквивалентную LL (1)-грамматику.

Разбор для LL(1)- грамматик.

Ядром предсказывающего алгоритма является управляющая таблица. В этом и следующих разделах будет показано как построить корректную управляющую таблицу.

АЛГ 1: Управляющая таблица для LL (1)-грамматики.

Вход : LL (1)- грамматика .

Выход : Корректная управляющая таблица.

Метод : Будем считать, что $-маркер дна магазина. Таблица определяется следующим образом:

(1) Если A ® a` - правило из P с номером i, то M[A,a]=(a` ,i) для всех a¹e, принадлежащих FIRST1(a` ). Если e ÎFIRST1(a` ), то M[A,b]=(a` ,i) для всех bÎFOLLOW1(A).

(2) M[a,a]=выброс для всех aÎE.

(3) M[$,e ]=допуск.

(4) В остальных случаях M[X,a]=ошибка для XÎNÈEÈ{$} и aÎEÈ{e}.

ТРМ: Предложенный алгоритм строит корректную управляющую таблицу для LL (1)- грамматики G .

Разбор для LL(k)- грамматик.

Построим управляющую таблицу для произвольной грамматики. Если грамматика сильная, то можно применить предыдущий алгоритм с аванцепочками расширенными до k символов. В противном случае возникает несколько проблем. В 1-м предсказывающем алгоритме разбора в магазин помещались только символы из E ÈN и оказывалось, что для однозначного определения очередного применяемого правила достаточно знать нетерминальный символ наверху магазина и текущий входной символ. Для не сильных грамматик этого может оказаться недостаточно.

ПРМ: Возьмем грамматику

S ®aAaa|bAba

A®b|e