                 Транслятор?.. Это очень просто!
                        (часть 2)

Дуванов Александр Александрович
duvanov@robotland.users.botik.ru
Осень, 1999 Переславль-Залесский

                          Машина имеет четыре скорости: первую,
                          вторую, третью  и четвертую, а  также
                          задний и боковой ход. В задней  части
                          машины  имеется  приспособление   для
                          стирки белья. Стирка  может  произво-
                          диться  во время  движения  на  любой
                          скорости. В спокойном  состоянии,  то
                          есть на остановках, машина рубит дро-
                          ва, месит глину и  делает  кирпичи, а
                          также чистит картошку.
                                                  Николай Носов

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


Ах уж эта рекурсия!
-------------------

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


ЭТО ошибка                         │
 шаг                               │Перемещение остатка записи
 ЕСЛИ НЕ ПУСТО ТО ошибка           │в первую строку
 ВЛЕВО                             │Возврат к месту ошибки
КОНЕЦ                              │

Вспомним, что процедура "шаг" выглядит так:

ЭТО шаг
 ВНИЗ ВПРАВО ВВЕРХ
КОНЕЦ

   Автор уверял  доверчивых  читателей,  что это будет работать:
Кукарача, якобы сделает влево не  один  шаг,  а столько, сколько
надо, чтобы встать точно под обнаруженной в записи ошибкой!

   Пусть,  исследуя  запись,  исполнитель встретил ошибку  (знак
"+"):

                    1 2 3 4 5 6 7 8 9 10
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
                 1 │ │ │1│2│+│ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 2 │ │ │ │ │¤│3│ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 3 │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤

   Теперь, Кукарача  должен  сдвинуть  остаток  записи  в первую
строку и  встать точно под ошибочным символом:

                    1 2 3 4 5 6 7 8 9 10
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
                 1 │ │ │1│2│+│3│ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 2 │ │ │ │ │¤│ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 3 │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤

   Неужели процедура "ошибка" это все сделает?

   Давайте проследим работу исполнителя по шагам.


Первой выполняется команда "шаг":          1 2 3 4 5 6 7 8 9 10
                                          ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
ЭТО ошибка                              1 │ │ │1│2│+│3│ │ │ │ │
┌───┐                                     ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│шаг│                                   2 │ │ │ │ │ │¤│ │ │ │ │
└───┘                                     ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 ЕСЛИ НЕ ПУСТО ТО ошибка                3 │ │ │ │ │ │ │ │ │ │ │
 ВЛЕВО                                    ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
КОНЕЦ

   Затем выполняется условная команда:

ЭТО ошибка
┌───┐
│шаг│
└─┬─┘
┌─┴─────────────────────┐
│ЕСЛИ НЕ ПУСТО ТО ошибка│
└───────────────────────┘
 ВЛЕВО
КОНЕЦ

   После выполнения условной команды должна выполняться команда,
следующая за ней, то есть команда ВЛЕВО. Но условная команда еще
не закончила свою работу: так как условие истинно, начнет выпол-
нятся копия программы "ошибка":
                                             1 2 3 4 5 6 7 8 9 10
                                            ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
ЭТО ошибка                                1 │ │ │1│2│+│3│ │ │ │ │
┌───┐                                       ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│шаг│                                     2 │ │ │ │ │ │ │¤│ │ │ │
└─┬─┘                     ЭТО ошибка        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
┌─┴─────────────────────┐ ┌───┐           3 │ │ │ │ │ │ │ │ │ │ │
│ЕСЛИ НЕ ПУСТО ТО ошибка├─┤шаг│             ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
└───────────────────────┘ └─┬─┘
 ВЛЕВО                    ┌─┴─────────────────────┐
КОНЕЦ                     │ЕСЛИ НЕ ПУСТО ТО ошибка│
                          └───────────────────────┘
                           ВЛЕВО
                          КОНЕЦ

   Теперь условие  ложно  и  выполнится  команда  ВЛЕВО в копии
программы "ошибка":
                                             1 2 3 4 5 6 7 8 9 10
                                            ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
