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

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


                       Напрасно я объяснял своим друзьям, что  телеви-
                    зионная техника  не  только не проста, но согласно
                    выражению  Незнайкина  дьявольски сложна,  что она
                    затрагивает различные области  физики, что положе-
                    ние еще усложняется из-за отсутствия международно-
                    го стандарта.
                       Ничего не  помогло.  Я  должен был покориться и
                    написать "Телевидение?.. Это очень просто!"
                                                             Е.Айсберг


   Эти заметки для тех, кто твердо уверен, что кулинария и мясо-
рубка - это не одно и тоже, но тем не  менее  готов ради хорошей
кухни покрутить ручку, пренебрегая всякими электрическими  изли-
шествами. Ведь "ручная" котлета сохраняет больше витаминов!
   Если переходить от  красивых  аллегорий к сермяжной жизни, то
речь пойдет  о  Роботландском  Университете, где школьники пишут
трансляторы в среде Кукарачи и Корректора.
   Те, кто знаком с этими чудаками (исполнителями), выразительно
засмеялись. Ну, что ж, чтобы веселья прибавилось, скажу пару слов
о Кукараче. Для тех, кто не знает. Пусть посмеются тоже.

Исполнитель Кукарача
--------------------
   Средой исполнителя  является  клетчатое  поле, обычный размер
которого 10x10. Но поле может быть продолжено вправо и вниз, ес-
ли это диктуется условием задачи.

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

   На рисунке  символом "¤" изображен исполнитель. Кукарача мо-
жет переползать из  клетки в клетку вверх, вниз, влево, вправо,
но не по  диагонали. Выход исполнителя за пределы поля запрещен
(ситуация "Не могу!"). Кроме самого исполнителя в каждой клетке
может находиться кубик  с нанесенным на его грань символом. Ку-
карача, перемещаясь по  полю,  может толкать один или несколько
кубиков перед собой и даже "сбрасывать" кубики за пределы поля.
   Некоторые кубики на поле могут иметь "скрытые" надписи: счи-
тается, что такие кубики расположены в  клетке "надписью вниз".
Толкая скрытый кубик, Кукарача перемещает его в следующую клет-
ку по ходу движения и переворачивает.
   Толкая кубик,  исполнитель  в  состоянии прочитать символ на
его грани независимо от того, была ли надпись обычной или скры-
той (перевернутой).

             Система команд Кукарачи (СКИ)

ВПРАВО - сместиться на одну клетку вправо на поле
ВЛЕВО  - сместиться на одну клетку влево на поле
ВВЕРХ  - сместиться на одну клетку вверх на поле
ВНИЗ   - сместиться на одну клетку вниз на поле
СТОЯТЬ - "пустая" команда, исполнитель не выполняет никаких
         действий

   Как видите,  Кукарача  - прямой наследник Муравья Звенигород-
ского. И таких насекомых от информатики в России развелось нема-
ло. Предполагается, что программирование робота, визуально пред-
ставленного на экране, гораздо понятнее зеленому юнцу, чем возня
с абстрактными вычислениями на Фортране, Бейсике или Паскале.
   И это, конечно, правильно, хотя обсуждать этот вопрос мне не-
интересно.
   Но теперь самое  время дружно посмеяться еще раз всем вместе:
о какой трансляции  можно  говорить в этой примитивной клетчатой
среде? Чего здесь транслировать-то, и во что?

   Вы заинтригованы?
   Ну, тогда читатель за мной! К вершинам тараканьей трансляции.

   Для начала помянем добрым словом стариков Бэкуса и Наура.

Язык Бэкуса-Наура
-----------------
   Язык, при  помощи которого описывают другие языки, называется
метаязыком. Понятно,  что русский язык является метаязыком. Ведь
на этом языке мы описываем, например, язык исполнителя Кукарача.
Однако русский язык, как и любой другой естественный язык, слиш-
ком неточен и словообилен для строгих формальных описаний.
   В программировании очень часто применяют метаязык  Бэкуса-На-
ура для описания  формальных  конструкций. Впервые этот язык был
использован для описания языка программирования Алгол-60.
   В языке Бэкуса-Наура используются следующие символы (метасим-
волы):

<>    - скобки, выделяющие определяемое понятие;
::=   - составной символ, который читается "по определению есть";
|     - символ, обозначающий альтернативу, читается "или".

   Примеры определений.

   Пример 1
    <знак сложения> ::= +
