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

     Грамматика G является LL(1)-грамматикой, т.к. для каждого нетерминала
А, имеющего альтернативные выводы, множества FIRST(1, A) попарно не пере-
секаются, а для нетерминала R они также не пересекаются со множеством
FOLLOW(1, R).
      Шаг 5. Разбор строки (a+(b-a)) для грамматики G показан в таблице 6.4.
      Таблица 6.4 - Разбор строки (a+(b-a)) для грамматики G
     Стек        Входной буфер                      Действие
S              (a+(b-a))          свертка S→TR, т.к. (∈ FIRST(1, TR)
TR             (a+(b-a))          свертка T→(S), т.к. (∈ FIRST(1, (S))
(S)R           (a+(b-a))          выброс
S)R            a+(b-a))           свертка S→TR, т.к. a∈ FIRST(1, TR)
TR)R           a+(b-a))           свертка T→a, т.к. a∈ FIRST(1, a)
aR)R           a+(b-a))           выброс
R)R            +(b-a))            свертка R→+TR, т.к. +∈ FIRST(1, TR)
+TR)R          +(b-a))            выброс
TR)R           (b-a))             свертка T→(S), т.к. (∈ FIRST(1, (S))
(S)R)R         (b-a))             выброс
S)R)R          b-a))              свертка S→TR, т.к. b∈ FIRST(1, TR)
TR)R)R         b-a))              свертка T→b, т.к. b∈ FIRST(1, b)
bR)R)R         b-a))              выброс
R)R)R          -a))               свертка R→-TR, т.к. -∈ FIRST(1, -TR)
-TR)R)R        -a))               выброс
TR)R)R         a))                свертка T→a, т.к. a∈ FIRST(1, a)
aR)R)R         a))                выброс
R)R)R          ))                 свертка R→ε, т.к. ) ∈ FOLLOW(1, R)
)R)R           ))                 выброс
R)R            )                  свертка R→ε, т.к. ) ∈ FOLLOW(1, R)
)R             )                  выброс
R              ε                  свертка R→ε, т.к. ε∈ FOLLOW(1, R)
ε              ε                  строка принята полностью

      Шаг 6. Получили следующую цепочку вывода:
      S⇒TR⇒(S)R⇒(TR)R⇒(aR)R⇒(a+TR)R⇒(a+(S)R)R⇒(a+(TR)R)R⇒
      ⇒(a+(bR)R)R⇒(a+(b-TR)R)R⇒(a+(b-aR)R)R⇒(a+(b-a)R)R⇒(a+(b-a))R
      ⇒(a+(b-a)).
      Нисходящее дерево разбора цепочки представлено на рисунке 6.1.

               Постановка задачи к лабораторной работе № 6
36