[antlr-interest] added pattern rewriting example

[Oliver Zeigermann]

2008/11/30 Terence Parr <parrt at cs.usfca.edu>:
>
> On Nov 30, 2008, at 1:07 PM, Oliver Zeigermann wrote:
>
>> OK. I do not quite grok it. Looking at
>>
>> topdown
>>   :   ^('*' INT ^(VEC (e+=.)+)) -> ^(VEC ^('*' INT $e)+)
>>   ;
>>
>> bottomup
>>   :  ^('*' a=. b=INT {$b.int==0}?) -> $b // x*0 -> 0
>>   ;
>>
>> Why has the second to be in bottomup?
>
> x*(4*0)
>
> If you do it top down, you won't see x*0, you'll see only x*(4*0).  You will
> rplace 4*0 with 0, but then you won't see x*0.  You need to do it innnermost
> (bottomup) not outermost (topdown) to see all opportunities.
>
> You need to do
>
> 4*0 -> 0
> x*0 -> 0
>
> not
>
> 4*0 -> 0
>
> and stop.

I think I understand now.

So this would also work by repetitively traversing the tree until no
more simplificaions are possible (which would of course have a bad
performance), right?

Oliver