Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 34 стр.

      Шаг 3. Для всех А∈VN вычислить:
          FOLLOW′i(1,A)=FOLLOWi(1,A)∪FIRST(1,B),∀B∈(FOLLOWi(1,A)∩VN).
      Шаг 4. Для всех А∈VN положить:
          FOLLOW″i(1, A)=FOLLOW′i(1, A)∪FOLLOW′i(1, B),
           ∀B∈(FOLLOW′i(1, A)∩VN), если ∃ правило B→ε.
      Шаг 5. Для всех А∈VN определить:
            FOLLOWi+1(1, A) = FOLLOW″i(1, A)∪FOLLOW″i(1, B),
            для всех нетерминальных символов B∈VN, имеющих правило вида
            B→αA, α∈(VT∪VN)*.
      Шаг 6. Если существует A∈VN такой, что FOLLOWi+1(1,A)≠FOLLOWi(1,A),
то положить i:=i+1 и вернуться к шагу 3, иначе перейти к шагу 7.
      Шаг 7. Исключить из построенных множеств все нетерминальные симво-
лы, т.е. ∀ A∈VN FOLLOW(1, A) = FOLLOWi(1, A)\ N.
            Алгоритм 6.3. Функционирование распознавателя цепочек
                             для LL(1)-грамматик
      Шаг 1. Помещаем в стек начальный символ грамматики S, а во входной
буфер исходную цепочку символов.
      Шаг 2. До тех пор пока в стеке и во входном буфере останется только
пустая строка ε либо будет обнаружена ошибка в алгоритме разбора, выполня-
ем одно из следующих действий:
      - если на верхушке стека находится нетерминальный символ А и оче-
редной символ входной строки символ а, то выполняем операцию «свертка» по
правилу А→х при условии, что а∈FIRST(1, x), т.е. извлекаем из стека символ А
и заносим в стек строку х, не меняя содержимого входного буфера;
      - если на верхушке стека находится нетерминальный символ А и оче-
редной символ входной строки символ а, то выполняем операцию «свертка» по
правилу А→ε при условии, что а∈FOLLOW(1, A), т.е. извлекаем из стека сим-
вол А и заносим в стек строку ε, не меняя содержимого входного буфера;
      - если на верхушке стека находится терминальный символ а, совпадаю-
щий с очередным символом входной строки, то выполняем операцию «вы-
брос», т.е. удаляем из стека и входного буфера данный терминальный символ;
      - если содержимое стека и входного буфера пусто, то исходная строка
прочитана полностью, и разбор завершен удачно;
      - если ни одно из данных условий не выполнено, то цепочка не принад-
лежит заданному языку, и алгоритм завершает свою работу с ошибкой.
      Пример 6.1. Дана грамматика G ({S, T, R}, {+, -, (, ), a, b}, P, S), с прави-
лами P: 1) S→TR; 2) R→ε | +TR | - TR; 3) T→(S) | a | b. Построить распознаватель
для строки (a+(b-a)) языка грамматики G.

34