Глава 5. Конечные автоматы в задачах обработки текстов

     Глава 5. Конечные автоматы в задачах обработки текстов

     5.1. Составные символы, комментарии и т.п.

     5.1.1.  В  тексте  возведение  в степень обозначалось двумя
идущими подряд звездочками. Решено заменить это  обозначение  на
'^'  (так  что,  к  примеру, 'x**y' заменится на 'x^y'). Как это
проще всего сделать? Исходный текст разрешается читать символ за
символом, получающийся текст требуется печатать символ за симво-
лом.

     Решение. В каждый момент программа  находится  в  одном  из
двух состояний: "основное" и "после звездочки"

Состояние    Очередной        Новое       Действие
           входной символ   состояние

основное        *             после          нет
основное     x <> '*'        основное     печатать x
после           *            основное     печатать '^'
после        x <> '*'        основное     печатать *, x

Замечание.  При  этом '***' заменится на '^*' (но не на '*^'). В
условии задачи мы не оговаривали деталей, как это часто делается
- предполагается, что программа "должна действовать разумно".  В
данном  случае,  пожалуй,  самый  простой  способ объяснить, как
программа действует - это описать ее состояния и действия в них.

     5.1.2. Написать программу, удалающую из текста подслова ви-
да 'abc'.

     5.1.3. В паскале комментарии заключаются в фигурные скобки:

                begin {начало цикла}
                i:=i+1; {увеличиваем i на 1}

Написать программу, которая удаляла бы комментарии  и  вставляла
бы  вместо  исключенного  комментария  пробел  (чтобы '1{один}2'
превратилось бы не в '12', а в '1 2').

     Решение. Программа имеет два состояния: "основное" и "внут-
ри комментария".

Состояние    Очередной        Новое       Действие
           входной символ   состояние

основное        {             внутри         нет
основное     x <> '{'        основное     печатать x
внутри          }            основное     печатать пробел
внутри       x <> '}'         внутри         нет

     Замечание. Эта программа не воспринимает вложенные  коммен-
тарии: строка вроде
       '{{комментарий внутри} комментария}'
превратится в
        '  комментария}'
(в  начале  стоят два пробела). Обработка вложенных комментариев
конечным автоматом невозможна (нужно "помнить число скобок" -  а
произвольное натуральное число не помещается в конечную память).

     5.1.4. В паскалевских программах бывают также строки,  зак-
люченные в кавычки. Если фигурная скобка стречается внутри стро-
ки, то она не означает начала или конца комментария. В свою оче-
редь, кавычка в комментарии не означает начала или конца строки.
Как изменить программу, чтобы это учесть?

     Указание. Состояний будет три: основное,  внутри  коммента-
рия, внутри строки.

     5.1.5. Еще одна возможность многих реализаций паскаля - это
комментарии вида

      i:=i+1;     (*   here i is increased by 1  *)

при этом закрывающая скобка должна  соответствовать  открываюшей
(то  есть  { ... *) не разрешается). Как удалять такие коммента-
рии?

     5.2. Ввод чисел

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

     Более конкретно, представим себе такую ситуацию. Последова-
тельность  символов на входе делится на прочитанную и оставшуюся
части. Мы можем пользоваться функцией Next:char, которая возвра-
щает первый символ оставшей части, а также функцией Move,  кото-
рая перводит забирает первый символ из оставшейся части, перево-
дя его в категорию прочитанных.

        ---------------------|--------------------------
          прочитанная часть  | Next |  ?  |  ?  |  ?  |
        ---------------------|--------------------------


Будем  называть десятичной записью такую последовательность сим-
волов:

  <0 или более пробелов> <1 или более цифр>

а также такую:

  <0 или более пробелов> <1 или более цифр>.<1 или более цифр>

