php - 用于提取嵌套元素的正则表达式

Question

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

{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"
}
}

Answer 1

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

这是为什么？

字母表

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

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

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

Σ = {s₁, s₂, ... ,s_n}

Σ* = {ε} ∪ {s_i1s_i2...s_im | s_ik ∈ Σ, m > 0, 1 ≤ k ≤ n}, where ε is an empty string

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

正则表达式和语言

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

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

有限自动机

每种常规语言都可以表示为 finite automaton ，一个可以识别正则表达式的设备。对于上述正则表达式 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. Regex & Automata

免责声明

如您所见，我跳过了正则表达式的归纳定义、范畴论角度的有限自动机、操作下的闭包以及其他一些正式内容。欢迎您在上述引用链接中阅读相关内容。