Macros in Python, and using reg exps to build a scheme interpreter

[Mike Dean]

<posted & mailed>

On Thursday 31 October 2002 03:50 pm, Alex Martelli <aleax at aleax.it> 
wrote in comp.lang.python:
>> And two does anyone
>> know a good place to look for how to implement a scheme parser using
>> regular expressions?
> 
> If I recall correctly, strictly speaking, regular expressions cannot
> parse a language with unlimited depth of nesting.  RE's with the many
> extensions that Python borrowed from Perl, and embedded in a richer
> language, of course, may be able to.  But the simplest and fastest
> approach is most likely to be one NOT using RE's, I would guess.
Can't find the page right now, but Jeffrey Friedl's Mastering Regular 
Expressions (from O'Reilly; really, a must-read for anyone even 
thinking about using regular expcessions) covers this very topic.  
Pretty much, there is no way for for an RE to match nested delimiters 
(braces, parents, whatever) (reason being: "RE's can't count").  An RE 
can be constructed to match an arbitrary, finit depth of delimiters (no 
more, no less, than the depth for which it was constructed), and a loop 
can be used to generate such an expression, but there is no way to 
match delimiters to a variable level of nesting.  Unless RE's have 
drastically changed since this book, which covers (in reasonable 
detail) Perl 5's regular expressions.

HTH,
Mike