Теория и реализация языков программирования

         

Основа


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


Рис. 4.5. 

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

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

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

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

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

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



Содержание  Назад  Вперед







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий