Альтернативой рекурсивному шаблону .Net является стек. Проблема в том, что нам нужно выразить грамматику в терминах стеков.
Вот один из способов сделать это:
Немного другое обозначение для грамматик
- Во-первых, нам нужны грамматические правила (например,
A и Q в вопросе).
- У нас есть один стек. Стек может содержать только правила.
- На каждом шаге мы извлекаем текущее состояние из стека, сопоставляем с тем, что нам нужно, и помещаем дополнительные правила в стек. Когда мы закончим с состоянием, мы ничего не нажимаем и не возвращаемся в предыдущее состояние.
Эта нотация находится где-то между CFG и Автоматом Pushdown , где мы помещаем правила в стек.
* * Пример тысяча двадцать-один: * * 1 022
Начнем с простого примера: a n b n . Обычная грамматика для этого языка:
S -> aSb | ε
Мы можем перефразировать это в соответствии с обозначением:
# Start with <push S>
<pop S> -> "a" <push B> <push S> | ε
<pop B> -> "b"
На словах:
- Мы начинаем с
S в стеке.
- Когда мы извлекаем
S из стека, мы можем либо:
- Ничего не соответствует или ...
- соответствует «a», но затем мы должны поместить состояние
B в стек. Это обещание, мы будем соответствовать "б". Затем мы также нажимаем S, чтобы мы могли продолжать сопоставлять «а», если хотим.
- Когда мы подобрали достаточно «a», мы начинаем выталкивать
B s из стека и сопоставлять «b» для каждого.
- Когда это будет сделано, мы сопоставим четное число «a» и «b».
или, более свободно:
Когда мы находимся в случае S, сопоставьте «a» и нажмите B, а затем S или ничего не подходите.
Когда мы находимся в случае B, сопоставьте «b».
Во всех случаях мы извлекаем текущее состояние из стека.
Запись шаблона в регулярном выражении .Net
Нам нужно как-то представлять разные состояния. Мы не можем выбрать '1' '2' '3' или 'a' 'b' 'c' , потому что они могут быть недоступны в нашей входной строке - мы можем соответствует только тому, что присутствует в строке.
Одним из вариантов является нумерация наших состояний (в приведенном выше примере S будет указывать номер 0, а B - это состояние 1).
Для состояния S ? мы можем поместить ? символов в стек. Для удобства мы вставим первые ? символов в начале строки. Опять же, нас не волнует , что это символы, сколько их.
Состояние нажатия
В .Net, если мы хотим поместить первые 5 символов строки в стек, мы можем написать:
(?<=(?=(?<StateId>.{5}))\A.*)
Это немного запутанно:
(?<=…\A.*) - это взгляд назад, идущий до самого начала строки. - Когда мы на старте, впереди есть взгляд:
(?=…). Это сделано для того, чтобы мы могли соответствовать текущей позиции - если мы находимся в позиции 2 , у нас нет 5 символов перед нами. Итак, мы смотрим назад и с нетерпением ждем.
(?<StateId>.{5}) поместите 5 символов в стек, указывая, что в какой-то момент нам нужно сопоставить состояние 5.
Pop state
Согласно нашим обозначениям, мы всегда извлекаем верхнее состояние из стека. Это легко: (?<-StateId>).
Но прежде чем мы это сделаем, мы хотим знать, в каком состоянии это было - или сколько символов оно захватило. Более конкретно, нам нужно явно проверять каждое состояние, например, блок switch / case.
Итак, чтобы проверить, имеет ли стек текущее состояние 5:
(?<=(?=.{5}(?<=\A\k<StateId>))\A.*)
- Опять же,
(?<=…\A.*) идет до самого начала.
- Теперь мы опережаем
(?=.{5}…) на пять символов ...
- И используйте другой вид сзади,
(?<=\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)(?!))
Рабочий пример для Regex Storm
Примечания:
- Обратите внимание, что квантификатор вокруг состояний равен
(?:(?:…){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
Открытые вопросы
- Может ли каждая грамматика быть преобразована в нотацию стека состояний?
- Is (счетчик состояний) × (входдлина) достаточно шагов, чтобы соответствовать всем словам?Какая другая формула может работать?
Исходный код
Код, использованный для генерации этих шаблонов и всех тестовых случаев, можно найти в https://github.com/kobi/RecreationalRegex