Могу ли я определить набор первых символов, соответствующих шаблону регулярного выражения?

Question

Я хотел бы иметь возможность вычислить набор всех символов, которые могут быть сопоставлены как первый символ в строке заданным экземпляром java.util.regex.Pattern.Более формально, учитывая, что DFA эквивалентен определенному регулярному выражению, мне нужен набор всех исходящих переходов из начального состояния.

Пример:

Pattern p = Pattern.compile("[abc]def|daniel|chris|\\s+");
Set<Character> first = getFirstSet(p);

Набор first должен содержать следующие элементы:

{ 'a', 'b', 'c', 'd', ' ', '\n', '\r', '\t' }

Есть идеи?Я прекрасно понимаю, что мог бы сам построить DFA и таким образом определить соответствующие состояния, но мне бы хотелось избежать подобных хлопот (читай:для меня это не так уж и дорого).Обратите внимание, что моим основным языком на самом деле является Scala, поэтому у меня есть доступ ко всем основным библиотекам Scala (какой бы они ни были).

Answer 1

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

Некоторые вещи просты:

• Последовательность:first(r1r2) = first(r1) + (если '' в first(r1) first(r2) иначе пустой набор)
• Чередование:первый(r1|r2) = первый(r1) + первый(r2)
• Итерация:первый(r*) = первый(r) + ''
• Персонажи:первый(с) = с
• Классы персонажей:Сначала ([C1-CN]) = SET (C1, C2, ..., CN) ...

Распространите это на все примитивы и специальные флаги, которые знает ваш диалект регулярных выражений, и все готово.

Answer 2

Вы можете решить это рекурсивно...

• Удалить закрывающую скобку и вызвать рекурсивно.
• Разделите альтернативы верхнего уровня и рекурсивно вызывайте каждую часть.
• Если альтернативы нет,
  • выведите все символы, начиная слева до первого необязательного символа.
  • Если есть группы символов, выведите все символы.

Вероятно, в этой идее много ошибок, но я бы попробовал именно это.Вам придется удалить утверждения, имена групп и тысячи других вещей.А если вы обнаружите класс инвертированных символов, например [^0-9], вам придется вывести много символов.

Поэтому я предполагаю, что это действительно сложная проблема.