Re: Compiler Theory

javadesigner <>
3 Jun 2003 01:16:34 -0400

          From comp.compilers

Related articles
Compiler Theory (2003-04-27)
Re: Compiler Theory (2003-05-06)
Re: Compiler Theory (Aby Paul) (2003-05-06)
Re: Compiler Theory (javadesigner) (2003-06-03)
| List of all articles for this month |

From: javadesigner <>
Newsgroups: comp.compilers
Date: 3 Jun 2003 01:16:34 -0400
Organization: Compilers Central
References: 03-04-088
Keywords: theory
Posted-Date: 03 Jun 2003 01:16:34 EDT

MeisterStiff wrote:

> I've two books on compiler theory/writing, but they seem to be all too
> difficult for my current knowledge. I'm looking up for pointers to
> documents available for free on the web with simple descriptions and
> "how to"-type of documents about general compiler theory. I'm mainly

Most of the "parsing" books out there in my opinion are full of
pseudo-math wanking. No really they _are_.

Euler is great. Fourier is great. _Real_ math is great. _Real_ math is
fun. Pseudo math and "set" theory is stupid. Stay away from it.

The following books stand out, in my opinion, head and shoulders
above the rest:

1) Computability theory:
      Godel, Escher, Bach
      Trust me, GEB is perhaps as good a "serious" introduction to computability
      theory as you will ever find. Tells you the implications of grammars that
      contain rules for both growing and shrinking sentences. Not a popular
      science book as is sometimes (mis)characterised as, but a very deep
      and serious textbook. (A small aside, godel is pronounced more like

      The Emperor's New Mind -- Roger Penrose
      The chapters on turing machines are a good complement and somewhat easier
      going than GEB.

These two will tell you all you need to know about models of computation. As
an aside, Hardware and logic design is also recommended to really understand
computers (what's _really_ going on in there ?) and books by Wakerly and
Patterson/Hennessy are essential. Programs/compilers are not written in
a vacuum but run on real hardware and it's good to know the hardware.

2) Parsing:
    2.a) "Parsing Techniques - A Practical Guide" by Grune and Jacobs
    (it's available for free as .pdf over the web - google is your friend)

    A lucid, entertaining and ultra-comprehensive treatment of parsing
    in general. Very easy to follow and very well written. Covers parsing
    for all top-down and bottom-up methods (including general techniques
    for context-free languages like CYK, Earley, Unger, Tomita and deterministic
    techniques for constant-time parsing like: LR, LALR, SLR, LL etc). Extensive
    bibliography and perhaps the one single best reference in the field.

    A web based introduction to parsing with prolog. Great for the theory,
    and examples and very lucid explanations of bottom-up and top-down
    methods. Prolog sample code -- but you don't really need to know prolog
    to understand the text itself [I didn't]. In any case, Prolog is easy to
    pick up (at least enough for the examples) in about 1 hour.
    Highly recommended to go along with 2.a

Also look at the source code for cup/jlex, java regex, various gnu
software and xml/sgml parsers. This is good for getting familiar
with diverse implementation techniques/ideas.

Best regards,


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.