Основы конструирования компиляторов

Основа


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

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


Рис. 4.7:

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

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

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

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

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

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

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

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

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

, это основа цепочки
. Подцепочка
справа от основы содержит только терминальные символы.

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

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

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

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


Чтобы

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

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

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


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