Структура данных для представления DFA - PullRequest
2 голосов
/ 12 октября 2010

Мне было интересно, что будет лучшей структурой данных для представления DFA?

Я смотрю на преобразование регулярного выражения в DFA и создание этой конкретной функциональности как библиотеки на Java.

Главное, чтобы каждая сущность в регулярном выражении несла набор значений, а не одно строковое значение, например "car".В моем случае каждая сущность будет иметь много свойств, таких как {автомобиль, Honda, 4x4, седан, ...} (хотя я не ищу автомобили, это всего лишь пример.)1007 *

Ответы [ 3 ]

0 голосов
/ 12 октября 2010

Если я правильно понимаю ваш вопрос, вы хотите иметь библиотеку соответствия / фильтрации для произвольного обычного языка в алфавите с динамическими типами?Исходя из примера с вашим автомобилем, я думаю, вы захотите создать выражение, чтобы сопоставить его со списком, в котором все автомобили (красного цвета, имеют от 2 до 6 пассажиров, а каждый пассажир - от 8 до88 лет) или (есть 1 пассажир).

По совпадению я сам искал что-то подобное (для проверки документов), и самым близким, что я мог получить, был Цзин ;Библиотека Java RELAX-NG.К сожалению, алфавит в Jing состоит из узлов XML, поэтому он не решил мою проблему.В настоящий момент я пытаюсь написать библиотеку, которая делает именно это (сопоставление с обычными языками по алфавиту произвольного типа), основываясь на сопоставлении с образцом в Цзин.Если вы хотите помочь с этим, пожалуйста, дайте мне знать;).

0 голосов
/ 03 ноября 2011

Я уверен, что этот ответ не будет полезен для первоначального вопроса из-за данных, но если кто-нибудь встретит это из Google ...

DFA и NFA можно сохранить как В таблице перехода состояний вы затем выполняете анализ, перемещая таблицу, следуя ссылкам как таковым.

0 голосов
/ 12 октября 2010

Веб-поиск даст несколько примеров DFA в Java.Тем не менее, лучшее представление зависит от ваших конкретных требований приложения;например, как ваше приложение будет использовать DFA.Я думаю, тебе нужно решить это для себя.

...