6

Prolog で DCG を使用して論理式を解析したいと考えています。

論理項はリストとして表されます。たとえば['x','&&','y']、x ∧ y結果は解析ツリーになりますand(X,Y)(以前と未割り当ての Prolog 変数です)。XY

私はそれを実装し、すべてが期待どおりに機能しますが、問題が 1 つあります。変数を
解析して実際の Prolog 変数を取得する方法と、後で真理値を割り当てる方法がわかりません。'x''y'XY

次のルールのバリエーションを試しました。

  • 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-term に直接解析するのは賢明だと思いました。

  • 入力: 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 テキストを解析すると、同じ問題が発生します。変数名と具体的な変数の間の関連付けは、トークン化中に既に確立されています。実際のパーサーはそれを処理する必要はありません。

トークン化中にこれを実行するには、基本的に 2 つの方法があります。

1moName=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 に答える