Обратно к goto
Задача
Дан текст (массив 8-битных символов), получить из него текст с нормализованными переводами строк. Предполагаются возможными следующие варианты оформления переводов строк:
- 1-символьные: LF (linefeed, символ с кодом 10, ‘\n’, ‘\xa’), CR (carriage return, символ с кодом 13, ‘\r’, ‘\xd’);
- 2-символьные: CR LF и LF CR.
Любой из этих вариантов должен заменяться на один символ LF.
Данный пример представляется мне не слишком простым и не слишком сложным, более того, можно даже позволить себе считать, что решение вышеприведённой задачи имеет практический смысл :).
Алгоритм
Проходим исходный массив подряд, нормализованную строку записываем в отдельный массив (в принципе, это можно делать и «на месте», поскольку нормализованная строка не может быть длиннее, чем исходная строка).
- Все символы, кроме LF и CR просто копируются, в случае же обнаружения CR или LF записываем перевод строки и переходим в состояние «встретился CR» или «встретился LF» соответственно. Если затем встретится не (LF или CR), то записываем встретившийся символ и выходим из этих состояний в исходное состояние.
- Если встретился тот же символ CR или LF соответственно, то записываем перевод строки и остаёмся в том же состоянии.
- Если же встретился «перекрёстный» символ LF или CR соответственно, то переходим в новое состояние «комбинация» (отвечающее двухсимвольному переводу строки), выход из которого производится с выводом перевода строки и «другого символа», если таковой встретился, либо возможен возврат в состояния «встретился CR» и «встретился LF» при получении соответствующих символов.
- Выход происходит, когда исходный массив будет просмотрен целиком.
Впрочем, нетрудно заметить, что по сути состояние «комбинация» совпадает с начальным состоянием «общее», т.е. состояния LF и CR попросту «поглощают» перекрёстный символ. Более подробно и ясно этот алгоритм можно представить в виде схемы конечного автомата.
Конечный автомат
Программа
Данная схема абсолютно механически переводится на язык программирования, допускающий переход по метке (инструкцию goto).
Пусть функция, реализующая автомат получает исходный массив в виде двух указателей from и end, первый из которых указывает на начало массива, а последний — на фиктивный элемент за последним, т.е. размер массива равен (end — from). Пусть результат записывается в массив, на начало которого указывает последний параметр функции — указатель to. Пусть функция возвращает указатель на элемент, следующий за последним записываемым (таким образом, будет легко определить, сколько символов было записано).
Итак, получим
char* normalize(const char *from, const char *end, char *to) { char ch; Begin_: if (from == end) return to; ch = *from++; if (ch == '\n') goto LF_; if (ch == '\r') goto CR_; *to++ = ch; goto Begin_; LF_: *to++ = '\n'; if (from == end) return to; ch = *from++; if (ch == '\r') goto Begin_; if (ch == '\n') goto LF_; *to++ = ch; goto Begin_; CR_: *to++ = '\n'; if (from == end) return to; ch = *from++; if (ch == '\n') goto Begin_; if (ch == '\r') goto CR_; *to++ = ch; goto Begin_; }
Данный код достаточно эффективен (хотя я не исключаю, что для этой задачи есть реализация получше). Состояние автомата определяется тем, какой участок кода исполняет процессор в данный момент. Не вводя переменные для явного хранения состояния автомата, можно придать данному коду немного более «структурный» вид, убрав goto. Код, впрочем, становится длиннее.
char* normalize(const char *from, const char *end, char *to) { char ch; while (from != end) { switch (ch = *from++) { case '\n': do { *to++ = '\n'; if (from == end) return to; ch = *from++; } while (ch == '\n'); if (ch != '\r') *to++ = ch; break; case '\r': do { *to++ = '\n'; if (from == end) return to; ch = *from++; } while (ch == '\r'); if (ch != '\n') *to++ = ch; break; default: *to++ = ch; } return to; }
Switch-case
Стандартный «структурный» подход к переводу конечных автоматов на язык программирования заключается во введении перечислимого типа, задающего набор возможных состояний автомата, переменной state, хранящей текущее состояние явно, и кодированию действий автомата в зависимости от текущего состояния в виде конструкции switch (state) { case … }, выполняемой в цикле.
Часто разница в производительности результирующего машинного кода варианта на основе switch-case не отличается заметно от варианта на goto (банальное чтение символа из потока ввода может оказаться достаточно дорогой операцией на фоне затрат на выполнение switch-case), однако у варианта switch-case есть ещё то практическое преимущество, что такой автомат позволяет более гибкое использование (здесь для простоты не будем рассматривать сопроцедуры как вариант реализации автомата) — явно хранимое состояние можно сохранить и потом запустить автомат «со старого места».
В данной задаче можно себе представить загрузку символов в буфер (массив), обработка и… повторная загрузка и обработка, но автомат нельзя каждый раз запускать из состояния Begin, т.к. 2-символьный перевод строки может оказаться разбит между двумя загрузками и в результате интерпретирован как два перевода, а не один. Т.е. автомат должен «помнить» своё последнее состояние.
Однако, никто не запрещает нам реализовать гибридный вариант, который я и приведу здесь.
struct NewLineNormalizer { enum State { Begin, LF, CR }; State state; explicit NewLineNormalizer(State st = Begin) : state(st) {} char* operator()(const char *from, const char *end, char *to) { if (from == end) return to; char ch; switch (state) { case LF: goto LF_; case CR: goto CR_; default:; // Begin falls-through here } do { switch (ch = *from++) { case '\n': do { *to++ = '\n'; if (from == end) return state = LF, to; LF_: ch = *from++; } while (ch == '\n'); if (ch != '\r') *to++ = ch; break; case '\r': do { *to++ = '\n'; if (from == end) return state = CR, to; CR_: ch = *from++; } while (ch == '\r'); if (ch != '\n') *to++ = ch; break; default: *to++ = ch; } } while (from != end); state = Begin; return to; } };
Ниже UPD 19.04.2015.
Switch-case + goto
Хотя выше и приведены варианты, «избавленные» от goto, выглядят они явно запутаннее, чем goto, отвечающие схеме автомата. В последнем случае («гибридном варианте») всё равно использовался goto для «заскока» в нужное место ранее остановленного автомата. Поэтому я решил добавить ещё один «гибридный вариант» — уже на основе оригинального goto-варианта.
class NewLineNormalizer { enum { Begin, LF, CR } state; public: // Конструктор устанавливает начальное состояние. NewLineNormalizer() : state(Other) {} // Оператор "скобки" позволяет вызывать объект данного класса как функцию. // Возвращает указатель на символ, следующий за последним записанным символом. char* operator()(const char *from, const char *end, char *to) { char input; switch (state) { Begin_: case Begin: if (from == end) // выход return state = Begin, to; input = *from++; if (input == '\n') goto LF_; if (input == '\r') goto CR_; *to++ = input; goto Begin_; LF_: *to++ = '\n'; case LF: if (from == end) // выход return state = LF, to; input = *from++; if (input == '\r') goto Begin_; if (input == '\n') goto LF_; *to++ = input; goto Begin_; CR_: *to++ = '\n'; case CR: if (from == end) // выход return state = CR, to; input = *from++; if (input == '\n') goto Begin_; if (input == '\r') goto CR_; *to++ = input; goto Begin_; default: assert(false); return to; } } };