3.2. Лексические анализаторы

                                    А вы
                                    ноктюрн сыграть
                                    могли бы
                                    на флейте водосточных труб?

                                                 В.В.Маяковский


Лексический анализ выражений
----------------------------
   Как известно, Кукарача  и  Корректор не понимают языка прог-
раммирования.
   Когда мы записываем  в программе ПОВТОРИ 5 ВПРАВО, то знаем,
что эта запись  исполнителю не доступна. Ведь такой команды нет
в его СКИ. Тем не  менее,  когда  программа работает, Корректор
послушно сдвигает окно на ленте вправо на 5  клеток, а Кукарача
сам перемещается на пять клеток вправо.
   Дело в том, что запись ПОВТОРИ 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 │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤



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


 Программа для Корректора

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

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


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

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

Отступление в "большую" информатику.
   Задачи на  лексический  анализ выражений занимают в "большой"
информатике важное место. Описанный  способ  решения применяется
достаточно  часто.  При этом  диаграмма  переходов  записывается
обычно в виде двумерного массива (таблицы).
   Для нашего определения (*) этот массив выглядит так:
┌───────┬─────────────────────┬─────┬──┬─────┬─────────────┐
│       │ класс нового символа│     │  │     │             │
│       └─────────────┐       │цифра│/ │ПУСТО│все остальное│
│предыдущее состояние │       │  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, а лексический анализатор (**) останется неизменным.

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