Знак сложения по определению есть символ "+".

   Пример 2.

    <цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

   Цифра по определению есть 0 или  1, или 2, или 3, или 4, или
5, или 6, или 7, или 8, или 9.

   Наиболее интересным является  использование языка Бэкуса-На-
ура для создания рекурсивных определений.

   Пример 3.

  <слово> ::= <буква> | <слово><буква>             (1)
  <буква> ::= а | м                                (2)

   Прочитать это определение можно так:
   "Слово"  по  определению есть: или "буква", или объект,  про
который мы знаем, что он "слово",  вслед  за  которым  записана
"буква".
   "Буква" - это либо символ "а", либо символ "м".
   Как видите, первая строка в определении содержит рекурсию!
   Проверим,  соответствуют ли  определению  "слово"  следующие
объекты: "а", "ма", "ав".
   1) Объект "а" - слово, потому что:
   а - буква (правило 2), а буква является словом (правило 1).
   2) Объект "ма" - слово, потому что:
   "м" - это слово (так  как  "м"  -  это буква по правилу 2, а
значит, слово по правилу  1).  Слово, за которым следует буква,
является словом (правило 1), значит, "ма" - слово.
   3) Объект "ав" - не слово, потому что за  словом "а" следует
не буква в смысле правила 2.

   Как проверить соответствие объекта определению? Нужно  следо-
вать правилам, заданным в этом определении.  Если правила рекур-
сивные, значит  и  проверка  будет содержать рекурсию. Проверим,
например, что объект "мама" является словом.

   Объект "мама" - слово, если словом является "мам" (правила 1
и 2).
   Объект "мам" -  слово, если словом является "ма"(правила 1 и
2).
   Объект "ма"  - слово, если  словом является "м" (правила 1 и
2).
   Объект "м" - слово (правило 2).

   Заметим, что по определению 1 словом является любая (не пус-
тая!)  последовательность  из букв "а" и "м". Наблюдение  легко
доказать используя метод математической индукции.

        Напоминание.  Математическая индукция  -  это  универсальный
     способ доказательства утверждения F, содержащее зависимость  от
     целого числа n. Зависимость обозначается как F(n).
        Доказательство методом математической  индукции проводится в
     три шага.
       1) База индукции.
        Утверждение F(n) проверяется при некотором начальном  n = n0
     (например, при n0 = 1).
       2) Индуктивное предположение.
        Выдвигается  индуктивное предположение.  Оно  заключается  в
     том, что утверждение F(n-1) считается справедливым (n > n0).
       3) Индуктивный переход.
        Доказывается справедливость F(n) с учетом индуктивного пред-
     положения, то есть предположения о справедливости F(n-1). Дока-
     зательство основывается на попытке представить зависимость F(n)
     через F(n-1).
        Итак, пользуясь методом математической индукции, мы  доказы-
     ваем, что F(n) справедливо, если справедливо  F(n-1). Это дока-
     зательство, наряду с проверкой F для  одного конкретного значе-
     ния n0 позволяет утверждать, что F(n) справедливо всегда. Поче-
     му?
        Мы доказали, что утверждение F(n) справедливо, если справед-
     ливо F(n-1). Этого достаточно чтобы утверждать,  что F(n) спра-
     ведливо для любого  n > n0, если F(n0) проверено непосредствен-
     но.

     ....
     F(5) справедливо, если справедливо F(4)
     F(4) справедливо, если справедливо F(3)
     F(3) справедливо, если справедливо F(2)
     F(2) справедливо, если справедливо F(1)
     F(1) - база индукции, справедливость проверена непосредственно.

        Мы как  будто заставляем работать некоторого исполнителя для
     проверки справедливости утверждения F для каждого конкретного n
     по следующей рекурсивной программе:

     ЭТО Индукция (n)
      ЕСЛИ n = 1
       ТО ОТВЕТ("F - справедливо для любого n")
       ИНАЧЕ Индукция (n-1)
     КОНЕЦ

        Например, процедура Индукция(3) рекурсивно выполнит процеду-
     ру Индукция(2). Ведь из  доказательства  индуктивного  перехода
     следует, что F(3) справедливо, если справедливо F(2). Процедура
     Индукция(2), аналогично, выполнит процедуру Индукция(1). В пос-
     ледней процедуре рекурсия заканчивается: ведь F(1)  справедливо
     - это проверенная база индукции.
        Приведенная программа, конечно, лишена всякого практического
     смысла. Она  просто  демонстрирует  математическую индукцию как
     рекурсивный процесс, который,  пользуясь доказанным индуктивным
     переходом сводит проверку F(n) к проверке F(1).

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

   1) База индукции. F(1) состоит из одного символа "а" или "м"
