Ответ 1
Альтернативой рекурсивному шаблону .Net является стек. Задача здесь состоит в том, что нам нужно выразить грамматику терминами стеков. Вот один из способов сделать это:
Немного отличается обозначение для грамматик
- Во-первых, нам нужны грамматические правила (например,
AиQв вопросе). - У нас есть один стек. Стек может содержать только правила.
- На каждом шаге мы выставляем текущее состояние из стека, сопоставляем то, что нам нужно, и нажимаем дополнительные правила в стек. Когда мы закончили с состоянием, мы ничего не нажимаем и не возвращаемся в предыдущее состояние.
Эта нотация находится где-то между CFG и Пуш-автомат, где мы вставляем правила в стек.
Пример:
Начнем с простого примера: a n b n. Обычная грамматика для этого языка:
S -> aSb | ε
Мы можем перефразировать это, чтобы соответствовать обозначению:
# Start with <push S>
<pop S> -> "a" <push B> <push S> | ε
<pop B> -> "b"
В словах:
- Начнем с
Sв стеке. - Когда мы выем
Sиз стека, мы можем:- Ничего не найдено или...
- соответствует "a" , но тогда нам нужно нажать состояние
Bв стек. Это обещание, которое мы будем соответствовать "b". Затем мы также нажимаемS, чтобы мы могли совместить "а" с, если хотим.
- Когда мы подобрали достаточно "а", мы начинаем выскакивать
Bиз стека и сопоставляем "b" для каждого из них. - Когда это будет сделано, мы сопоставим четное число "a" и "b" s.
или, более свободно:
Когда мы в случае S, сопоставим "a" и нажимаем B, а затем S или ничего не сравниваем.
Когда мы в случае B, сравним "b".
Во всех случаях мы выставляем текущее состояние из стека.
Запись шаблона в регулярном выражении .Net
Нам нужно каким-то образом представить разные состояния. Мы не можем выбрать '1' '2' '3' или 'a' 'b' 'c', потому что они могут быть недоступны в нашей строке ввода - мы можем только соответствовать тому, что присутствует в строке.
Один из вариантов - это число наших состояний (в приведенном выше примере S будет указывать номер 0, а B - состояние 1).
Для состояния S 𝒊 мы можем переместить 𝒊 символов в стек. Для удобства мы будем нажимать первые 𝒊 символы с начала строки. Опять же, нам все равно, каковы эти персонажи, сколько есть.
Нажмите состояние
В .Net, если мы хотим перенести первые 5 символов строки в стек, мы можем написать:
(?<=(?=(?<StateId>.{5}))\A.*)
Это немного запутанно:
-
(?<=…\A.*)- это lookbehind, который доходит до начала строки. - Когда мы на старте, посмотрим вперед:
(?=…). Это делается для того, чтобы мы могли выходить за пределы текущей позиции - если мы находимся в позиции 2, у нас нет 5 символов перед нами. Поэтому мы оглядываемся назад и смотрим вперед. -
(?<StateId>.{5})нажмите 5 символов в стек, указав, что в какой-то момент нам нужно совместить состояние 5.
Поп-состояние
Согласно нашим обозначениям, мы всегда выставляем верхнее состояние из стека. Это легко: (?<-StateId>).
Но прежде чем мы это сделаем, мы хотим знать, какое состояние было - или сколько персонажей он захватил. В частности, нам нужно явно проверить для каждого состояния, например, блок switch/case.
Итак, чтобы проверить, содержит ли текущий стек состояние 5:
(?<=(?=.{5}(?<=\A\k<StateId>))\A.*)
- Опять же,
(?<=…\A.*)подходит к началу. - Теперь мы продвигаем
(?=.{5}…)на пять символов... - И используйте другой lookbehind,
(?<=\A\k<StateId>), чтобы убедиться, что в стеке действительно есть 5 символов.
Это имеет очевидный недостаток - когда строка слишком короткая, мы не можем представить число больших состояний. Эта проблема имеет решения:
- Количество коротких слов на языке является окончательным в любом случае, поэтому мы можем добавить их вручную.
- Используйте что-то более сложное, чем один стек, - мы можем использовать несколько стеков, каждый с нулевым или одним символом, фактически бит нашего состояния (там пример в конце).
Результат
Наш шаблон для n b n выглядит следующим образом:
\A
# Push State A, Index = 0
(?<StateId>)
(?:
(?:
(?:
# When In State A, Index = 0
(?<=(?=.{0}(?<=\A\k<StateId>))\A.*)
(?<-StateId>)
(?:
# Push State B, Index = 1
(?<=(?=(?<StateId>.{1}))\A.*)
a
# Push State A, Index = 0
(?<StateId>)
|
)
)
|
(?:
# When In State B, Index = 1
(?<=(?=.{1}(?<=\A\k<StateId>))\A.*)
(?<-StateId>)
b
)
|\Z
){2}
)+
\Z
# Assert state stack is empty
(?(StateId)(?!))
Рабочий пример бурения в регулярном выражении
Примечания:
- Обратите внимание, что квантификатор вокруг состояний
(?:(?:…){2})+- то есть (счет состояния) × (длина ввода). Я также добавил чередование для\Z. Не будем вдаваться в это, но это обходное решение для раздражающей оптимизации в модуле .Net. - То же самое можно записать как
(?<A>a)+(?<-A>b)+(?(A)(?!))- это просто упражнение.
Чтобы ответить на вопрос
Грамматика из вопроса может быть переписана как:
# Start with <push A>
<pop A> -> <push A> ( @"," | <push Q> ) | ε
<pop Q> -> \w
| "<" <push Q2Close> <push A>
| "[" <push Q1Close> <push QStar> <push Q1Comma> <push QStar> <push Q1Semicolon> <push A>
<pop Q2Close> -> ">"
<pop QStar> -> <push QStar> <push Q> | ε
<pop Q1Comma> -> ","?
<pop Q1Semicolon> -> ";"
<pop Q1Close> -> "]"
Образец:
\A
# Push State A, Index = 0
(?<StateId>)
(?:
(?:
(?:
# When In State A, Index = 0
(?<=(?=.{0}(?<=\A\k<StateId>))\A.*)
(?<-StateId>)
(?:
# Push State A, Index = 0
(?<StateId>)
(?:
,
|
# Push State Q, Index = 1
(?<=(?=(?<StateId>.{1}))\A.*)
)
|
)
)
|
(?:
# When In State Q, Index = 1
(?<=(?=.{1}(?<=\A\k<StateId>))\A.*)
(?<-StateId>)
(?:
\w
|
<
# Push State Q2Close, Index = 2
(?<=(?=(?<StateId>.{2}))\A.*)
# Push State A, Index = 0
(?<StateId>)
|
\[
# Push State Q1Close, Index = 6
(?<=(?=(?<StateId>.{6}))\A.*)
# Push State QStar, Index = 3
(?<=(?=(?<StateId>.{3}))\A.*)
# Push State Q1Comma, Index = 4
(?<=(?=(?<StateId>.{4}))\A.*)
# Push State QStar, Index = 3
(?<=(?=(?<StateId>.{3}))\A.*)
# Push State Q1Semicolon, Index = 5
(?<=(?=(?<StateId>.{5}))\A.*)
# Push State A, Index = 0
(?<StateId>)
)
)
|
(?:
# When In State Q2Close, Index = 2
(?<=(?=.{2}(?<=\A\k<StateId>))\A.*)
(?<-StateId>)
>
)
|
(?:
# When In State QStar, Index = 3
(?<=(?=.{3}(?<=\A\k<StateId>))\A.*)
(?<-StateId>)
(?:
# Push State QStar, Index = 3
(?<=(?=(?<StateId>.{3}))\A.*)
# Push State Q, Index = 1
(?<=(?=(?<StateId>.{1}))\A.*)
|
)
)
|
(?:
# When In State Q1Comma, Index = 4
(?<=(?=.{4}(?<=\A\k<StateId>))\A.*)
(?<-StateId>)
,?
)
|
(?:
# When In State Q1Semicolon, Index = 5
(?<=(?=.{5}(?<=\A\k<StateId>))\A.*)
(?<-StateId>)
;
)
|
(?:
# When In State Q1Close, Index = 6
(?<=(?=.{6}(?<=\A\k<StateId>))\A.*)
(?<-StateId>)
\]
)
|\Z
){7}
)+
\Z
# Assert state stack is empty
(?(StateId)(?!))
К сожалению, слишком долго подходит для URL-адреса, поэтому нет онлайн-примера.
Если мы используем "двоичные" стеки с одним или нулевым символом, это выглядело бы так: https://gist.github.com/kobi/8012361
Вот скриншот шаблона, проходящего все тесты: http://i.stack.imgur.com/IW2xr.png
Bonus
Механизм .Net может делать больше, чем просто сбалансировать - он также может захватывать каждый экземпляр A или Q. Для этого требуется небольшая модификация шаблона: https://gist.github.com/kobi/8156968.
Обратите внимание, что мы добавили к шаблону группы Start, A и Q, но они не влияют на поток, они используются исключительно для захвата.
Результат: например, для строки "[<a>b;<c,d>,<e,f>]", мы можем получить эти Capture s:
Group A
(0-17) [<a>b;<c,d>,<e,f>]
(1-4) <a>b
(2-2) a
(7-9) c,d
(13-15) e,f
Group Q
(0-17) [<a>b;<c,d>,<e,f>]
(1-3) <a>
(2-2) a
(4-4) b
(6-10) <c,d>
(7-7) c
(9-9) d
(12-16) <e,f>
(13-13) e
(15-15) f
Открытые вопросы
- Можно ли преобразовать каждую грамматику в нотацию состояния стека?
- Есть (количество состояний) × (длина ввода) достаточно шагов для соответствия всем словам? Какая другая формула может работать?
Исходный код
Код, используемый для создания этих шаблонов и всех тестовых примеров, можно найти на https://github.com/kobi/RecreationalRegex