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!
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: