Основа
В процессе разбора снизу-вверх типа сдвиг-свертка строится дерево разбора входной цепочки, начиная с листьев (снизу) к корню (вверх). Этот процесс можно рассматривать как "свертку" цепочки w к начальному символу грамматики. На каждом шаге свертки подцепочка, которую можно сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила вывода, и если на каждом шаге выбирается правильная подцепочка, то в обратном порядке прослеживается правосторонний вывод (рис. 4.5) Здесь ко входной цепочке, так же как и при анализе LL(1)-грамматик, приписан концевой маркер $.
Рис. 4.5. Основой цепочки называется подцепочка сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода. Самая левая подцепочка, которая сопоставляется правой части некоторого правила вывода A
?, не обязательно является основой, поскольку свертка по правилу A
? может дать цепочку, которая не может быть сведена к аксиоме.
Формально, основа правой сентенциальной формы z - это правило вывода A
? и позиция в z, в которой может быть найдена цепочка ? такие, что в результате замены ? на A получается предыдущая сентенциальная форма в правостороннем выводе z. Так, если
, то A
? в позиции, следующей за
, это основа цепочки
??. Подцепочка ? справа от основы содержит только терминальные символы.
Вообще говоря, грамматика может быть неоднозначной, поэтому не единственным может быть правосторонний вывод
?? и не единственной может быть основа. Если грамматика однозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу. Замена основы в сентенциальной форме на нетерминал левой части называется отсечением основы. Обращение правостороннего вывода может быть получено с помощью повторного применения отсечения основы, начиная с исходной цепочки w. Если w - слово в рассматриваемой грамматике, то w =
n, где
n - n-я правая сентенциальная форма еще неизвестного правого вывода
.
Чтобы восстановить этот вывод в обратном порядке, выделяем основу ?n в
n и заменяем ?n на левую часть некоторого правила вывода An
?n, получая (n - 1)-ю правую сентенциальную форму
n-1. Затем повторяем этот процесс, то есть выделяем основу ?n-1
в
n-1 и сворачиваем эту основу, получая правую сентенциальную форму
n-2. Если, повторяя этот процесс, мы получаем правую сентенциальную форму, состоящую только из начального символа S, то останавливаемся и сообщаем об успешном завершении разбора. Обращение последовательности правил, использованных в свертках, есть правый вывод входной строки.
Таким образом, главная задача анализатора типа сдвиг- свертка - это выделение и отсечение основы.
Содержание раздела
