Грамматика в прологе - PullRequest
Новая
       15

Грамматика в прологе

0 голосов
/ 28 апреля 2018

Я хочу иметь возможность переводить массивы типа [int(2), sep(<), int(1), sep(-), id(N)] в условия (в этом примере [int(2) < int(1)-id(N)]) с помощью грамматики. У меня есть грамматика ниже: 

cond(_, A > B) --> expr(_,A), [sep(>)], expr(_,B).
cond(_, A < B) --> expr(_,A), [sep(<)], expr(_,B).
expr(_, int(X)) --> [int(X)].
expr(_, id(X)) --> [id(X)].
expr(_, X + Y) --> expr(_,X), [sep(+)], expr(_,Y).
expr(_, X - Y) --> expr(_,X), [sep(-)], expr(_,Y).

Что я не понимаю, так это тот факт, что если у меня есть массив: [int(2), sep(>), int(1), sep(+), id(N)] все хорошо, условие переводится правильно. Затем я делаю некоторые изменения, заменяя + на - или > на < (учтите тот факт, что в моей грамматике > это одна строка над <, так же, как + и -) и это не переводится, оно попадает в бесконечный цикл: 

Call:  (18)  ? [sep(-), id(N)]=[sep(+)|_G2290032]creep
Fail:  (18)  ? [sep(-), id(N)]=[sep(+)|_G2290032]creep

Он всегда сравнивается со строкой с sep(+). Что не так в этой грамматике?

- ИЗМЕНИТЬ добавленную трассировку 

phrase(cond(_, X), [int(2), sep(<), int(1), sep(-),id(N)]).
   Call:  (10)  ? cond(_G2313, _G2314, [int(2), sep(<), int(1), sep(-), id(_G2336)], [])creep
   Call:  (11)  ? expr(_L254, _G2482, [int(2), sep(<), int(1), sep(-), id(_G2336)], _L235)creep
   Exit:  (11)  ? expr(_L254, int(2), [int(2), sep(<), int(1), sep(-), id(_G2336)], [sep(<), int(1), sep(-), id(_G2336)])creep
   Call:  (11)  ? [sep(<), int(1), sep(-), id(_G2336)]=[sep(>)|_G2488]creep
   Fail:  (11)  ? [sep(<), int(1), sep(-), id(_G2336)]=[sep(>)|_G2488]creep
   Redo:  (11)  ? expr(_L254, _G2482, [int(2), sep(<), int(1), sep(-), id(_G2336)], _L235)creep
   Call:  (12)  ? expr(_L279, _G2485, [int(2), sep(<), int(1), sep(-), id(_G2336)], _L260)creep
   Exit:  (12)  ? expr(_L279, int(2), [int(2), sep(<), int(1), sep(-), id(_G2336)], [sep(<), int(1), sep(-), id(_G2336)])creep
   Call:  (12)  ? [sep(<), int(1), sep(-), id(_G2336)]=[sep(+)|_G2491]creep
   Fail:  (12)  ? [sep(<), int(1), sep(-), id(_G2336)]=[sep(+)|_G2491]creep
   Redo:  (12)  ? expr(_L279, _G2485, [int(2), sep(<), int(1), sep(-), id(_G2336)], _L260)creep
   Call:  (13)  ? expr(_L304, _G2488, [int(2), sep(<), int(1), sep(-), id(_G2336)], _L285)creep
   Exit:  (13)  ? expr(_L304, int(2), [int(2), sep(<), int(1), sep(-), id(_G2336)], [sep(<), int(1), sep(-), id(_G2336)])creep
   Call:  (13)  ? [sep(<), int(1), sep(-), id(_G2336)]=[sep(+)|_G2494]creep
   Fail:  (13)  ? [sep(<), int(1), sep(-), id(_G2336)]=[sep(+)|_G2494]creep
   Redo:  (13)  ? expr(_L304, _G2488, [int(2), sep(<), int(1), sep(-), id(_G2336)], _L285)creep
   Call:  (14)  ? expr(_L329, _G2491, [int(2), sep(<), int(1), sep(-), id(_G2336)], _L310)creep
   Exit:  (14)  ? expr(_L329, int(2), [int(2), sep(<), int(1), sep(-), id(_G2336)], [sep(<), int(1), sep(-), id(_G2336)])creep
   Call:  (14)  ? [sep(<), int(1), sep(-), id(_G2336)]=[sep(+)|_G2497]creep
   Fail:  (14)  ? [sep(<), int(1), sep(-), id(_G2336)]=[sep(+)|_G2497]creep
   Redo:  (14)  ? expr(_L329, _G2491, [int(2), sep(<), int(1), sep(-), id(_G2336)], _L310)creep
   Call:  (15)  ? expr(_L354, _G2494, [int(2), sep(<), int(1), sep(-), id(_G2336)], _L335)creep
   Exit:  (15)  ? expr(_L354, int(2), [int(2), sep(<), int(1), sep(-), id(_G2336)], [sep(<), int(1), sep(-), id(_G2336)])creep
   Call:  (15)  ? [sep(<), int(1), sep(-), id(_G2336)]=[sep(+)|_G2500]creep
   Fail:  (15)  ? [sep(<), int(1), sep(-), id(_G2336)]=[sep(+)|_G2500]
   ...

1 Ответ

0 голосов
/ 28 апреля 2018

Как подсказывает @TomasBy, левая рекурсия в нетерминальном выражении // 2 приводит к не завершению. В SWI-Prolog есть библиотека ( tabling ), просто импортируйте ее и объявите expr // 2 как tabled. 

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