регулярное выражение пересечения с группами, как получить пересечение сгруппированного бита?

Question

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

Логика пересечения, которую я собираюсь использовать, - это алгоритм Книги Дракона для преобразования NFA в DFA, но выполняемый на двух NFA одновременно. Поскольку все DFA являются NFA (но с очень небольшим недетерминизмом), вы можете повторить это по мере необходимости для большего количества пересечений.

Моя проблема в том, что у одного из моих регулярных выражений есть группы, которые можно использовать в дальнейшем как часть нового регулярного выражения. В частности:

bin/x86/a.out: obj/x86/.*\.o

obj/{[a-zA-Z0-9]+}/{.*}.o: src/\2.c

В конце первой строки у меня есть регулярное выражение, которое соответствует всем объектам для целей x86. Во второй строке у меня есть регулярное выражение, которое указывает возможную строку сборки, которая должна соответствовать первой группе с фиксированным «x86», а второй - любой данной строке после нее. В этом примере первое совпадение еще не используется, но оно должно быть извлекаемым. Чтобы убедиться, что сопоставление заканчивается (и разрешить рекурсивные правила), я хочу использовать информацию, полученную из первого регулярного выражения, в сопоставлении со вторым. Правило выбирается путем взятия второго регулярного выражения из первой и первого из второй строки и определения, имеет ли пересечение двух (DFA, являющееся результатом пересечения) состояние принятия. Если это так, то есть предложения, которые оба могут анализировать, и, следовательно, некоторые значения, которые может принимать группа.

Можно ли вообще извлечь информацию из первого регулярного выражения для использования при сопоставлении группы второго регулярного выражения?

Если нет, то какие ограничения мне нужно добавить?

Answer 1

Почему ваши примеры выглядят как правила Makefile, хотя Makefiles не поддерживают регулярные выражения?

Потому что это то, что я пытаюсь сделать (без каламбура).

Какую библиотеку регулярных выражений вы используете?

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

Некоторые поддерживают выражения предпросмотра, которые являются еще одним способом пересечения выражений

Идея, лежащая в основе пересечения, состоит в том, чтобы определить общие правила, которые могут содержать несколько различных левых частей (использование% в обычных make-файлах, но без необходимости делать какие-то рекурсивные make, если у вас естьболее одной точки вариации - например, платформа, тип сборки или имя файла).Если я не могу принять во внимание второе регулярное выражение для группы, я не могу использовать такое правило рекурсивно, потому что рекурсия не будет иметь никаких изменений между каждым шагом / уровнем.Это уменьшит щедрость, но все равно будет приемлемым.Тем не менее, это интересный вопрос, чтобы узнать ответ (IE, может ли это быть сделано в общем), и он будет принимать решение в требованиях, которые я буду иметь для библиотеки регулярных выражений.

(Не опубликовано как оригиналавтор, поскольку я потерял свой файл cookie и ожидаю объединения учетных записей).

Answer 2

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