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> 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 Seima Rao 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 627 26th Avenue San Mateo, CA 94403