Заметим, что согласно этому  определению  '1.',  '.1',  '1.  1',
'-1.1' не являются десятичными записями. Сформулируем теперь за-
дачу точно:

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

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

    var state:
     (Accept, Error, Initial, IntPart, DecPoint, FracPart);

    state := Initial;
    while (state <> Accept) or (state <> Error) do begin
    | if state = Initial then begin
    | | if Next = ' ' then begin
    | | | state := Initial; Move;
    | | end else if Digit(Next) then begin
    | | | state := IntPart; {после начала целой части}
    | | | Move;
    | | end else begin
    | | | state := Error;
    | | end;
    | end else if state = IntPart then begin
    | | if Digit (Next) then begin
    | | | state := IntPart; Move;
    | | end else if Next = '.' then begin
    | | | state := DecPoint; {после десятичной точки}
    | | | Move;
    | | end else begin
    | | | state := Accept;
    | | end;
    | end else if state = DecPoint then begin
    | | if Digit (Next) then begin
    | | | state := FracPart; Move;
    | | end else begin
    | | | state := Error; {должна быть хоть одна цифра}
    | | end;
    | end else if state = FracPart then begin
    | | if Digit (Next) then begin
    | | | state := FracPart; Move;
    | | end else begin
    | | | state := Accept;
    | | end;
    | end else if
    | | {такого  быть не может}
    | end;
    end;

Заметьте,  что присваивания state:=Accept и state:=Error не соп-
ровождаются сдвигом (символ, который не может быть частью числа,
не забирается).

     Приведенная программа не запоминает  значение  прочитанного
числа.

     5.2.2. Решить предыдущую задачу с дополнительным требовани-
ем: если прочитанный кусок является десятичной записью, то в пе-
ременную val:real следует поместить ее значение.

     Решение.  При  чтении дробной части используется переменная
step - множитель при следующей десятичной цифре.

    state := Initial; val:= 0;
    while (state <> Accept) or (state <> Error) do begin
    | if state = Initial then begin
    | | if Next = ' ' then begin
    | | | state := Initial; Move;
    | | end else if Digit(Next) then begin
    | | | state := IntPart; {после начала целой части}
    | | | val := DigitValue (Next);
    | | | Move;
    | | end else begin
    | | | state := Error;
    | | end;
    | end else if state = IntPart then begin
    | | if Digit (Next) then begin
    | | | state := IntPart; val := 10*val + DigitVal(Next);
    | | | Move;
    | | end else if Next = '.' then begin
    | | | state := DecPoint; {после десятичной точки}
    | | | step := 0.1;
    | | | Move;
    | | end else begin
    | | | state := Accept;
    | | end;
    | end else if state = DecPoint then begin
    | | if Digit (Next) then begin
    | | | state := FracPart;
    | | | val := val + DigitVal(Next)*step; step := step/10;
    | | | Move;
    | | end else begin
    | | | state := Error; {должна быть хоть одна цифра}
    | | end;
    | end else if state = FracPart then begin
    | | if Digit (Next) then begin
    | | | state := FracPart;
    | | | val := val + DigitVal(Next)*step; step := step/10;
    | | | Move;
    | | end else begin
    | | | state := Accept;
    | | end;
    | end else if
    | | {такого  быть не может}
    | end;
    end;

     5.2.3. Та же задача, если перед  число  может  стоять  знак
"минус" или знак "плюс" (а может ничего не стоять).

     Формат  чисел  в этой задаче обычно иллюстрируют такой кар-
тинкой:

   -----      ---------
---| + |---->-| цифра |-------->--------------------->
 | -----  | | --------- | |                      |
 | -----  | |           | | -----     ---------  |
 |-| - |--| |----<------| |-| . |->---| цифра |--|
 | -----  |                 -----   | --------- |
 |        |                         |-----<-----|
 |--->----|


     5.2.4.  Та же задача, если к тому же после числа может сто-
ять показатель степени десяти, как  в  254E-4  (=0.0254)  или  в
0.123E+9 (=123000000). Нарисуйте соответствующую картинку.

     5.2.5. Что надо изменить в программе  задачи  5.2.2,  чтобы
разрешить пустые целую и дробную части (как в '1.', '.1' или да-
же '.' - последнее число считаем равным нулю)?

     Мы  вернемся  к  конечным автоматам в главе 10 (Сравнение с
образцом).