ЭТО ошибка                                1 │ │ │1│2│+│3│ │ │ │ │
┌───┐                                       ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│шаг│                                     2 │ │ │ │ │ │¤│ │ │ │ │
└─┬─┘                     ЭТО ошибка        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
┌─┴─────────────────────┐ ┌───┐           3 │ │ │ │ │ │ │ │ │ │ │
│ЕСЛИ НЕ ПУСТО ТО ошибка├─┤шаг│             ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
└───────────────────────┘ └─┬─┘
 ВЛЕВО                    ┌─┴─────────────────────┐
КОНЕЦ                     │ЕСЛИ НЕ ПУСТО ТО ошибка│
                          └─┬─────────────────────┘
                          ┌─┴───┐
                          │ВЛЕВО│
                          └─────┘
                          КОНЕЦ

   Работа копии программы  "ошибка"  завершена и, тем самым, за-
вершилось  выполнение  условной команды  в  оригинале.  Кукарача
приступает к выполнению последней команды ВЛЕВО и устанавливает-
ся точно под знаком "+":
                                             1 2 3 4 5 6 7 8 9 10
                                            ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
ЭТО ошибка                                1 │ │ │1│2│+│3│ │ │ │ │
┌───┐                                       ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│шаг│                                     2 │ │ │ │ │¤│ │ │ │ │ │
└─┬─┘                     ЭТО ошибка        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
┌─┴─────────────────────┐ ┌───┐           3 │ │ │ │ │ │ │ │ │ │ │
│ЕСЛИ НЕ ПУСТО ТО ошибка├─┤шаг│             ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
└───────────────────────┘ └─┬─┘
┌─────┐                   ┌─┴─────────────────────┐
│ВЛЕВО│ <───────────┐     │ЕСЛИ НЕ ПУСТО ТО ошибка│
└─────┘             │     └─┬─────────────────────┘
КОНЕЦ               │     ┌─┴───┐
                    └─────┤ВЛЕВО│
                          └─────┘
                          КОНЕЦ

   Фокус  разоблачен!  Команда  ВЛЕВО  выполнится  столько  раз,
сколько  работала  процедура "шаг" в рекурсивных вызовах. А  это
гарантирует, что исполнитель вернется к  месту  ошибки  со  100%
точностью, где бы не располагалась ошибка в записи!
   Разоблачение фокуса заключено в простом понимании, что рекур-
сия это не GOTO (переход на начало процедуры). Рекурсивный вызов
- это выполнение  КОПИИ  процедуры: он может порождать "отложен-
ные" команды, которые начнут выполняться после завершения рекур-
сии.  И  будут выполнятся столько раз, сколько было  рекурсивных
вызовов.

   Ребята из Барнаула (руководитель команды Анатолий  Владимиро-
вич Бычков) нашли в прошлом году очень выразительный и емкий ас-
социативный термин для описания работы отложенных в рекурсии ко-
манд - "рекурсивная пружина".

   Кукарача, делая  рекурсивный "шаг", сжимает пружину. По окон-
чанию  рекурсии  пружина разжимается:  команда  ВЛЕВО  сработает
столько раз, сколько витков было "закручено".

   Как можно решить эту задачу на Бейсике? Да  очень просто: за-
вели бы переменную (ячейку памяти), считали бы в  ней шаги впра-
во, а потом: Кукарача, шагай столько же раз влево!

   Но Кукарача - парень без головы! Ну, нет у него  памяти! Сов-
сем! И вот рекурсия выступает как протез отсутствующего органа.
   С рекурсией Кукарача (ого!) умеет считать и запоминать!

   Вот совсем  простое упражнение с рекурсивной пружинкой (ответ
в конце статьи).

   Упражнение. (автор  Лилитко  Е.П.). Кукарача находится в вер-
хней строке поля. Где-то под ним (в том  же столбце) расположена
буква А. Требуется  спуститься к букве  (где бы она  ни  находи-
лась), подвинуть  ее один раз и  вернуться к исходной  позиции в
верхнюю строку.
                1 2 3 4 5 6 7 8 9 10
               ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
             1 │ │ │ │¤│ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             2 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             3 │ │ │ │А│ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤


   Вам понравилась рекурсия? Очаровательная штучка, правда?  Од-
