Разработка компиляторов. Ишакова Е.Н. - 20 стр.

символ грамматики, а целевой – заданная строка языка. На каждом шаге разбо-
ра правило грамматики применяется к самому левому нетерминалу сентенции.
Данный процесс соответствует построению дерева разбора цепочки сверху вниз
(от корня к листьям).
      Пример 2.8. Дана грамматика G ({a, b, c, ⊥}, {S , A, B}, P, S ) с правилами
P : 1) S → AB ⊥; 2) A → a; 3) A → cA; 4) B → bA . Требуется выполнить
анализ строки cabca⊥.
      Левосторонний вывод цепочки имеет вид:
      S ⇒ AB ⊥⇒ cAB ⊥⇒ caB ⊥⇒ cabA ⊥⇒ cabcA ⊥⇒ cabca ⊥ .
      Нисходящее дерево разбора цепочки представлено на рисунке 2.6.

                              S


                      A           B       ⊥


             c            A       b       A


                  a                   c           A


                                              a


             Рисунок 2.6 – Дерево нисходящего разбора цепочки cabca⊥

      Метод рекурсивного спуска реализует разбор цепочки сверху вниз сле-
дующим образом. Для каждого нетерминального символа грамматики создает-
ся своя процедура, носящая его имя. Задача этой процедуры – начиная с ука-
занного места исходной цепочки, найти подцепочку, которая выводится из это-
го нетерминала. Если такую подцепочку считать не удается, то процедура за-
вершает свою работу вызовом процедуры обработки ошибок, которая выдает
сообщение о том, что цепочка не принадлежит языку грамматики и останавли-
вает разбор. Если подцепочку удалось найти, то работа процедуры считается
нормально завершенной и осуществляется возврат в точку вызова. Тело каждой
такой процедуры составляется непосредственно по правилам вывода соответст-
вующего нетерминала, при этом терминалы распознаются самой процедурой, а
нетерминалам соответствуют вызовы процедур, носящих их имена.
      Пример 2.9. Построим синтаксический анализатор методом рекурсивного
спуска для грамматики G из примера 2.8.
      Введем следующие обозначения:
      1) СH – текущий символ исходной строки;

                                                                              20