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 -- [EMAIL PROTECTED] 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
signature.asc
Description: This is a digitally signed message part
_______________________________________________ PD-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list