Stack limit (0.2Gb) exceeded...Probable infinite recursion (cycle):

Question

Pretty new to Prolog, but I'm trying to implement a context-free grammar and I'm having an issue passing a test case with the rules I have.

I've tried changing the order of my rules to seem more logically correct, but I can't seem to get consistent correct outputs and I continue to get the same stack error. I think it has something to do with vp --> vp, np. being recursive, but if that's the case, then why doesn't np --> np, pp. give me an error as well? My code is below:

:- use_module(library(tabling)).
:- table s/2.

s --> np, vp.
np --> det, n.
np --> np, pp.
vp --> vp, pp.
vp --> v, np.
pp --> p, np.

det --> [the].
n --> [cop].
n --> [criminal].
n --> [street].
v --> [chased].

p --> [in].
p --> [by].

Asking this to the query ideally should return true:

$- s([the,cop,chased,the,criminal], []).

And asking this should return false:

$- s([the, cop, the, criminal, chased], []).

I've tried both and they just give me the same error:

Stack limit (0.2Gb) exceeded
  Stack sizes: local: 0.2Gb, global: 22Kb, trail: 5Kb
  Stack depth: 1,561,893, last-call: 0%, Choice points: 1,561,869
  Probable infinite recursion (cycle):
    [1,561,893] vp([length:3], _1424)
    [1,561,892] vp([length:3], _1456)

Any feedback is appreciated!

Answer 1

The problem is that you have constructed a left recursive grammar. Indeed if we look at the rules you defined, we see:

:- use_module(library(tabling)).
:- table s/2.

s --> np, vp.
np --> det, n.
np --> np, pp.
vp --> vp, pp.
vp --> v, np.
pp --> p, np.

det --> [the].
n --> [cop].
n --> [criminal].
n --> [street].
v --> [chased].

p --> [in].
p --> [by].

Now based on how Prolog implements predicates, it can not work with such left recursive grammar, since if you call np/2, it will first call np/2, and hence we never get out of the "loop" (until the call stack overflows).

We can however use tabling here, like you somehow did with s/2, which is not necessary, since there is no left-recursive path in s that yields (directly or indirectly) s --> s, .... We need to table np/2 and vp/2, like:

:- use_module(library(tabling)).
:- table np/2.
:- table vp/2.

s --> np, vp.
np --> det, n.
np --> np, pp.
vp --> vp, pp.
vp --> v, np.
pp --> p, np.

det --> [the].
n --> [cop].
n --> [criminal].
n --> [street].
v --> [chased].

p --> [in].
p --> [by].

We then indeed can obtain the expected results:

?- s([the,cop,chased,the,criminal], []).
true.

?- s([the, cop, the, criminal, chased], []).
false.