Мне было интересно, какая структура данных будет лучшей для представления DFA?
Я рассматриваю преобразование регулярного выражения в DFA и делаю эту конкретную функциональность библиотекой на Java.
Главное, что каждый объект в регулярном выражении содержит набор значений, а не одно строковое значение, такое как «car». В моем случае каждая сущность будет иметь множество свойств, таких как {car, Honda, 4x4, седан, ...} (хотя я не ищу автомобили, это просто пример).
Какие-либо предложения?
Если я правильно понимаю ваш вопрос, вы хотите иметь библиотеку сопоставления/фильтрации для произвольного регулярного языка по алфавиту с динамическими типами? Возвращаясь к примеру с вашим автомобилем, я полагаю, вы захотите создать выражение для сопоставления со списком, в котором все автомобили (имеют красный цвет, имеют от 2 до 6 пассажиров, и каждый пассажир находится между 8 и 88 лет) или (иметь 1 пассажира).
По совпадению, я сам искал что-то подобное (для проверки документов), и самое близкое, что я мог найти, было Цзин; Библиотека Java RELAX-NG. К сожалению, алфавит в Jing состоит из узлов XML, поэтому мою проблему это не решило. На данный момент я сам пытаюсь написать библиотеку, которая делает именно это (сопоставление с обычными языками по произвольному типу алфавита), на основе сопоставления с образцом в Jing. Если вы хотите помочь с этим, пожалуйста, дайте мне знать;).
Веб-поиск даст несколько примеров DFA в Java. Однако наилучшее представление зависит от конкретных требований вашего приложения; например как ваше приложение будет использовать DFA. Я думаю, вам нужно решить это для себя.
Я уверен, что этот ответ не будет полезен для исходного вопроса из-за данных, но если кто-то столкнется с этим из Google...
DFA и NFA можно хранить как таблицу перехода состояний, затем вы выполняете синтаксический анализ, перемещая таблицу по ссылкам как таковым.
