我需要运行以下测试:如果一个表达式包含 '{' 则仅在找到另一个 '}' 时才接受该表达式 有效的表达式是 'aaa{aaa}aaa', '{aa}' , 'a{aa {aa}aa}aa'、'{a{a}a}' 等...我该怎么做?
如果重要,我将在 XSD 文档中运行此测试...
您所描述的语言(与 Dyck 语言密切相关)是上下文无关的,而不是常规的(乔姆斯基层次结构中的类型 2)。也就是说,不可能使用基本的正则表达式来构造该语言单词的接受器。
但是,堆栈机器可以决定您描述的语言类型的单词问题。要实现这一点,您应该将字符串标记为字符,遍历每个字符,如果发现左括号,则将初始化为 0 的计数器加一。如果您发现右括号将其减一。如果在整个执行过程中不变量counter >= 0
成立并且计数器的最终状态为 0,则接受该字。
由于 Michael Schmeißer 概述的原因,XSD 正则表达式无法识别问题中描述的语言。(它可能可以被 Perl 兼容的模式识别,这些模式早已将 class-3 语言抛在后面,但 XSD 不使用反向引用和其他设备,这些设备为 Perl 表达式提供了额外的功能。)
您对 MS 回答的评论表明您可能愿意接受问题中描述的语言的常规近似值。如果是这样,那么您可以在常规子语言(仅接受原始语言的单词但可能错误地拒绝其中一些单词)或常规超集语言(接受该语言的所有单词但错误地接受某些非语言)之间进行选择。话也是如此。
MS答案的评论中给出的表达式是一个常规子集。它有三个明显的局限性:
aaa
”)。a{a}a{a}a
”)。像第一个这样的限制是不可避免的。您可以选择大于 3 的数字,但在常规子集中总是会有最大嵌套深度。然而,其他两个不是必需的,可以通过子集表达式的系统开发来避免。
为简单起见,使用原始帖子中说明的语言,我们可以用类似 BNF 的符号表示它:
<S> ::= <empty> | <S> a | <S> { <S> } .
<empty> ::= .
或者,在扩展的 BNF 中:
S ::= (a|{S})*
然后我们可以重写它来跟踪嵌套(以词缀语法的风格):
S ::= (a|{S1})*
S1 ::= (a|{S2})*
S2 ::= (a|{S3})*
etc.
在选定的级别n,我们可以这样结束递归(从而使语言变得规则):
Sn ::= a*
然后我们可以通过一次替换一个级别来构建正则表达式:
S = (a|{S1})*
= (a|{(a|{S2})*})*
= (a|{(a|{(a|{S3})*})*})*
etc.
在这种情况下,它归结为:为了允许嵌套n层深度,我们从字符串“ ”的n 个副本开始,以“ (a|{
”继续,并以字符串“ ”的n 个副本a*
结束。要允许除 以外的字符,我们可以用而不是重写。 })*
a
[^{}]
a
如果我们用四级嵌套大括号停止替换,我们得到表达式
([^{}]|{([^{}]|{([^{}]|{([^{}]|{[^{}]*})*})*})*})*
如果重要的是永远不会拒绝任何合法表达式,我们可以通过用[^{}]*
or.*
替换中心表达式来将其转换为超集表达式(.|\n)*
;然后我们有一个正则表达式,它接受 (a) 正确嵌套的大括号不超过四个深度的字符串,以及 (b) 带有嵌套四个深度的大括号的字符串,在最内层包含任意字符串(所以第五个、第六个或第 n 个嵌套级别不一定正确)。
([^{}]|{([^{}]|{([^{}]|{([^{}]|{[(.|\n)*})*})*})*})*
相比之下,如果不接受任何非法表达式很重要,那么最好坚持使用子集表达式。