Re: Best language for implementing compilers?

Very nice post!


On Sun, 10 Mar 2019 04:13:47 -0700 (PDT), Christopher F Clark
<christopher.f.clark@compiler-resources.com> wrote:


>Unless you have written a one-pass compiler, the output of your lexer/parser
>combination is usually some form of syntax tree (either a parse tree or an
>AST). That may or may not be a convenient intermediate representation (IR).
>If it's not you need to "rewrite" it into one. Usually making one of more
>passes over the tree to do so.
>
>This is where ML style pattern matching shines. You have a tree (DAG, graph,
>some sort of data structure that has links in it) and you want to modify it.
>The ML pattern match allows you to specify the shape of the tree you want to
>match and extract the relevant parts into convenient local variables. You can
>then use those variables to construct a new tree that has the parts
>reconnected (rewritten) into the shape you desire in your IR.


It also can be useful to use tree matching for code generation: the
basic idea being to map the IR onto the instructions of the target
machine (where a target "instruction" might be a sequence of native
instructions).


You create tree patterns that correspond to target "instructions",
treat those patterns as tiles and try to cover the IR tree using a
minimum "weight" of tiles [where the tile "weight" could be cycles
consumed, registers needed, energy used, etc. ... whatever is useful
for the given task].


This works with any ISA, but it is particularly useful for CISC
machines that often provide more than one way to perform the same
operation. The minimum weight tiling will correspond to an optimal
program [for some definition of "optimal"].


George

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