Глава 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 (Сравнение с образцом).