Рекурсивные(?) регулярные выражения в tcl?

Question

[dtestyk]

Есть следующая программа на tcl:

#!/usr/bin/tclsh

set p {}

while {[gets stdin c] >= 0} {

set r $p$c

#puts [execute r]

set p {}

regexp {^([^\}]*\{)(?:[^{}]*(?:\{[^{}]*\})?)?$} $r -> p

puts -nonewline $p

flush stdout

}

Видно, что можно открывать сразу несколько скобочек в одной команде(здесь "([^\}]*\{)"). Можно ли сделать такое же и для закрывающих, причем чтобы каждая закрывающая закрывала ровно одну открывающую, не изменяя сильно код(в идеале только регулярное выражение)?

Comments

[dtestyk]

a{s{d{f{g{h}}} -> a{s{

[dtestyk]

Интересует не столько соответствие канонам теории формальных языков, сколько варианты применения отклонения от них для этой задачи, как в perl.
Есть ли отличие в этом плане(третий тип грамматик и реализация расширения его возможностей) между этой задачей(внутри скобок есть не более одних скобой) и задачей подсчета скобой?

[dtestyk]

s/скобой\b/скобок/g :)

Answer 1

[MikhailEdoshin]

Я не совсем понял вопрос, может быть, но если вам нужно проверять соответствие скобок регулярным выражением, то это в принципе невозможно. Регулярные выражения могут описывать только регулярные грамматики, это третий тип грамматик, их можно разбирать автоматом без памяти, а соответствие скобок — это грамматики второго типа, более мощные, для них нужен парсер. Вы можете проверять соответствие скобок, если у вас, допустим, не более пяти пар в строке (то есть ограниченное число), но в общем случае нет.

Хотя современные регулярки довольно мощные с кучей всяких дополнительных возможностей, но не думаю, что туда что-то подобное добавят — там существенно отличающиеся алгоритмы.