"Brian Candler" <B.Candler / pobox.com> wrote in message
news:20030221172438.A85978 / linnet.org...

> I think some things which programmers consider part of "regular
expressions"
> are not formally part of regexps anyway. In particular, a true regular
> expression cannot parse a grammar like matching open and close brackets
> (e.g. "match a number of A's followed by an equal number of B's")

But this is to my knowledge also not possible in regular expressions
implementations. If you match a finite number of parentheses you can both
formally and in real-world regular expressions. Otherwise you enter the
world of LL-1 grammars etc. and you need to write a stack supported
recursive descent parser or a bottom-up parser (LR, or LALR) parser.

To be more precise regular expressions are supported by finite state
machines (finite as in no stack), whereas a bottom-up parser like Yacc is
also a state machine, but not a finite one - it uses an infinite stack and
thus support infinite nesting levels.

Mikkel