Глава 5.

синтаксический анализ сверху

вниз

В этой главе мы рассмотрим методы разбора снизу вверх в целом и опишем один конкретный метод (LR-разбор), который применим к широкому классу языков и грамматик. Мы покажем, как автоматически построить синтаксический анализатор на основании LR-грамматики, и дадим сравнительную оценку достоинств LL- и LR-методов разбора (в последнем разделе).

5.1. Разбор снизу вверх

Как уже отмечалось, синтаксические анализаторы, работающие по принципу "снизу вверх", сводят предложение языка к начальному символу путем последовательного применения правил грамматики. Рассмотрим, например, язык, генерируемый правилами

(1) Sreal 1DL1ST

(2) 1DL1ST MIDLIST, ID

(3) IDLISTID

(4) idabcd

(для простоты примем (4) за одно порождающее правило). Предложение

real A, B, C

принадлежит этому языку и может быть разобрано снизу вверх следующим образом. Каждый символ, считанный анализатором, немедленно помещается в верхнюю часть стека анализатора. Например, считывается real и помещается в стек. Первые два действия анализатора схематически показываются так:

real ФА, B, C

Real

real Аф, B, C

А real

Здесь стрелка ставится непосредственно после последнего считанного символа. Затем анализатор заменяет А с помощью правила (4). Это действие известно как приведение. В разборе снизу вверх правила применяются иначе, чем в разборе

сверху вниз, т.е. правые части правил заменяются их соответствующими левыми частями. Представим приведение схематически:

real Аф, B, C

Далее применяется правило (3) для другого приведения:

ID real

real Аф, B, C

IDLIST real

Теперь анализатор читает следующий символ:

real А, ФВ, C

IDLIST real

и другой:

real А, Вф, C

IDLIST

real

Очередные два действия - приведения с использованием правил (4) и (2):

real А, Вф, C

ID IDLIST

real

real А, Вф, C

IDLIST

real

и последующим считыванием еще двух символов:

real A, B, фС

IDLIST real

real A, B, Сф

IDLIST

real

Последние три действия - приведения с использованием правил (4), (2) и (1):

real А, B, Сф

ID IDLIST

real

real А, B, Сф

IDLIST

real

real А, B, Сф

Разбор считается завершенным, когда в стеке остается только начальный символ и предложение считано целиком. Стек разбора соответствует части автомата магазинного типа, описанного в гл.4.

Синтаксический анализатор, работающий по принципу "снизу вверх", выполняет действия двух типов:

1) сдвиг, во время которого считывается и помещается в стек символ. Это соответствует продвижению на один пункт вдоль какого-либо правила грамматики;

2) приведение, во время которого множество элементов в верхней части стека замещаются каким-либо нетерминалом грамматики с помощью одного из порождающих правил этой грамматики.

Методы разбора снизу вверх почти всегда детерминированные, и перед анализатором стоит единственная задача: знать в конкретной ситуации, какое действие (сдвиг или приведение) выполнять. Если возможны два варианта