Best Computer Science School in Utah

Levi Pearson levi at
Tue Sep 25 22:53:58 MDT 2007

Hans Fugal <hans at> writes:
>> Though, 252 teaches real regular expressions, which are far more
>> limited than your standard perl-compatible regexp library.  Of course,
>> it also teaches you how to recognize a regular language and prove that
>> it is so.  And it gives you an idea of why you might sometimes want to
>> use a regular language instead of a more powerful one.
> And by limited of course you are talking about syntax. They are equal in
> what they can match (regular languages).

No, I mean that perl 'regular expressions' match more than regular
languages.  This makes them useful in more situations, but also makes
them slower.  E.g. (.*)\1; the language which it matches is neither
regular nor context-free.  

> I think everyone who enjoys regular expressions should also look into
> parsers and compilers, e.g. context-free grammars via recursive descent
> or lex/yacc. I read a blog entry by some bigwig once saying that
> compilers is the most important CS class, and while I'm not sure if it's
> the *most* important it is definitely very important. Overcoming the
> fear of building compilers (really, you can do it and with the right
> tools it doesn't take very long) can make a big positive difference in
> the problems you can tackle and how you tackle them.

I agree, and I'll quote Hal Abelson from the Foreword of the CS 330
textbook, 'Essentials of Programming Languages':

> This book brings you face-to-face with the most fundamental idea in
> computer programming: The interpreter for a computer language is just
> another program.  It sounds obvious, doesn't it?  But the implications
> are profound.  If you are a computational theorist, the interpreter
> idea recalls Godel's discovery of the limitations of formal logical
> systems, Turing's concept of a universal computer, and von Neumann's
> basic notion of the stored-program machine.  If you are a programmer,
> mastering the idea of an interpreter is a source of great power.  It
> provokes a real shift in mindset, a basic change in the way you think
> about programming.

Of course, compiling and interpreting are different, but both are
essential to understanding computer programming and they're closely
related, in that both are about matching languages and assigning
meaning to them.


More information about the PLUG mailing list