Как уже отмечалось многими, HTML не является обычным языком, который может затруднить его синтаксический анализ. Мое решение состоит в том, чтобы превратить его в обычный язык, используя аккуратную программу, а затем использовать синтаксический анализатор XML для использования результатов. Для этого есть много хороших вариантов. Моя программа написана с использованием Java с библиотекой jtidy , чтобы превратить HTML в XML, а затем Jaxen в xpath в результат.
Нет. Это так просто. Конечный автомат (который представляет собой структуру данных, лежащую в основе регулярного выражения) не имеет памяти, кроме состояния, в котором он находится, и если у вас есть произвольно глубокое вложение, вам нужен произвольно большой автомат, который сталкивается с понятием конечный автомат.
Вы можете сопоставлять вложенные / парные элементы с фиксированной глубиной, где глубина ограничена только вашей памятью, потому что автомат становится очень большим. На практике, однако, вы должны использовать push-down automaton, т. Е. Синтаксический анализатор для контекстно-свободной грамматики, например LL (сверху вниз) или LR (снизу вверх). Вы должны учитывать худшее поведение во время выполнения: O (n ^ 3) по сравнению с O (n), с n = длина (ввод).
Существует множество генераторов синтаксического анализатора, например ANTLR для Java. Найти существующую грамматику для Java (или C) также не сложно. Для получения дополнительной информации: Теория автоматов в Википедии
Нет. Вам нужен полноразмерный парсер для этого типа проблем.
... при условии, что существует некоторое максимальное количество гнезд, с которыми вы были бы счастливы остановиться.
Позвольте мне объяснить.
@ torsten-marek прав, что регулярное выражение не может проверять вложенные шаблоны, подобные этому, но возможно определить вложенный шаблон регулярного выражения, который позволит вам захватите вложенные структуры, подобные этому , до некоторой максимальной глубины . Я создал один, чтобы записать комментарии в формате EBNF ( попробуйте здесь ), например:
(* This is a comment (* this is nested inside (* another level! *) hey *) yo *)
Регулярное выражение (для комментариев с одной глубиной ) является следующим:
m{1} = \(+\*+(?:[^*(]|(?:\*+[^)*])|(?:\(+[^*(]))*\*+\)+
Это может быть легко адаптировано для ваших целей, заменив \(+\*+
и \*+\)+
на {
и }
и заменив все между простыми [^{}]
:
p{1} = \{(?:[^{}])*\}
( Вот ссылка , чтобы попробовать это.)
Чтобы вложить, просто разрешите этот шаблон внутри самого блока:
p{2} = \{(?:(?:p{1})|(?:[^{}]))*\}
...or...
p{2} = \{(?:(?:\{(?:[^{}])*\})|(?:[^{}]))*\}
Чтобы найти тройные вложенные блоки, используйте:
p{3} = \{(?:(?:p{2})|(?:[^{}]))*\}
...or...
p{3} = \{(?:(?:\{(?:(?:\{(?:[^{}])*\})|(?:[^{}]))*\})|(?:[^{}]))*\}
Появился четкий шаблон. Чтобы найти комментарии, вложенные в глубину N
, просто используйте регулярное выражение:
p{N} = \{(?:(?:p{N-1})|(?:[^{}]))*\}
where N > 1 and
p{1} = \{(?:[^{}])*\}
Сценарий можно записать для рекурсивного генерации этих регулярных выражений, но это выходит за рамки того, для чего мне это нужно. (Это остается как упражнение для читателя.
Да, если это .NET RegEx-движок. .Net поддерживает конечный конечный автомат, поставляемый с внешним стеклом. см. подробности
Мой вопрос + ответ связан, и я делаю выражение и мета-выражение, которое может соответствовать произвольным (конечным) уровням вложенности. Это довольно изящно, но что еще вы можете ожидать? Используйте обратные ссылки в матче, если ваш движок поддерживает его.
Нет, вы попадаете в область Контекстных свободных грамматик в этой точке.
Использование регулярных выражений для проверки вложенных шаблонов очень просто.
'/(\((?>[^()]+|(?1))*\))/'
(?>...)
(в PHP 5.2) заключается в том, что часть ?>
интерпретируется как: «конец скрипта»). Вот как я напишу: /\((?:[^()]++|(?R))*+\)/
. Это немного более эффективно для совпадения и несоответствия. В своей минимальной форме /\(([^()]|(?R))*\)/
это действительно замечательная вещь!
– ridgerunner
12 March 2011 в 07:35
(?1)
, чтобы комментарии были в другом тексте (я разорвал его и упростил его из регулярного выражения моего адреса электронной почты). И (?>
использовался, потому что я считаю, что он ускоряет работу (если требуется). Это неправильно?
– MichaelRushton
19 March 2011 в 13:27
'(a (b c)) (d e)'
использование простого выражения '/\([^()]*\)/'
дает мне тот же результат. Есть ли преимущества для вашего долгого выражения?
– Cœur
13 October 2015 в 07:38
/^(\((?>[^()]+|(?1))*\))+$/
и /^\([^()]*\)+$/
для соответствия (a (b c))(d e)
. Бывшие спички, но последний этого не делает.
– MichaelRushton
13 October 2015 в 09:16
Использование рекурсивного соответствия в PHP-регулярном выражении значительно быстрее процедурного соответствия скобок. особенно с более длинными строками.
http://php.net/manual/en/regexp.reference.recursive.php
, например
$patt = '!\( (?: (?: (?>[^()]+) | (?R) )* ) \)!x';
preg_match_all( $patt, $str, $m );
vs.
matchBrackets( $str );
function matchBrackets ( $str, $offset = 0 ) {
$matches = array();
list( $opener, $closer ) = array( '(', ')' );
// Return early if there's no match
if ( false === ( $first_offset = strpos( $str, $opener, $offset ) ) ) {
return $matches;
}
// Step through the string one character at a time storing offsets
$paren_score = -1;
$inside_paren = false;
$match_start = 0;
$offsets = array();
for ( $index = $first_offset; $index < strlen( $str ); $index++ ) {
$char = $str[ $index ];
if ( $opener === $char ) {
if ( ! $inside_paren ) {
$paren_score = 1;
$match_start = $index;
}
else {
$paren_score++;
}
$inside_paren = true;
}
elseif ( $closer === $char ) {
$paren_score--;
}
if ( 0 === $paren_score ) {
$inside_paren = false;
$paren_score = -1;
$offsets[] = array( $match_start, $index + 1 );
}
}
while ( $offset = array_shift( $offsets ) ) {
list( $start, $finish ) = $offset;
$match = substr( $str, $start, $finish - $start );
$matches[] = $match;
}
return $matches;
}
Лемма Pumping для правильных языков является причиной того, что вы не можете этого сделать.
Сгенерированный автомат будет иметь конечное число состояний, например k, поэтому a строка из k + 1 открывающих скобок обязана иметь состояние, повторяющееся где-то (поскольку автомат обрабатывает символы). Часть строки между одним и тем же состоянием может быть продублирована бесконечно много раз, и автомат не узнает разницу.
В частности, если он принимает k + 1 открывающих скобок, за которыми следуют k + 1 замыкающие скобки ( который он должен), он также примет количество накачиваемых открывающих скобок, за которым следуют неизменные k + 1 замыкающие браки (что не должно).
Правильные регулярные выражения не могли бы этого сделать, поскольку вы покинули бы территорию обычных языков для приземления на территориях свободного пространства контекста.
Тем не менее, пакеты «регулярного выражения», которые предлагают многие языки,
Например, регулярные выражения Lua имеют распознаватель «%b()
», который будет соответствовать сбалансированной круглой скобке. В вашем случае вы будете использовать «%b{}
»
. Еще один сложный инструмент, подобный sed, - gema , где вы очень легко сопоставляете сбалансированные фигурные скобки с помощью {#}
.
Итак, в зависимости от инструментов, которые у вас есть, ваше «регулярное выражение» (в более широком смысле) может соответствовать вложенным скобкам.
Кажется, что это работает: /(\{(?:\{.*\}|[^\{])*\})/m
, как упоминалось zsolt, некоторые двигатели регулярных выражений поддерживают рекурсию - конечно, обычно это те, которые используют алгоритм обратного отслеживания, поэтому он не будет особенно эффективен. пример: /(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm