algorithm for removing left-recursion in DCG grammars

Quote:

> Hello,

> I need to write a DCG like grammar which allows left-recursive rules.

> i.e. I should be able to enter a rule like

> np(N) --> np(N1), [and], np(N2) {f(N,N1,N2)}.

> The left recursion would prevent termination so another parsing algorithm is

> required in the body of the function f. I have looked for solutions but they

> only document the possiblity of changing the grammar, not the parsing

> algorithm. Maybe a bottom-up strategy should be used? Thanks!

Indeed, bottom-up or tabular methods would address your problem.

There's a discussion of these in my book with Stu Shieber "Prolog and

Natural-Language Analysis" (CSLI, 1987), and I imagine that other books

on Prolog and NLP discuss it too.

-- F