6

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

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

我实现了它，一切都按预期工作，但我有一个问题：
我无法弄清楚如何解析变量'x'并'y'获取真正的 Prolog 变量X以及Y以后分配真值。

我尝试了以下规则变体：

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

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

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

提前谢谢了！

编辑：

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

  • 输入：一些逻辑项，例如 T =[x,'&&',y]
  • 解析后的术语：（[G_123,'&&',G_456]现在具有“真实”的 Prolog 变量）
  • 将 { boolean(t), boolean(f) } 中的值赋给 T 中的第一个未绑定变量。
  • 简化术语。
  • ...重复或回溯，直到v找到分配，v(T) = t或者搜索空间被耗尽。

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

4

2 回答 2

3

您希望将诸如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).
%        ^^^^                ^^^^^                 ^^^^

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

在解析 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 使用一些明确的字典来尽早合并它们。

有点相关的是这个问题。

于 2014-11-18T14:54:10.823 回答
1

不确定你是否真的想做你所要求的。您可以通过保留变量关联列表来做到这一点，以便您知道何时重用变量以及何时使用新变量。

这是一个贪婪下降解析器的例子，它将用&&and解析表达式||：

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)].
于 2014-11-18T15:04:41.277 回答