нако  Ворчуны  среди вас наверняка найдутся. Специально для  них
небольшое отступление против рекурсии.

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

           f(1)  = 1, f(2)  = 1,
           f(n)  = f(n-1)+f(n-2) , для всех n > 2

                 Напоминание о числах Фибоначчи
        Числа Фибоначчи определяются  следующей бесконечной последо-
     вательностью целых чисел: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
        Каждый n-й элемент этой последовательности, начиная с треть-
     его, равен сумме двух непосредственно предшествующих элементов.
     Первые два члена последовательности равны единице.
        Эти числа  являются  решением  следующей задачи (итальянский
     математик Фибоначчи сформулировал ее в 1202 году):
        "Каждый месяц самка из пары кроликов приносит двух детенышей
     (самца и самку). Через два месяца новая самка сама приносит па-
     ру кроликов.  Нужно найти число кроликов  в конце года,  если в
     начале года была одна новорожденная пара, и в течение этого го-
     да кролики не умирали."
        Ответ:  к  концу  года  число пар кроликов  достигнет  числа
     f(12)=144, то есть,  поголовье  возрастет до 288 кроличьих еди-
     ниц.
        Однако, надо заметить, что на практике такое размножение кро-
     ликов ни к чему хорошему не приведет. Родственные "браки" повле-
     кут быстрое вырождение потомства. Когда-то в  детстве автор раз-
     водил кроликов и,  не  имея соответствующего образования (и дол-
     жной ответственности перед живой природой!), пришел  к этому вы-
     воду на практике. И потом, насколько я помню, крольчихи вступают
     в половую зрелость  не через 2  месяца после рождения,  а  через
     три. Последнее замечание наводит  на  мысль о новой задаче: опи-
     сать и построить последовательность для решения задачи Фибоначчи
     при условии, что кролики вступают в "брак" через  3 месяца после
     рождения.  Сколько  кроликов будет в крольчатнике к концу  года,
     если колония начала плодиться с одной пары?
        Заядлые крольчатники  сделают еще одно замечание: очень редко
     самка приносит только двух детенышей.  Обычный  приплод  -  6-12
     (однажды  крольчиха  подарила мне 18 ушастиков!). И кроме  того,
     опытные кролиководы  не  позволяют самкам становиться мамами так
     часто как это описал  Фибоначчи!.  Это еще один повод формулиро-
     вать новые рекурсивные задачи.

   Несколько примеров рекурсивных описаний.
1) Факториал.
              0! = 1
              n! = n*(n-1)!
2) Сумма последовательности.
    Пусть дана бесконечная последовательность чисел
               а1, a2, ..., an, ...
   Если обозначить через  S(n) - сумму n членов этой последова-
тельности, то
                 S(1) = a1
                 S(k) = S(k-1) + ak

3) Бинарное дерево.
        o - есть бинарное дерево (называемое пустым деревом).
        Если b1 и b2 - бинарные деревья, то объект
                               o
                             /   \
                            b1    b2
        тоже является бинарным деревом.

 4) Решение задачи о ханойских башнях.
   Пусть H(n, i,  j, k) описывает  алгоритм переноса n  колец  с
i-го стержня на j-ый, используя k-ый стержень как рабочий (i, j,
k принимают значения из множества {1, 2, 3} и различны между со-
бой).

Тогда:
                 H(1, i, j, k)   = i -> j

                                  | H(n-1, i, k, j)
                 H(n, i,  j, k) = | i -> j
                                  | H(n-1, k, j, i)

   Замечание. Операция -> введена для обозначения переноса коль-
ца с одного стержень на другой. Например, запись 1 ->  3 обозна-
чает перенос кольца с первого стержня на третий.

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

   Первый камень.  Использовать  рекурсию  разумнее всего тогда,
