regular expression for nested matching braces

[Piet van Oostrum]

>>>>> Boris^2 <borcis at geneva-link.ch> (B) writes:

B> Darrell wrote:

>> Tim Peters Explains it here.
>> http://groups.google.com/groups?th=ed6a75bc5eed7ee9&seekm=000401be9e6d%2427a98ec0%24029e2299
>> Searched on "tim peters match"
>> It's result 203$


B> Tim expounds there that :

>>> "Regular expressions can't count" -- nested brackets are beyond their
B> abilities.

B> Nevertheless, searching google groups with "context-free expressions" turns
B> up :

B> http://groups.google.ch/groups?q=context-free+expressions&hl=de&selm=1v35mpINNl78%40uwm.edu&rnum=1

B> that tells a slightly different (and interesting) story.

Not different. First it is as its subject says, about context-free
expressions rather than regular expressions. Moreover:

* Regular expressions are characterized as degree-0 context free expressions
* Degree 1 context free expressions are exactly those that can be processed
  by counter automata (a finite state automaton that uses a counter instead
  of a stack) 

I.e to count you need at least a degree-1 context free expression, you
can't do it wqith a degree-0 context-free expression (a.k.a. regular
expression).

In fact python's regular expressions are a little bit stronger than the
theoretical ones because of the allowed \n constructs, but still can't
count. 
-- 
Piet van Oostrum <piet at cs.uu.nl>
URL: http://www.cs.uu.nl/~piet [PGP]
Private email: P.van.Oostrum at hccnet.nl