Джеффри Фридл перечисляет 3 основных типа регулярных выражений двигателей в своей книге "Регулярные выражения":Какой тип двигателя регулярного выражения использует R в качестве стандарта?
Какой из они используют R в качестве стандарта?
Мое понимание (но я не нашёл это в официальных документах) заключается в том, что по умолчанию функция R regex использует библиотеку регулярных выражений tcl, которая является гибридом DFA и NFA.
Двигатель сначала сканирует регулярное выражение для любых частей, не совместимых с DFA, и извлекает части, которые являются DFA (поэтому удаляет ссылки и другие вещи, которые доступны только в NFA). Затем он пытается найти совпадение с этим (возможно) упрощенным шаблоном с использованием механизма DFA. Если он не может найти совпадение, полное регулярное выражение не будет совпадать и оно будет возвращено с ошибкой. Если он находит совпадение, он возвращается и соответствует полному регулярному выражению, используя движок NFA (я думаю, традиционный/неприсоединившийся), но начинаю с того места, где произошло упрощенное совпадение. Это намного быстрее (как для матчей, так и для матчей), чем для прямого механизма NFA, но все же позволяет использовать все вещи в NFA, которые DFA не поддерживает.
Если вы укажете perl=TRUE в любой функции, то он переключится на библиотеку pcre, которая больше похожа на традиционную NFA (хотя я понимаю, что это не F, A или традиционный).
'? Regex' цитирует документацию TRE-библиотеки. –
Посмотрите на ?regex для всех подробностей (HTML version). Существует несколько вариантов.
Процитируем одну порцию:
Этот раздел охватывает регулярные выражения разрешены в режиме по умолчанию из Grep, RegExpr, gregexpr, подразделам, GSUB и strsplit. Они используют реализацию стандарта POSIX 1003.2 : это позволяет использовать некоторую область для интерпретации, а интерпретациями здесь являются те, которые в настоящее время используются , используемые R. Реализация поддерживает некоторые расширения стандарта.
Также проверьте далее на странице справки о «Perl-подобных выражениях», в которых используется механизм PCRE.
Это все еще не отвечает на вопрос. Я понимаю, что это POSIX, но это NFA или DFA? – histelheim
@histelheim как обратные ссылки поддерживаются в режиме POSIX, это будет движок NFA. –
Я не знаю, и эти термины не отображаются в документации или пакетах R. 'Библиотека ("СОС"); findFn ("DFA"); findFn («NFA») 'возвращает только тривиальные, несвязанные ответы. Может быть, кто-то еще узнает. –
На странице ?regex приведена документация TRE. В верхней части grep.c source мы видим:
/* As from TRE 0.8.0, tre.h replaces regex.h */
#include <tre/tre.h>
И копируя мой предыдущий комментарий: http://swtch.com/~rsc/regexp говорит TRE использует НКУ. Затем PCRE используется для perl=TRUE.
https://swtch.com/~rsc/regexp/ говорит, что TRE использует NFA, –