когда природа задачи сама по себе  рекурсивна. Искусственно пос-
троенная рекурсия (как альтернатива циклу) редко бывает оправда-
на. Например, для суммирования членов последовательности,  лучше
применить цикл, а не  рекурсию.  В чем заключается опасность ре-
курсии при машинных вычислениях? Дело в том, что  при каждом ре-
курсивном вызове расходуется дополнительно часть машинной памяти
(в ней сохраняется адрес возврата и  локальные переменные проце-
дуры, если язык допускает использование переменных). При "глубо-
ких" рекурсивных  вызовах  вся доступная память компьютера может
быстро исчерпаться.
   Но даже в некоторых естественно-рекурсивных задачах рекурсию
использовать не  всегда  разумно. В качестве примера рассмотрим
упоминаемую выше последовательность чисел Фибоначчи.
   Каждое обращение к f(n) при n > 2 приводит к  двум рекурсив-
ным обращениям.  Посмотрите,  как  быстро  растет число вызовов
процедуры f при рекурсивном вычислении чисел Фибоначчи:
                                 f
                  ┌──────────────┴───────────────┐
2         ┌───────f────────┐             ┌───────f────────┐
4     ┌───f────┐      ┌────f───┐     ┌───f────┐       ┌───f───┐
8   ┌─f─┐    ┌─f─┐  ┌─f─┐    ┌─f─┐ ┌─f─┐    ┌─f─┐   ┌─f─┐   ┌─f─┐
16  f   f    f   f  f   f    f   f f   f    f   f   f   f   f   f

   Число рекурсивных вызовов растет как степень двойки, то есть
так же быстро, как размножаются кролики!
   Числа Фибоначчи лучше вычислять при помощи цикла ПОКА:

    ЭТО f(n)
     i:= 1          // i - счетчик чисел Фибоначчи
     x:= 1          // x - сумматор
     y:= 0          // y - вспомогательная переменная
     ПОКА i < n
     {
       x:= x + y    // суммируем два предыдущих значения
       y:= x - y    // первое из них запоминаем в y
       i:= i + 1
     }
    ВЕРНУТЬ x
    КОНЕЦ

   Второй камень. Использовать рекурсию как замену отсутствующей
в языке конструкции  GOTO  еще вреднее, чем использование самого
GOTO. Рассматривать рекурсию как переход в начало процедуры неп-
равильно: ведь рекурсия  это не переход, а выполнение копии про-
цедуры; выполнение без  всякого перехода, в том самом месте, где
стоит рекурсивный вызов.

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

К нашим баранам
---------------
   Рекурсия - очень интересная тема. Быть может мы еще доберемся
до важной практической  части: как сделать так, чтобы рекурсии в
рекурсии было как можно меньше! Интрига обозначена, а теперь...

Знакомьтесь: Корректор
----------------------
   Корректор работает с длинной лентой, которая разбита на клет-
ки (ячейки).  В ячейку можно  записать один символ. Символ - это
буква, цифра,  знак "+" или что-нибудь  еще в этом  роде. Полный
набор допустимых символов составляет алфавит исполнителя.
   Считается, что  лента  спрятана в непрозрачный для Корректора
футляр. Исполнитель может видеть только одну  ячейку ленты через
специальное окно в  футляре, и записывать в "оконную" ячейку лю-
бые символы из своего  алфавита.  Он может также перемещать окно
вправо и  влево по ленте  и, таким образом, записывать символы в
любые клетки на ней.
   Еще робот имеет "ящик"  -  специальную ячейку памяти. В ящике
можно хранить один символ.

                        ┬─┬
                        │т│               - ящик Корректора
                        ┴─┴
                                                                                                                       │
┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
│░│░│░║т║е│к│с│т│ │н│а│ │л│е│н│т│е│░│░│░│ - лента Корректора
┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴
       │
       └── "окно" на ленте

   Ниже приводится полный набор команд Корректора и его алфавит.

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

                     Алфавит Корректора
      ПУСТО 0 1 2 3 4 5 6 7 8 9 а б в г д е ж з и й к л
      м н о п р с т у ф х ц ч ш щ ъ ы ь э ю я   - + / *
      = < > ( ) [ ] { } . , ! ? ; : ' " # | $ % ~ @

   Замечание. ПУСТО - это специальный символ.  Мы будем рисовать
