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

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)
• Итерация: first (r *) = first (r) + ''
• Символы: первая (с) = с
• Классы символов: first ([c1-cn]) = набор (c1, c2, ..., cn) ...

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

Answer 2

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

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

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

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