Отношения предшествования

Вспомним восходящий разбор. При применении любых из методов восходящего разбора возникает вопрос, как найти основу и выяснить, к какому нетерминалу нужно её приводить Мы рассмотрим этот вопрос для определённого класса грамматик называемых грамматиками простого предшествования (грамматики класса 2 по Холмскому или LL1 грамматики).

Как же найти основу, если задача сентенциальная форма x? Хотелось бы, двигаясь слева направо и по любым только двум соседних символам, одновременно суметь определить: нашли ли мы хвост основы. А затем, двигаясь назад к левому концу сентенциальной формы, найти голову основы, опять принимая каждый раз решение только по двум соседним символам.

Пусть U, C, D - нетерминальные символы, x, y, z, w – любые цепочки, возможно пустые.

Грамматикой предшествования называют грамматику, в которой:

1) Для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более, чем одно из трёх отношений предшествования, определяемых следующим образом:

А) S_i S_j, если и только есть правило U -> xS_iS_jy

Б) S_i S_j, если и только есть правило U->xS_iDy и вывод D=>*S_jz.

В) S_i S_j, если и только есть правило U->x c S_jy и вывод С=>*zS_i или правило U ->x c Dy и выводы С=>*zS_i; D=>*S_jw.

Заметим, что между любыми двумя (2) соседними символами S_i и S_j приводимой строки могут существовать лишь 3 отношения:

S_i S_i, если символ S_i – самый левый символ некоторой основы S_i S_j…

S_i- основа

S_i S_i+1, если символ S_i - самый правый символ основы …S_i S_i+1. (…S_i - основа)

S+ S_i+1, если символы S_i и S_i+1 принадлежат одной основе … S_iS_i+1… - основа

Отношения предшествования зависят от порядка, в котором стоят символы и из S_i S_j не следует S_j S_i.

2) Разные порождающие правила имеют различные правые части.

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

Дата добавления: 2014-01-11