From: dblack@...
Date: 2006-12-22T01:51:54+09:00
Subject: Re: Regexp Question: Checking for [/joe] pairs

Hi --

On Fri, 22 Dec 2006, Arne Brasseur wrote:

> 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.

If you're using scan, though, doesn't that mean that you're not really
trying to match one string to the regex, but rather a series of
strings?  That means that the state machine gets completely restarted
as the scan method goes along the string.  I think that's a different
situation.  You're not really saying: match all the pairs; you're
saying: find the first substring that has a matching pair, then
discard it and don't worry about backtracking through it; etc.


David

-- 
Q. What's a good holiday present for the serious Rails developer?
A. RUBY FOR RAILS by David A. Black (http://www.manning.com/black)
    aka The Ruby book for Rails developers!
Q. Where can I get Ruby/Rails on-site training, consulting, coaching?
A. Ruby Power and Light, LLC (http://www.rubypal.com)