[antlr-interest] RE: antlr-interest Digest, Vol 14, Issue 17

[Nigel Sheridan-Smith]

> 
> Message: 4
> Date: Wed, 11 Jan 2006 12:19:02 -0500
> From: Andy Tripp <antlr at jazillian.com>
> Subject: [antlr-interest] Re: Source-driven v. Target-driven xforms
> 	(was Re: New article on StringTemplates and Treewalkers)
> To: Gregg Reynolds <gar at arabink.com>
> Cc: antlr-interest at antlr.org
> Message-ID: <43C53E06.4090700 at jazillian.com>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
> 
> On one hand, when Terence says "your pattern matcher may never
> terminate", I can't help but assume he's right
> and I just haven't yet noticed some fatal flaw. But on the other hand,
> an expert in computation complexity will
> tell you "your traveling salesman algorithm may take forever", and you
> know right away that he's talking
> about *in theory*, but you know full well that it works just fine *in
> practice*.
> 


The non-termination of rule-based algorithms is fairly well established,
particularly if you are applying back-tracking or goal-searching.

Pick up a book on language design and check out the description of Prolog -
particular combinations of rules and facts in particular orders will not
terminate. E.g. Ghezzi and Jazayeri "Programming Language Concepts" 1987 p
304 states "Both the order in which facts and rules are listed ... and the
order in which subgoals are listed are significant. There are programs that
behaviour correctly ... but enter an infinite loop or generate a run-time
error if the order changes".

So the order that you apply the rules and the size of the rule-set will
affect the efficiency of the algorithm and whether it terminates. If you are
applying those rules sequentially, and they are not cyclical, then you might
be okay as long as you have a good idea of when to terminate the rule
search. Prolog has the "cut" operator to limit back-tracking and increase
efficiency. Sebesta "Concepts of programming languages" 1999 p 629 has a
good example of infinite recursion in Prolog.

It seems that Andy's approach gives more granularity of control over
particular pattern matching and manipulation - things that would have to be
coded as an action in an ANTLR tree-walker. However, the disadvantage is
that it requires somebody to write such a rule engine to process the 200 or
so rules that you have written. It does sound like it would be more
intuitive to write these rules in certain circumstances, depending on what
patterns were acceptable.

Nigel

--
Nigel Sheridan-Smith
PhD research student

Faculty of Engineering
University of Technology, Sydney
Phone: 02 9514 7946
Fax: 02 9514 2435