3 ms·

"You don't need to build an AST. All books that give this advice originate from academic environment and are completely out of touch with reality. Unfortunately

"You don't need to build an AST. All books that give this advice originate from academic environment and are completely out of touch with reality. Unfortunately these books can be credited for the terribly bloated compilers that we are using, including Python and Perl." Can you give an example of an Open Source (so we can learn how it is done) compiler that embodies an alternate strategy?

mojuba 18y ago
Lua, but I'm sure there are many more. The generate-as-you-go technique is best described in Wirth's Algorithms + Data Structures = Programs, first edition (the last chapter about compilers was removed in later editions for some reason). Turbo Pascal - probably the smallest and the fastest commercial compiler ever made - well, for an imperative language - was inspired by Wirth's book, too (see http://en.wikipedia.org/wiki/Algorithms_%2B_Data_Structures_%3D_Programs http://en.wikipedia.org/wiki/Algorithms_%2B_Data_Structures_... )
- comatose_kid 18y ago
  The last chapter was removed because (from the preface of the 2nd ed): "The entire fifth chapter of the first Edition has been omitted. It was felt that the subject of compiler construction was somewhat isolated from the preceding chapters and would rather merit a more extensive treatment in its own volume. "
- LogicHoleFlaw 18y ago
  There are some memories :D Turbo Pascal was the compiler I used when I took my first computer programming course in High School.
kragen 18y ago
Jack Crenshaw's "Let's Build a Compiler" gives a tutorial in Pascal of how to do this. My own StoneKnifeForth compiles itself in an AST-free way in less than 120 lines of code, but I haven't released it yet. Ur-Scheme (http://canonical.org/~kragen/sw/urscheme/ http://canonical.org/~kragen/sw/urscheme/) doesn't have any intermediate representation other than the S-expression representation of the code; it uses that to perform closure analysis. Probably an AST is the easiest form to perform this on. The Lua guys came up with an implementation technique for closures that doesn't require building a parse tree first, but it's quite a bit more complicated.

mojuba 18y ago

Lua, but I'm sure there are many more. The generate-as-you-go technique is best described in Wirth's Algorithms + Data Structures = Programs, first edition (the last chapter about compilers was removed in later editions for some reason). Turbo Pascal - probably the smallest and the fastest commercial compiler ever made - well, for an imperative language - was inspired by Wirth's book, too (see http://en.wikipedia.org/wiki/Algorithms_%2B_Data_Structures_%3D_Programs http://en.wikipedia.org/wiki/Algorithms_%2B_Data_Structures_... )

comatose_kid 18y ago
The last chapter was removed because (from the preface of the 2nd ed): "The entire fifth chapter of the first Edition has been omitted. It was felt that the subject of compiler construction was somewhat isolated from the preceding chapters and would rather merit a more extensive treatment in its own volume. "
LogicHoleFlaw 18y ago
There are some memories :D Turbo Pascal was the compiler I used when I took my first computer programming course in High School.

kragen 18y ago

Jack Crenshaw's "Let's Build a Compiler" gives a tutorial in Pascal of how to do this. My own StoneKnifeForth compiles itself in an AST-free way in less than 120 lines of code, but I haven't released it yet. Ur-Scheme (http://canonical.org/~kragen/sw/urscheme/ http://canonical.org/~kragen/sw/urscheme/) doesn't have any intermediate representation other than the S-expression representation of the code; it uses that to perform closure analysis. Probably an AST is the easiest form to perform this on. The Lua guys came up with an implementation technique for closures that doesn't require building a parse tree first, but it's quite a bit more complicated.