PCRE имеет функцию, названную рекурсивным шаблоном, который может использоваться для соответствия вложенным подгруппам. Например, рассмотрите "грамматику"
Q -> \w | '[' A ';' Q* ','? Q* ']' | '<' A '>'
A -> (Q | ',')*
// to match ^A$.
Это может быть сделано в PCRE с шаблоном
^((?:,|(\w|\[(?1);(?2)*,?(?2)*\]|<(?1)>))*)$
(Тестовый сценарий в качестве примера: http://www.ideone.com/L4lHE)
abcdefg
abc,def,ghi
abc,,,def
,,,,,,
[abc;]
[a,bc;]
sss[abc;d]
as[abc;d,e]
[abc;d,e][fgh;j,k]
[b;
<,,,>
<>
<><>
<>,<>
a<<<<>>>>
<<<<<>>>><><<<>>>>
[[;];]
[,;,]
[;[;]]
[<[;]>;<[;][;,<[;,]>]>]
В.NET нет никакого рекурсивного шаблона. Вместо этого это предоставляет балансирующимся группам для стекового управления для соответствия простым вложенным шаблонам.
Действительно ли возможно преобразовать вышеупомянутое шаблон PCRE в.NET стиль Regex?
(Да я знаю, что лучше не использовать regex в для этого. Это - просто теоретический вопрос.)
The answer is (probably) Yes.
The technique is much more complex than the (?1)
recursive call, but the result is almost 1-to-1 with the rules of the grammar - I worked in a such methodical way I can easily see it scripted. Basically, you match block-by-block, and use the stack to keep track of where you are. This is an almost working solution:
^(?:
(\w(?<Q>)) # Q1
|
(<(?<Angle>)) #Q2 - start <
|
(\>(?<-Angle>)(?<-A>)?(?<Q>)) #Q2 - end >, match Q
|
(\[(?<Block>)) # Q3 start - [
|
(;(?<Semi-Block>)(?<-A>)?) #Q3 - ; after [
|
(\](?<-Semi>)(?<-Q>)*(?<Q>)) #Q3 ] after ;, match Q
|
((,|(?<-Q>))*(?<A>)) #Match an A group
)*$
# Post Conditions
(?(Angle)(?!))
(?(Block)(?!))
(?(Semi)(?!))
It is missing the part of allowing commas in Q->[A;Q*,?Q*]
, and for some reason allows [A;A]
, so it matches [;,,]
and [abc;d,e,f]
. Rest of the strings match the same as the test cases.
Another minor point is an issue with pushing to the stack with an empty capture - it doesn't. A
accepts Ø, so I had to use (?<-A>)?
to check if it captured.
The whole regex should look like this, but again, it is useless with the bug there.
There is not way of synchronizing the stacks: if I push (?)
and (?)
, I can pop them in any order. That is why this pattern cannot differentiate
from
... we need one stack for all.
Это можно решить для простых случаев, но здесь мы имеем нечто гораздо более сложное - целый Q
или A
, а не просто "<" или "[".