prolog - 使用 DCG 解析 Prolog 变量

Question

我想在 Prolog 中使用 DCG 解析逻辑表达式。

逻辑术语表示为列表，例如['x','&&','y'] for x ∧ y 结果应该是解析树 and(X,Y)(X 和 Y 是未分配的 Prolog 变量)。

我实现了它，一切都按预期工作，但我有一个问题:
我不知道如何解析变量 'x' 和 'y' 以获取真正的 Prolog 变量 X 和 Y 以便稍后分配真值。

我尝试了以下规则变体:

v(X) --> [X].:
这当然不起作用，它只返回 and('x','y') 。
但是我可以用 Prolog 变量统一替换这个术语中的逻辑变量吗？我知道谓词 term_to_atom (它被提议作为 similar problem 的解决方案)，但我认为它不能在这里使用来达到预期的结果。

v(Y) --> [X], {nonvar(Y)}.:
这确实会返回一个未绑定(bind)的变量，但每次都会返回一个新变量，即使逻辑变量 ('x','y',...) 已经在术语中，所以['X','&&','X'] 被评估为 and(X,Y) ，这也不是所需的结果。

这个问题有什么优雅或惯用的解决方案吗？

提前谢谢了!

编辑:

这个问题的背景是我正在尝试在 Prolog 中实现 DPLL-algorithm 。我认为将逻辑术语直接解析为 Prolog 术语以方便使用 Prolog 回溯工具会很聪明:

输入:一些逻辑术语，例如 T = [x,'&&',y]

解析后的术语:[G_123,'&&',G_456](现在具有“真实”Prolog 变量)

将 { boolean(t), boolean(f) } 中的值赋给 T 中的第一个未绑定(bind)变量。

简化术语。

...重复或回溯，直到找到分配v，以便v(T) = t或搜索空间耗尽。

我对 Prolog 很陌生，老实说，我想不出更好的方法。我对更好的选择非常感兴趣! (所以我有点半信半疑，这就是我想要的 ;-) 非常感谢你到目前为止的支持......)

Answer 1

您想关联基本术语，如 x (无需写 'x' )带有未实例化的变量。当然，这并不构成纯粹的关系。所以我不清楚你是否真的想要这个。

你从哪里得到列表[x, &&, x]首先？你可能有某种标记器。如果可能，请尝试在实际解析之前将变量名称与变量相关联。如果您坚持在解析期间执行该关联，您将不得不在整个语法中使用一对变量。也就是说，而不是 clean grammar像

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

你现在必须写

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

因为您正在将上下文引入其他上下文无关的语法中。

在解析 Prolog 文本时，也会出现同样的问题。变量名称和具体变量之间的关联在标记化期间已经建立。实际的解析器不必处理它。

在标记化期间基本上有两种方法可以执行此操作:

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).

2do 使用一些明确的字典来尽早合并它们。

有点相关的是this question .