его на ленте как "░" (чтобы не путать с пробелом, который идет в
алфавите после буквы "я").  В  начальный момент все ячейки ленты
заполнены символом ПУСТО. Говорят, что лента - пустая.



Пример программы для Корректора.

   Задача. На ленте написано трехсимвольное слово,  и в началь-
ный момент окно установлено на его  начало. Написать программу,
которая меняет местами первый и последний символ.

                     ┬─┬─┬─╦═╦─┬─┬─┬─┬─┬
                     │░│░│░║к║о│т│░│░│░│
                     ┴─┴─┴─╩═╩─┴─┴─┴─┴─┴
Решение.

ЭТО Перевертыш
 ЯЩИК+            // Поместить первый символ в ящик
 ПОВТОРИ 2 ВПРАВО // Идти в конец слова
 ОБМЕН            // Обменять местами символы в ящике и на ленте
 ПОВТОРИ 2 ВЛЕВО  // Идти в начало слова
 ОБМЕН            // Обменять местами символы в ящике и на ленте
КОНЕЦ


        Корректор  был  придуман автором статьи в 1986 (двумя  годами
     позже Кукарачи). Как давно это было! Эти ребята-робята ровестни-
     ки школьной информатики. Но в те, ершовские времена, никто с ни-
     ми так не обращался. Не шинковали ими капусту и не  чистили кар-
     тошку, как  это  делают теперь школьники Роботландского сетевого
     университета.


Лексический анализатор Корректора
---------------------------------

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

 Постановка задачи.

   Программа  должна  проверить запись на ленте и поместить  ре-
зультат проверки  справа от нее в виде двух  букв "ош", "цл" или
"др".
 Здесь:
ош - запись числом не является
цл - запись есть "целое"
др - запись есть "дробь"

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


                                   │
// Окошко перед записью            │
ЭТО вход                           │Состояние (вход)
 ВПРАВО                            │Смотрим следующий символ
 ЕСЛИ  ЦИФРА ТО целое              │
 ИНАЧЕ ошибка                      │
КОНЕЦ                              │
                                   │
ЭТО целое                          │Состояние (целое)
  ВПРАВО                           │Смотрим следующий символ
  ЕСЛИ       ПУСТО  ТО ответ_целое │
  ИНАЧЕ ЕСЛИ ЦИФРА  ТО целое       │
  ИНАЧЕ ЕСЛИ /      ТО дробь?      │
  ИНАЧЕ                ошибка      │
КОНЕЦ                              │
                                   │
ЭТО дробь?                         │Состояние (дробь?)
  ВПРАВО                           │Смотрим следующий символ
  ЕСЛИ ЦИФРА ТО дробь              │
  ИНАЧЕ ошибка                     │
КОНЕЦ                              │
                                   │
ЭТО дробь                          │Состояние (дробь)
  ВПРАВО                           │Смотрим следующий символ
  ЕСЛИ       ПУСТО ТО ответ_дробь  │
  ИНАЧЕ ЕСЛИ ЦИФРА ТО дробь        │
  ИНАЧЕ ошибка                     │
КОНЕЦ                              │
                                   │
// Запишем ответ "ош" и            │
// вернемся к месту ошибки         │
ЭТО ошибка                         │
 ВПРАВО                            │Перемещение окна в конец записи
 ЕСЛИ ПУСТО ТО ответ_ошибка        │и запись ответа.
 ИНАЧЕ ошибка                      │
 ВЛЕВО                             │Возврат к месту ошибки
КОНЕЦ                              │
                                   │
ЭТО ответ_ошибка                   │
 ВПРАВО ПИШИ о                     │
 ВПРАВО ПИШИ ш                     │
 ПОВТОРИ 2 ВЛЕВО                   │
КОНЕЦ                              │
                                   │
