ДРоботландский Университет 
2000/2001 учебный год
Курс 31 "Азы программирования"
Корректор
------------------------------------------------
     Р О Б О Т Л А Н Д С К О Е  П Р О Г Р А М М И Р О В А Н И Е

                                  (C) А.А. Дуванов

                                      Под редакцией
                                      Ю.А. Первина

                                      Пособие   распространяется
                                      только в рамках  Роботлан-
                                      дских  Курсов  и  является
                                      объектом авторского права.


                       К О Р Р Е К Т О Р



Глава 7. Трансляторы


7.1. Проверка объектов

   Петя. Моя последняя курсовая работа была посвящена транслято-
рам. Очень интересная тема! Можно ли написать транслятор на язы-
ке Корректора?
   Папа. Почему бы и нет! Напомни Васе, что это такое.
   Вася. Я думаю, что не забыл наши уроки. Транслятор - это спе-
циальная программа, которая переводит текст с языка программиро-
вания в программу на СКИ робота.
   Петя. Верно! Одной из важных задач трансляции является задача
по анализу  и распознаванию отдельных элементов текста программ.
Например, часто необходима проверка, является ли выделенный объ-
ект программы числом.
   Папа. Вот и давайте начнем наше занятие с такой задачи:

   Задача.  <<testd1.kor,  testd2.kor>> Проверить,  является ли
текст на ленте числом.  В  начальный момент окно установлено на
первый символ текста.

   Петя. Что мы будем понимать под числом?
   Папа. Правильный вопрос. Ну, давайте для  начала решим задачу
для целых неотрицательных чисел без знака.
   Вася. Ну, это просто. Проверяем  каждый  символ  текста - все
они должны быть  цифрами.  Результат проверки будем записывать в
ящик. Сначала в него поместим  1,  а если обнаружим в записи  не
цифру, поместим в него 0:

// Проверка целых неотрицательных чисел
ЭТО Проверка_числа
 Подготовка_ящика
 Работа
 Запись_ответа
КОНЕЦ

ЭТО Подготовка_ящика
 ОБМЕН
 ПИШИ 1
 ОБМЕН
КОНЕЦ

ЭТО Работа
 ПОКА НЕ ПУСТО
 {
  ЕСЛИ НЕ ЦИФРА
   ТО
   {
     ОБМЕН
     ПИШИ 0
     ОБМЕН
   }
  ВПРАВО
 }
КОНЕЦ

ЭТО Запись_ответа
  ВПРАВО
  ЯЩИК-
  ЕСЛИ 1
   ТО
   {
     ПИШИ д
     ВПРАВО
     ПИШИ а
   }
   ИНАЧЕ
   {
     ПИШИ н
     ВПРАВО
     ПИШИ е
     ВПРАВО
     ПИШИ т
   }
КОНЕЦ

   Папа. Теперь решим задачу для любых  целых чисел, положитель-
ных и отрицательных.
   Вася. Значит, перед цифрами может стоять знак минус, и первый
символ нужно проверить отдельно.
   Папа. Будем  предполагать  возможность  обработки  чисел и со
знаком плюс. Правильными будут теперь считаться, например, такие
числа: 4652, -657, +8675.
   Вася.  Решение  получается  небольшим  изменением  предыдущей
программы:

// Проверка любых целых чисел
ЭТО Проверка_числа
 Подготовка_ящика
 Проверка_первого
 Проверка_остальных
 Запись_ответа
КОНЕЦ

ЭТО Подготовка_ящика
 ОБМЕН
 ПИШИ 1
 ОБМЕН
КОНЕЦ

ЭТО Проверка_первого
 ЕСЛИ НЕ ЦИФРА ТО
  ЕСЛИ НЕ + ТО
   ЕСЛИ НЕ - ТО Ошибка
 ВПРАВО
КОНЕЦ

ЭТО Проверка_остальных
 ПОКА НЕ ПУСТО
 {
  ЕСЛИ НЕ ЦИФРА ТО Ошибка
  ВПРАВО
 }
КОНЕЦ

ЭТО Запись_ответа
  ВПРАВО
  ЯЩИК-
  ЕСЛИ 1
   ТО
   {
     ПИШИ д
     ВПРАВО
     ПИШИ а
   }
   ИНАЧЕ
   {
     ПИШИ н
     ВПРАВО
     ПИШИ е
     ВПРАВО
     ПИШИ т
   }
