4 ms·

every language gets parsed, turned into an AST (Abstract Syntax Tree), and then compiled or interpreted This is one of the most widespread misconceptions about

by mojuba 18y ago

every language gets parsed, turned into an AST (Abstract Syntax Tree), and then compiled or interpreted This is one of the most widespread misconceptions about compilers. 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.

jules 18y ago
Building an AST will make your job MUCH easier if you want to do any kind of transformation/optimization.
- mojuba 18y ago
  No, it will not make anything easier, except will just bloat the compiler and slow down the whole process. All kinds of optimizations you probably mean are possible at the level of intermediate/pseudo code, and should be done there together with the other optimization techniques. We can look at specific examples if you wish.
  - eru 18y ago
    Depends on your definition of intermediate code, doesn't it?
    - mojuba 18y ago
      Usually a stack-based language, very close to assembly with a lot of simplifications, e.g. no registers. Because of these simplifications, intermediate code is easier to optimize and to generate native code from.
      - eru 18y ago
        I'd extend the definition to include things like GRIN code. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.3918 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.3...
  - ntoshev 18y ago
    Intermediate code will obfuscate code's intent. Why require from the optimizer to reverse-engineer what you meant from a description at a different (lower) level of abstraction?
    - mojuba 18y ago
      On the philosophical level, "code's intent" is to run on a machine using machine language. Practically speaking, I've never seen any problem that couldn't be solved by analyzing intermediate code.
  - jules 18y ago
    Interesting. Do you have pointers to any papers/implementations of optimizing compilers without abstract syntax trees. Also, are you still able to implement optimizations with the same effort? I'd gladly trade 10x longer compile time for 10% faster execution time. > We can look at specific examples if you wish. Common Subexpression Elimination, for example. Not just syntactically equal expressions but also cases like this: a1 = b + c a2 = c + b // eliminated And how do you do loop fusion & interchange? Edit: I now realise that we may be talking about different abstract syntax trees. I thought that you meant no intermediate data structures. But you probably meant that you don't need a parse tree, you can translate to the intermediate language directly from the source. If that's the case then here's another challenge: how do you produce error messages for type errors?
plinkplonk 18y ago
"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.
mattknox 18y ago
Why do you think it's so common? I mean, as a lisp/forth guy I can certainly buy the idea that everyone does a stupid thing for a long time, so I could understand if there wasn't a reason, but surely some kinds of high-level optimization are easier if your code has a tree structure, no?

by mojuba 18y ago

jules 18y ago

Building an AST will make your job MUCH easier if you want to do any kind of transformation/optimization.

mojuba 18y ago
No, it will not make anything easier, except will just bloat the compiler and slow down the whole process. All kinds of optimizations you probably mean are possible at the level of intermediate/pseudo code, and should be done there together with the other optimization techniques. We can look at specific examples if you wish.
- eru 18y ago
  Depends on your definition of intermediate code, doesn't it?
  - mojuba 18y ago
    Usually a stack-based language, very close to assembly with a lot of simplifications, e.g. no registers. Because of these simplifications, intermediate code is easier to optimize and to generate native code from.
    - eru 18y ago
      I'd extend the definition to include things like GRIN code. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.3918 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.3...
- ntoshev 18y ago
  Intermediate code will obfuscate code's intent. Why require from the optimizer to reverse-engineer what you meant from a description at a different (lower) level of abstraction?
  - mojuba 18y ago
    On the philosophical level, "code's intent" is to run on a machine using machine language. Practically speaking, I've never seen any problem that couldn't be solved by analyzing intermediate code.
- jules 18y ago
  Interesting. Do you have pointers to any papers/implementations of optimizing compilers without abstract syntax trees. Also, are you still able to implement optimizations with the same effort? I'd gladly trade 10x longer compile time for 10% faster execution time. > We can look at specific examples if you wish. Common Subexpression Elimination, for example. Not just syntactically equal expressions but also cases like this: a1 = b + c a2 = c + b // eliminated And how do you do loop fusion & interchange? Edit: I now realise that we may be talking about different abstract syntax trees. I thought that you meant no intermediate data structures. But you probably meant that you don't need a parse tree, you can translate to the intermediate language directly from the source. If that's the case then here's another challenge: how do you produce error messages for type errors?

plinkplonk 18y ago

"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.

mattknox 18y ago

Why do you think it's so common? I mean, as a lisp/forth guy I can certainly buy the idea that everyone does a stupid thing for a long time, so I could understand if there wasn't a reason, but surely some kinds of high-level optimization are easier if your code has a tree structure, no?