Использование DCG с фразой / 2 в качестве генератора :
operator --> [+].
operator --> [-].
operator --> [*].
operator --> [/].
expr_trinary -->
[1],
operator,
[2],
operator,
[3].
expr(E) :-
phrase(expr_trinary,Expr_trinary),
atomics_to_string(Expr_trinary,E).
Пример выполнения:
?- expr(E).
E = "1+2+3" ;
E = "1+2-3" ;
E = "1+2*3" ;
E = "1+2/3" ;
E = "1-2+3" ;
E = "1-2-3" ;
E = "1-2*3" ;
E = "1-2/3" ;
E = "1*2+3" ;
E = "1*2-3" ;
E = "1*2*3" ;
E = "1*2/3" ;
E = "1/2+3" ;
E = "1/2-3" ;
E = "1/2*3" ;
E = "1/2/3".
Поскольку ваш вопрос работает со списком, способ увидеть DCG в качестве обработки списка - использовать перечисление / 1 для преобразования его в обычный пролог.
?- listing(operator).
operator([+|A], A).
operator([-|A], A).
operator([*|A], A).
operator([/|A], A).
true.
?- listing(expr_trinary).
expr_trinary([1|A], B) :-
operator(A, C),
C=[2|D],
operator(D, E),
E=[3|B].
true.
, который можетназываться обычным прологом.
?- expr_trinary(E,[]).
E = [1, +, 2, +, 3] ;
E = [1, +, 2, -, 3] ;
E = [1, +, 2, *, 3] ;
E = [1, +, 2, /, 3] ;
E = [1, -, 2, +, 3] ;
E = [1, -, 2, -, 3] ;
E = [1, -, 2, *, 3] ;
E = [1, -, 2, /, 3] ;
E = [1, *, 2, +, 3] ;
E = [1, *, 2, -, 3] ;
E = [1, *, 2, *, 3] ;
E = [1, *, 2, /, 3] ;
E = [1, /, 2, +, 3] ;
E = [1, /, 2, -, 3] ;
E = [1, /, 2, *, 3] ;
E = [1, /, 2, /, 3].
Расширенное решение с использованием числа (1,2,3) в любой позиции:
number --> [1].
number --> [2].
number --> [3].
operator --> [+].
operator --> [-].
operator --> [*].
operator --> [/].
expr_trinary -->
number,
operator,
number,
operator,
number.
expr(E) :-
phrase(expr_trinary,Expr_trinary),
atomics_to_string(Expr_trinary,E).
Пример выполнения:
?- expr(E).
E = "1+1+1" ;
E = "1+1+2" ;
E = "1+1+3" ;
E = "1+1-1" ;
E = "1+1-2" ;
E = "1+1-3" ;
...
Объяснение того, как генерировать с помощью DCG, см. В этом разделе Amzi : Создание со списками различий
В комментариях для другого ответаВы писали:
это не работа более чем на 3 элемента?Можете ли вы разработать его для большего количества элементов?
По мере увеличения числа элементов увеличивается комбинаторный взрыв .
Чтобы подавить комбинаторный взрыв, напримерЗапустите это будет использовать только два числа (1,2) и два оператора (+, *), вы можете добавить больше по своему вкусу.
number(1) --> [1].
number(2) --> [2].
operator(+) --> [+].
operator(*) --> [*].
expr(N) --> number(N).
expr((E1,Op,E2)) --> operator(Op),expr(E1),expr(E2).
expr(E) :-
length(Expr,_),
phrase(expr(E),Expr).
Обратите внимание, что это использует длина / 2 за итеративное углубление .В основном length/2 генерирует список увеличивающейся длины, а затем фразу / 2 приходит с ответами, которые имеют такую длину.
?- length(Ls,N).
Ls = [],
N = 0 ;
Ls = [_870],
N = 1 ;
Ls = [_870, _876],
N = 2 ;
Ls = [_870, _876, _882],
N = 3 ;
Ls = [_870, _876, _882, _888],
N = 4 ;
Ls = [_870, _876, _882, _888, _894],
N = 5 ;
Ls = [_870, _876, _882, _888, _894, _900],
N = 6
...
Так что генератор работает, как и ожидалось, нормальный BNF и DCG, например,
<expr> ::= <expr> <op> <expr>
expr((E1,Op,E2)) --> expr(E1),operator(Op),expr(E2).
, то есть прямая левая рекурсия , преобразуется в этот
<expr> ::= <op> <expr> <expr>
expr((E1,Op,E2)) --> operator(Op),expr(E1),expr(E2).
Пример выполнения:
?- expr(E).
E = 1 ;
E = 2 ;
E = (1, (+), 1) ;
E = (1, (+), 2) ;
E = (2, (+), 1) ;
E = (2, (+), 2) ;
E = (1, (*), 1) ;
E = (1, (*), 2) ;
E = (2, (*), 1) ;
E = (2, (*), 2) ;
E = (1, (+), 1, (+), 1) ;
...
E = (1, (+), 2, (+), 2, (*), 1) ;
E = (1, (+), 2, (+), 2, (*), 2) ;
E = (1, (+), (1, (+), 1), (+), 1) ;
E = (1, (+), (1, (+), 1), (+), 2) ;
E = (1, (+), (1, (+), 2), (+), 1) ;
...