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

сдвиг. (Это определение не изменилось по сравнению с SLR(1)-слу-

чаем - вторые компоненты пар из Сост(S) не учитываются.)

Если в Сост(S) есть ситуация, в которой справа от подчерки-

вания ничего нет, а вторым членом пары является терминал t, то

говорят, что для пары (S, t) LR(1)-возможна свертка (по соот-

ветствующему правилу). Говорят, что для пары (S, t) возникает

конфликт типа сдвиг/свертка, если возможен и сдвиг, и свертка.

Говорят, что для пары (S, t) возникает конфликт типа

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

свертка.

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

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

пары (S, t).

14.4.6. Построить алгоритм проверки выводимости слова в

LR(1)-грамматике.

Решение. Как и раньше, на каждом шаге LR-процесса можно од-

нозначно определить, какой шаг только и может быть следующим.

Полезно (в частности, для LALR(1)-разбора, смотри ниже) по-

нять, как связаны понятия LR(0) и LR(1)-согласованности.

14.4.7. Сформулировать и доказать соответствующее утвержде-

ние.

Ответ. Пусть фиксирована некоторая грамматика. Слово S из

терминалов и нетерминалов является LR(0)-согласованным с ситу-

ацией K->U_V тогда и только тогда, когда оно LR(1)-согласовано с

парой [K->U_V, t] для некоторого терминала t (или для t=EOI). То

же самое другими словами: Лев(K) есть объединение Лев(K, t) по

всем t. В последней форме это совсем ясно.

Замечание. Таким образом, функция Сост(S) в LR(1)-смысле

является расширением функции Сост(S) в LR(0)-смысле: Сост1(S)

получается из Сост0(S), если во всех парах выбросить вторые чле-

ны.

Теперь мы можем дать определение LALR(1)-грамматики. Пусть

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

терминалов, t - некоторый терминал (или EOI). Будем говорить,

что для пары (S, t) LALR(1)-возможна свертка по некоторому прави-

лу, если существует другое слово S1 с Сост0(S)=Сост0(S1), причем

для пары (S1,t) LR(1)-возможна свертка по рассматриваемому пра-

вилу. Далее определяются конфликты (естественным образом), и

грамматика называется LALR(1)-грамматикой, если конфликтов нет.

14.4.8. Доказать, что всякая SLR(1)-грамматика является

LALR(1)-грамматикой, а всякая LALR(1)-грамматика является

LR(1)-грамматикой.

Указание. Это - простое следствие определений.

14.4.9. Построить алгоритм проверки выводимости в

LALR(1)-грамматике, который хранит в стеке меньше информации,

чем соответствующий LR(1)-алгоритм.

Указание. Достаточно хранить в стеке множества Сост0(S),

поскольку согласно определению LALR(1)-возможность свертки ими

определяется. (Так что сам алгоритм ничем не отличается от

SLR(1)-случая, кроме таблицы возможных сверток.)

14.4.10. Привести пример LALR(1)-грамматики, не являющейся

SLR(1)-грамматикой.

14.4.11. Привести пример LR(1)-грамматики, не являющейся

LALR(1)-грамматикой.

14.5. Общие замечания о разных методах разбора.

Применение этих методов на практике имеет свои хитрости и

тонкости, которых мы не касались. (Например, таблицы следует

хранить по возможности экономно.) Часто оказывается также, что

для некоторого входного языка наиболее естественная грамматика

не является LL(1)-грамматикой, но является LR(1)-грамматикой, а

также может быть заменена на LL(1)-грамматику без изменения язы-

ка. Какой из этих вариантов выбрать, не всегда ясно. Диле-

тантский совет: если Вы сами проектируете входной язык, то не

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

разных целей - и тогда обычно несложно написать LL(1)-грамматику

или рекурсивный анализатор. Если же входной язык задан заранее с

помощью LR(1)-грамматики, не являющейся LL(1)-грамматикой, то

лучше ее не трогать, а разбирать как есть. При этом могут ока-

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

ров, наиболее известными из которых являются yacc (UNIX) и bison

(GNU).

Большое количество полезной и хорошо изложенной информации

о теории и практике синтаксического разбора имеется в книге:

Alfred V. Aho, Ravi Sethi, Jeffrey D. pilers:

principles, techniques and tools. Addison Wesley (1985).

