Re: RM and abstract syntax trees

From: Marshall <>
Date: Thu, 01 Nov 2007 16:53:25 -0000
Message-ID: <>

On Nov 1, 8:04 am, paul c <> wrote:
> David BL wrote:
> > In the following I compare different techniques for representing an
> > Abstract Syntax Tree (AST), concluding that RM is poorly suited.
> > ...
> I could just as well say that your choice of application is poorly suited.
> From Wikepedia:
> "In computing, it is used in a parser as an intermediate between a parse
> tree and a data structure"
> To me, trying this is reminiscent of EAV attempts, ie., using the RM to
> give an "intermediate" implementation. Apart from "jobs for the boys",
> why would one want to? Surely the application here is the manipulation
> of the parse tree, not the AST.

Well, I'd have to disagree. Syntax is largely to help the human. Once your compiler reads in the program text, it will really "prefer" (if I may anthropomorphize a bit) to work on the minimal data structure it can; this is the AST.

The are applications where one wants to manipulate the parse tree directly, such as when making source-to-source transformations. Like when your IDE has the ability to rename a variable.

But much of what a compiler does, in analysis and optimization and code generation, is done against the AST.

My long term hypothesis is that there actually exists an idiom to work with ASTs in the RM that is about as good as any other way, but we just haven't identified it yet. I have this problem on my queue of problems that I wish to look in to in detail. Whether I'll ever get there is an open question.

Marshall Received on Thu Nov 01 2007 - 17:53:25 CET

Original text of this message