Итак, задача:
Нужно написать модуль\метод\функцию\объект, позволяющий разбирать строки, содержащие следующие элементы:
- Собственно цифры-буквы и прочие символы языков
- места вставки: подстрока между символами {}
- переменные: набор буков и цифр, начинающийся со знака % и буквы. Переменная может располагаться только в месте вставки
- Формат переменной: произвольный набор символов, идущий после описания переменной и отделенный от нее символом ":". (на самом деле в формате также были ограничения, однако для простоты о них я рассказывать не буду).
- Для отображения в конечной строке открывающей или закрывающей фигурных скобок их нужно экранировать собой же. Т.е. для вывод открывающей фигурной скобки нужно написать {{.
Решение.
Как только появилась эта задача, в голове всплыла теория конечных автоматов, которую я курсе на третьем учил (или просто сдавал) в университете.
В подробности самой теории вдаваться не буду, все можно почитать на той же википедии (http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82).
В общих чертах смысл в том, что задается некий алфавит (перечень возможных элементов входной строки), а также набор состояний. Переход из состояния в состояние жестко фиксирован и зависит от поступившего на вход элемента алфавита.
Таким образом строится таблица переходов, по которой можно осуществлять разбор строк (ну или текстов. Например, трансляторы языков строятся на тех же принципах).
По сути в задачах такого рода главным является как раз определение входного алфавита и состояний.
В нашем случае входной алфавит можно описать следующим образом:
обычная строка - просто набор символов за исключением фигурных скобок.
открывающая фигурная скобка
закрывающая фигурная скобка
знак % - воспринимается как отдельный элемент алфавита только в месте вставки
двоеточие - воспринимается как отдельный элемент алфавита только в месте вставки
описание переменной - набор букв и цифр, начиная с буквы; воспринимается как отдельный элемент алфавита только в месте вставки.
Состояния:
Обычное состояние, оно же стартовое - в этом состоянии мы ждем любой из стандартных элементов входного алфавита (обычную строку либо фигурные скобки)
Состояние открытой фигурной скобки - в этом состоянии мы ждем либо еще одну открывающую фигурную скобку, либо % как символ определения переменной
Состояние определения переменной - в этом состоянии ждем элемент алфавита "описание переменной"
Состояние ожидания двоеточия - из названия все понятно )
Состояние формата - ждем описание формата переменной
Состояние ожидания закрывающей фигурной скобки
Конечное состояние - мы все разобрали
Состояние ошибки - где-то пришел неожиданный элемент алфавита
Переход между состояниями показан на картинке ниже (я не стал изображать здесь конечное состояние и состояние ошибки. В состояние ошибки можно перейти из любого состояния, кроме обычного, если пришел не отображенный на рисунке элемент алфавита; в конечное состояние можно перейти лишь из обычного, если мы разобрали всю строку):
Реализация.
Хоть в итоге разработка и велась на JavaScript, но сначала каркас я решил написать на C#, т.к. это сделать мне быстрее, привычнее и удобнее. Да и отладить базовую логику, используя Visual Studio куда удобнее, чем дебаггер хрома )
Итак, что нам нужно.
Во-первых, входная точка. Или другими словами класс, представляющий собой наш конечный автомат. Не мудрствуя лукаво, так его и обзовем, FiniteStateMachine.
В этом классе должен быть метод, который и будет содержать логику разбора строки. Пусть будет Process. Пусть он возвращает булев флаг, указывающий на то, успешно ли прошел разбор или нет. Также в автомате, поскольку он является основой взаимодействия с пользователем, неплохо было бы сохранить результат разбора.
Что же может быть результатом разбора? Тут варианта 2: либо набор лексем, либо какая-то ошибка.
Каждая лексема из итогового набора должна содержать собственно значение, а также некий тип, показывающий, что в последствии с этой лексемой делать.
В моем случае лексемы могут быть трех типов: литерал, переменная и формат переменной. Хоть здесь и не рассмотрена дальнейшая работа с результатами разбора, однако разделение на этих три типа позволяет легко формировать финальную строку:
- литерал мы просто переписываем в выходную строку
- вместо переменной мы берем некоторое значение из переданного набора (по соответствию имени переменной)
- к выбранной переменной применяем формат, если он был задан.
Итого создадим класс для лексемы:
public class Lexem
{
public LexemType Type { get; set; }
public string Value { get; set; }
}
Перечисление типов лексем:
public enum LexemType
{
Literal,
Variable,
Format
}
А в классе конечного автомата создадим ридонли список лексем и метод для установки новой лексемы:
private IList m_lexems = new List();
public IList Lexems
{
get { return m_lexems; }
}
public void AddLexem(string value, LexemType type)
{
m_lexems.Add(new Lexem() { Type = type, Value = value });
}
Что касается ошибки.
Можно было бы конечно сразу формировать строку описания ошибки, однако это лишило бы возможности локализации. Поэтому я решил сделать перечисление типов ошибок и хранить в автомате именно элемент этого перечисления. Таким образом прикладной разработчик (пользователь автомата) может без труда получить условно код ошибки и обработать его так, как ему вздумается.
Собственно перечисление и свойство автомата ниже:
public enum ErrorCodes
{
SingleOpenBracket, // после открывающей скобки нет ни еще одной скобки, ни знака процента
SingleCloseBracket, // одинарная закрывающая скобка в месте, где их должно быть 2
NoCloseBracket, // после описания переменной идет символ, отличный от : и закрывающей скобки
NoVariable, // после % идет некорректный символ
NoFormat // после : идет сразу закрывающая скобка
}
public ErrorCodes ErrorCode { get; internal set; }
С автоматом разобрались.
Теперь пришла очередь разобраться с состояниями и переходами между ними.
В описанной реализации я решил использовать способ, когда каждое состояние определяется отдельным классом и само отвечает за то, в какое состояние нужно перейти в зависимости от входного элемента (возвращая новое состояние как результат работы). Конечный же автомат всего лишь устанавливает начальное состояние, а также циклично вызывает метод обработки у текущего активного состояния до тех пор, пока мы не окажемся в конечном состоянии либо состоянии ошибки.
По сути схема проста: создаем базовый класс для всех состояний с определением виртуального метода обработки строки, наследники (по одному на каждое состояние), и циклим обработку в автомате.
Базовый класс состояний:
public class State
{
protected FiniteStateMachine m_stateMachine;
public State(FiniteStateMachine stateMachine)
{
m_stateMachine = stateMachine;
}
public virtual State Process(ref string inputString)
{
throw new NotImplementedException();
}
}
Основной цикл обработки:
StatesManager.Initialize(this);
ActiveState = StatesManager.StartState;
while (ActiveState != StatesManager.ErrorState &&
ActiveState != StatesManager.EndState)
{
ActiveState = ActiveState.Process(ref inputStringCopy);
}
Пару слов о написанном выше.
Для начала касательно состояния.
Во-первых, в нем есть поле для хранения ссылки на сам автомат. Нужно оно для того, чтобы можно было добавлять лексемы в коллекцию или записывать код ошибки в поле автомата.
Во-вторых, строка в метод обработки передается по ссылке. Это сделано для того, чтобы во время работы метода можно было просто и легко изменять начальную строку, удаляя из нее обработанные символы. Таким образом я не создаю лишние переменные, а также могу легко определить необходимость перехода в конечное состояние: строка будет пустой.
Теперь об основном цикле обработки. В нем фигурирует обращение к классу StatesManager, о котором я не упоминал. Смысл этого класса в том, чтобы хранить в себе инстанцированные объекты состояний. Ведь нет необходимости при переходе на каждое последующее состояние заново создавать объект класса состояния. Куда лучше единожды все классы инстанцировать, а потом их использовать. Именно в этом и заключается смысл класса менеджера состояний:
public static class StatesManager
{
public static StartState StartState { get; private set; }
public static EndState EndState { get; private set; }
public static OpenBracketState OpenBracketState { get; private set; }
public static VariableState VariableState { get; private set; }
public static ErrorState ErrorState { get; private set; }
public static ColonState ColonState { get; private set; }
public static CloseBracketState CloseBracketState { get; private set; }
public static FormatState FormatState { get; private set; }
///
/// Общая инициализация состояний.
///
///
public static void Initialize(FiniteStateMachine stateMachine)
{
//...
}
}
Сам код методов обработки состояний не особо интересен, поэтому здесь его не привожу.
Единственное, что стоит выделить, так это то, что для состояния определения переменной и формата использовались простейшие регулярные выражения, описанные ниже:
Regex regEx = new Regex(@"^\S\w*");
Regex regEx = new Regex(@"[^\}]+");
Ниже показана диаграмма классов получившегося модуля:
Перевод на JavaScript и дальнейшая обработка.
Поскольку в проекте (а точнее в продукте), над которым я неустанно тружусь, используется прототипное наследование, и уже давно были написаны функции для инициализации классов, то перенос кода не составил никакого труда.
Но есть 2 вещи, которые я хотел бы упомянуть.
1. в JavaScript просто взять и передать входной параметр по ссылке не получится. Поэтому входным параметром методов обработки в состояниях пришлось делать объект вида
{ inputString: ... }
В самом методе inputString сохранялся, обрабатывался, а затем обратно присваивался в переменную объекта.
2. Для изменения (удаления символов) строки я использовал функцию slice, которая, если я не ошибаюсь, является самой быстрой из всего набора функций для вырезания кусков строк. Ведь о быстродействии тоже забывать нельзя :)
Что касается дальнейшей обработки.
Здесь все просто.
В метод, внутри которого вызывается разбор на лексемы, помимо входной строки также передается json-объект, содержащий некоторые свойства. Именно эти свойства мы и используем при подстановке вместо переменных, найденных в итоговой строке.
Комментариев нет:
Отправить комментарий