и в  силу правила (2) является буквой, а  значит в силу правила
(1) - словом.
   2) Индуктивное предположение. Считаем, что F(n-1) - слово.
   3) Индуктивный переход. Докажем, что F(n) - тоже слово.
   Представим F(n) для n > 1 в виде двух частей:  последний сим-
вол и все остальное. Тогда F(n) можно записать как:

                     F(n)  = F(n-1) s                 (*)

   Здесь s  - это последний символ  в F(n), он  может принимать
значение "a" или "m", то есть является буквой в силу (2).
   Итак, мы представили F(n) как слово F(n-1) за которым следу-
ет буква. Но тогда в силу (1) - F(n) тоже слово.

   Ниже следует список задач с  ответами.  Эти  задачи можно ис-
пользовать на занятиях со школьниками для  практической работы с
определениями, заданными в нотации Бэкуса-Наура.

 Задача 1.
   Определение 1
   -------------
<имя> ::= <буква> | <имя><буква> | <имя><цифра>
<буква> ::= x | y
<цифра> ::= 1 | 2

   Проверить, являются  ли  приведенные  ниже объекты именами в
смысле определения 1.

1) x   2) xy    3) x1    4) 2y    5) xxxxxxx  6) y321  7) 1212
8) x21    9) X21

Ответ: именами не являются объекты 4), 6), 7), 9)

   Доказать следующее утверждение.
   Именем является любая последовательность из букв и цифр, которая
начинается с буквы.

 Задача 2.
   Определение 2
   -------------
<имя> ::= <буква> | <имя><буква> | <имя><цифра>
<буква> ::= <пусто> | x | y
<цифра> ::= 1 | 2
<пусто> ::=
   Проверить, являются  ли  приведенные  ниже объекты именами в
смысле определения 2.

1) x   2) xy    3) x1    4) 2y    5) xxxxxxx  6) y321  7) 1212

Ответ: именем не является объект 6)

   Верно ли следующие утверждения.
   а) Любая последовательность  из  символов "x" и "1" является
именем в смысле определения 2.
   б) Совпадает ли  множество  таких "имен" со множеством имен,
задаваемых определением 2?

Задача 3.
   Определение 3
   -------------
<выражение> ::= <число> |(<выражение>) | <число> + <выражение>
<число> ::= 20 | 30
   Проверить, являются ли приведенные ниже объекты  выражениями
в смысле определения 3.
1) 2  2) 20  3) 2030 4) 20+30 5) (20) 6) (20+30) 7) 20 + (30+30)
8) 20 +
9) + 30
10) (20+(30+(20+20)))

Ответ: выражениями не являются объекты 1), 3), 8), 9)

Задача 4.
   Запишите следующее определение при  помощи  языка Бэкуса-На-
ура.
   Пример - это несколько цифр, соединенные  между собой знаком
"-".

Ответ:
<пример> ::= <цифра> - <цифра> | <пример> - <цифра>
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Задача 5.
   Запишите при помощи языка Бэкуса-Наура определение натураль-
ного числа.

Ответ:
<натуральное число> ::= <ненулевая цифра> |
                        <натуральное число> <цифра>
<ненулевая цифра> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<цифра> ::= 0 |<ненулевая цифра>

Задача 6.
   Запишите при  помощи  языка  Бэкуса-Наура определение целого
числа.

 Ответ:
<целое> ::= <целое без знака> | +<целое без знака> | -<целое без знака>
<целое без знака> ::= <цифра> | <целое без знака><цифра>
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Задача 7.
Определение 4
-------------
<выражение> ::= <терм> | <выражение> + <терм>
<терм> ::= <первичный> | <терм> * <первичный>
<первичный> ::= x | y | z
   Проверить, являются ли приведенные ниже объекты  выражениями
в смысле определения 4.
1) z   2) x*y+z  3) x+y+z  4)  (x+y)*z  5) x*x  6) y+y*y+y
7) xy  8) +x     9) z+

Ответ: выражениями не являются объекты 4), 7), 8), 9)



Лексический анализ выражений
----------------------------

   Открою обман: я не умею писать трансляторы в среде Кукарачи!
   На самом деле это обман только наполовину:
   - я умею писать  в  среде Кукарачи лексические анализаторы, а
это, все же, составная часть транслятора;
   - я, на самом  деле, умею писать трансляторы в среде исполни-
