カットせずにプロログを解析する？

StackOverflow https://stackoverflow.com/questions/6358556

質問

私はプロログのリスプを解析するためのこの素敵なスニペットを見つけました（から ここ):

ws --> [W], { code_type(W, space) }, ws.
ws --> [].

parse(String, Expr) :- phrase(expressions(Expr), String).

expressions([E|Es]) -->
    ws, expression(E), ws,
    !, % single solution: longest input match
    expressions(Es).
expressions([]) --> [].

% A number N is represented as n(N), a symbol S as s(S).

expression(s(A))         --> symbol(Cs), { atom_codes(A, Cs) }.
expression(n(N))         --> number(Cs), { number_codes(N, Cs) }.
expression(List)         --> "(", expressions(List), ")".
expression([s(quote),Q]) --> "'", expression(Q).

number([D|Ds]) --> digit(D), number(Ds).
number([D])    --> digit(D).

digit(D) --> [D], { code_type(D, digit) }.

symbol([A|As]) -->
    [A],
    { memberchk(A, "+/-*><=") ; code_type(A, alpha) },
    symbolr(As).

symbolr([A|As]) -->
    [A],
    { memberchk(A, "+/-*><=") ; code_type(A, alnum) },
    symbolr(As).
symbolr([]) --> [].

ただし、式ではカットを使用します。これは効率のためだと思います。カットなしで効率的に機能するように、このコードを書くことは可能ですか？

また、Mercuryのソフトカット /コミットされた選択を含む興味のある回答にもなります。

役に立ちましたか？

解決

カットは効率に使用されるのではなく、最初のソリューションにコミットするために使用されます（！/0の横にあるコメント：「単一のソリューション：最長入力マッチ」を参照）。 ！/0にコメントすると、たとえば次のようになります。

?- parse("abc", E).
E = [s(abc)] ;
E = [s(ab), s(c)] ;
E = [s(a), s(bc)] ;
E = [s(a), s(b), s(c)] ;
false.

そのような場合には、トークンを形成する最も長い文字のシーケンスで構成される最初の解決策のみが望まれていることは明らかです。したがって、上記の例を考えると、私は「false」に同意しません：式// 1は曖昧です。水銀では、決定論宣言CC_NONDETを使用して、もしあれば解決策にコミットすることができます。

他のヒント

ここでは非常に深い問題に触れています。カットの場所で、「最長の入力マッチ」というコメントを追加しました。しかし、あなたが実際にしたことは、非ターミナルの「最も長い入力マッチ」を生成する最初のソリューションにコミットすることでした ws//0 しかし、必ずしもそうではありません expression//1.

多くのプログラミング言語は、最長の入力マッチに基づいてトークンを定義しています。これはしばしば非常に奇妙な効果につながります。たとえば、数字の後に多くのプログラミング言語の手紙が続く場合があります。これは、Pascal、Haskell、Prolog、その他多くの言語の場合です。例えば if a>2then 1 else 2 有効なHaskellです。有効なプロログ： X is 2mod 3.

それを考えると、そのような機能にまったく依存しないように、プログラミング言語を定義することをお勧めします。

もちろん、文法を最適化したいと思います。しかし、そもそも明確な定義から始めることをお勧めします。

効率（および純度）について：

eos([],[]).

nows --> call(eos).
nows, [W] --> [W], { code_type(W, nospace) }.

ws --> nows.
ws --> [W], {code_type(W, space)}, ws.

解析表現文法（PEG）ですでにその場所を見つけたコンストラクトを使用できますが、DCGでも利用できます。つまり、DCG目標の否定。ペグでは、感嘆符（！）が否定に使用されます。 e。 DCGでは、DCG目標の否定は（+）演算子によって表されます。これは、通常のプロログ条項とクエリの失敗として通常の否定にすでに使用されています。

したがって、最初にDCGで（+）がどのように機能するかを説明しましょう。フォームの制作ルールがある場合：

 A --> B, \+C, D.

次に、次のように翻訳されます。

 A(I,O) :- B(I,X), \+ C(X,_), D(X,O).

つまり、C DCGの目標を解析する試みが行われますが、実際に入力リストを消費することはありません。これは、必要に応じてカットを交換するために使用でき、もう少し宣言的な感覚を与えます。アイデアを説明するために、WS // 0のない文法があると仮定できます。したがって、式// 1の元の句セットは次のとおりです。

expressions([E|Es]) --> expression(E), !, expressions(Es).
expressions([]) --> [].

否定では、これを次のカットレス形式に変えることができます。

expressions([E|Es]) --> expression(E), expressions(Es).
expressions([]) --> \+ expression(_).

残念ながら、式を解析しようとする試みが2回行われるため、上記のバリアントは非常に効率的ではありません。最初のルールに一度、そして否定の2番目のルールに再び。ただし、次のことを行い、表現の始まりの否定のみを確認できます。

expressions([E|Es]) --> expression(E), expressions(Es).
expressions([]) --> \+ symbol(_), \+ number(_), \+ "(", \+ "'".

否定を試してみると、比較的厳格なパーサーが得られることがわかります。これは、入力の最大プレフィックスを解析しようとする場合、およびいくつかのエラーを検出する場合に重要です。それを試してみてください：

?- phrase(expressions(X),"'",Y).

式の最初のシンボルをチェックする否定バージョンで失敗を取得する必要があります。カットとカットフリー版では、結果として空のリストで成功します。

ただし、エラーを別の方法で処理することもできます。エラーの例を作成して、否定バージョンがどのように機能するかを少し強調するだけです。

他の設定、たとえばCykパーサーでは、否定を非常に効率的にすることができ、すでにチャートに配置されている情報を使用できます。

よろしくお願いします

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top