On Sun, 2007-11-18 at 12:35 -0500, Hans-Christoph Steiner wrote:
On Nov 18, 2007, at 4:56 AM, Claude Heiland-Allen wrote:
Hans-Christoph Steiner wrote:
So... anyone want to write a regexp that escapes any unclosed
brackets? That would be a tricky one... but very useful for Pd.I guess that it's not possible at all with regular expressions:
http://en.wikipedia.org/wiki/ Regular_language#Regular_languages_over_an_alphabet --8<-- A simple example of a language that is not regular is the set of
strings { a^n b^n | n >= 0 }. --8<--This is precisely the "matching brackets" problem.
regexps plus something else perhaps. It's pretty simple to do, just
count open brackets and close brackets, see if there is a difference,
then go find the extra and escape it. Many text editors keep track
of this stuff on the fly.
the language { a^n b^n | n >= 0 } cannot be described by a regular expression, as it is not a regular language (easy to prove via the pumping lemma). you need a parser for a context-free grammar in order to match this structure ...
hth, tim
-- tim@klingt.org http://tim.klingt.org
Most of the trouble in this world has been caused by folks who can't mind their own business, because they have no business of their own to mind, any more than a smallpox virus has. William S. Burroughs