Основа

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

процесс можно рассматривать как «свертку» цепочки w к начальному символу грамматики. На каждом шаге свертки подцепочка, которую можно сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила вывода, и если на каждом шаге выбирается правильная подцепочка, то в обратном порядке прослеживается правосторонний вывод (рис.4.7). Здесь ко входной цепочке, так же как и при анализе LL(1)-грамматик, приписан концевой маркер $.

Рис. 4.7:

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

, не обязательно является основой, поскольку свертка по правилу A

может дать цепочку, которая не может быть сведена к аксиоме.

Формально, основа

правой сентенциальной формы z - это правило вывода A

и позиция в z, в которой может быть найдена цепочка

такие, что в результате замены

на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если S

, то A

в позиции, следующей за

, это основа цепочки

. Подцепочка

справа от основы содержит только терминальные символы.

Вообще говоря, грамматика может быть неоднозначной, поэтому не единственным может быть правосторонний вывод

и не единственной может быть

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

n, где

n - n-я правая сентенциальная форма еще неизвестного правого вывода S =

r...

n-1

n = w.

Чтобы

восстановить этот вывод в обратном порядке, выделяем основу

n в

n и заменяем

n на левую часть некоторого правила вывода An

n, получая (n - 1)-ю правую сентенциальную форму

n-1. Затем повторяем этот процесс, т.е. выделяем основу

n-1 в

n-1 и сворачиваем эту основу, получая правую сентенциальную форму

n-2. Если, повторяя этот процесс, мы получаем правую сентенциальную форму, состоящую только из начального символа S, то останавливаемся и сообщаем об успешном завершении разбора. Обращение последовательности правил, использованных в свертках, есть правый

вывод входной строки.

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

Содержание раздела

Главная сайта