From: Arne Brasseur <arne@...>
Date: 2006-12-22T01:40:18+09:00
Subject: Re: Regexp Question: Checking for [/joe] pairs

Joe Peck wrote:
> The problem is I don't want it to accept things like:
> "[joe] hello [joe] how are [/joe] you"
> where there are two opening tags before a closing tag is reached. 
> Similarly, I don't want to accept something like:
> "hey [joe] it's hot today[/joe] where [joe] is the ac"
> where there is one correct pair but then an opening tag without a 
> closing one.
>   
I missed the beginning of this thread, but if I recall correctly from my 
course on formal languages, this sort if thing can't be done with 
regular expressions.

Regular expressions can be used to test whether a string belongs to a 
certain regular language, which is a subset of all possible languages 
(where a language is a set of strings). Regular expressions are 
equivalent to finite state automata in this respect. Since a finite 
state automata can only be in a finite number of states. You'd like to 
match a possibly infinitely large number of [joe][/joe] pairs. The FSA 
would need a new state for every extra [joe] it reads to remember it 
still needs to consume a matching [/joe] for it.

If this sounds like Chinese, just remember regexpes aren't keen on 
matching this sort of stuff. Stacks on the other hand seem to be custom 
designed for these purposes.

A.