From: Daniel Martin <martin@...>
Date: 2006-09-15T22:30:11+09:00
Subject: Re: Regular expression question.

"Francis Cianfrocca" <garbagecat10@gmail.com> writes:

> One more point. Someone upthread gave an example similar to this:
>
> /* printf ("*/"); */
>
> Considered strictly as a lexical construction, I think this is regular.
> However, I have a funny feeling that this:
>
> /* printf ("/*......*/"); */
>
> is actually context-free. Does anyone know for sure?

So you want to know if a grammar is regular or not?  Sounds like you
need the Myhill-Nerode theorem
(http://en.wikipedia.org/wiki/Myhill-Nerode_theorem).

And according to that, a language that allows arbitrary nesting of
comment expressions like this is indeed not regular, and therefore not
parseable with regular expressions as traditionally defined in
computer science.  To parse arbitrarily nested constructs you either
need something like perl's evaluate-code-at-regexp-match-time feature
(which so far as I know exists in no other language), or an actual
grammar.  (or anything else that can get as complicated
computationally as a pushdown automaton)

-- 
s=%q(  Daniel Martin -- martin@snowplow.org
       puts "s=%q(#{s})",s.map{|i|i}[1]       )
       puts "s=%q(#{s})",s.map{|i|i}[1]