теля Корректор!

   Как известно, исполнитель не понимает языка программирования.
   Когда мы записываем в  программе  ПОВТОРИ 5 ВПРАВО, то знаем,
что эта запись исполнителю не доступна. Ведь такой команды нет в
его СКИ. Тем  не менее, когда программа работает, Кукарача пере-
мещается на пять клеток вправо.
   Дело в  том, что запись ПОВТОРИ 5 ВПРАВО  - это команда языка
программирования, а язык программирования "понимает" не исполни-
тель, а компьютер, и то не сам, а с помощью транслятора.
   Транслятор  -  это  специальная программа, которая  переводит
текст с  языка  программирования  в последовательность команд из
СКИ робота. Эту последовательность команд компьютер передает ис-
полнителю. И Кукарача делает пять своих прыжков.
   Одна из важных задач трансляции -  сборка из последовательных
символов отдельных  элементов текста программы. Эти элементы на-
зываются лексемами.
   Лексический анализ выражений - это выделение в тексте лексем,
кирпичиков, из  которых строятся конструкции языка. До лексичес-
кого анализа текст рассматривается как однородная цепочка симво-
лов, после - как цепочка лексем.
   Например, текст
ПОВТОРИ 5 ВПРАВО
содержит 16 символов (среди них два символа пробела). После лек-
сического анализа, текст преобразуется в цепочку из трех лексем:
ПОВТОРИ  - ключевое слово, начало цикла
5        - число
ВПРАВО   - ключевое слово, команда из СКИ

Диаграмма переходов
-------------------

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

Определение.
<число> ::= <целое> | <дробь>
<целое> ::= <цифра> | <целое><цифра>                (*)
<дробь> ::= <целое>/<целое>
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

   Диаграмма переходов  для  анализа  записи  по определению (*)
изображается следующим образом:

      (ответ_целое)    (ошибка)
          ^             ^ ^
          │  остальное  │ │
    пусто │ ┌───────────┘ │ остальное
          │ │             │
          │ │     цифра   │
  ┌──── (целое) <───────(вход)
  │      ^ │
  │      │ │
  │цифра │ │/
  └──────┘ │
           │
           V       остальное
       (дробь?)────────────>(ошибка)
           │
 цифра     │
┌───────┐  │цифра
│       │  │
│       V  V      остальное
└──── (дробь)  ───────────>(ошибка)
           │
           │ пусто
           │
           V
     (ответ_дробь)

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

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


 Программа для Кукарачи

   Пусть запись расположена  во  второй строке, а исполнитель -
перед ней:

                    1 2 3 4 5 6 7 8 9 10
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
                 1 │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 2 │ │¤│з│а│п│и│с│ь│ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 3 │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤

   Задание. Проверить запись на  соответствие  определению (*).
   Если  запись  "целое" - установить исполнителя за записью  в
первой строке:
                    1 2 3 4 5 6 7 8 9 10
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
                 1 │ │ │з│а│п│и│с│ь│¤│ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 2 │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 3 │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤

   Если запись - "дробь" - в конце записи во второй строке:

                    1 2 3 4 5 6 7 8 9 10
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
                 1 │ │ │з│а│п│и│с│ь│ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 2 │ │ │ │ │ │ │ │ │¤│ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 3 │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤

   Если в записи есть ошибки, установить исполнителя под первой
из них:
                    1 2 3 4 5 6 7 8 9 10
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
                 1 │ │ │з│а│п│и│с│ь│ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 2 │ │ │ │ │¤│ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 3 │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤



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


   Не правда ли, программа  получилось,  пусть и не очень корот-
кая, но простая, предельно понятная и  даже  скучная?  Она  пол-
ностью соответствует построенной диаграмме.


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

Отступление в "большую" информатику.
   Задачи на  лексический  анализ выражений занимают в "большой"
информатике важное место. Описанный  способ  решения применяется
достаточно  часто.  При этом  диаграмма  переходов  записывается
обычно в виде двухмерного массива (таблицы).
   Для нашего определения (*) этот массив выглядит так:
┌───────┬─────────────────────┬─────┬──┬─────┬─────────────┐
│       │ класс нового символа│     │  │     │             │
│       └─────────────┐       │цифра│/ │ПУСТО│все остальное│
│предыдущее состояние │       │  0  │1 │  2  │     3       │
├─────────────────────┴───────┼─────┼──┼─────┼─────────────┤
│(вход)                     0 │  1  │4 │  4  │     4       │
│(целое)                    1 │  1  │2 │  0  │     4       │
│(дробь?)                   2 │  3  │4 │  4  │     4       │
│(дробь)                    3 │  3  │4 │  0  │     4       │
│(ошибка)                   4 │  0  │0 │  0  │     0       │
└─────────────────────────────┴─────┴──┴─────┴─────────────┘
   Этот массив, например, на Си можно записать так:

