Как часто меняется конечный автомат?Если оно какое-то время остается постоянным, я перевожу его в жестко запрограммированную подпрограмму на любом языке, который я предпочитаю.
Откуда берется диаграмма перехода конечного автомата?Это происходит из регулярного выражения?Вы знаете, что можете перевести это непосредственно в структурированный код без предварительного построения набора дуг.На самом деле, для начала может быть проще написать этот код.
Затем я либо просто создаю эту часть приложения, либо динамически компилирую и связываю ее с dll и динамически загружаю ее.Последнее занимает всего пару секунд.
Конечные автоматы настолько просты, что в основном они должны работать за небольшую долю времени, необходимого для загрузки буфера ввода / вывода.Они не должны делать никакого ненужного выделения памяти, построения структуры данных или чего-то подобного.
Помните, конечный автомат, представленный в виде набора состояний и кортежей дуг, является теоретической моделью.Он существует, как и машины Тьюринга, чтобы доказать теоремы об этом.Как и машина Тьюринга, это не обязательно хороший метод реализации в коде.
Просто чтобы показать вам, что я имею в виду, рассмотрим регулярное выражение для десятичных целых чисел:
dd*
где «d» означает цифру.В качестве конечного автомата (кортежей) это будет:
A d -> B
B d -> B
как код:
char c = getc();
if (DIGIT(c)){
c = getc();
while(DIGIT(c)){
c = getc();
}
}
Видите сходство этого кода с регулярным выражением?Не думайте о c = getc() как о «получить следующий символ с».Думайте об этом как «принять текущий символ с».Я надеюсь, что вы видите, что код не может стать намного быстрее, чем этот.
Если вы действительно начинаете с набора дуг, вы можете сгенерировать это:
c = getc();
A:
if (DIGIT(c)){c = getc(); goto B;}
goto END;
B:
if (DIGIT(c)){c = getc(); goto B;}
goto END;
END:
, которыйэто код спагетти, но не больше, чем набор дуг, и он будет таким же быстрым, как и структурированный код.(Фактически, это более или менее то, во что компилятор преобразует ваш структурированный код.)