(PHP) 解析正则表达式字符串 - 平衡括号

Question

我将尝试在PHP中解析以下格式的字符串（EBNF，希望我理解正确）：

<exp>      ::= <base>[{<modifier>["!"]"("<exp>")"}]
<base>     ::= <role>[{<modifier><role>}]
<modifier> ::= "&" | "|"
<role>     ::= ["!"]<str>[","<str>]

在这里，<str> 是任何可以通过 [a-zA-Z0-9\-]+ 的字符串。

以下是需要解析的模式示例：

token1
token1&token2
token1|(token2&!token3)
(token1&token2)|(token3&(token4|(!token5,12&token6)))
!(token1&token2|(token3&!token4))|token5,12

我试图编写一个正则表达式模式，总是会给我四个组：

1. 最左边的。从上面的示例中，这将是： - token1 - token1 - token1 - token1&token2 - token1&token2|(token3&!token4)

2. 如果["!"]存在，则为null或!。

3. 下一个的（如果有）。这将是： - null - & - | - | - | 4. 模式的其余部分。 - null - token2 - token2&!token3 - token3&(token4|(!token5,12&token6)) - token5,12 只要第一个表达式不包含任何，就可以解析它。

^\(?(!?)([a-zA-Z0-9\-]+)\)?([&|]?)(.*)$

我卡在这个点了。我尝试使用环视，但是我无法弄清楚如何确保当所有括号都平衡时，组被捕获。这是否可以通过正则表达式实现，还是需要编写使用循环等的代码来完成？

- Bart Platak

---

+1，干得好，我会关注这个帖子的回复。 - Ionut Flavius Pogacian

你几乎可以直接将描述翻译成PCRE的?(DEFINE)块。但是，PCRE只允许匹配，而不是解析。你无法获得所需的拆分结果列表。(除非你还使用递归的preg_replace_callback来收集所有令牌。) - mario

Answer 1

据我所知，这是不可能的。

您拥有一个无上下文语法（EBNF适用于此类语法-第2型语法），它不能使用正则表达式进行解析（正则表达式适用于正则语法-第3型语法）。

http://en.wikipedia.org/wiki/Chomsky_hierarchy

作为您无法在此处处理的事情的示例：开括号的数量 - 您只能为每个这些数字编写一个正则表达式（但是可以无限制，对吧？），否则就无法确定匹配的关闭括号的数量是否相同。无法计算由具有量词（+、*等）的正则表达式的特定部分匹配的字符数。

- scriptin

---

PHP的正则表达式确实允许递归，但我建议不要使用它。 - Evert

@Evert 是的，但这并没有帮助。例如："$m=array(); preg_match('/ < ( (?>[a-z]+) | (?R) )* > /x', '<abc<<>', $m); var_dump($m);" - 这个可以工作是因为正则表达式不匹配整个字符串 - 没有 ^ 和 $。但是，如果我们添加 ^ 和 $，即使对于 '<abc<>>' 作为输入字符串，它也不会工作，因为 (?R) 现在包含 ^ 和 $。我希望这个解释是可理解的。 - scriptin

我已经研究了递归，但它似乎是一种非常混乱的方法。相反，我现在正在编写自己的解析器来处理这个问题。谢谢 :) - Bart Platak

不正确。仅仅因为它们被称为“正则表达式”，并不意味着它们局限于正则语言。而且你也可以递归地调用特定的子表达式 (?1)，从而排除了 ^ 和 $。 - mario