[Baypiggies] How to Implement Compilers and Interpreters

Stephen McInerney spmcinerney at hotmail.com
Thu Jul 31 10:59:33 CEST 2008

Well I took Stanford CS143, so here's my modest take:
- your task depends largely on whether you're tackling some arbitrary syntax
someone just made up, or parsing some well-known standardized language
(e.g. Scheme, Lisp, Haskell, C etc.).
(FYI gcc uses an ad-hoc parser under-the-hood for raw speed, not a yacc-generated one.)
- the dragon book (Aho, Sethi, Ullman) is, if I may say, pretty awful,
a bad read, clunky typesetting, inadequate examples (Pascal fragments?)
and dwells morbidly on parsing theory. All you really need to know in the real
world is that yacc/bison will handle SLR(1) grammars, which are the only ones
we care about, and we handle ambiguity in expressions via operator
precedence and associativity rules.
Corollary: if yacc rejects your grammar and you can't fix it, it ain't SLR(1).
It seems like computer scientists love to go overboard on this theory, NFAs and so on.
You only need an appreciation of how they work, and to familiarize yourself
with how yacc runs by trying to build a grammar for a subset of C (or Scheme).
- I am not aware of any more approachable book, but in either case,
 better than any book is to take Stanford CS143 via
  Stanford Online, it runs almost every semester.
If you're too busy to do the 4 programming exercises (which are the most
valuable part of the course), then just take it CR/NC or Audit.
- I have no opinion on "Essentials of Programming Languages" (2nd ed),
but from the reviews it sounds slightly better and does mention Scheme.
- Basically this is one of the those topics you will learn infinitely more by doing
than by reading. With any of these books, be prepared to speed-read or
skim the hundreds of pages that are not directly relevant to your needs.
- If you get as far as code generation, you will come to detest explicit
pointers even more than you already do (not applicable to Scheme).
PS Anyway, are you doing this as a learning exercise, or is there genuinely no
existing off-the-shelf open-source parser that will fit your needs?

Date: Thu, 31 Jul 2008 01:23:58 -0700From: jjinux at gmail.comTo: baypiggies at python.orgSubject: [Baypiggies] How to Implement Compilers and Interpreters
I'm looking for some advice implementing compilers and interpreters.  If you know about such things, can you respond to my blog post?http://jjinux.blogspot.com/2008/07/computer-science-how-to-implement.htmlThanks,-jj-- Lisp programmers know the value of everything, but the cost of nothing...On my Lisp, '() costs 4 bytes.http://jjinux.blogspot.com/
With Windows Live for mobile, your contacts travel with you.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/baypiggies/attachments/20080731/28e6dc4c/attachment.htm>

More information about the Baypiggies mailing list