Использование callable_iterator (re.finditer) приводит к зависанию Python

У меня есть функция, которая вызывается для каждой строки текста.

def tokenize_line(line: str, cmd = ''):
    matches = re.finditer(Patterns.SUPPORTED_TOKENS, line)
    tokens_found, not_found, start_idx = [], [], 0
    print(matches)
    for match in matches:
        pass
        # Rest of code

Результат print(matches) выглядит примерно так: <callable_iterator object at 0x0000021201445000>

Однако когда я преобразую итератор в список:

matches = list(re.finditer(Patterns.SUPPORTED_TOKENS, line))

или когда я повторяю с помощью for:

for match in matches:
   print(match)

...Питон зависает.

Эта проблема возникает непоследовательно. Например:

tokenize_line('$color AS $length') # Works fine
tokenize_line('FALSE + $length IS GT 7 + $length IS 4') # Freezes

Итак, проблема возникает при преобразовании callable_iterator в список или переборе по нему.

Вот шаблон (Patterns.SUPPORTED_TOKENS), который я использую:

(°p\d+°|°a\d+°|°m\d+°)|((?<!\S)(?:!\'(?:\\.|[^\'\n\\])*\'|!"(?:\\.|[^\n"\\])*")(?!\S))|((?:\'(?:\\.|[^\'\n\\])*\'|"(?:\\.|[^\n"\\])*"))|((\{(.*)\}))|((?<!\S)([@$][\w]*(?:\.[\w]*)*)(?!\S))|((?<!\d)-?\d*\.?\d+)|(\*\*|[\+\-\*\(\)/%\^]|==|&&|\|\||!=|>=|<=|>|<|~~|!~~|::|!::)|([\:/])|(\b(?:AS|AND|AT|:|BETWEEN|BY|FROM|IN|INTO|ON|OF|OR|THAN|TO|USING|WITH)\b)|(\b[a-zA-Z_][a-zA-Z0-9_]* *((?:[^;()\'""]*|"(?:[^"\\]|\\.)*"|\'(?:[^\'\\]|\\.)*\'|\([^)]*\))*?;))|((\b(?:EMPTY|STRING|NUMBER|BOOL|ARRAY|MAP|TRUE|FALSE|NULL|UNKNOWN|DOTALL|IGNORECASE|MULTILINE|ARRAY_ARRAY|ARRAY_STRING|ARRAY_MAP|ARRAY_NUMBER|ARRAY_NULL|DOT|SPACE|NEWLINE|SEMICOLON|COLON|HASH|COMMA|TAB)\b)|(\b(?:IS NOT LT|IS NOT GT|IS NOT GEQ|IS NOT LEQ|IS NOT|IS LT|IS GT|IS GEQ|IS LEQ|IS|NOT IN|NOT|IN|HAS NOT|HAS|AND|OR)\b))

Объяснение шаблона регулярного выражения:

Пользовательские токены: Соответствуют определенным пользовательским токенам, которые начинаются с определенных символов и сопровождаются цифрами.

Строки в кавычках: Соответствует строкам как в одинарных, так и в двойных кавычках, включая строки с escape-символами. Содержимое фигурных скобок: соответствует всему, что заключено в фигурные скобки.

Переменные: Соответствует переменным, которые начинаются с определенных символов (например, @ или $) и могут включать точки для вложенных свойств.

Числа: Соответствует как целым числам, так и числам с плавающей запятой, включая отрицательные числа.

Операторы: Соответствует различным математическим и логическим операторам. Двоеточия и косые черты: Соответствует определенным символам пунктуации, таким как двоеточия и косые черты.

Ключевые слова: Соответствует определенным ключевым словам, зарезервированным в языке. Определения функций: Сопоставляет определения функций или аналогичные структуры, гарантируя, что они соответствуют определенным правилам синтаксиса.

Типы данных и модификаторы: Соответствует ключевым словам, которые представляют типы данных или модификаторы.

Логические операторы: Соответствует сложным логическим операторам, используемым в условных выражениях.

Пример:

import re

SUPPORTED_TOKENS = r'(°p\d+°|°a\d+°|°m\d+°)|((?<!\S)(?:!\'(?:\\.|[^\'\n\\])*\'|!"(?:\\.|[^\n"\\])*")(?!\S))|((?:\'(?:\\.|[^\'\n\\])*\'|"(?:\\.|[^\n"\\])*"))|((\{(.*)\}))|((?<!\S)([@$][\w]*(?:\.[\w]*)*)(?!\S))|((?<!\d)-?\d*\.?\d+)|(\*\*|[\+\-\*\(\)/%\^]|==|&&|\|\||!=|>=|<=|>|<|~~|!~~|::|!::)|([\:/])|(\b(?:AS|AND|AT|:|BETWEEN|BY|FROM|IN|INTO|ON|OF|OR|THAN|TO|USING|WITH)\b)|(\b[a-zA-Z_][a-zA-Z0-9_]* *((?:[^;()\'""]*|"(?:[^"\\]|\\.)*"|\'(?:[^\'\\]|\\.)*\'|\([^)]*\))*?;))|((\b(?:EMPTY|STRING|NUMBER|BOOL|ARRAY|MAP|TRUE|FALSE|NULL|UNKNOWN|DOTALL|IGNORECASE|MULTILINE|ARRAY_ARRAY|ARRAY_STRING|ARRAY_MAP|ARRAY_NUMBER|ARRAY_NULL|DOT|SPACE|NEWLINE|SEMICOLON|COLON|HASH|COMMA|TAB)\b)|(\b(?:IS NOT LT|IS NOT GT|IS NOT GEQ|IS NOT LEQ|IS NOT|IS LT|IS GT|IS GEQ|IS LEQ|IS|NOT IN|NOT|IN|HAS NOT|HAS|AND|OR)\b))'

def tokenize_line(line: str, cmd = ''):
    if not line:
        return [], []
    
    matches = list(re.finditer(SUPPORTED_TOKENS, line))
    print(list)
    
    

lines = [
    '$color AS $length',
    'EMPTY + $length IS GT 7 + $length IS 4'
]


for x in lines:
    tokenize_line(x)

Будем очень признательны за любую помощь, чтобы понять, почему это происходит и как это исправить!

Анализ регулярного выражения может оказаться сложной задачей, но наиболее вероятной причиной может оказаться катастрофический возврат. Трассировка вашего примера приводит к тому, что механизм регулярных выражений застревает в получении первого совпадения при циклическом выполнении matches. Есть ли конкретная причина, по которой вы пытаетесь решить эту проблему с помощью одного регулярного выражения?

Grismar 22.07.2024 02:32

Помимо @Grismar, в вашем регулярном выражении есть вложенные квантификаторы (то есть ((.*)*)), что очень часто приводит к катастрофическим результатам бэктестинга. Либо предоставьте несколько допустимых входных строк, либо вообще рассмотрите возможность использования какого-либо синтаксического анализатора.

Jan 22.07.2024 03:20

Спасибо вам, ребята! Я подумываю позже использовать «родной» парсер вместо регулярных выражений.

Martin A. 22.07.2024 08:53
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
2
3
81
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Как указано в комментариях, зависание вызвано катастрофическим возвратом, когда вы переносите шаблон [^;()\'""]*, который может соответствовать всему введенному вами вводу или любой его части, в группу, которая может повторять от нуля до много раз, за ​​которым следует ;, что не соответствует введенным вами данным. В случае сбоя механизм регулярных выражений возвращает символ, все еще соответствующий [^;()\'""]*, но с внешним * он повторяет внутренний шаблон, чтобы соответствовать оставшемуся символу, только для того, чтобы снова потерпеть неудачу со следующим ;. Он снова вернется с двумя оставшимися символами, чтобы внутренний шаблон мог соответствовать им обоим или по одному.

Другими словами, возврат продолжается до тех пор, пока механизм регулярных выражений не исчерпает все возможные способы разделения входных данных, что приводит к быстрому выходу из-под контроля 2 ^ (<number of characters> + 1) количества комбинаций, поскольку каждая позиция пробела во входных данных может быть либо разделением, либо нет.

В этом случае катастрофический возврат можно исправить, удалив внутренний квантор * из (?:[^;()\'""]*|...)*?;, поскольку внешний квантор *? уже допускает повторение внутреннего шаблона от нуля до многих. То есть изменить:

(?:[^;()\'""]*|...)*?;

к:

(?:[^;()\'""]|...)*?;

Демо: https://regex101.com/r/MszbVf/1

Если вы используете Python 3.11 или более позднюю версию, вы также можете избежать катастрофического возврата, сделав группу атомарной группой, чтобы механизм регулярных выражений не пытался выполнить возврат после успешного сопоставления самой атомарной группы, даже если совпадение затем не удалось. со следующим ;. То есть изменить:

(?:[^;()\'""]*|...)*?;

к:

(?>[^;()\'""]*|...)*?;

Демо: https://regex101.com/r/MszbVf/2

Ох чувак, спасибо тебе огромное! Он работает отлично! И теперь я немного больше понимаю о катастрофическом возврате назад. Я не знал об атомных группах. Это очень интересно, и я обязательно прочитаю об этом больше. Еще раз большое спасибо!

Martin A. 22.07.2024 09:00

Другие вопросы по теме