КОНЕЦ

ЭТО Ошибка
 ОБМЕН
 ПИШИ 0
 ОБМЕН
КОНЕЦ

   Задача 1. На ленте  записан  текст. Проверить, является ли он
числом, и записать результат проверки на ленте в виде:
 цп - целое положительное
      (примеры: 75, +83)
 цо - целое отрицательное
      (пример: -17)
 дп - положительная десятичная дробь
      (примеры: 75.33, +35.79, .56, +.89)
 до - отрицательная десятичная дробь
      (пример: -60.45. -.78)
 пп - простая дробь положительная
      (пример: 55/65, +85/10)
 по - простая дробь отрицательная
      (пример: -25/45)
 ош - ошибка в записи
   В начальный момент окно установлено на первый символ текста.
   Замечание. Не забудьте  учесть тот факт, что наличие в записи
нескольких знаков ".", "/" - считается ошибкой.

   Задача  2.  Идентификатор - это последовательность из букв  и
цифр, которая начинается  с  буквы. Проверить, является ли текст
на ленте идентификатором. В начальный момент окно установлено на
первый символ текста.

7.2. Транслятор для Плюсика.

   Петя. Мне кажется, роботландский исполнитель Плюсик - хороший
объект для упражнений по программированию трансляторов.
   Папа. Согласен. Стек, на котором Плюсик  проводит свои вычис-
ления, почти всегда используют  при  программировании транслято-
ров, да и, вообще, это интересный исполнитель.
   Петя. Для наших  целей я немного изменил СКИ этого исполните-
ля. Вот его описание, пригодное для наших занятий.

                       Исполнитель Плюсик

   Плюсик  -  это исполнитель,  предназначенный  для  выполнения
арифметических вычислений  над целыми неотрицательными  числами.
Его среда  состоит  из стека, арифметического устройства (сокра-
щенно АУ) и канала связи между стеком и АУ:

             │           │══════════════════╗
             ├───────────┤  Канал связи     ║
             ├───────────┤                  ║
             ├───────────┤         ┌────────╨────────┐
             ├───────────┤         │        АУ       │
             ├───────────┤         │ (арифметическое │
             ├───────────┤         │   устройство)   │
             ├───────────┤         └─────────────────┘
             └───────────┘
                Стек

   СКИ Плюсика включает следующие команды:

   пt - запомнить в стеке число t
   о  - очистить стек
   с  - сложить
   в  - вычесть
   у  - умножить
   д  - делить

   Папа.  Давайте  сначала вспомним, как работает стек, а  затем
уточним, как Плюсик выполняет свои команды.
   Вася. Стек -  это  специальное устройство для хранения чисел.
Оно похоже на детскую пирамидку: как ее кольца  по очереди нани-
зываются на стержень, так и числа по очереди поступают в стек.

        │                     │         │
  ┌─────┼─────┐               │ 3232    │
 ┌┴─────┼─────┴┐              │ 5443    │
┌┴──────┼──────┴┐             │ 234444  │
└───────┴───────┘             └─────────┘
   Петя. Вообще говоря, в стеке могут храниться не только числа,
но у Плюсика это действительно так.
   Папа. А как извлекать информацию из стека?
   Вася. Так же, как в пирамидке мы не можем снять  нижнее коль-
цо, не сняв предварительно верхние, так и в стеке всегда доступ-
но только число, поступившее туда последним.
   Папа. Очень хорошо! Теперь давайте рассмотрим, как Плюсик вы-
полняет команды из своей СКИ.
   Петя. Первая команда  предназначена  для записи чисел в стек.
Вот несколько примеров:

  Команда        Пояснение                 Состояние стека после
                                           выполнения команды

  п125    Положить в стек число 125        │  125      │
                                           │           │
                                           │           │
                                           └───────────┘
  п25     Положить в стек число 25         │  25       │
                                           │  125      │
                                           │           │
                                           └───────────┘
  п10     Положить в стек число 10         │  10       │
                                           │  25       │
                                           │  125      │
                                           └───────────┘

   Вася. Вторая команда "о" - проста  и  понятна:  выполняя  ее,
