Программирование: теоремы и задачи (стр. 35 )

налы справа от K можно заменить на терминалы (а слева от K при

этом ничего не изменится).

14.1.6. Построить грамматику, содержащую для каждого нетер-

минала K исходной граммaтики нетерминал <ЛевK>, причем следующее

свойство должно выполняться для любого нетерминала K исходной

грамматики: в новой грамматике из <ЛевK> выводимы все элементы

Лев(K) и только они.

Решение. Пусть P - начальный нетерминал грамматики. Тогда в

новой грамматике будет правило

<ЛевP> -> (пустое слово)

Для каждого правила исходной грамматики, например, правила

K -> L t M N (L, M, N - нетерминалы, t - терминал),

в новую грамматику мы добавим правила

<ЛевL> -> <ЛевK>

<ЛевM> -> <ЛевК> L t

<ЛевN> -> <ЛевK> L t M

и аналогично поступим с другими правилами. Смысл новых правил

таков: пустое слово может появиться слева от P; если слово X мо-

жет появиться слева от K, то X может появиться слева от L, XLt

может появиться слева от M, XLtM - слева от N. Индукцией по дли-

не правого вывода легко проверить, что все, что может появиться

слева от какого-то нетерминала, появляется в соответствии с эти-

ми правилами.

14.1.7. Почему в предыдущей задаче важно, что мы рассматри-

ваем только правые выводы?

Ответ. В противном случае следовало бы учитывать преобразо-

вания, происходящие внутри слова, стоящего слева от K.

14.1.8. Для данной грамматики построить алгоритм, который

по любому слову выясняет, каким из множеств Лев(K) оно принадле-

жит.

(Замечание для знатоков. Существование такого алгоритма - и

даже конечного автомата, т. е. индуктивного расширения с конечным

числом значений, - вытекает из предыдущей задачи, т. к. построен-

ная в ней грамматика имеет специальный вид: в правых частях ее

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

нее мы приведем явное построение.)

Решение. Будем называть ситуацией данной грамматики одно из

ее правил, в правой части которого отмечена одна из позиций (до

первой буквы, между первой и второй буквой,..., после последней

буквы). Например, правило

K -> L t M N (K, L, M, N - нетерминалы, t - терминал)

порождает пять ситуаций

К -> _LtMN, K-> L_tMN, K-> Lt_MN, K-> LtM_N, K -> LtMN_.

(позиция указывается знаком подчеркивания).

Будем говорить, что слово S согласовано с ситуацией K->U_V,

если S кончается на U, то есть S=TU при некотором T, и, кроме

того, T принадлежит Лев(K). (Смысл этого определения примерно

таков: в стеке S подготовлена часть U для будущей свертки UV в

K.) В этих терминах ЛевКонт(K->X) - это множество всех слов,

согласованных с ситуацией K->X_, а Лев(К) - это множество всех

слов, согласованных с ситуацией K->_X (где K->_X - любое правило

для нетерминала K).

Эквивалентное определение в терминах LR-процесса: S согла-

совано с ситуацией K->U_V, если существует успешный LR-процесс,

в котором события развиваются так:

- в ходе процесса в стеке появляется слово S, и оно оканчи-

чивается на U;

- некоторое время S не затрагивается, а справа от него по-

является V;

- UV сворачивается в K;

- процесс продолжается и успешно завершается.

14.1.9. Доказать эквивалентность этих определений.

Указание. Если S=TU и T принадлежит Лев(K), то можно полу-

чить в стеке сначала T, потом U, потом V, потом свернем UV в K и

затем успешно завершим процесс. (Мы используем несколько раз тот

факт, что из любого нетерминала что-то да выводится: благодаря

этому мы можем добавить в стек любое слово.)

Наша цель - построение алгоритма, распознающего принадлеж-

ность произвольного слова к Лев(K). Рассмотрим функцию, сопос-

тавляющую с каждым словом S (из терминалов и нетерминалов) мно-

жество всех согласованных с ним ситуаций. Это множество называют

состоянием, соответствующим слову S. Будем обозначать его

Сост(S). Достаточно показать, что функция Сост(S) индуктивна,

т. е. что значение Сост(SJ), где J - терминал или нетерминал, мо-

жет быть вычислено, если известно Сост(S) и символ J. (Мы видели

ранее, как принадлежность к Лев(К) выражается в терминах этой

функции.) Значение Сост(SJ) вычисляется по таким правилам:

(1) Если слово S было согласовано с ситуацией K->U_V, при-

чем слово V начиналось на букву J, то есть V=JW, то теперь слово

SJ будет согласовано с ситуацией K->UJ_W.

Это правило полностью определяет все ситуации с непустой

левой половиной (то есть не начинающиеся с подчеркивания), сог-

ласованные с SJ. Осталось определить, для каких нетерминалов K

слово SJ принадлежит Лев(K). Это делается по двум правилам:

(2) Если уже выяснено, что ситуация L->U_V согласована с SJ

(по правилу (1)), а V начинается на нетерминал К, то SJ принад-

лежит Лев(K).

(3) Если уже выяснено, что SJ входит в Лев(L) для некоторо-

го L, L->V - правило грамматики и V начинается на нетерминал K,

то SJ принадлежит Лев(K).

Заметим, что правило (3) можно рассматривать как аналог

правила (2): в указанных в (3) предположениях ситуация L->_V

согласована с SJ, а V начинается на нетерминал K.

Корректность этих правил в общем-то очевидна, если хоро-