int diagramma [5] [4] =
{
  1, 4, 4, 4,
  1, 2, 0, 4,
  3, 4, 4, 4,
  3, 4, 0, 4,
  0, 0, 0, 0,
};

   Элемент diagramma[i][j] = m означает, что на диаграмме стрел-
ка, выходящая из состояния i при обнаружении символа с номером j
приводит в состояние m или приводит к завершению  работы, если m
= 0.  В последнем случае  программа должна выдать в качестве ре-
зультата число i  (или соответствующий ему текст - название сос-
тояния).
   Когда массив  переходов  задан,  анализ выражения выполняется
при помощи следующего кода:

int i = 0;
int j = diagramma [i] [TypeNextSymbol()];
do
{                                                (**)
  i = j;
  j = diagramma [i] [TypeNextSymbol()];
} while (j);

   Здесь функция TypeNextSymbol() читает следующий символ  вход-
ной записи и возвращает класс этого символа, то  есть в соответ-
ствии с таблицей переходов выдает:
0 - если символ "цифра";
1 - если символ "/";
2 - если символ "ПУСТО";
3 - в остальных случаях.

   Как видите, анализатор (**) совершенно не зависит от вида оп-
ределения (*). При смене определения (*) на другое (какой угодно
сложности) лексический анализатор (**) останется прежним и будет
содержать те же 7 строк программного кода. Будет меняться массив
diagramma, а лексический анализатор (**) останется неизменным.

   В большой информатике проблема та же, что и в малой: как пра-
вильно составить диаграмму переходов по заданному определению?
   Надо уметь понимать и  "чувствовать"  рекурсивность определе-
ния. А для этого нужен хороший практикум. Такие вещи не приходят
по наитию, нужно достаточно долго с  этим  работать.  Не  только
смотреть, как это  делают другие, а на самом деле практиковаться
самому, решать задачи.

                           * * *

   Вы не заметили? А  ведь  в приведенной программе для Кукарачи
есть одно тонкое место - процедура "ошибка":

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

   Кажется,  что  автор статьи свихнулся: как может эта  простая
процедура установить исполнителя точно под обнаруженной ошибкой?
РАЗВЕ ОНА ЭТО ДЕЛАЕТ?

   Кто понял в чем дело - молчите! Пусть остальные немного пому-
чаются! Следующий раз я обязательно займусь "разоблачением" это-
го рекурсивного фокуса.
   А теперь, несколько задач из конкурса Роботландского сетевого
университета прошлого года.

Задача 1  (5 баллов)
  Введем такое определение числа.
Определение 1
-------------
<число> ::= <цифра> | <число><цифра>    (1)
<цифра> ::= 0 | 1                       (2)

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

Задача 2  (7 баллов)
   Решить задачу 4,  но если запись не является числом, устано-
вить исполнитель под первым неверным символом  в записи. Напри-
мер:
                         1021
                           ¤
   Если запись - число, установить исполнитель  за последним ее
символом. Например:
                         1011¤

Задача 3. (8 баллов)

 Введем следующее определение числа:
Определение 2
-------------
<число>   ::= <целое> | <дробное>
<целое>   ::= <цифра> | <целое><цифра>
<дробное> ::= .<целое> | <целое>. | <целое>.<целое>
<цифра>   ::= 0 | 1

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

1)   1010¤

2)   121.34
      ¤
3)   .00¤

4)   .10.0
        ¤

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

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

Задача 5. (9 баллов)

 Введем следующее определение выражения
Определение 4
-------------
<выражение> ::= <число>+<число> | <число>+<выражение>
<число>   ::= <цифра> | <число><цифра>
<цифра> ::= 0 | 1
   Задание. Напишите программу для Кукарачи, которая проверяет,
является ли запись  на его поле выражением в смысле определения
4.
   В начальный  момент  исполнитель расположен перед кубиками с
записью во второй строке:
                         ¤запись
   Если проверяемая запись - выражение, установить исполнитель в
конец записи:
                         запись¤
   Если запись - не выражение, поставить исполнитель под первым
неверным символом:
                         запись
                           ¤

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

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