Определение грамматики операторного предшествования

ОпределениеКС-грамматика G (V_N, V_T, P, S) называется грамматикой операторного предшествования, если выполняются следующие условия:

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

а) а =× b, если и только если существует правило A—>xaby ÎР или правило А->хаСbу, где a,bÎV_T, A,C ÎV_N, x.yÎV*;

б) а <× b, если и только если существует правило А->хаСу ÎР и вывод C=>*bz или вывод C=>*Dbz, где a,bÎV_T, A,C,DÎV_N, x,y,zÎV*;

в) а ×> b, если и только если существует правило А—>хСЬу ÎР и вывод C=>*za или вывод C=>*zaD, где a,bÎV_T, A,C,DÎV_N, x,y,zÎV*.

2) Различные правила в грамматике имеют разные правые части, e-правила от­сутствуют.

3) Правила грамматики операторного предшествования не могут содержать двух смежных нетерминальных символов в правой части, т.е. в грамматике опера­торного предшествования G(V_N,V_T,P,S) не может быть ни одного правила вида: А->хВСу, где A,B,CÎV_N, x,yÎV* (здесь х и у — это произвольные цепочки символов, могут быть и пустыми).

3.5.1.2.2 Построение множеств L^t(A) и R^t(A)

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

Для грамматики данного вида на основе установленных отношений предшествования также строится матрица предшествования, но она содержит только терминальные символы грамматики.

Для построения этой матрицы удобно ввести множества крайних левых и крайних правых терминальных символов относительно нетерминального символаА – L^t(A) или R^t(A):

L^t(A) = {t | A=>*tz или A=>*Ctz }, где tÎV_T,A.CÎV_N, zÎV*;

R^t(A)= {t | A=>*zt или A=>*ztC }, где tÎVT, A,CÎVN, zÎV*.

Тогда определения отношений операторного предшествования будут выглядеть так:

а) а =× b, если правило A→xaby ÎР или правило U->xaCby, где a,bÎV_T, А,СÎV_N х,уÎV*;

б) а <× b, если правило А→хаСу ÎР и bÎ L^t (C), где a,bÎV_T, A,CÎV_N, x,yÎV*;

в) а ×> b, если правило A→xCby ÎР и aÎ R^t(C), где a,bÎVT, A,CÎV_N, x,yÎV*.

В данных определениях цепочки символов x,y,z могут быть и пустыми цепочками.

Для нахождения множеств L^t(A) и R^t(A)предварительно необходимо выполнить построение множеств L(A) и R(A), как это было рассмотрено ранее. Далее для построения L^t(A) и R^t(A) используется следующий алгоритм:

Шаг 1. AÎV_N:

