Я пытаюсь создать инструмент, который использует что-то вроде регулярных выражений для поиска шаблонов в строке (не в текстовой строке, но сейчас это не важно). Я знаком с теорией автоматов, т.е. знаю, как реализовать базовое сопоставление регулярных выражений и вывести true или false, если строка соответствует моему регулярному выражению, путем имитации автомата по учебнику.
Скажем, меня интересуют все a, предшествующие b, и не более a перед b, поэтому это регулярное выражение: a[^a]*b. Но я не просто хочу узнать, содержит ли моя строка такую часть, я хочу получить в качестве вывода a, чтобы я мог его проверить (помните, я на самом деле не имею дело с текстом).
Подводя итог: допустим, я помечаю a круглыми скобками, например так: (a)[^a]*b и запускаю его на входной строке bcadacb, затем мне нужно второе a в качестве вывода.
Или, в более общем смысле, можно ли узнать, какие символы во входной строке соответствуют какой части регулярного выражения? Как это делается в текстовых редакторах? Они хотя бы знают, где начался матч, потому что могут подсвечивать матчи. Должен ли я использовать подход с возвратом или есть более умный и менее затратный в вычислительном отношении способ?
РЕДАКТИРОВАТЬ: Правильные обратные ссылки, т.е. захват с помощью скобок и ссылки с помощью \1 и т. д., могут не потребоваться. Я знаю, что обратные ссылки вводят необходимость обратного отслеживания (или чего-то подобного) и делают проблему (IIRC) NP-сложной. Мой вопрос, по сути, таков: является ли часть захвата без обратных ссылок менее затратной в вычислительном отношении, чем правильные обратные ссылки?
