Re: Alternatives to Syntax Trees

Seima Rao <seimarao@gmail.com> wrote:
+---------------
| Are there alternatives to syntax trees (i.e. the tree data
| structure) when compiling via yacc or yacc like tools ?
|
| [There's quadruples, doubly linked lists of data structures. They
| make it easier to rearrange code, but harder to do just about anything
| else. There's also DAGs, which are trees that can have shared subtrees,
| useful when you're doing common subexpressions or tail merging. -John]
+---------------


CMU Common Lisp (CMUCL) [circa 1990ff] used Implicit Continuation
Representation (ICR) as its first intermediate representation
(a.k.a. "IR1"). The key point w.r.t. Seima's question is that
IR1 is "represented as a flow-graph rather than a syntax tree":


        https://common-lisp.net/project/cmucl/doc/CMUCL-design.pdf
        Design of CMU Common Lisp
        Robert A. MacLachlan (ed)
        January 15, 2003
        ...
        Chapter 3
        Compiler Overview
        ...
        Two major intermediate representations are used in the compiler:


        * The Implicit Continuation Representation (ICR) represents
            the lisp-level semantics of the source code during the
            initial phases. Partial evaluation and semantic analysis are
            done on this representation. ICR is roughly equivalent to a
            subset of Common Lisp, but is represented as a flow-graph
            rather than a syntax tree. Phases which only manipulate ICR
            comprise the front end. It would be possible to use a
            different back end such as one that directly generated code
            for a stack machine.


        * The Virtual Machine Representation (VMR) [a.k.a. "IR2"]
            represents the implementation of the source code on a
            virtual machine. ...[trimmed]...


        Each phase is briefly described here. The phases from "local
        call analysis" to "constraint propagation" all interact; for
        maximum optimization, they are generally repeated until nothing
        new is discovered.
        ...[trimmed]...




-Rob


-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <http://rpw3.org/>
San Mateo, CA 94403

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