18

Prolog で Lisp を解析するためのこの素敵なスニペットを見つけました (ここから):

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([]) --> [].

ただし表現はカットを使用。これは効率化のためだと思います。このコードをカットせずに効率的に動作するように書くことは可能ですか?

マーキュリーのソフトカット/献身的な選択を含む興味深い回答にもなります.

4

3 に答える 3

8

カットは効率のために使用されるのではなく、最初のソリューションにコミットするために使用されます（！/ 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」に同意しません。number//1とsymbolr// 1があいまいであるため、expression//1はあいまいです。Mercuryでは、決定論宣言cc_nondetを使用して、ソリューションがある場合はそれをコミットできます。

于 2011-06-15T17:08:20.587 に答える
7

ここでかなり深い問題に触れています。カットの場所に「最長の入力一致」というコメントを追加しました。しかし、あなたが実際に行ったことは、非端末に対して「最長の入力一致」を生成する最初のソリューションにコミットすることでしたが、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.
于 2011-06-15T17:02:00.840 に答える
4

Parsing Expression Grammars (PEG) で既にその場所を見つけた構造を使用できますが、DCG でも使用できます。つまり、DCG 目標の否定です。PEG では、引数付きの感嘆符 (!) が否定に使用されます。e. DCG では、DCG ゴールの否定は (\+) 演算子によって表現されます。これは、通常の Prolog 句およびクエリでの失敗として、通常の否定に既に使用されています。

では、最初に (\+) が DCG でどのように機能するかを説明しましょう。次の形式のプロダクション ルールがある場合:

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

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

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

つまり、C DCG ゴールを解析しようとしますが、実際には入力リストを消費しません。必要に応じて、これを使用してカットを置き換えることができます。これにより、もう少し宣言的な感覚が得られます。この考えを説明するために、with が ws//0 のない文法を持っていると仮定しましょう。したがって、式 //1 の元の句セットは次のようになります。

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

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

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

残念ながら、式を解析しようとする試みが 2 回行われるため、上記のバリアントはまったく効率的ではありません。最初のルールで 1 回、次に否定の 2 番目のルールでもう一度。ただし、次のようにして、式の先頭の否定のみをチェックすることもできます。

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

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

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

式の最初の記号をチェックする否定バージョンでは失敗するはずです。カットありとカットなしのバージョンでは、結果として空のリストで成功します。

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

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

よろしくお願いします

于 2011-06-21T19:52:09.153 に答える