Конечные автоматы и обработка текстов

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

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

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

Если в конце текста программа оказывается в состоянии "после", то следует напечатать звездочку (и кончить работу).

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

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

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

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

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

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

Замечание. Эта программа не воспринимает вложенные комментарии: строка вроде

{{комментарий внутри} комментария}

превратится в

комментария}

(в начале стоят два пробела). Обработка вложенных комментариев конечным автоматом невозможна (нужно "помнить число скобок" - а произвольное натуральное число не помещается в конечную память).

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

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

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

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

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

5.2. Ввод чисел

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

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

Будем называть десятичной записью такую последовательность символов:$$\langle \text {0 {или более пробелов}}\rangle\ \langle \text {1 {или более цифр}}\rangle,$$ а также такую:$$\langle \text {0\ {или более пробелов}}\rangle\ \langle \text {1\ {или более цифр}}\rangle{.} \langle \text {1\ {или более цифр}}\rangle.$$ Заметим, что согласно этому определению$$\setbox0\hbox{\verb*|1. 1|} {1.} \qquad \qquad {.1} \qquad \qquad \box0 \qquad \qquad {-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 ( $$=123\,000\,000$$ ). Нарисовать соответствующую картинку.

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

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