如何使用递归正则表达式或其他方法在Python中递归验证这个类似BBcode的标记？

Question

我正在尝试编写一个程序来验证用类似于BBcode的标记语言编写的文档。

此标记语言具有匹配（[b]bold[/b] text）和非匹配（today is [date]）标记。不幸的是，使用不同的标记语言不是一种选择。

但是，我的正则表达式并没有按照我想要的方式行事。它似乎始终停在第一个匹配的结束标记，而不是使用递归(?R)标识嵌套标记。

我正在使用regex模块，它支持(?R)，而不是re。

我的问题是：

• 如何有效地使用递归正则表达式匹配嵌套标记而不终止第一个标记？
• 如果有一个比正则表达式更好的方法，那么该方法是什么？

一旦我建立它就是正则表达式：\[(b|i|u|h1|h2|h3|large|small|list|table|grid)\](?:((?!\[\/\1\]).)*?|(?R))*\[\/\1\]

这是一个不能按预期工作的测试字符串：[large]test1 [large]test2[/large] test3[/large]（它应匹配整个字符串但在test3之前停止）

这是regex101.com上的正则表达式：https://regex101.com/r/laJSLZ/1

此测试不需要在几毫秒甚至几秒内完成，但它确实需要能够在Travis-CI构建合理的时间内验证大约100个文件，每个1,000到10,000个字符。

对于上下文，以下是使用此正则表达式的逻辑：

import io, regex # https://pypi.org/project/regex/

# All the tags that must have opening and closing tags
matching_tags = 'b', 'i', 'u', 'h1', 'h2', 'h3', 'large', 'small', 'list', 'table', 'grid'

# our first part matches an opening tag:
# \[(b|i|u|h1|h2|h3|large|small|list|table|grid)\]
# our middle part matches the text in the middle, including any properly formed tag sets in between:
# (?:((?!\[\/\1\]).)*?|(?R))*
# our last part matches the closing tag for our first match:
# \[\/\1\]
pattern = r'\[(' + '|'.join(matching_tags) + r')\](?:((?!\[\/\1\]).)*?|(?R))*\[\/\1\]'
myRegex = re.compile(pattern)

data = ''
with open('input.txt', 'r') as file:
    data = '[br]'.join(file.readlines())

def validate(text):
    valid = True
    for node in all_nodes(text):
        valid = valid and is_valid(node)
    return valid

# (Only important thing here is that I call this on every node, this
# should work fine but the regex to get me those nodes does not.)
# markup should be valid iff opening and closing tag counts are equal
# in the whole file, in each matching top-level pair of tags, and in
# each child all the way down to the smallest unit (a string that has
# no tags at all)
def is_valid(text):
    valid = True
    for tag in matching_tags:
        valid = valid and text.count(f'[{tag}]') == text.count(f'[/{tag}]')
    return valid

# this returns each child of the text given to it
# this call:
# all_nodes('[b]some [large]text to[/large] validate [i]with [u]regex[/u]![/i] love[/b] to use [b]regex to [i]do stuff[/i][/b]')
# should return a list containing these strings:
# [b]some [large]text to[/large] validate [i]with [u]regex[/u]![/i] love[/b]
# [large]text to[/large]
# [i]with [u]regex[/u]![/i]
# [u]regex[/u]
# [b]regex to [i]do stuff[/i][/b]
# [i]do stuff[/i]
def all_nodes(text):
    matches = myRegex.findall(text)
    if len(matches) > 0:
        for m in matches:
            result += all_nodes(m)
    return result

exit(0 if validate(data) else 1)

Answer 1

你的主要问题是在((?!\[\/\1\]).)*?脾气贪婪的令牌。

首先，它是低效的，因为你量化它然后你量化它所在的整个组，所以使正则表达式引擎寻找更多的方法匹配字符串，这使它相当脆弱。

其次，您只匹配结束标记，并且您没有限制起始标记。第一步是在/可选之前制作\1，\/?。它不会在[tag]之前停止，就像没有属性的标签一样。要添加属性支持，请在\1，(?:\s[^]]*)?之后添加一个可选组。它匹配一个空格的可选序列，然后匹配除]之外的任何0+字符。

固定的正则表达式看起来像

\[([biu]|h[123]|l(?:arge|ist)|small|table|grid)](?:(?!\[/?\1(?:\s[^]]*)?]).|(?R))*\[/\1]

不要忘记使用regex.DOTALL编译它以匹配多个换行符。