Compilers: Principles, Techniques, and Tools (2nd Edition)

Author: Alfred V. Aho
All Stack Overflow 42
This Year Stack Overflow 5
This Month Reddit 5

Compilers: Principles, Techniques, and Tools (2nd Edition)


Review Date:


by anonymous   2018-03-26
[Compilers: Principles, Techniques, and Tools]( by Aho, et al.
by anonymous   2018-03-19

Yes, you can certainly use lex and yacc to build a compiler/translator for a programming or scripting language. There are GNU variants of these tools, called flex and bison. John Levine's lex & yacc was for many years the gold standard for books about these tools. That book may be out of print, but I expect that the successor book, Flex & Bison, is just as good. To dig deeper into building a compiler, start with Aho et al., Compilers: Principles, Techniques, and Tools, 2/e. (Again, my recommendation is based on the first edition of this book.)

by Bluegorilla101   2018-02-16

Should have gotten her this dragon book so she can get a headstart on writing compilers.

by correctsbadalts   2018-02-16

Was expecting this dragon book

by OhYourFuckingGod   2018-02-16

She's trying to hide her disappointment. I'm pretty sure this is the one she wanted .

by thaumasiotes   2017-10-23
I used the dragon book (2nd edition) -

That proof isn't a problem in the book; it's mentioned, with a hint for those inclined to derive it themselves, in the running text.

by dvt   2017-10-05
I strongly suggest you build something esoteric and fun first. This should be a "bare minimum" VM or interpreter. Here's one of mine that I wrote like a 8 years ago[1]:
by wenc   2017-09-07
You'll want the Dragon Book as a reference, not necessary to get started with, but to build the semantic tree on which you will need to pin concepts on.

If you aren't yet committed to any language, you can start building a parser with PyParsing. It's really easy.

If you want to take a quick (albeit expensive) class on it, Dave Beazley offers one:

by anonymous   2017-09-05
If you want to show it as a text, then VZ's answer is the way to go; however, if you want to show the `result` of an arithmetic operation, then you need to write a small parser, a good book would be:
by anonymous   2017-08-20

How many contemporary algorithms are there to build a parser?

To start with one can look at the list of the common parser generators.
See: Comparison of parser generators and look under the heading Parsing algorithm.

Backtracking Bottom-up  
Backtracking LALR(1)  
Backtracking LALR(k)  
LL(1), Backtracking, Shunting yard
LL(k) + syntactic and semantic predicates  
LL, Backtracking  
Recursive descent  
Recursive descent, Backtracking  
PEG parser interpreter, Packrat  
Packrat (modified)  
Packrat + Cut + Left Recursion  
Packrat (modified), mutating interpreter  
2-phase scannerless top-down backtracking + runtime support  
Packrat (modified to support left-recursion and resolve grammar ambiguity)  
Parsing Machine  
Recursive descent + Pratt  
Packrat (modified, partial memoization)  
Hybrid recursive descent / operator precedence  
Scannerless GLR  
runtime-extensible GLR  
Scannerless, two phase  
Earley/combinators, infinitary CFGs  
Scannerless GLR  
delta chain  

Besides parser generators, there are also other algorithms/means to parse. In particular Prolog has DCG and most people who have written their first parser from scratch without formal training typically start with recursive descent. Also Chart parser and Left corner parser.

In writing parsers the first question that I always ask myself is how can I make a grammar for the language at the highest type in the Chomsky hierarchy. Here lowest is Type-0 and highest is Type-3.

Almost 90% of the time it is a Type-2 grammar (context-free grammars), then for the easer task it is a Type-3 grammar (regular grammars). I have experimented with Type-1 grammars (context-sensitive grammars) and even Type-0 grammars (unrestricted grammars).

And what's the advantage/limitation of ANTLR's Adaptive LL(*) algorithm?

See the paper written by Terrence Parr the creator of Adaptive LL(*): Adaptive LL(*) Parsing: The Power of Dynamic Analysis

In practical terms Adaptive LL(*) lets you get from a grammar to a working parser faster because you do not have to understand as much parsing theory because Adaptive LL(*) is, shall I say, nimble enough to side step the mines you unknowingly place in the grammar. The price for this is that some of the mines you unknowingly place in the grammar can lead to inefficiencies in the runtime of the parser.

For most practical programming language purposes Adaptive LL(*) is enough. IIRC Adaptive LL(*) can NOT do Type-0 grammars (unrestricted grammars) which Prolog DCG can, but as I said, most people and most common programming task only need either type 2 or type 3.

Also most parser generators are for type 2, but that does not mean they can't do type 1 or possibly type 0. I cannot be more specific as I do not have practical experience with all of them.

Anytime you use a parsing tool or library there is a learning curve to learning how to use it and what it can and can not do.

If you are new to lexing/parsing and really want to understand it more then take a course and/or read Compilers: Principles, Techniques, and Tools (2nd Edition)