Re: Alternatives to Syntax Trees

Path	csiph.com!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder1.iad1.usenetexpress.com!216.166.98.84.MISMATCH!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From	rpw3@rpw3.org (Rob Warnock)
Newsgroups	comp.compilers
Subject	Re: Alternatives to Syntax Trees
Date	Mon, 16 Jan 2017 12:12:01 -0000 (UTC)
Organization	Rob Warnock, Consulting Systems Architect
Lines	53
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<17-01-005@comp.compilers> (permalink)
References	<17-01-002@comp.compilers>
Injection-Info	miucha.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="33108"; mail-complaints-to="abuse@iecc.com"
Keywords	parse, optimize, Lisp
Posted-Date	16 Jan 2017 09:23:04 EST
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
Xref	csiph.com comp.compilers:1811

Show key headers only | View raw

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

Thread

Alternatives to Syntax Trees Seima Rao <seimarao@gmail.com> - 2017-01-15 16:52 -0500
  Re: Alternatives to Syntax Trees Kaz Kylheku <221-501-9011@kylheku.com> - 2017-01-15 22:31 +0000
  Re: Alternatives to Syntax Trees George Neuner <gneuner2@comcast.net> - 2017-01-16 06:11 -0500
  Re: Alternatives to Syntax Trees rpw3@rpw3.org (Rob Warnock) - 2017-01-16 12:12 +0000
    Alternatives to Syntax Trees Seima Rao <seimarao@gmail.com> - 2017-01-17 14:16 +0530
      Re: Alternatives to Syntax Trees Kaz Kylheku <221-501-9011@kylheku.com> - 2017-01-17 22:39 +0000
      Re: Alternatives to Syntax Trees George Neuner <gneuner2@comcast.net> - 2017-01-17 22:08 -0500

csiph-web