ПРОГРАММИРОВАНИЕ: ТЕОРЕМЫ И ЗАДАЧИ

НЕСКОЛЬКО ЗАМЕЧАНИЙ ВМЕСТО ПРЕДИСЛОВИЯ

Книга написана по материалам занятий программированием со

школьниками математических классов школы N 57.

Книга написана в убеждении, что программирование имеет свой

предмет, не сводящийся ни к конкретным языкам и системам, ни к

методам построения быстрых алгоритмов.

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

ма, но не в правильности программы. Одна из целей книги - попы-

таться продемонстрировать, что это не так.

В принципе, возможность практического исполнения программ не яв-

ляется непременным условием изучения программирования. Однако

она является сильнейшим стимулом - без такого стимула вряд ли у

кого хватит интереса и терпения.

Выбранный жанр книги по необходимости ограничивает ее "програм-

мированием в малом", оставляя в стороне необходимую часть прог-

раммистского образования - работу по модификации больших прог-

рамм. Автор продолжает мечтать о наборе учебных программных сис-

тем эталонного качества, доступных для модификации школьниками.

Кажется, Хоар сказал, что эстетическая прелесть программы - это

не архитектурное излишество, а то, что отличает в программирова-

нии успех от неудачи. Если, решая задачи из этой книги, читатель

почувствует прелесть хорошо написанной программы, в которой "ни

убавить, ни прибавить", и сомнения в правильности которой кажут-

ся нелепыми, то автор будет считать свою цель достигнутой.

Характер глав различен: в одних предлагается набор мало связан-

ных друг с другом задач с решениями, в других по существу изла-

гается один-единственный алгоритм. Темы глав во многом пересека-

ются, и мы предпочли кое-какие повторения формальным ссылкам.

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

краткими теоретическими сведениями (как в задачнике -

вича).

Уровень трудности задач и глав весьма различен. Мы старались

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

чинающих, так и трудные задачи, которые могут посадить в лужу и

сильного школьника. (Хоть и редко, но это бывает полезно.)

В качестве языка для записи программ был выбран паскаль (если не

считать небольшого введения, в котором программы управления Ро-

ботом записываются на специальном мини-языке). Паскаль достачно

прост и естествен, имеет неплохие реализации (мы ссылаемся на

Turbo Pascal 3.0 и 5.0 фирмы Borland) и позволяет записать реше-

ния всех рассматриваемых задач. Возможно, Модула-2 или Оберон

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

Неудачный опыт писания "популярных" учебников по программирова-

нию учит: никакого сюсюканья! писать надо так, чтобы потом самим

было не стыдно прочесть.

Большинство задач и алгоритмов, разумеется, не являются новыми и

взяты из различных книг. Вместе с тем мы надеемся, что во многих

случаях алгоритмы (и особенно доказательства) изложены более ко-

ротко и отчетливо.

Это не только и не столько учебник для школьника, сколько спра-

вочник и задачник для преподавателя, готовящегося к занятию.

---------------------------------------------------------------

Первое знакомство

+ Игра в Робота

+/- Игрушечный функциональный язык

+/- Схемы из функциональных элементов

Основы программирования

+ Переменные

+ Массивы

+ Индуктивные функции

+ Некоторые средства паскаля

+ Порождение комбинаторных объектов

+ Обход дерева. Перебор с возвратами

+ Сортировка

+ Рекурсия

+ Типы данных и их реализация

+ Устранение рекурсии. Динамическое программирование.

Стеки, польская запись

+ Представление множеств: хеширование

+ Представление множеств: сбалансированные деревья

+/- Графы. Кратчайшие пути. Минимальное остовное дерево.

Поиск в глубину и ширину? Число связных компонент

Форд - Фалкерсон и паросочетания

-/+ Конечные автоматы как средство спецификации и реализации

+ Алгоритмы сравнения с образцом

+/- Контекстно-свободные языки. LL(1)-разбор

-/+ LR(1)-разбор

-/+ Геометрические алгоритмы

Вероятностные алгоритмы

Отдельные сюжеты, которые стоит дописать

порождение всех расстановок скобок, числа Каталана

мат ферзем (или ладьей?) и неподвижным королем

подпись в spelling checker

определение стратегии в игре (дерево с min-max)

предвычисление древесного порядка

сток в графе за O(n) и поиск наибольшего