Scryer-prolog: Tabled DCG unexpectedly fails

[triska]

With the following definitions:

:- use_module(library(dcgs)).
:- use_module(library(tabling)).

:- table expr//0.

expr --> "1".
expr --> expr, "+", expr.

I get:

?- phrase(expr, "1+1+1").
false.

Expected: true.

[mthom]

This case is tricky. The tabling library indexes answer tries using "variants" of queries, which it attaches to unique table identifiers. The variant of your query is expr("1+1+1", []), but the variant of the first internal expr call is expr("1+1+1", '$VAR'(0)). The tabling library doesn't recognize that expr("1+1+1", '$VAR'(0)) can unify with expr("1+1+1", []), and should therefore be tried as an answer source.

I agree, this query should succeed. I will try to generalize the library accordingly.

[triska]

Thank you for looking into this! This feature is very important for writing parsers with left-recursion. Combining tabling with DCGs in this way yields a parsing strategy that is called packrat parsing.

Could it be a workable solution to store variants using Prolog variables, such as expr("1+1+1", X), and then to use subsumes_term/2 or a variant check?

This would use Prolog's built-in mechanisms to detect variants.

[mthom]

Fixed. I was totally wrong about variants being the culprit.

[triska]

Very nice, thank you a lot, this is truly awesome!