На основе этих двух множеств строится k-предсказывающий алгоритм для МПА R({q},VT,V,d,q,S,{q}), где V=VTÈVN, S – целевой символ грамматики G, а функция переходов автомата строится на основе управляющей таблицы M, которую строят на базе правил грамматики.
Таблица M для LL(k) (k>0) отображает множество (VÈ{l})´VT*k (последнее обозначает цепочки длины не более k символов) на множество, состоящее из следующих элементов:
§ пар вида (b, i), где b – цепочка символов, помещаемая автоматом на верхушку стека, i – номер правила: (A®b)ÎR(i), AÎVN, bÎV*;
§ «выброс»;
§ «допуск»;
§ «ошибка».
Автомат имеет два стека (второй – для записи последовательности правил). Поскольку состояние распознавателя МПА q единственно, можно его не упоминать в конфигурациях; тогда конфигурация такого распознавателя будет иметь вид (a, L1, L2) – непрочитанная часть входной цепочки и содержимое обоих стеков.
Пусть аванцепочка (т.е. первые k символов входной цепочки) обозначена через w: w=FIRST(k,a), остаток входной цепочки – через a, символ на верхушке стека – через x.
Тогда алгоритм распознавания (построение d по M) содержит шаги:
§ (a, xg, m)├–(a, bg, m i), xÎVN, gÎV*; если M(x,w)=(b, i);
§ (aa’, xg, m)├–(a’, g, m), если x=aÎVT, a=aa’, M(a,w)= «выброс»;
§ (l,l,m) – завершение работы (с положительным результатом), если M(l,l)= «допуск»;
§ иначе завершение с ошибкой.
Рассмотрим класс LL(k)-грамматик на примере LL(1)-грамматик.
Алгоритм работы распознавателя для LL(1)-грамматик на вход получает текущий терминальный символ цепочки «a» и верхний символ стека. Возможны различные варианты работы распознавателя.
1. Построение таблицы M, описанной выше, и распознавание с помощью рассмотренного алгоритма. При этом построение таблицы упрощается, таблица отображает множество (VÈ{l})´(VTÈ{l}) на множество, состоящее из описанных элементов.
Построение таблицы M для LL(1):
1)
"a¹l, aÎFIRST(1,b): если (A®b)ÎR(i), то M(A,a)=(b,i);
"bÎFOLLOW(1,A): если
lÎ FIRST(1,b), то M(A,b)=(b,i);
2) M(a,a)= «выброс» для "aÎVT;
3) M(l,l)= «допуск»;
4) для всех остальных M(x,a)=«ошибка»: "xÎ(VÈ{l}), aÎ(VTÈ{l}).
2. Распознавание без предварительного построения таблицы; рассмотренный алгоритм модифицируется с учетом того, что аванцепочка состоит не более, чем из одного символа. В этом случае алгоритм можно описать так:
1) Если на верхушке стека находится нетерминальный символ A, то алгоритм должен выбрать альтернативу, для чего и проверяет два условия:
§ Если aÎFIRST(1,x), то в качестве альтернативы выбирается правило A®x.
§ Если aÎFOLLOW(1,A), то в качестве альтернативы выбирается правило A®l.
Если не выполняется ни одно из этих условий, то цепочка не принадлежит языку, о чём выдается соответствующее сообщение.
2) Если на верхушке стека находится терминальный символ «a», то выполняется шаг «выброса», на котором работа алгоритма остается без изменений – при совпадении символа «a» с текущим символом цепочки символ из стека удаляется, а считывающая головка смещается вправо на одну позицию. В противном случае цепочка не принимается.
Первый из рассмотренных вариантов распознавания более предпочтителен в случаях, когда требуется разбирать большое количество цепочек. Второй вариант не требует дополнительной памяти для размещения таблицы, но несколько медленнее осуществляет разбор.
Для того чтобы определить, относится ли грамматика к типу LL(1), необходимо и достаточно проверить условие: для каждого нетерминального символа, для которого существует более одного правила вида A ®a1½a2½…½an должно выполняться требование: " i ¹ j, n ³ i,j > 0 FIRST(1,aiFOLLOW(1,A)) Ç FIRST(1,ajFOLLOW(1,A))= Æ.
Если для символа A нет пустого правила, то это условие очевидным образом вырождается в стандартную проверку отсутствия пересечений множеств FIRST(1, ai) для различных ai.
Построение множества FIRST(1,a) выполняется очевидным образом, если цепочка a начинается с терминального символа. Иначе, если в a первый символ нетерминальный (т.е. a=Ax, xÎ(VTÈVN)*, AÎVN), то FIRST(1,a) = FIRST(1,A). После построения множества FIRST(1,A) строится FOLLOW(1,A).
1) Алгоритм построения множества FIRST(1,A):
Сначала требуется устранить из множества правил исходной грамматики пустые правила. Затем для всех нетерминальных символов полученной грамматики строятся множества FIRST(1,A). При построении используется метод последовательного приближения.
Шаг 1. Для всех нетерминалов AÎVN: FIRST0(1,A) = {X½(A®Ca)ÎR, CÎ(VTÈVN), aÎ(VTÈVN)*} – т.е. для каждого нетерминального символа A во множество заносим все символы, стоящие в начале правых частей правил для этого нетерминала; i:=1.
Шаг 2. Для всех AÎVN: FIRSTi+1(1,A) = FIRSTi(1,A)ÈFIRSTi(1,B) для всех нетерминалов BÎ (FIRSTi(1,A)ÇVN) – если в FIRSTi(1,A) есть нетерминальные символы B, то добавляем к нему FIRSTi(1,B).
Шаг 3. Если $ AÎVN: FIRSTi+1(1,A) ¹ FIRSTi(1,A), то i:=i+1 и вернуться к шагу 2, иначе перейти на шаг 4 (т.е. после предыдущего шага множество FIRSTi(1,A) хотя бы для одного нетерминала изменилось).
Шаг 4. Для всех AÎVN: FIRST(1,A) = FIRSTi(1,A)\VN (исключаем из построенных множеств все нетерминальные символы).
2) Алгоритм построения множества FOLLOW(1,A):
Множества FOLLOW(1,A) также строятся для всех нетерминальных символов грамматики методом последовательного приближения.
Шаг 1. Для всех AÎVN: FOLLOW0(1,A) = {X½$(B ® aAXb)ÎR, BÎVN, CÎ(VTÈVN), a,bÎ(VTÈVN)*}. Т.е. первоначально для каждого нетерминала A во множество FOLLOW0(1,A) вносим те символы, которые стоят непосредственно за A в правых частях правил; i:=0.
Шаг 2. FOLLOW0(1,S) = FOLLOW0(1,S) È{l} – вносим пустую цепочку во множество последующих символов для нетерминала S, это означает, что в конце разбора за целевым символом цепочка кончается.
Шаг 3. Для " AÎVN: FOLLOW¢i(1,A) = FOLLOWi(1,A) È FIRST(1,B), для всех нетерминальных символов BÎ(FOLLOWi(1,A) ÇVN).
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.