шенько подумать. Единственное, что требует некоторых пояснений -

это то, почему с помощью правил (2) и (3) обнаружатся ВСЕ терми-

налы K, для которых SJ принадлежит Лев(K). Попытаемся это объяс-

нить. Рассмотрим правый вывод, в котором SJ стоит слева от K.

Откуда мог взяться в нем нетерминал K? Если правило, которое его

породило, породило также и конец слова SJ, то принадлежность SJ

к Лев(K) будет обнаружена по правилу (2). Если же K было первой

буквой слова, порожденного каким-то другим нетерминалом L, то -

благодаря правилу (3) - достаточно установить принадлежность SJ

к Лев(L). Осталось применить те же рассуждения к L и т. д.

В терминах LR-процесса то же самое можно сказать так. Сна-

чала нетерминал K может участвовать в нескольких свертках, не

затрагивающих SJ (они соответствуют применению правила (3)), но

затем он обязан подвергнуться свертке, затрагивающей SJ (что со-

ответствует применению правила (2)).

Осталось выяснить, какие ситуации согласованы с пустым сло-

вом, то есть для каких нетерминалов K пустое слово принадлежит

Лев(K). Это определяется по следующим правилам: (1) начальный

нетерминал таков; (2) если K таков и K -> V - правило граммати-

ки, причем слово V начинается с нетерминала L, то и L таков.

14.1.10. Проделать описанный анализ для грамматики

E -> E + T

E -> T

T -> T * F

T -> F

F -> x

F -> ( E )

Решение.

Слово S Сост(S)

_________________________________________________

пустое E->_E+T;E->_T;T->_T*F;T->_F;F->_x;F->_(E)

E E->E_+T

T E->T_; T->T_*F;

F T->F_

x F->x_

( F->(_E);E->_E+T;E->_T;T->_T*F;T->_F;F->_x;F->_(E)

E+ E->E+_T;T->_T*F;T->_F;F->_x;F->_(E)

T* T->T*_F;F->_x;F->_(E)

(E F->(E_);E->E_+T;

(T = T

(F = F

(x = x

(( = (

E+T E->E+T_;T->T_*F

E+F = F

E+x = x

E+( = (

T*F T->T*F_;

T*x = x

T*( = (

(E) F->(E)_

(E+ = E+

E+T* = T*

Знак равенства означает, что множества ситуаций, являющиеся зна-

чениями функции Сост(S) на словах, стоящих слева и справа от

знака равенства, одинаковы.

Правило определения Сост(SJ), если известны Сост(S) и J (S

- слово из терминалов и нетерминалов, J - терминал или нетерми-

нал), таково:

надо найти Сост(S) в правой колонке, взять соответствующее

ему слово T в левой колонке, приписать к нему J и взять мно-

жество, стоящее напротив слова ТJ (если слово ТJ в таблице от-

сутствует, то Сост(SJ) пусто).

14.2. LR(0)-грамматики.

Напомним, что наша основная цель - это поиск вывода задан-

ного слова, или, другими словами, поиск успешного LR-процесса

над ним. Во всех рассматриваемых нами грамматиках успешный

LR-процесс (над данным словом) единствен. Искать этот единствен-

ный успешный процесс мы будем постепенно: в каждый момент мы

смотрим, какой шаг возможен следующим. Для этого на грамматику

надо наложить дополнительные требования, и сейчас мы рассмотрим

простейший случай так называемых LR(0)-грамматик.

Мы уже знаем:

(1) В успешном LR-процессе возможна свертка по правилу K->U

при содержимом стека S тогда и только тогда, когда S принадлежит

ЛевКонт(K->U) или, другими словами, когда слово S согласовано с

ситуацией K->U_.

Аналогичное утверждение про сдвиг гласит:

(2) В успешном LR-процессе при содержимом стека S

возможен сдвиг с очередным символом a тогда и только тогда, ког-

да S согласовано с некоторой ситуацией K->U_aV.

14.2.1. Докажите это.

Указание. Пусть произошел сдвиг и к стеку S добавилась бук-

ва a. Рассмотрите первую свертку, затрагивающую эту букву.

Теперь мы можем дать

Определение. Рассмотрим некоторую грамматику и произвольное

слово S из терминалов и нетерминалов. Если множество Сост(S) со-

держит ситуацию, в которой справа от подчеркивания стоит терми-

нал, то говорят, что для слова S возможен сдвиг. Если в Сост(S)

есть ситуация, в которой справа от подчеркивания ничего нет, то

говорят, что для слова S возможна свертка (по соответствующему

правилу). Говорят, что для слова S возникает конфликт типа

сдвиг/свертка, если возможен и сдвиг, и свертка. Говорят, что

для слова S возникает конфликт типа свертка/свертка, если есть

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

Грамматика называется LR(0)-грамматикой, если в ней нет

конфликтов типа сдвиг/свертка и свертка/свертка ни для одного

слова S.

14.2.2. Является ли приведенная выше грамматика LR(0)-грам-

матикой?

Решение. Нет, не является. Для слов T и E+T имеются

конфликты типа сдвиг/свертка.

14.2.3. Являются ли LR(0)-грамматиками такие:

(а) T->0

T->T1

T->TT2

T->TTT3

(б) T->0

T->1T

T->2TT

T->3TTT

Решение. (а)

Слово S Сост(S)

_________________________________________

пустое Т->_0;T->_T1;T->_TT2;T->_TTT3