1

我需要运行以下测试:如果一个表达式包含 '{' 则仅在找到另一个 '}' 时才接受该表达式 有效的表达式是 'aaa{aaa}aaa', '{aa}' , 'a{aa {aa}aa}aa'、'{a{a}a}' 等...我该怎么做?

如果重要,我将在 XSD 文档中运行此测试...

4

2 回答 2

2

您所描述的语言(与 Dyck 语言密切相关)是上下文无关的,而不是常规的(乔姆斯基层次结构中的类型 2)。也就是说,不可能使用基本的正则表达式来构造该语言单词的接受器。

但是,堆栈机器可以决定您描述的语言类型的单词问题。要实现这一点,您应该将字符串标记为字符,遍历每个字符,如果发现左括号,则将初始化为 0 的计数器加一。如果您发现右括号将其减一。如果在整个执行过程中不变量counter >= 0成立并且计数器的最终状态为 0,则接受该字。

于 2012-10-05T12:21:37.983 回答
1

由于 Michael Schmeißer 概述的原因,XSD 正则表达式无法识别问题中描述的语言。(它可能可以被 Perl 兼容的模式识别,这些模式早已将 class-3 语言抛在后面,但 XSD 不使用反向引用和其他设备,这些设备为 Perl 表达式提供了额外的功能。)

正则近似

您对 MS 回答的评论表明您可能愿意接受问题中描述的语言的常规近似值。如果是这样,那么您可以在常规子语言(仅接受原始语言的单词但可能错误地拒绝其中一些单词)或常规超集语言(接受该语言的所有单词但错误地接受某些非语言)之间进行选择。话也是如此。

评论中的近似值

MS答案的评论中给出的表达式是一个常规子集。它有三个明显的局限性:

  • 它允许大括号最多嵌套三个深度。
  • 它至少需要一对大括号(它不接受字符串“ aaa”)。
  • 它在每一层嵌套中最多允许一对大括号(它不接受“ a{a}a{a}a”)。

像第一个这样的限制是不可避免的。您可以选择大于 3 的数字,但在常规子集中总是会有最大嵌套深度。然而,其他两个不是必需的,可以通过子集表达式的系统开发来避免。

系统地开发子集表达式

从 BNF 开始

为简单起见,使用原始帖子中说明的语言,我们可以用类似 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*

用 RHS 代替 LHS

然后我们可以通过一次替换一个级别来构建正则表达式:

S = (a|{S1})*
  = (a|{(a|{S2})*})*
  = (a|{(a|{(a|{S3})*})*})*
etc.

在这种情况下,它归结为:为了允许嵌套n层深度,我们从字符串“ ”的n 个副本开始,以“ (a|{”继续,并以字符串“ ”的n 个副本a*结束。要允许除 以外的字符,我们可以用而不是重写。 })*a[^{}]a

n = 4的结果

如果我们用四级嵌套大括号停止替换,我们得到表达式

([^{}]|{([^{}]|{([^{}]|{([^{}]|{[^{}]*})*})*})*})*

超集表达式作为替代

如果重要的是永远不会拒绝任何合法表达式,我们可以通过用[^{}]*or.*替换中心表达式来将其转换为超集表达式(.|\n)*;然后我们有一个正则表达式,它接受 (a) 正确嵌套的大括号不超过四个深度的字符串,以及 (b) 带有嵌套四个深度的大括号的字符串,在最内层包含任意字符串(所以第五个、第六个或第 n 个嵌套级别不一定正确)。

([^{}]|{([^{}]|{([^{}]|{([^{}]|{[(.|\n)*})*})*})*})*

相比之下,如果不接受任何非法表达式很重要,那么最好坚持使用子集表达式。

于 2012-10-10T02:09:16.773 回答