algorithm for removing left-recursion in DCG grammars 
Author Message
 algorithm for removing left-recursion in DCG grammars

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!



Wed, 14 May 2003 03:00:00 GMT  
 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



Thu, 15 May 2003 03:00:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Removing Left-Recursion from Definite Clause Grammars

2. DCG Grammar in Prolog

3. computations in DCG grammars

4. Operator precedence in DCG grammars

5. DCG Grammar for C

6. DCG-style grammars in Lisp?

7. Recursion in Python grammar

8. Left-Recursion

9. RECURSION RECURSION RECURSION ... AAARRGGHHHH

10. SMASHING A FIELD (remove spaces; left justify)

11. Removing Recursion

12. Algorithm To Remove Redundant Elements From An Array

 

 
Powered by phpBB® Forum Software