Плюсик очищает стек от всех чисел.
   Петя. Остальные команды предназначены для выполнения вычисле-
ний. Они все работают одинаково. Из стека извлекается последова-
тельно два  числа. По каналу связи они передаются  в АУ, где над
ними выполняется  арифметическое  действие  и результат снова по
каналу связи помещается в стек.
   Папа. Важно  отметить, что последнее извлеченное число стано-
вится первым  операндом предстоящей операции, а извлеченное пер-
вым - вторым.
   Петя. Да, я это продемонстрирую на типичной задаче для Плюси-
ка: написать программу для вычисления арифметического примера:
                       2*(127-32)

   Вот как может выглядеть решение:
     п2
     п127
     п32
     в
     у

   Вася. А я нарисовал схему выполнения Плюсиком этой программы:

  Команда        Пояснение              Состояние стека после
                                        выполнения команды

  п2      Положить в стек число 2          │  2        │
                                           │           │
                                           │           │
                                           └───────────┘
  п127    Положить в стек число 127        │  127      │
                                           │  2        │
                                           │           │
                                           └───────────┘
  п32     Положить в стек число 10         │  32       │
                                           │  127      │
                                           │  2        │
                                           └───────────┘
  в       Извлечь из стека два числа,      │  95       │
          от последнего отнять первое,     │  2        │
          результат поместить в стек       │           │
                                           └───────────┘
  у       Извлечь из стека два числа,      │  190      │
          последнее умножить на первое,    │           │
          результат поместить в стек       │           │
                                           └───────────┘

   Папа. Ну, с Плюсиком мы разобрались,  теперь давайте вернемся
к Корректору.
   Петя. Предлагаю такую задачу:

   Задача. Перевести пример  на  сложение двух чисел в программу
для Плюсика. Например,  запись  25+7 должна быть преобразована в
текст п25п7с. В начальный момент  в  окошко  виден первый символ
примера.

   Вася. Я предлагаю такую главную процедуру:

ЭТО Транслятор
 Записать_команду_п
 Перенести_число     // перенести первое число
 Записать_команду_п
 ВПРАВО              // перешагнуть через знак +
 Перенести_число     // перенести второе число
 Записать_команду_с
КОНЕЦ

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

ЭТО Записать_команду_п
 ВПРАВО
 ЕСЛИ НЕ ПУСТО
  ТО    Записать_команду_п
  ИНАЧЕ Поставить_п
 ВЛЕВО
КОНЕЦ

ЭТО Поставить_п
 ВПРАВО
 ПОКА НЕ ПУСТО ВПРАВО
 ПИШИ п
 ПОКА НЕ ПУСТО ВЛЕВО
КОНЕЦ

ЭТО Записать_команду_с
 ВПРАВО
 ЕСЛИ НЕ ПУСТО
  ТО    Записать_команду_с
  ИНАЧЕ Поставить_с
 ВЛЕВО
КОНЕЦ

ЭТО Поставить_с
 ВПРАВО
 ПОКА НЕ ПУСТО ВПРАВО
 ПИШИ с
 ПОКА НЕ ПУСТО ВЛЕВО
КОНЕЦ

   Петя. Для записи команд  "п"  и "с" получилось два экземпляра
почти одинакового текста.
   Вася. Я понял твой намек и придумал, как сократить программу:
надо использовать  ящик!  Тогда можно обойтись одним экземпляром
процедуры,  записывающей  в конец результата символ из ящика.  в
первом случае это символ "п", а во втором "с". Вот новый вариант
моего решения (я внес правку и в главную процедуру программы):

ЭТО Транслятор
 // Запись команды п
 ОБМЕН
 ПИШИ п
 ОБМЕН
 Записать_символ
 Перенести_число // первое число
 // Запись команды п
 ОБМЕН
 ПИШИ п
 ОБМЕН
 Записать_символ
 ВПРАВО // перешагнуть через знак +
 Перенести_число // второе число
 // Запись команды с
 ОБМЕН
 ПИШИ с
 ОБМЕН
 Записать_символ
КОНЕЦ

ЭТО Записать_символ
 ВПРАВО
 ЕСЛИ НЕ ПУСТО
  ТО    Записать_символ
  ИНАЧЕ Записать
 ВЛЕВО