R^t₀(A){t | A→ytB или A→yt, tÎV_T, BÎV_N, yÎV*;

L^t₀(A){t | A→Bty или A→ty, tÎV_T, BÎV_N, yÎV*;

Для каждого нетерминального символа А ищем все правила, содержащие А в левой части. Во множество L(A) включаем самый левый терминальный символ изправой части правил, игнорируя нетерминальные символы, а во множество R(А) - самый крайний правый терминальный символ из правой части правил. Переходим к шагу 2.

Шаг 2. AÎV_N:

R^t_i(A) = R^t_i-1(A) R^t_i-1 (B), В Î (R(A) V_N),

L^t_i(А) = L^t_i-1(A) L^t_i-1(B), В Î (L(A) VN).

Для каждого нетерминального символа А: если множество L(A) содержит нетерминальные символы грамматики А', А", ..., то его надо дополнить символами входящими в соответствующие множества L ^t(А’), L ^t(A"), ... и не входящими в L ^t(А). Ту же операцию надо выполнить для множеств R(A) и R^t(А).

Шаг З. Если AÎV_N : R^t_i(A) R^t_i-1(Aили L^t_i(А) L^t_i-1(A), то i:=i+1 и вернутсяк шагу 2, иначе построение закончено: R^t(A) = R^t_i(A) и L^t(A) = L^t_i(А).

Если на предыдущем шаге хотя бы одно множество R^t(A) или L^t(A) для некоторого символа грамматики изменилось, то надо вернуться к шагу 2, иначе построение закончено.

Для практического использования матрицу предшествования дополняют символами и ( начало и конец цепочки). Для них определены следующие отношения предшествования:

<· a, aÎV_T, если S=>*ax или S=>*Cax, где S,CÎV_N, xÎV* или если aÎ L^t(S);

·> а, aÎV_T, если S=>*xa или S=>*xaC, где S,CÎV_N, xÎV* или если aÎ R^t(S).

Здесь S — целевой символ грамматики.

Матрица предшествования служит основой для работы распознавателя языка, заданного грамматикой операторного предшествования. Поскольку она содержит только терминальные символы, то, следовательно, будет иметь меньший размер, чем аналогичная матрица для грамматики простого предшествования. Следует отметить, что напрямую сравнивать матрицы двух грамматик нельзя — не всякая грамматика простого предшествования является грамматикой операторного пред­шествования, и наоборот.

3.5.1.2.4 Алгоритм «сдвиг-свертка» для грамматики операторного предшествования

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

Алгоритм состоит из следующих шагов.

Шаг 1. Поместить в верхушку стека символ , считывающую головку — в нача­ло входной цепочки символов.

Шаг 2. Сравнить с помощью отношения предшествования терминальный сим­вол, ближайший к вершине стека (левый символ отношения), с текущим симво­лом входной цепочки, обозреваемым считывающей головкой (правый символ отношения). При этом из стека надо выбрать самый верхний терминальный сим­вол, игнорируя все возможные нетерминальные символы.

Шаг 3. Если имеет место отношение <· или =×, то произвести сдвиг (перенос то­щего символа из входной цепочки в стек и сдвиг считывающей головки на один шаг вправо) и вернуться к шагу 2. Иначе перейти к шагу 4.

Шаг 4. Если имеет место отношение ·>, то произвести свертку. Для этого надо найти на вершине стека все терминальные символы, связанные отношение («основу»), а также все соседствующие с ними нетерминальные символы (при определении отношения нетерминальные символы игнорируются). Если терминальных символов, связанных отношением =×, на верхушке стека нет, то в качестве основы используется один, самый верхний в стеке терминальный символ сте­ка. Все (и терминальные, и нетерминальные) символы, составляющие основу надо удалить из стека, а затем выбрать из грамматики правило, имеющее правую часть, совпадающую с основой, и поместить в стек левую часть выбранного правила. Если правило, совпадающее с основой, найти не удалось, то необходимо прервать выполнение алгоритма и сообщить об ошибке, иначе, если разбор не за­кончен, то вернуться к шагу 2.

Шаг 5. Если не установлено ни одно отношение предшествования между текущим символом входной цепочки и самым верхним терминальным символом в стеке, то надо прервать выполнение алгоритма и сообщить об ошибке.

Конечная конфигурация данного МП-автомата совпадает с конфигурацией при распознавании цепочек грамматик простого предшествования.

Пример

Дано: G({(, ), ^, &, ~, a}, {S, T, E, F}, P, S), где

P: S→S^T | T

T→T&E | E

E→~E | F

F→ (E) | a

Построить: распознаватель для G.

Таблица 3.10 - Построение множеств L(A) и R(A)

Таблица 3.11 - Построение множеств Lt(A) и Rt(A)

Таблица 3.12 - Матрица операторного предшествования символов грамматики

Символы	^	&	~	(	)	а
^	·>	<·	<·	<·	·>	<·	·>
&	·>	·>	<·	<·	·>	<·	·>
~	·>	·>	<·	<·	·>	<·	·>
(	<·	<·	<·	<·	=×	<·
)	·>	·>			·>		·>
а	·>	·>			·>		·>
	<·	<·	<·	<·		<·

Для ^ находящейся в правиле вывода слева от нетерминала Т, во множество Lt(Т) входят символы &, ~, (, a , значит в строке матрицы для ^ ставим знак меньшего предшествования в позициях этих символов. С другой стороны этот символ ^ находится справа от S. Во множество Rt(S) входят символы ^, &, ~, ), a, значит знак большего предшествования ставится в столбце для ^ в позициях этих символов. Символы ( и ) в правиле вывода находятся радом, поэтому в позиции этих символов ставится знак равного предшествования (игнорируя нетерминал Е).