#ide #grammar #parser-generator
#ide #грамматика #анализатор-генератор
Вопрос:
Я осматривался, чтобы посмотреть, что доступно для того, чтобы помочь пользователям создавать грамматики. Существуют различные IDE, но … похоже, что это текстовые редакторы, которые работают с самим файлом грамматики. Я ищу что-то, что работает на основе подхода, ориентированного на данные. Итак, допустим, у меня есть множество примеров данных, которые я хочу проанализировать с помощью синтаксического анализатора. Итак, я хочу поработать с этим образцом данных и определить грамматику непосредственно из него.
Существует ли какое-либо существующее программное обеспечение, которое делает что-то подобное?
Я постараюсь быть более ясным…
Подход, ориентированный на данные, о котором я упоминаю, заключается в том, что пользователь загружает выборку данных. Затем они будут выбирать фрагменты, указывающие, что они являются полями, или выбирать элементы и отмечать их как разделители или тому подобное.
В отличие от большинства IDE, которые я вижу, существуют только текстовые редакторы для написания на самом языке грамматики.
Комментарии:
1. Я всегда задавался этим вопросом, но я думаю, что вам нужно экстраполировать грамматику из вашего набора данных, но мне не терпится увидеть ответы других людей.
2. Интересный вопрос. Посмотрите, движется ли мой ответ в правильном направлении… Я могу подробнее остановиться на любом из шагов, которые я упоминаю при получении обычной грамматики / регулярного выражения.
3. 1) В общем случае невозможно вывести уникальную грамматику из данных. 2) Языки описания грамматики существуют, потому что люди серьезно исследовали эту проблему и придумали лучшие (с их точки зрения) решения. Таким образом, отсутствие «подхода, ориентированного на данные», является одним из признаков того, что эта идея нежизнеспособна.
Ответ №1:
Любой конечный набор строк представляет собой обычный язык. Написать NFA, принимающий такой язык, тривиально. Исходя из этого, вы можете сгенерировать DFA, используя конструкцию подмножества, и минимизировать его, используя тот факт, что DFA требуется только одно состояние для каждого класса эквивалентности отношения неразличимости. Так что это полностью алгоритмический процесс… получение регулярного выражения и / или грамматики тогда так же просто.
При этом, если вы хотите создать грамматику, которая генерирует строки и, возможно, другие … ваша проблема кажется некорректной. Для любого конечного набора строк бесконечно много грамматик генерируют их и другие строки… бесконечность числа проистекает из того факта, что вы можете генерировать любые другие строки, пока вы попадаете в целевой набор данных. Ваш вопрос, по сути, таков: «учитывая начало последовательности a1, a2, …, an, …, скажите, каковы следующие n элементов». Это невозможно сделать, если вы просто не хотите получить какой-то ответ… в этом случае вы всегда можете начать с DFA и предложить способы обобщения этого (т. Е. Принимать только больше строк).
Действительно, учитывая, например, обычную грамматику, легко вводить новые строки… так что, возможно, используйте первый ответ в качестве отправной точки. Однако обратите внимание, что преобразование из NFA в DFA может быть крайне неэффективным… асимптотически экспоненциальный.
Комментарии:
1. Обычно эта проблема ставится так: «каково минимальное описание, которое охватывает все данные?» это приводит к гораздо меньшему набору грамматик, которые не доминируют друг над другом по какому-либо размеру или другому показателю сложности. OP также нужны встречные примеры, чтобы получить хорошие грамматики, в противном случае грамматика G = CHAR * будет единственным ответом, который он получит (будучи довольно минимальным). По сути, это проблема машинного обучения. В общем, я не думаю, что у него все получится, если его данные не будут действительно регулярными, и в этом случае ему не понадобится инструмент.
2. Отличная информация, но… Я спрашиваю о программных инструментах, а не об алгоритмах. Я не предполагаю, что что-то может сделать это автоматически, скорее просто есть IDE, ориентированная на данные, вместо IDE, ориентированной на грамматику.
3. @taotree: Как я упоминал в сообщении, похоже, что создание минимального DFA и соответствующей регулярной грамматики было бы хорошей отправной точкой… понятия не имею, действительно ли что-то делает это или нет!
Ответ №2:
Я не думаю, что вы хотите ограничить это FSA, а скорее грамматиками (независимо от того, свободны они от контекста или нет). Я предлагаю посмотреть на http://en.wikipedia.org/wiki/Grammar_induction ; кажется, там есть какие-то обсуждения алгоритмов (извините, не программного обеспечения).