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

                 Алгоритм 7.2. Построение множеств L(A) и R(A)
      Шаг 1. Для каждого нетерминального символа А ищем все правила, со-
держание А в левой части. Во множество L(A) включаем самый левый символ
из правой части правил, а во множество R(A) – самый крайний правый символ
из правой части, т.е.
           ∀ A ∈VN: L0(A) = {X | A→Xy, X ∈ V, y ∈ V*},
                    R0(A) = {X | A→yX, X ∈ V, y ∈ V*}.
      Шаг 2. Для каждого нетерминального символа А: если множество L(A)
содержит нетерминальные символы грамматики А′, A″, …, то множество L(A)
надо дополнить символами, входящими в соответствующие множества L(А′),
L(A″) и т.д., … и не входящими в L(A). Аналогичную операцию выполнить для
множеств R(A), т.е.
           ∀ A ∈ VN: Li(A) = Li-1(A)∪Li-1(B), ∀ B ∈ (Li-1(A)∩ VN),
                     Ri(A) = Ri-1(A)∪Ri-1(B), ∀ B ∈ (Ri-1(A)∩ VN).
      Шаг 3. Если на предыдущем шаге хотя бы одно множество L(A) или R(A)
для некоторого символа грамматики изменилось, то вернуться к шагу 2, иначе
построение закончено. Т.е. если существует A∈VN: Ri(A)≠Ri-1(A) или
Li(A)≠Li-1(A), то положить i:=i+1 и вернуться к шагу 2, иначе построение закон-
чено и R(A) = Ri(A) и L(A) = Li(A).
       Алгоритм 7.3. Функционирование распознавателя для грамматик
                         простого предшествования
      Шаг 1. Поместить в верхушку стека символ ⊥н, считывающую головку – в
начало входной цепочки символов.
      Шаг 2. До тех пор, пока не будет обнаружена ошибка, либо успешно за-
вершен алгоритм разбора, сравниваем отношение простого предшествования
символа на верхушке стека и очередного символа входной строки. При этом
возможны следующие ситуации:
      - если самый верхний символ стека имеет меньшее или равное предше-
ствование, чем очередной символ входной строки, то производим операцию
«сдвиг» (перенос текущего символа из входной цепочки в стек и перемещение
считывающей головки на один символ вправо);
      - если самый верхний символ стека имеет большее предшествование,
чем очередной символ входной строки, то выполняем операцию «свертка». Для
этого находим на верхушке стека «основу» сентенции, т.е. все символы, имею-
щие равное предшествование или один символ на верхушке стека. Символы ос-
новы удаляем из стека, выбираем правило вывода грамматики, имеющее пра-
вую часть, совпадающую с основой, и помещаем в стек левую часть выбранно-
го правила. Если такого правила вывода найти не удалось, то выдается сообще-
ние об ошибке, и разбор завершен неудачно;


40