mime_type
Guest
Алгоритм работы регулярных выражений
Здравствуйте!
Я пишу универсальный парсер.
Который на основе грамматики парсит текст.
Грамматика задаётся в виде:
<rule1>::= ... .
<rule2>::= ... <rule1> ... .
Есть такие элементы как:
[] - опциональность (аналог "?" в рег. выр.)
{} - повторение (аналог "+", "*", ... в рег. выр.)
?...|...|...? - альтернативы (аналог "|")
У есть несколько вопросов. Был бы очень признателен, если бы вы на них ответили.
Вопросы:
1) Жадность, как я понял, задается только для элементов повторения (квантификаторов). Это так?
2) Если квантификатор ЖАДЕН, то он пытается захватить как можно больше символов входного текста, или же "реализовать" как можно больше повторений? (Я думаю, что это принципиально разные вещи...)
3) Как производится перебор по всем возможным вариантам "реализации" повторения (квантификатора)?
Пусть у нас есть рег. выр. "(a|b|c){0,3}", или если
переписать на мой синтаксис грамматики: "{?a|b|c?!,3}".
Подшаблон "(a|b|c)" имеет 3 возможных варианта реализации.
Весь шаблон "(a|b|c){0,3}" имеет 40 возможных вариантов реализации.
40 = 1 (0 повторений) + 3 (1 повторение) + 3*3 (2 повторения) + 3*3*3 (3 повторения);
Пусть альтернатива "a|b|c" перебирает последовательно, т.е. начала "a", затем "b", и в конце "c".
Меня интересует трассировка перебора по возможным вариантам.
Если ЖАДЕН:
(сначала по максимуму длинны)
aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc
(затем чуть короче)
aa
ab
ac
ba
bb
bc
ca
cb
cc
(еще короче)
a
b
c
(и минимум - т.е. ничего, т.е. ноль повторений)
[]
Так это происходит?
А если максимальный предел длинны не установлен?
Если я правильно понимаю, то здесь количество реальных (не возможных, а реальных) вариантов "реализации" на следующей итерации зависит от того, что было до этого.
Если ЩЕДРЫЙ:
(сначала минимум - т.е. ничего, т.е. ноль повторений)
[]
(затем чуть больше)
a
b
c
(еще больше)
aa
ab
ac
ba
bb
bc
ca
cb
cc
(и еще больше (...по аналогии))
Это так происходит?
Спасибо.
Здравствуйте!
Я пишу универсальный парсер.
Который на основе грамматики парсит текст.
Грамматика задаётся в виде:
<rule1>::= ... .
<rule2>::= ... <rule1> ... .
Есть такие элементы как:
[] - опциональность (аналог "?" в рег. выр.)
{} - повторение (аналог "+", "*", ... в рег. выр.)
?...|...|...? - альтернативы (аналог "|")
У есть несколько вопросов. Был бы очень признателен, если бы вы на них ответили.
Вопросы:
1) Жадность, как я понял, задается только для элементов повторения (квантификаторов). Это так?
2) Если квантификатор ЖАДЕН, то он пытается захватить как можно больше символов входного текста, или же "реализовать" как можно больше повторений? (Я думаю, что это принципиально разные вещи...)
3) Как производится перебор по всем возможным вариантам "реализации" повторения (квантификатора)?
Пусть у нас есть рег. выр. "(a|b|c){0,3}", или если
переписать на мой синтаксис грамматики: "{?a|b|c?!,3}".
Подшаблон "(a|b|c)" имеет 3 возможных варианта реализации.
Весь шаблон "(a|b|c){0,3}" имеет 40 возможных вариантов реализации.
40 = 1 (0 повторений) + 3 (1 повторение) + 3*3 (2 повторения) + 3*3*3 (3 повторения);
Пусть альтернатива "a|b|c" перебирает последовательно, т.е. начала "a", затем "b", и в конце "c".
Меня интересует трассировка перебора по возможным вариантам.
Если ЖАДЕН:
(сначала по максимуму длинны)
aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc
(затем чуть короче)
aa
ab
ac
ba
bb
bc
ca
cb
cc
(еще короче)
a
b
c
(и минимум - т.е. ничего, т.е. ноль повторений)
[]
Так это происходит?
А если максимальный предел длинны не установлен?
Если я правильно понимаю, то здесь количество реальных (не возможных, а реальных) вариантов "реализации" на следующей итерации зависит от того, что было до этого.
Если ЩЕДРЫЙ:
(сначала минимум - т.е. ничего, т.е. ноль повторений)
[]
(затем чуть больше)
a
b
c
(еще больше)
aa
ab
ac
ba
bb
bc
ca
cb
cc
(и еще больше (...по аналогии))
Это так происходит?
Спасибо.