ЭТО ответ_целое                    │
 ВПРАВО ПИШИ ц                     │
 ВПРАВО ПИШИ л                     │
 ПОВТОРИ 2 ВЛЕВО                   │
КОНЕЦ                              │
                                   │
ЭТО ответ_дробь                    │
 ВПРАВО ПИШИ д                     │
 ВПРАВО ПИШИ р                     │
 ПОВТОРИ 2 ВЛЕВО                   │
КОНЕЦ                              │


                            * * *

   Следующий раз  попробуем  продвинуться  в  более сложные темы
трансляции. А  теперь,  по сложившейся традиции, несколько задач
Корректора  из  конкурса  Роботландского  сетевого  университета
прошлого года.
   Первые  три  задачи - это обычный лексический анализ  (разной
сложности).
   А вот в задачах 4 и 5 нужно таки, написать транслятор! В этих
упражнениях после проверки выражения нужно его ВЫЧИСЛЯТЬ! А как?
Ведь  Корректору  незнакомы  арифметические операции. Для  этого
парня, что "2+2", что "дядя Вася" - всего лишь цепочка символов,
ничуть не лучше и не хуже одна другой.
   Ничего не поделаешь, нужен транслятор.


Задача 1. (5 баллов)
 Введем следующее определение:
Определение
-----------
<число> ::= <целое> | <дробь>
<целое> ::= <цифра> | <целое><цифра>
<дробь> ::= <простая> | <десятичная>
<простая> ::= <целое>/<целое>
<десятичная> ::= .<целое> | <целое>. | <целое>.<целое>
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

   Задание. Напишите программу, которая проверяет запись на лен-
те и помещает результат проверки справа от нее в виде двух букв:
   ош - запись числом не является;
   цл - запись есть "целое";
   дс - запись есть "десятичная";
   пр - запись есть "простая".
   В начальный момент окошко расположено перед записью, а в кон-
це работы - сразу за ней, если в записи нет ошибок.
   Если запись неверная, окошко должно указывать  на первый оши-
бочный символ.

   Примеры работы программы:

Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┐
│░│░║░║1│2│7│░│░│░│░│    ─────>     │░│░│░│1│2│7║░║ц│л│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┘

Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┐
│░│░║░║1│!│9│░│░│░│░│    ─────>     │░│░│░│1║!║9│░│о│ш│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┘


Задача 2. (8 баллов)
 Введем следующее определение:
Определение
-----------
<выражение> ::= <число>+<число> | <выражение>+<число>
<число> ::= <целое> | <дробь>
<целое> ::= <цифра> | <целое><цифра>
<дробь> ::= .<целое> | <целое>. | <целое>.<целое>
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

   Задание. Напишите программу, которая проверяет запись на лен-
те и помещает результат проверки справа от нее в виде  двух букв:
   ош - запись не является ни числом, ни выражением;
   чс - запись есть "число";
   вр - запись есть "выражение";

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

   Примеры работы программы:

Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┐
│░│░║░║1│2│7│░│░│░│░│    ─────>     │░│░│░│1│2│7║░║ч│с│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┐
│░│░║░║1│.│7│░│░│░│░│    ─────>     │░│░│░│1│.│7║░║ч│с│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┘

Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┐
│░│░║░║1│.│7│+│1│░│░│    ─────>     │░│░│░│1│.│7│+│1║░║в│р│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┘

Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┐
│░│░║░║1│!│9│░│░│░│░│    ─────>     │░│░│░│1║!║9│░│о│ш│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┘

Задача 3. (10 баллов)
 Введем следующее определение:
Определение
-----------
<выражение> ::= <число> |
                <выражение>+<выражение> |
                <выражение>-<выражение> |
                (<выражение>)

<число>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

   Задание. Напишите  программу, которая проверяет  правильность
записи выражения. Если запись правильная, то  нужно  за  ней  на
ленте записать "ок".
   Если запись ошибочная, то нужно записать "ош" и дополнительно
