🚀 go-pugleaf

In <3164@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A.
O'Keefe) presents a Datalog example of a context-free grammar which
includes mutual recursions and asks:

>(If someone who is really at home with magic sets would care to explain
>what the magic sets method would do with this example I would be grateful.)

Not being an expert in magic sets, and at the risk of
oversimplifying, I will try to give my intuitions about magic sets
and grammars. 

The result of executing the ``Magic set''-transformed program
bottom-up (semi-naive) is essentially the same as Extension Table (or
OLDT) evaluation. (So one might think of Magic-sets as a
``compilation'' technique for extension tables.) And Extension Table
evaluation is essentially the same as Earley Deduction. And Earley
Deduction on Datalog grammars as Richard presented is Earley's
context-free recognition algorithm. So by transitivity of
``essentially the same as'', magic sets on Datalog grammars is Earley
recognition. Evidence for the validity of this claim is Raghu
Ramakrishnan's comment that under magic sets, left-recursion is
linear and right-recursion is quadratic, exactly as it is in Earley
recognition. 

David S. Warren
 warren@sbcs.sunysb.edu