КОНЕЦ

ЭТО Записать
 ВПРАВО
 ПОКА НЕ ПУСТО ВПРАВО
 ЯЩИК-
 ПОКА НЕ ПУСТО ВЛЕВО
КОНЕЦ

   Папа. Осталось написать текст процедуры, выполняющей  копиро-
вание числа.
   Вася. Будем использовать уже готовую процедуру  Записать_сим-
вол:

ЭТО Перенести_число
 ПОКА ЦИФРА
 {
   ЯЩИК+
   Записать_символ
   ВПРАВО
 }
КОНЕЦ

   Петя. Отлично! У меня есть повод гордиться своим младшим бра-
том.

   Однако, когда  программа была запущена, обнаружилось, что она
работает не совсем правильно: последняя команда "с" записывается
не вплотную к предыдущей записи, а через пустое место от него:

         ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬──┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
         │░│░│░│2│5│+│7│ │п│ 2│5│п│7│ │с│░│░│░│░│░│░│░│
         ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴──┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴

   Когда первое удивление  прошло,  братья быстро нашли ошибку и
исправили ее. Читателю предлагается это сделать самостоятельно в
задаче 3.

   Задача 3. Найти и исправить  логическую  ошибку  в  программе
Транслятор.

   Задача 4. Перевести пример на  сложение  нескольких  чисел  в
программу для Плюсика. Например, запись 25+7+20  может быть пре-
образована в текст п25п7сп20с. В начальный момент в окошко виден
первый пустой символ за записью примера.

   Задача 5. Арифметический пример содержит только целые неотри-
цательные числа, соединенные  знаками  "+" и "-". Написать прог-
рамму для преобразования примера в программу для Плюсика. Напри-
мер, запись  100-20+67  может  быть  преобразована  в  программу
п100п20вп67с.  В  начальный момент в окошко виден первый  пустой
символ за примером.

Задача 6. Написать программу, которая переводит команду
                      ПОВТОРИ число команда    (*)
в последовательность команд "команда" из СКИ исполнителя. Напри-
мер, запись
                        ПОВТОРИ 4 ВПРАВО
должна переводиться в запись
                  ВПРАВО ВПРАВО ВПРАВО ВПРАВО,
а запись
                     ПОВТОРИ 3 ПИШИ 5
в запись
                 ПИШИ 5 ПИШИ 5 ПИШИ 5.

   Предполагается, что "команда"  в  записи (*) может быть любой
командой из СКИ Корректора, а "число" может быть принимать любые
целые неотрицательные  значения,  не  превышающие длину алфавита
Корректора.

Задача 7.
   Построить на  базе Корректора нового исполнителя со следующей
СКИ:
 п - ВПРАВО
 л - ВЛЕВО
 + - ПЛЮС
 - - МИНУС
 зs - ПИШИ s
 я+ - ЯЩИК+
 я- - ЯЩИК-
 о - ОБМЕН
   Информация на ленте Корректора имеет следующую структуру:
                программа|рабочая область|данные
   Программа составлена из команд СКИ нового исполнителя, следу-
ющих друг за другом без каких-либо разделителей.
   Рабочая область занимает 4 клетки, их  содержимое в начальный
момент произвольно. Рабочую область можно использовать для моде-
лирования ящика  нового исполнителя и временного хранения другой
информации.
   Данные, подлежащие обработке программой, написанной для ново-
го исполнителя, расположены за рабочей областью.
   Считается, что окно нового исполнителя, установлено на первую
клетку данных.
   В начальный момент Корректор смотрит на  первую команду прог-
раммы. Исполняя программу, Корректор, в соответствии с командами,
обрабатывает  данные.  Обработка заканчивается,  когда выполнена
последняя команда.
   Написать программы для нового исполнителя, решающие следующие
задачи:
   а) Записать на ленту слово "кот";
   б) Перевернуть трехсимвольное слово в  области  данных "задом
наперед";
   в) В области  данных записано число трехзначное число, каждая
цифра которого больше единицы. Отнять от этого числа число 111;
   г) В области  данных записано число трехзначное число, каждая
цифра которого не больше  восьми.  Прибавить к этому числу число
111;
   д) Придумать другие  задачи для нового исполнителя и написать
для него программы, решающие эти задачи.