установить окошко на первый неверный символ или на место обнару-
жения ошибки в случае ошибок со скобками.
   В начальный момент окошко расположено  перед  записью.

   Примеры работы программы:

Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─┬─┬─╥─┬─╦═╦─┬─┬─┐
│░│░║░║1│+│(│8│)│░│░│    ─────>     │░│░│░│1│+│(║8│)║░║о│к│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─┴─┴─╨─┴─╩═╩─┴─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐
│░│░║░║1│░│░│░│░│░│░│    ─────>     │░│░│░│1║░║о│к│░│░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┐
│░│░║░║1│-│2│)│░│░│░│    ─────>     │░│░│░│1│-│2║)║░│о│ш│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┘


Задача 4. (9 баллов)
 Введем следующее определение:
Определение
-----------
<выражение> ::= <число> | <выражение>+<число>
<число>   ::= 0 | 1 | 2

   Задание. Напишите программу, которая вычисляет выражение, ес-
ли оно правильное,  или записывает на ленту сообщение "ош", если
запись содержит  ошибку. Если запись ошибочная, то дополнительно
к сообщению "ош" окошко должно указывать на первый неверный сим-
вол.
   Замечание 1. Значение выражения должно быть записано на ленте
в виде обычного целого десятичного числа.
   Замечание 2. Предполагается, что результат вычислений выраже-
ния меньше числа, равного длине алфавита Корректора.

   В начальный момент окошко расположено перед записью.

   Примеры работы программы:

Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┐
│░│░║░║1│+│2│░│░│░│░│    ─────>     │░│░│░│1│+│2║=║3│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┐
│░│░║░║1│░│░│░│░│░│░│    ─────>     │░│░│░│1║=║1│░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┘

Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐
│░│░║░║1│.│7│+│1│░│░│    ─────>     │░│░│░│1║.║7│+│1│░│о│ш│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘

Задача 5. (9 баллов)
 Введем следующее определение:
Определение
-----------
<выражение> ::= <число> | <выражение>+<число> | <выражение>-<число>
<число>   ::= 0 | 1 | 2

   Задание. Напишите программу, которая вычисляет выражение, ес-
ли оно правильное,  или записывает на ленту сообщение "ош", если
запись содержит  ошибку. Если запись ошибочная, то дополнительно
к сообщению "ош" окошко должно указывать на первый неверный сим-
вол.
   Замечание 1. Значение выражения должно быть записано на ленте
в виде обычного целого десятичного числа.
   Замечание 2. Предполагается, что конечный и промежуточные ре-
зультаты вычислений меньше числа, равного длине алфавита Коррек-
тора.
   Замечание 3. Если конечный или промежуточный результат вычис-
ления выражения окажется меньше нуля, записать  на ленту сообще-
ние "ав" (авария)  и установить окошко на знак операции, которая
приводит к отрицательному результату.
   В начальный момент окошко расположено перед записью.

   Примеры работы программы:

Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─┬─┬─╥─┬─╦═╦─┬─┐
│░│░║░║1│-│1│+│2│░│░│    ─────>     │░│░│░│1│-│1║+│2║=║2│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─┴─┴─╨─┴─╩═╩─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┐
│░│░║░║1│░│░│░│░│░│░│    ─────>     │░│░│░│1║=║1│░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐
│░│░║░║1│.│7│+│1│░│░│    ─────>     │░│░│░│1║.║7│+│1│░│о│ш│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐
│░│░║░║1│-│2│+│1│░│░│    ─────>     │░│░│░│1║-║2│+│1│░│а│в│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘

                       * * *

Ответ на упражнение
------------------

ЭТО Прогулка
  ВНИЗ
  ЕСЛИ НЕ А ТО Прогулка
  ВВЕРХ
КОНЕЦ

   На первый  взгляд  кажется,  что  программа неверная: команда
ВНИЗ, записанная последней, работает только один раз, и Кукарача
в общем случае не вернется в исходное положение на поле.  Но это
не  так.  Команда ВНИЗ сработает ровно столько, сколько  команда
ВВЕРХ, обеспечивая перемещение исполнителя в исходную точку.

                      -------------------------------------------
                                   Продолжение следует
