3.2.7. Рекурсивный спуск

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

Процедуры рекурсивного спуска могут быть записаны, как это изображено на рис. 3.9. В процедуре N для случая, когда имеется альтернатива N -> u_i -> *e (не может быть более одной альтернативы, из которой выводится e), приведены два варианта 1.1 и 1.2. В варианте 1.1 делается проверка, принадлежит ли следующий входной символ FOLLOW(N). Если нет - выдается ошибка. Во втором варианте этого не делается, так что анализ ошибки откладывается на процедуру, вызвавшую N.

Рис. 3.9

3.3. Разбор снизу-вверх типа сдвиг-свертка

3.3.1. Основа

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

Пример 3.5. Рассмотрим грамматику арифметических выражений, приведенную на рис.3.14 а). Строка a+b*c может быть сведена к S, как показано на рис.3.14.б). Дерево этой строки приведено на рис.3.14 в).

В строке a+b*c ищется подстрока, которую можно сопоставить с правой частью некоторого правила вывода. Этому удовлетворяют подстроки a, b и c. Если выбрать самое левое a и заменить его на F - левую часть правила F -> id , то получим строку F+b*c . Теперь правой части того же правила можно сопоставить подстроки b и c. Эти свертки представляют собой в обратном порядке правосторонний вывод:

Подстрока сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода, называется основой строки. В приведенном выше выводе основы подчеркнуты. Самая левая подстрока, которая сопоставляется правой части некоторого правила вывода A -> v , не обязательно является основой, поскольку свертка по правилу A -> v может дать строку, которая не может быть сведена к аксиоме. Если, скажем, в примере 3.5 заменить a на F и b на F, то получим строку F+F*c , которая не может быть сведена к S.

Формально, основа правой сентенциальной формы z - это правило вывода A -> v и позиция в z, в которой может быть найдена строка v такие, что в результате замены v на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если S *uAw uvw , то A -> w в позиции, следующей за u, это основа строки uvw. Строка w справа от основы содержит только терминальные символы. Вообще говоря, грамматика может быть неоднозначной, поэтому не единственным может быть правосторонний вывод uvw и не единственной может быть основа. Если грамматика однозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу.

Замена основы в сентенциальной форме на нетерминал левой части называется отсечением основы. Обращение правостороннего вывода может быть получено с помощью повторного применения отсечения основы, начиная с разбираемой строки w. Если w - слово в рассматриваемой грамматике, то w = Z_n,n -я правая сентенциальная форма еще неизвестного правого вывода

S z₀ z₁ z₂ ... z_n-1 z_n =w

Чтобы восстановить этот вывод в обратном порядке, выделяем основу V_n в Z_n и заменяем V_n на левую часть некоторого правила вывода A_n -> V_n , получая (n-1) -ю правую сентенциальную форму Z_n-1 . Затем повторяем этот процесс, т.е. выделяем основу em>V_n-1 в em>Z_n-1 и сворачиваем эту основу, получая правую сентенциальную форму em>Z_n-2 . Если, повторяя этот процесс, мы получаем правую сентенциальную форму, состоящую только из начального символа S, то останавливаемся и сообщаем об успешном завершении разбора. Обращение последовательности правил, использованных в свертках, есть правый вывод входной строки.

Таким образом, главная задача анализатора типа сдвиг-свертка - это выделение и отсечение основы.