Prolog DCG: Match different symbols on a chain

Question

I'm trying to match some sentences (e.g. 001 [0,0,1], (1+(1/0)) ['(',1,+,'(',1,/,0,')',')'], and so on.

I've made myself following small DCG.

g3 --> s3.
s3 --> e3.

e3 --> eAdd.
e3 --> eMin.
e3 --> eMul.
e3 --> eDiv.
e3 --> n3.

eAdd --> ['('],e3,['+'],e3,[')'].
eMin --> ['('],e3,['-'],e3,[')'].
eMul --> ['('],e3,['*'],e3,[')'].
eDiv --> ['('],e3,['/'],e3,[')'].


n3 --> d3.
n3 --> n3,d3.
d3 --> [0].
d3 --> [1].

Now my problem is, it won't match with sentences using -,* or / but it works for recursive sentences using only +.

E.g:

phrase(g3,['(',1,'+','(',1,'+',1,')',')']).

Will work, but

phrase(g3,['(',1,'+','(',1,'/',1,')',')']).

Won't work.

Any help would be appreciated, thanks!

false · Answer 1 · 2022-08-11T18:38:13.027

First of all, whenever you are using DCGs, consider to

:- set_prolog_flag(double_quotes, chars).

This permits to use a much more readable syntax. Here are the rules and queries that change due to this convention.

:- set_prolog_flag(double_quotes, chars).

eAdd --> "(", e3, "+", e3, ")".
eMin --> "(", e3, "-", e3, ")".
eMul --> "(", e3, "*", e3, ")".
eDiv --> "(", e3, "/", e3, ")".

d3 --> "0".
d3 --> "1".

?- phrase(g3,"(1+(1+1))").

?- phrase(g3,"(1+(1/1))").

Note that already your first query has a problem, even if it succeeds. This can be easily seen on the toplevel:

?- phrase(g3,"(1+(1+1))").
   true
;  resource_error(_). % ERROR: Out of local stack

So the toplevel insisted that there is something else apart from the actual success. To narrow this down in a systematic manner I will use a failure-slice which adds false to regular goals and {false} within the grammar.

:- set_prolog_flag(double_quotes, chars).

g3 --> s3, {false}.

s3 --> e3, {false}.

e3 --> {false}, eAdd.
e3 --> {false}, eMin.
e3 --> {false}, eMul.
e3 --> {false}, eDiv.
e3 --> n3, {false}.

n3 --> {false}, d3.
n3 --> n3, {false}, d3.

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

Because this tiny fragment loops, the entire program loops, too. Note that + is no longer part of the program! The problem had nothing to do with + at all.

score 4 · Accepted Answer · answered Aug 25 '17 at 11:55

Your problem is due to the rule

n3 --> n3,d3.

This is a so-called left recursive rule. It says that to match an n3, you must first match an n3, for which you must first match an n3, for which you must first, etc., and this never terminates.

Basically, you want every recursive grammar rule to first match some nonterminals before performing a recursive call. (Similarly, in the bodies of "normal" Prolog predicates, you should have other goals before any recursive call.)

If you change this rule to the right-recursive variant

n3 --> d3,n3.

your grammar becomes well-behaved:

?- phrase(g3,['(',1,'+','(',1,'+',1,')',')']).
true ;
false.

?- phrase(g3,['(',1,'+','(',1,'/',1,')',')']).
true ;
false.

?- length(L, 6), phrase(g3, L).
L = ['(', 0, +, 0, 0, ')'] ;
L = ['(', 0, +, 0, 1, ')'] ;
L = ['(', 0, +, 1, 0, ')'] ;
L = ['(', 0, +, 1, 1, ')'] ;
L = ['(', 1, +, 0, 0, ')'] ;
L = ['(', 1, +, 0, 1, ')'] ;
L = ['(', 1, +, 1, 0, ')'] ;
L = ['(', 1, +, 1, 1, ')'] ;

etc.

Here are a few old questions about left recursion in DCGs that might provide additional helpful information:

DCG and left recursion

Removing left recursion in DCG - Prolog

Removing left recursion grammar using DCG

Prolog DCG: Match different symbols on a chain

2 Answers2