Синтаксический анализ переменных Пролога с помощью DCG

Я хочу проанализировать логическое выражение с помощью DCG в Прологе.

Логические термины представлены в виде списков, например ['x','&&','y'] для x ∧ y результатом должно быть дерево синтаксического анализа and(X,Y) (были X и Y неназначенные переменные Пролога).

Я реализовал это, и все работает, как ожидалось, но у меня есть одна проблема:
Я не могу понять, как анализировать переменные 'x' и 'y', чтобы получить реальные переменные Prolog X и Y для последующего присвоения значений истинности.

Я пробовал следующие варианты правил:

v(X) --> [X].:
Конечно, это не работает, возвращается только and('x','y').
Но могу ли я единообразно заменить логические переменные в этом термине на переменные Пролога? Я знаю предикат term_to_atom (который предлагается как решение аналогичной проблемы), но я не думаю, что здесь можно использовать его для достижения желаемого результата.
v(Y) --> [X], {nonvar(Y)}.:
Это действительно возвращает несвязанную переменную, но, конечно же, каждый раз новую, даже если логическая переменная ('x', 'y', ...) уже была в термине, поэтому ['X','&&','X'] оценивается как and(X,Y), что является тоже не желаемый результат.

Есть ли какое-нибудь изящное или идиоматическое решение этой проблемы?

Спасибо заранее!

РЕДАКТИРОВАТЬ:

Предпосылкой к этому вопросу является то, что я пытаюсь реализовать алгоритм DPLL на Прологе. Я подумал, что было бы разумно напрямую проанализировать логический термин в Prolog-term, чтобы упростить использование средства обратного отслеживания Prolog:

Ввод: какой-нибудь логический термин, например, T = [x,'&&',y]
Срок действия после синтаксического анализа: [G_123,'&&',G_456] (теперь с "настоящими" переменными Пролога)
Присвойте значение из {boolean (t), boolean (f)} первой несвязанной переменной в T.
упростить термин.
... повторять или возвращаться, пока не будет найдено v присвоение, так что v(T) = t или пространство поиска не будет исчерпано.

Я новичок в Prolog и, честно говоря, не мог придумать лучшего подхода. Меня очень интересуют альтернативы получше! (Так что я наполовину уверен, что это то, чего я хочу ;-) и большое спасибо за вашу поддержку до сих пор ...)

jules 18.11.2014 источник

comment

В какой момент вы действительно хотите взглянуть на X и Y? Вы настаиваете на 'x' карте X? Или вы просто хотите, чтобы все ваши 'x' ссылались на одну и ту же переменную в конечном дереве синтаксического анализа? - 18.11.2014

comment

@Boris Я отредактировал вопрос, чтобы дать больше контекста - меня не интересует имя переменной, поскольку оно всегда относится к одной и той же переменной. - jules 18.11.2014

Ответы (2)

arrow_upward
3
arrow_downward

Вы хотите связать основные термины, такие как x (не нужно писать 'x'), с неустановленными переменными. Конечно, это не чистое отношение. Так что для меня не совсем ясно, действительно ли вы этого хотите.

А где вообще вы берете список [x, &&, x]? У вас наверняка есть токенизатор какой-то. Если возможно, попробуйте связать имена переменных с переменными до фактического анализа. Если вы настаиваете на выполнении этой ассоциации во время синтаксического анализа, вам придется прописать пару переменных по всей вашей грамматике. То есть вместо чистой грамматики вроде

power(P) --> factor(F), power_r(F, P).

теперь тебе нужно будет написать

power(P, D0,D) --> factor(F, D0,D1), power_r(F, P, D1,D).
%        ^^^^                ^^^^^                 ^^^^

поскольку вы вводите контекст в грамматику, свободную от контекста.

Та же проблема возникает при разборе текста Пролога. Связь между именем переменной и конкретной переменной уже установлена во время токенизации. Фактическому парсеру не нужно иметь дело с этим.

По сути, есть два способа сделать это во время токенизации:

1mo собрать все вхождения Name=Variable в список и объединить их позже:

v(N-V, [N-V|D],D) --> [N], {maybesometest(N)}.

unify_nvs(NVs) :-
   keysort(NVs, NVs2),
   uniq(NVs2).

uniq([]).
uniq([NV|NVs]) :-
   head_eq(NVs, NV).
   uniq(NVs).

head_eq([], _).
head_eq([N-V|_],N-V).
head_eq([N1-_|_],N2-_) :-
   dif(N1,N2).

2Используйте какой-нибудь явный словарь, чтобы объединить их на ранней стадии.

Отчасти связанный с этим этим вопросом.

false 18.11.2014

comment

Большое спасибо за ваше подробное объяснение ... Я также добавил некоторую предысторию вопроса в некотором контексте; теперь я думаю, что мне нужно пересмотреть весь свой подход. - jules; 18.11.2014

arrow_upward
1
arrow_downward

Не уверен, действительно ли ты хочешь сделать то, о чем просил. Вы можете сделать это, сохранив список ассоциаций переменных, чтобы знать, когда использовать переменную повторно, а когда - новую.

Это пример парсера с жадным спуском, который анализирует выражения с помощью && и ||:

parse(Exp, Bindings, NBindings)-->
  parseLeaf(LExp, Bindings, MBindings),
  parse_cont(Exp, LExp, MBindings, NBindings).

parse_cont(Exp, LExp, Bindings, NBindings)-->
  parse_op(Op, LExp, RExp),
  {!},
  parseLeaf(RExp, Bindings, MBindings),
  parse_cont(Exp, Op, MBindings, NBindings).
parse_cont(Exp, Exp, Bindings, Bindings)-->[].

parse_op(and(LExp, RExp), LExp, RExp)--> ['&&'].
parse_op(or(LExp, RExp), LExp, RExp)--> ['||'].

parseLeaf(Y, Bindings, NBindings)-->
  [X],
  {
    (member(bind(X, Var), Bindings)-> Y-NBindings=Var-Bindings ; Y-NBindings=Var-[bind(X, Var)|Bindings])
  }.

Он анализирует выражение и возвращает также привязки переменных.

Примеры результатов:

?- phrase(parse(Exp, [], Bindings), ['x', '&&', 'y']).
Exp = and(_G683, _G696),
Bindings = [bind(y, _G696), bind(x, _G683)].

?- phrase(parse(Exp, [], Bindings), ['x', '&&', 'x']).
Exp = and(_G683, _G683),
Bindings = [bind(x, _G683)].

?- phrase(parse(Exp, [], Bindings), ['x', '&&', 'y', '&&', 'x', '||', 'z']).
Exp = or(and(and(_G839, _G852), _G839), _G879),
Bindings = [bind(z, _G879), bind(y, _G852), bind(x, _G839)].

gusbro 18.11.2014

comment

Большое спасибо, я бы хотел принять два ответа! Я также добавил немного предыстории к вопросу, чтобы поместить его в контекст. - jules; 18.11.2014

Синтаксический анализ переменных Пролога с помощью DCG

Ответы (2)

Похожие вопросы