Цели: приобретение навыков конструирования и программной реализации простых детерминированных конечных автоматов.
Критерии полноты
Область применения конечных автоматов: трансляторы (синтаксический анализ, “регулярные выражения”), системы управления (аппаратные контроллеры, сетевые протоколы), моделирование систем объектов, включая физические устройства.
Понятие конечного автомата уже вводилось в “Основах вычислений”. Ниже оно рассмотрено более подробно и дано в традиционной формулировке. На вход автоматов будем отправлять “символы”.
Конечный автомат (КА; автомат с конечным множеством состояний) finite automaton (FA), finite state machine (FSM) — абстрактная машина, которая:
Итак, математически конечный автомат задаётся пятёркой (A, Σ, s0, a, ρ), где:
Часто конечные автоматы изображаются в виде диаграмм, на которых состояния изображены в виде кружков или овалов, которые соединены обозначающими переходы стрелками, помеченными соответствующими входными символами. Непомеченные стрелки отвечают переходу “при всех прочих (неуказанных) входных символах”. При этом принимающие состояния помечают двойной или более широкой границей кружка, а входное состояние стрелкой, не имеющей привязки к состоянию исхода.
Детерминированный конечный автомат (ДКА) deterministic finite automaton (DFA) — конечный автомат, для которого правило ρ является функцией только текущего состояния и входного символа. Вместо функции ρ можно использовать конечное множество правил вида A×Σ → Σ (троек), при этом необходимо, чтобы для каждого элемента A×Σ существовало не более одного правила.
Диаграммы удобны при составлении и анализе конечных автоматов. Построенную диаграмму легко “механически” перевести в программный код, моделирующий (реализующий) соответствующий ДКА. Однако, сделать это можно различными способами. Выбор конкретного способа зависит от:
С точки зрения п.1 нужно определить:
Существуют отдельные библиотеки, позволяющие строить произвольные конечные автоматы и решающие все или многие из упомянутых вопросов. Здесь же мы ограничимся “ручным” кодированием достаточно простых случаев.
Пусть дано:
Какие строки принимает этот автомат?
Итак, закодируем рассмотренный выше автомат в классической форме “цикл+switch по состоянию”.
Цикл будет считывать символы с потока ввода, пока это возможно, или не произойдёт застопоривание. Признак отсутствия застопоривания будем хранить в явной форме в переменной running. Результат функции — ответ на вопрос “пришёл ли в конце работы автомат в принимающее состояние”.
Для удобства продублируем схему.
// Возвращает истину, если автомат остановился в принимающем состоянии.
bool dfa_example(std::istream &is)
{
int state = 0;
bool running = true;
for (char input; is.get(input) && running; ) switch (state)
{
case 0:
if (input == 'a')
state = 1;
else
running = false;
break;
case 1:
if (input == 'b')
state = 2;
else
running = false;
break;
case 2:
if (input == 'c')
state = 3;
else if (input == 'b')
state = 4;
else
running = false;
break;
case 3:
state = 0;
break;
case 4:
if (input == 'b')
state = 1;
else
running = false;
break;
}
// Состояние 4 -- принимающее.
return state == 4;
}
Тот же автомат можно представить в объектной форме. Объект автомата будет обрабатывать по одному символу, который передаётся ему извне. Т.е. в данном примере цикл for вынесен в код, использующий автомат.
// Конечный автомат в объектной оболочке, отвязанный от istream -- принимает по одному символу.
class Dfa_example
{
int state;
public:
// Конструктор по умолчанию устанавливает начальное состояние.
Dfa_example()
: state(0) {} // список инициализации: здесь то же, что state = 0
// Проверить, находится ли автомат в принимающем состоянии.
bool accepts() const // const говорит, что вызов данной функции не меняет состояние объекта
{
return state == 4;
}
// Возвращает ложь, если автомат застопорился (можно проигнорировать).
// Возвращает истину, если автомат не застопорился и ожидает следующий символ.
bool operator()(char input)
{
switch (state)
{
case 0:
if (input == 'a')
state = 1;
else
return false;
break;
case 1:
if (input == 'b')
state = 2;
else
return false;
break;
case 2:
if (input == 'c')
state = 3;
else if (input == 'b')
state = 4;
else
return false;
break;
case 3:
state = 0;
break;
case 4:
if (input == 'b')
state = 1;
else
return false;
break;
default:
assert(false); // сюда должно быть невозможно попасть
}
return true; // нет застопоривания
}
};
Распознавание символьного литерала C++. Рассмотрим упрощённый синтаксис символьного литерала: непустая последовательность символов, заключённая в одинарные кавычки ', возможно экранирование кавычки символом \.
Данную диаграмму легко “перевести” на C++.
/// Просматривает диапазон массива символов [from, to).
/// Возвращает указатель на символ, следующий за последним принятым (т.е. за литералом).
/// Возвращает nullptr, если литерал не был успешно распознан.
const char* char_lit(const char *from, const char *to)
{
// Возможные состояния автомата.
enum
{
open_quote, // ожидается открывающая '
close_quote, // ожидается закрывающая '
not_quote, // первый символ литерала, не может быть '
escape, // после \
accepted, // литерал закончился
stuck // застопоривание: не литерал
} state = open_quote;
while (from != to)
{
const char ch = *from++;
switch (state)
{
case open_quote:
state = ch == '\''? not_quote : stuck;
break;
case not_quote:
switch (ch)
{
case '\\': state = escape; break;
case '\'': state = stuck; break;
default: state = close_quote;
}
break;
case close_quote:
switch (ch)
{
case '\\': state = escape; break;
case '\'': state = accepted; return from;
default:; /* ничего не менять */
}
break;
case escape:
/* просто пропустить символ */
state = close_quote;
break;
case stuck:
return nullptr;
default:
assert(!"impossible FSM state occured");
}
}
return nullptr; // слишком рано кончилась строка
}
Не составит труда заметить, что полученный код несколько избыточен. Мы можем убрать некоторые состояния автомата: достаточно проверить, что первый символ — кавычка до входа в цикл, и тогда состояние open_quote не нужно. Состояния stuck и accepted можно убрать, потому что переход в них соответствует возвращению значения из функции.
/// Просматривает диапазон массива символов [from, to).
/// Возвращает указатель на символ, следующий за последним принятым (т.е. за литералом).
/// Возвращает nullptr, если литерал не был успешно распознан.
const char* char_lit(const char *from, const char *to)
{
// Вытащим open_quote: данное состояние имеет смысл только на первом символе.
if (from == to || *from++ != '\'')
return nullptr;
// Возможные состояния автомата.
enum
{
close_quote, // ожидается закрывающая '
not_quote, // первый символ литерала, не может быть '
escape // после \
} state = not_quote;
while (from != to)
{
const char ch = *from++;
switch (state)
{
case not_quote:
if (ch == '\'')
return nullptr;
state = ch == '\\' ? escape : close_quote;
break;
case close_quote:
if (ch == '\'')
return from;
if (ch == '\\')
state = escape;
break;
case escape:
/* просто пропустить символ */
state = close_quote;
break;
default:
assert(!"impossible FSM state occured");
}
}
return nullptr; // слишком рано кончилась строка
}
Впрочем, аналогично состоянию open_quote можно убрать и состояние not_quote, выполнив проверку второго символа последовательности на неравенство ' также перед циклом.
/// Просматривает диапазон массива символов [from, to).
/// Возвращает указатель на символ, следующий за последним принятым (т.е. за литералом).
/// Возвращает nullptr, если литерал не был успешно распознан.
const char* char_lit(const char *from, const char *to)
{
// Вытащим open_quote: данное состояние имеет смысл только на первом символе.
if (from == to || *from++ != '\'')
return nullptr;
// Вытащим not_quote: данное состояние имеет смысл только на втором символе.
if (from == to || *from == '\'')
return nullptr;
// Возможные состояния автомата.
enum
{
close_quote, // ожидается закрывающая '
escape // после \
} state = *from++ == '\\'? escape: close_quote;
while (from != to)
{
const char ch = *from++;
switch (state)
{
case close_quote:
if (ch == '\'')
return from;
if (ch == '\\')
state = escape;
break;
case escape:
/* просто пропустить символ */
state = close_quote;
break;
default:
assert(!"impossible FSM state occured");
}
}
return nullptr; // слишком рано кончилась строка
}
Теперь внутри цикла осталось всего два возможных состояния: close_quote и escape. Заменим state на булевскую переменную await_quote (её значение соответствует условию state == close_quote). Заодно совместим проверки перед циклом в один if.
const char* char_lit(const char *from, const char *to)
{
// Не менее трёх символов.
// Первый символ должен быть кавычкой, второй символ не должен быть кавычкой.
if (to - from < 3 || from[0] != '\'' || from[1] == '\'')
return nullptr;
bool await_quote = from[1] != '\\';
for (from += 2; from != to;)
{
const char ch = *from++;
if (await_quote)
{
if (ch == '\'')
return from;
if (ch == '\\')
await_quote = false;
}
else
await_quote = true;
}
return nullptr; // слишком рано кончилась строка
}
Впрочем, из-за того, что варианту await_quote == false соответствует просто пропуск очередного символа с переходом в состояние await_quote == true, мы можем вообще избавиться от явного состояния автомата: в ситуации await_quote == false следует просто пропустить ещё один символ.
const char* char_lit(const char *from, const char *to)
{
// Не менее трёх символов.
// Первый символ должен быть кавычкой, второй символ не должен быть кавычкой.
if (to - from < 3 || from[0] != '\'' || from[1] == '\'')
return nullptr;
for (++from; from != to;)
{
switch (*from++)
{
case '\\':
if (from++ == to)
return nullptr;
break;
case '\'':
return from;
default:; /* do nothing */
}
}
return nullptr;
}
Тот же самый цикл можно переписать без switch-case компактнее.
const char* char_lit(const char *from, const char *to)
{
// Не менее трёх символов.
// Первый символ должен быть кавычкой, второй символ не должен быть кавычкой.
if (to - from < 3 || from[0] != '\'' || from[1] == '\'')
return nullptr;
for (++from;;)
{
if (from == to)
return nullptr;
const char ch = *from++;
if (ch == '\\' && from++ == to)
return nullptr;
if (ch == '\'')
return from;
}
}
Сокращение числа состояний и избавление от явного состояния в виде переменной может считаться оптимизацией (такой программный код, скорее всего, будет выполняться быстрее и будет компактнее и после компиляции). Однако вносить в него изменения в случае необходимости может стать сложнее.
Дальнейшая оптимизация быстродействия подобного кода может производиться путём обработки нескольких символов (байт) за одну итерацию.
Данный пример показывает, что от схемы КА мы можем прийти к достаточно компактному и эффективному коду. Таким образом, КА предоставляет нам инструмент, позволяющий в ряде случаев “получать” эффективные линейные алгоритмы-обработчики последовательностей данных, которые может быть сложно придумать сразу. Что ещё важнее, анализировать корректность автомата проще, чем некоторого “вроде бы правильного” кода. Поэтому получить корректный и близкий к оптимальному код из автомата также может быть проще.
Дополнительный пример: распознавание (и считывание значения) записи (литерала) целого числа в формате, принятом в стандартном C++14:
Решение варианта 4 из работы 6. Требуется классифицировать последовательность как (–1) монотонно (нестрого) убывающую, (+1) монотонно (нестрого) возрастающую, (0) состоящую из одинаковых элементов или как (2) содержащую как возрастающие, так и убывающие подпоследовательности. Указанные номера будем использовать в качестве состояний автомата. Все состояния будем считать принимающими. На вход автомата будем подавать числа: (–1), если в очередной паре соседних элементов второй меньше первого, (0), если они равны, и (+1), если второй больше первого.
Шаблон функции сравнения:
template <class Val>
inline int compare(const Val &a, const Val &b)
{
return a < b ? 1 : b < a ? -1 : 0;
}
Перепишем данную диаграмму на C++.
enum Sequence_type
{
monotone_decreasing = -1,
empty_or_constant = 0,
monotone_increasing = 1,
not_monotone = 2
};
/// ValIt -- итератор (обобщение указателя),
/// последовательность принадлежит полуинтервалу [from, to).
template <class ValIt>
Sequence_type sequence_type(ValIt from, ValIt to)
{
Sequence_type state = empty_or_constant;
if (from != to)
{
for (ValIt a = from, b = std::next(from); b != to; a = b++)
{
const int relation = compare(*a, *b);
switch (state)
{
case monotone_decreasing:
if (relation == 1)
state = not_monotone;
break;
case empty_or_constant:
if (relation == -1)
state = monotone_decreasing;
else if (relation == 1)
state = monotone_increasing;
break;
case monotone_increasing:
if (relation == -1)
state = not_monotone;
break;
case not_monotone:
break; /* do nothing */
default:
assert(!"sequence_type: impossible Sequence_type");
}
}
}
return state;
}Попробуйте преобразовать (сократить) данный код аналогично тому, как это было сделано в примере 2 выше.
Конечный автомат с выходом finite state transducer (FST) — конечный автомат, расширенный возможностью вывода. Задаётся шестёркой (A, Σ, s0, a, ρ, B), где B — алфавит символов вывода, а ρ сопоставляет паре из A×Σ пару из Σ×B*. Здесь B* есть множество всех строк (включая пустую) на алфавите B. Этот второй элемент (строка) идёт на вывод автомата на соответствующем шаге.
Детерминированный автомат с выходом ограничен относительно произвольного конечного автомата с выходом аналогично “простому” конечному автомату (распознавателю) тем, что ρ: A×Σ → Σ×B* есть математическая функция в обычном смысле и может быть представлена в виде конечного множества правил с различными левыми частями.
Замечание 1
Описанный выше автомат с выходом также называется автоматом Мили Mealy machine. В автоматах Мили своя выходная строка отождествляется с каждым переходом (стрелкой на диаграмме).
Существует более узкий класс автоматов, называемых автоматами Мура Moore machine, в которых выход формируется только в зависимости от состояния, в которое приходит автомат. Т.е. можно считать, что в автомате Мура отображение ρ имеет вид A×Σ → Σ, и задано дополнительное отображение β: Σ → B*. При каждом переходе, автомат выводит β от текущего состояния. Таким образом, в автомате Мура выходная строка отождествляется с каждым состоянием.
Замечание 2
Следует понимать, что “преобразование входного текста в выходной” — это абстрактная формулировка. Элементами B могут быть некие “события” или “действия”, тогда B* — множество всех возможных последовательностей событий или применения действий из множества B. Такой автомат может быть управляющим устройством, посылающим управляющие сигналы управляемой системе.
Замечание 3
Наконец, автомат-распознаватель (“автомат без выхода”) можно считать частным случаем автомата с выходом, в котором (в простейшем случае) B = { ожидает, застопорился, принял } — набор событий, которые могут происходить при распознавании строки.
В качестве примера рассмотрим конечный автомат, решающий задачу нормализации переводов строк. Среди управляющих символов кодировки ASCII есть два символа, традиционно используемые для оформления переводов строк: код 10 (LF line feed, сдвинуть каретку на строку вниз, \n в C) и код 13 (CR carriage return, вернуть каретку в начало строки, \r в C). Есть четыре варианта их использования: LF (Unix-подобные системы), CR LF (Windows, а также текстовые сетевые протоколы, например, HTTP), а также CR и LF CR, не используемые на современных системах. Все эти четыре варианта будем “переводить” в \n. Диаграмма автомата приведена ниже.
Обозначения на стрелках имеют вид символ на входе (опционально) / символ на выходе, где символ на выходе может быть “nl” (перевод строки, '\n'), “*" (символ на входе, т.е. вывести прочитанный символ) или “-” (ничего не выводить).
Итак, наш конечный автомат будет заменять во входном тексте все четыре варианта переводов на '\n', а прочие символы оставлять неизменными. Переведём эту схему на C++.
// Возвращает указатель на символ, следующий за последним записанным символом.
char* crlf_normalize(const char *from, const char *end, char *to)
{
enum { Other, LF, CR } state = Other;
while (from != end)
{
const char input = *from++;
switch (state)
{
case Other:
switch (input)
{
case '\n':
*to++ = '\n';
state = LF;
break;
case '\r':
*to++ = '\n';
state = CR;
break;
default:
*to++ = input;
}
break;
case LF:
switch (input)
{
case '\n':
*to++ = '\n';
break;
case '\r':
state = Other;
break;
default:
*to++ = input;
state = Other;
}
break;
case CR:
switch (input)
{
case '\n':
state = Other;
break;
case '\r':
*to++ = '\n';
break;
default:
*to++ = input;
state = Other;
}
break;
default:
assert(!"crlf_normalize: impossible state");
}
}
return to;
}
При реализации конечных автоматов вместо явно выписанного цикла и switch по состоянию нередко применяется простой переход по меткам (отвечающим состояниям) с помощью инструкции goto. Такой код также непосредственно соответствует схеме автомата и может порождаться автоматически (программой по схеме автомата). Его преимущества перед использованием switch состоят в потенциально большей производительности полученного машинного кода (роль переменной, хранящей текущее состояние автомата, играет специальный регистр процессора — указатель инструкции), что может быть заметно как раз при прямой обработке массивов символов в памяти. Его недостаток — меньшая гибкость.
char* crlf_normalize(const char *from, const char *end, char *to)
{
char input;
Other:
if (from == end) return to;
input = *from++;
if (input == '\n') goto LF;
if (input == '\r') goto CR;
*to++ = input;
goto Other;
LF:
*to++ = '\n';
if (from == end) return to;
input = *from++;
if (input == '\r') goto Other;
if (input == '\n') goto LF;
*to++ = input;
goto Other;
CR:
*to++ = '\n';
if (from == end) return to;
input = *from++;
if (input == '\n') goto Other;
if (input == '\r') goto CR;
*to++ = input;
goto Other;
}
Конечно, данный код можно немного модифицировать, чтобы убрать goto, организующие явные циклы. Можно вообще убрать все goto, не вводя дополнительных переменных, но код от этого не станет проще, короче и понятнее.
Теперь представим, что автомат обрабатывает блок данных заранее неизвестной длины, получая их блоками ограниченного размера (имеет буфер ввода и буфер вывода). Таким образом, иногда необходимо приостанавливать автомат, чтобы загрузить или передать следующую порцию данных. Если взять вариант на основе switch, то благодаря явно хранящемуся состоянию несложно модифицировать код так, чтобы можно было продолжить обработку следующей порции данных с того состояния, в котором автомат закончил обработку предыдущей порции. Для хранения переменной состояния можно организовать объект-обёртку как в примере 1. Однако, к сожалению, то же самое нельзя сказать о варианте на основе goto: в нём состояние не хранится в переменной.
Следующий пример является синтезом этих двух вариантов, позволяющий обрабатывать данные в потоке с загрузкой в промежуточные буферы. Инструкция switch обеспечивает “восстановление” автомата с места останова. Метки case могли бы быть расположены сразу после инструкций return, отражая логику работы (продолжение после возврата), но в примере они “подняты”, чтобы входной диапазон обязательно проверялся на пустоту.
// Автомат, запоминающий состояние между вызовами.
class Crlf_normalizer
{
enum { Other, LF, CR } state;
public:
// Конструктор устанавливает начальное состояние.
Crlf_normalizer() : state(Other) {}
// Оператор "скобки" позволяет вызывать объект данного класса как функцию.
// Возвращает указатель на символ, следующий за последним записанным символом.
char* operator()(const char *from, const char *end, char *to)
{
char input;
switch (state)
{
Other_:
case Other:
if (from == end) // выход
return state = Other, to;
input = *from++;
if (input == '\n') goto LF_;
if (input == '\r') goto CR_;
*to++ = input;
goto Other_;
LF_:
*to++ = '\n';
case LF:
if (from == end) // выход
return state = LF, to;
input = *from++;
if (input == '\r') goto Other_;
if (input == '\n') goto LF_;
*to++ = input;
goto Other_;
CR_:
*to++ = '\n';
case CR:
if (from == end) // выход
return state = CR, to;
input = *from++;
if (input == '\n') goto Other_;
if (input == '\r') goto CR_;
*to++ = input;
goto Other_;
default:
assert(false);
return to;
}
}
};
Объект Crlf_normalizer является функтором — его можно использовать как функцию crlf_normalize из предыдущих вариантов, однако, в отличие от них, можно применять его повторно, передавая данные по частям, “разрывая” поток данных в произвольной позиции.
Пусть дан файл с исходным кодом на языке C++. Требуется удалить из него все комментарии. Будем решать эту задачу с помощью конечного автомата, получающего на вход исходный файл и выдающего на выход тот же файл, но уже без комментариев. На схеме указаны следующие состояния:
\, возможно, присоединяющий следующую строку к комментарию./sp обозначает вывод пробела.Схема несколько упрощена по сравнению с современным синтаксисом C++ (не поддерживаются ' внутри числовых литералов, а также raw-литералы символов и строк).
Приведённый ниже код, реализующий данный автомат, рассчитан на обработку одного файла исходного кода, целиком размещённого в оперативной памяти. Для выполнения этой задачи в память (объект string) считывается всё содержимое потока ввода. Затем данные обрабатывает автомат, и результат записывается в поток вывода.
// Автомат читает блок символов из диапазона [from, to)
// и записывает результат обработки в массив по адресу out.
char* cpp_decomment(const char *from, const char *to, char *out)
{
Normal_mode:
while (from != to)
{
switch (const char in = *from++)
{
case '\'':
*out++ = in;
goto Char_literal;
case '\"':
*out++ = in;
goto String_literal;
case '/':
goto Possible_comment;
default:
*out++ = in;
}
}
return out;
Char_literal:
while (from != to)
{
switch (const char in = *from++)
{
case '\\': // Char_escape
*out++ = in;
if (from != to)
*out++ = *from++;
break;
case '\'':
*out++ = in;
goto Normal_mode;
default:
*out++ = in;
}
}
return out;
String_literal:
while (from != to)
{
switch (const char in = *from++)
{
case '\\': // String_escape
*out++ = in;
if (from != to)
*out++ = *from++;
break;
case '\"':
*out++ = in;
goto Normal_mode;
default:
*out++ = in;
}
}
return out;
Possible_comment:
if (from == to)
return *out++ = '/', out;
switch (const char in = *from++)
{
case '/': goto Oneliner;
case '*': goto Multiliner;
default:
out[0] = '/';
out[1] = in;
out += 2;
goto Normal_mode;
}
Oneliner:
while (from != to)
{
switch (const char in = *from++)
{
case '\n':
*out++ = in;
goto Normal_mode;
case '\\': // Comment_concat
if (from != to)
++from; // just skip the next char
break;
default:; // skip
}
}
return out;
Multiliner:
while (from != to)
{
if (*from++ == '*')
goto Possible_end;
}
return out;
Possible_end:
if (from != to && *from++ == '/')
{
*out++ = ' ';
goto Normal_mode;
}
goto Multiliner;
}
Вместо метки в коде, каждому состоянию можно сопоставить собственную функцию. Тогда goto заменяются на вызов функции. Однако, это имеет практический смысл только в том случае, если компилятор гарантированно выполняет оптимизацию хвостового вызова (т.е. фактически заменяет вызовы функций на те же самые goto).
Ряд вариантов ниже предлагают выполнить аналогичную задачу (удаление комментариев) для других языков программирования. Её можно решать путём замены автомата в коде вышеприведённого примера на автомат для заданного языка программирования.
Удаление комментариев из исходных файлов на языке MATLAB.
% или (вариант 2) с ....%{, заканчиваются %}.'the simplest'. Escape-последовательности как в C.Удаление комментариев из исходных файлов на языке Pascal (предполагается диалект Free Pascal).
//.{, заканчиваются }.(*, заканчиваются *).'no abstract escape-seqs'. Escape-последовательности не предусмотрены.Удаление комментариев из исходных файлов на языке Python.
Упрощённый синтаксис:
#.'left' или в двойных кавычках "right". Escape-последовательности как в C.'''too 'much' nuisance''' или в утроенных двойных кавычках """let me speak "Abracadabra"!""".Удаление комментариев из исходных файлов на языке Lua.
Упрощённый синтаксис:
--.--[[, заканчиваются ]].'say "Hello!"\n'. Escape-последовательности как в C."I don't say \"Hello!\"\0". Escape-последовательности как в C.[[ до ]] без escape-последовательностей.[=[ до ]=] без escape-последовательностей. Строго говоря, может быть произвольное число знаков = в открывающей скобке (п.3 — частный случай), столько же знаков = должно быть в закрывающей скобке. Корректное поведение в такой ситуации можно реализовать с помощью дополнительного состояния: целочисленного счётчика знаков =.Удаление комментариев из исходных файлов на языке Julia.
Упрощённый синтаксис
#.#=, заканчиваются =#. Строго говоря, они ведут себя как скобки, т.е. сколько было открывающих #=, столько затем должно быть и закрывающих =#. Корректное поведение в такой ситуации можно реализовать с помощью дополнительного состояния: целочисленного счётчика текущей глубины вложенности (количества встреченных к моменту открытых #=).'\\'. Escape-последовательности как в C."This is a \"quote\"". Escape-последовательности как в C."""Contains "quote" characters""".r"^\s*(?:#|$)".Удаление комментариев из исходных файлов на языке Haskell.
Упрощённый синтаксис
--, после которых идёт либо -, либо пробельный символ, либо буква (это важно, т.к. в коде на Haskell возможны операции вроде -->, которые не должны случайно открывать комментарий).{-, заканчиваются -}. Могут быть вложенными как скобки, т.е. на каждую открывающую пару {- должна приходиться своя закрывающая пара -}. Корректное поведение в такой ситуации можно реализовать с помощью дополнительного состояния: целочисленного счётчика текущей глубины вложенности (количества встреченных к моменту открытых {-).'\t'. Escape-последовательности как в C."Hello,\n". Escape-последовательности как в C.Заменить маленькие буквы, начинающие предложения, на большие. Определить количество предложений (дополнительное состояние: счётчик предложений). Считать, что каждое предложение заканчивается по крайней мере одной буквой, за которой следует последовательность точек, восклицательных или вопросительных знаков, а затем или заканчивается входная последовательность, или идёт последовательность пробельных символов.
Выполнить распознавание записи (литерала) числа с плавающей точкой в формате, принятом в языке C. Автомат должен определять правую границу записи и сохранять распознанное число по переданной ссылке на переменную.
Примеры литералов: .10, 1., 2e2, 1.05E-50, 500.e+100.
Построить конечный автомат, распознающий последовательности из нулей и единиц, содержащие чётное число единиц и не содержащие единиц, идущих подряд друг за другом.
Примеры
00000 — принять
01000 — не принимать (нечётное число единиц)
00011 — не принимать (две единицы подряд)
10100 — принять
10110 — не принимать (нечётное число единиц и две единицы подряд)
Кувшинов Д.Р. © 2016