3

我有包含以下结构的文本文档

{1,"StructEx",
[{1,"Element_1",[{2,"name","exampleName"},{3,"exampleValue",1},{2,"exampleComment","foo"}]},
[{1,"Element_2",[{2,"name","exampleName2"},{3,"exampleValue",2},{2,"exampleComment","bar"}]}]}

括号中的第一个值是数据类型。我需要正则表达式，它将返回（通过几次迭代）StructEx 中的所有元素，所以我可以将它打包成这样的东西

["StructEx"]=>
array(2) {
["Element_1"]=>
array(3) {
  ["name"]=>
  string(11) "exampleName"
  ["exampleValue"]=>
  int(1)
  ["exampleComment"]=>
  string(3) "foo"
}
["Element_2"]=>
array(3) {
  ["name"]=>
  string(12) "exampleName2"
  ["exampleValue"]=>
  int(2)
  ["exampleComment"]=>
  string(3) "bar"
}
}
4

1 回答 1

1

假设嵌套是任意深度的，那么答案是否定的，你不能用正则表达式解析这种文本文档。如果深度是有限的，那会很痛苦，但也是可行的。

为什么会这样？

字母表

为了更详细地回答您的问题，让我们介绍一些很棒的干理论。

让我们将字母 Σ 定义为一组非空符号（技术上更正确的定义来自范畴论，将字母视为非空的自由对象，但为了论证，这个定义就足够了。

在我们的字母表 Σ 中，我们可以在字母表上定义一组所有有限字符串（读作：单词），即：

Σ = {s 1 , s 2 , ... ,s n }

Σ* = {ε} ∪ {s i1 s i2 ...s im | s ik ∈ Σ, m > 0, 1 ≤ k ≤ n}，其中 ε 为空字符串

例如，这意味着如果我们有一个字母表Σ = {a, b, c}，而 Σ* 中的一些单词将是aaaaaa, abababa，但不是abd，因为我们甚至不知道它的d存在。

正则表达式和语言

给定字母 Σ，我们有正则表达式，如ab*|c。我跳过了正则表达式的正式定义以减少混淆，所以让我们假设它是我们普通的旧“实用”正则表达式。

每个正则表达式都定义了一种正则语言，例如在这个例子中，语言由单词a, ab, c,组成abbbbbc，但不是abc。

有限自动机

每种正则语言都可以表示为一个有限自动机，一种可以识别正则表达式的设备。对于前面提到的正则表达式ab*|c，自动机看起来像这样：

ab*|c

0 是开始状态，双圈是接受状态。简而言之，自动机从状态 0 开始，消耗一个单词的每个字母，并根据转换箭头移动。如果它最终处于接受状态，我们说它接受字符串。否则，我们说它拒绝它。

因此，在这种情况下，将字符串abb输入我们的机器：

  1. 从状态 0 开始
  2. 消费a，进入状态1
  3. 消费b，进入状态 3
  4. 消费b，进入状态 3
  5. 字符串是空的，状态 3 是接受状态，所以这台机器接受字符串，或者等效地，我们的正则表达式模式匹配字符串。

让我们看看当我们abc输入机器时会发生什么：

  1. 从状态 0 开始
  2. 消费a，进入状态1
  3. 消费b，进入状态 3
  4. 消费c，无处可去，字符串被拒绝

所以我们的正则表达式不匹配abc。所有这些都与实际的正则表达式基本相同，并增加了一些理论。

等价

有一个定理表明每种常规语言都是有限自动机可识别的。这意味着，如果存在可以匹配您所需模式的正则语言（和底层正则表达式），则应该有一个等效的有限自动机。

那么，为什么不呢？

但是您的模式中的嵌套具有无限的深度。因此，您将需要一个与常规语言等效的无限大有限自动机，这与有限自动机的定义相矛盾。

参考

  1. 正则表达式和自动机

免责声明

正如你所看到的，我跳过了正则表达式的归纳定义、从范畴论的角度来看的有限自动机、操作下的闭包以及其他一些正式的东西。欢迎您在上述参考链接中阅读它。

于 2013-07-16T03:54:26.290 回答