[antlr-interest] Non-local optimizations with treewalker?

Randall R Schulz rschulz at sonic.net
Sat Sep 15 14:39:08 PDT 2007


Sohail,

On Saturday 15 September 2007 14:01, Sohail Somani wrote:
> ...
>
> I'm not sure you entirely understood what I was trying to do. The
> idea is that computing f(x) is expensive. If the language has no
> side-effects, then calling f(x) always gives the same result.
> Therefore, if you can "match" (I'm not entirely sure that I want to
> use that term) f(x) in more than one subexpression within some
> lexical scope, then you can replace all computations of f(x) with t
> where t = f(x).

One term for saving values rather than recomputing them 
is "memoization."

I think you're looking (asking) in the wrong place. I think most of the 
people using ANTLR and other parser generators are _not_ producing 
classical compilers that turn a source language into machine code of 
some sort, efficient or otherwise. Clearly the answers you've received 
indicate that some here do have such a background, but I suspect 
they're the minority and probably those that are versed don't have the 
time to bring you along as a teacher would.

There's a huge literature on the techniques about which you're 
(implicitly) asking. The field goes back several decades, now. I 
strongly suggest you do some conventional literature search and begin 
your self-education that way.

Much of this stuff is subtle and complex, but it's not magic. Dig in and 
I'm sure you can come up to speed fairly quickly. It's far better to 
start with the accumulated knowledge (much of it, anyway) of the 
practitioners who've gone before you than it is to start from scratch 
developing the concepts!

Good luck.


> ...
>
> Sohail


Randall Schulz


More information about the antlr-interest mailing list