(PHP)解析RegEx字符串 - 平衡括号

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

我正在尝试编写一个总是给我四组的RegEx模式:

1. 最左边的<expression>.从上面的例子可以看出:
   • token1
   • token1
   • token1
   • token1&token2
   • token1&token2|(token3&!token4)
2. 如果["!"]有的话.即
   • null
   • null
   • null
   • null
   • !
3. 的<modifier>下一个<expression>(如果有的话).这将是:
   • null
   • &
   • |
   • |
   • |
4. 剩下的模式.
   • null
   • token2
   • token2&!token3
   • token3&(token4|(!token5,12&token6))
   • token5,12

如果第一个表达式不包含任何<modifier>s ,我可以解析它.

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

我被困在这一点上.我已经尝试过使用lookarounds,但是我无法弄清楚如何在所有括号均衡时确保捕获该组.这可以通过RegEx实现,还是需要使用循环等编写代码来执行此操作？

Answer 1

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

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

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

作为你不能在这里处理的事情的一个例子：左括号的数量 - 你只能为其中的每个数字编写一个正则表达式（但可以是无限的，对吧？），否则无法判断匹配的数量右括号是相同的。无法计算正则表达式的特定部分与量词（ 、 等）计算出的+字符*数