4

トークンのリストの形式で数式を取り込んで T を見つける parse(Tkns, T) を記述し、演算の順序と結合性を考慮して、抽象構文を表すステートメントを返す必要があります。

例えば、

?- parse( [ num(3), plus, num(2), star, num(1) ], T ).

T = add(integer(3), multiply(integer(2), integer(1))) ;
No

+ と * を次のように実装しようとしました

parse([num(X)], integer(X)).
parse(Tkns, T) :-
  (  append(E1, [plus|E2], Tkns),
     parse(E1, T1),
     parse(E2, T2),
     T = add(T1,T2)
  ;  append(E1, [star|E2], Tkns),
     parse(E1, T1),
     parse(E2, T2),
     T = multiply(T1,T2)
  ).

これは正しい答えを見つけますが、結合性や操作の順序に従わない答えも返します。

元）

parse( [ num(3), plus, num(2), star, num(1) ], T ).

も返す

mult(add(integer(3), integer(2)), integer(1))

と

parse([num(1), plus, num(2), plus, num(3)], T)

1+2+3 および 1+(2+3) と同等のものを返しますが、前者のみを返す必要があります。

これを機能させる方法はありますか？

編集: 詳細: +、-、*、/、negate (-1、-2 など) を実装するだけでよく、すべての数値は整数です。コードが文法と同様に構造化されるというヒントが与えられました

<expression> ::= <expression> + <term>
              |  <expression> - <term>
              |  <term>

      <term> ::= <term> * <factor>
              |  <term> / <factor>
              |  <factor>

    <factor> ::= num
              |  ( <expression> )

ネゲートも実装されている場合のみ。

Edit2: Prolog で書かれた文法パーサーを見つけました ( http://www.cs.sunysb.edu/~warren/xsbbook/node10.html )。文法の左手派生を出力するように変更する方法はありますか (Prolog インタープリターが「T=[正解]」を出力するという意味での「出力」)

4

3 に答える 3

7

左再帰を削除すると、DCG ベースの文法に移行します。

しかし、興味深い代替方法があります:ボトムアップ解析を実装します。

これは Prolog ではどれくらい難しいですか? Pereira と Shieber が素晴らしい本「プロローグと自然言語分析」で示しているように、6.5 章からは非常に簡単です。

Prolog は、デフォルトで、DCG に対してトップダウン、左から右、バックトラック解析アルゴリズムを提供します。

この種のトップダウン解析アルゴリズムが左再帰ルールでループすることはよく知られています (プログラム 2.3 の例を参照)。

文脈自由文法から左再帰を除去する手法は利用可能ですが、これらの手法は DCG に容易に一般化することはできません。

別の方法として、Prolog で直接ボトムアップの解析方法を実装することを検討することもできます。さまざまな可能性のうち、ここでは、DCG への適応の 1 つである左コーナー法を検討します。

プログラミングの便宜上、左隅の DCG インタープリターの入力文法は、DCG 表記のわずかなバリエーションで表されます。規則の右辺は、リテラルの接続詞ではなくリストとして与えられます。したがって、規則は次の形式の単位句です。

s ---> [np, vp].

また

optrel ---> [].

終端は、word(w,PT) 形式の辞書単位節によって導入されます。

先に進む前に講義を完了することを検討してください (情報ページでタイトルごとに無料の本のエントリを検索してください)。

それでは、ボトムアップ プロセッサを作成してみましょう。

:- op(150, xfx, ---> ).

parse(Phrase) -->
    leaf(SubPhrase),
    lc(SubPhrase, Phrase).

leaf(Cat) --> [Word], {word(Word,Cat)}.
leaf(Phrase) --> {Phrase ---> []}.

lc(Phrase, Phrase) --> [].

lc(SubPhrase, SuperPhrase) -->
    {Phrase ---> [SubPhrase|Rest]},
    parse_rest(Rest),
    lc(Phrase, SuperPhrase).

parse_rest([]) --> [].
parse_rest([Phrase|Phrases]) -->
    parse(Phrase),
    parse_rest(Phrases).

% that's all! fairly easy, isn't it ?

% here start the grammar: replace with your one, don't worry about Left Recursion
e(sum(L,R)) ---> [e(L),sum,e(R)].
e(num(N)) ---> [num(N)].

word(N, num(N)) :- integer(N).
word(+, sum).

たとえば、

phrase(parse(P), [1,+,3,+,1]).
P = e(sum(sum(num(1), num(3)), num(1)))

使用される左再帰文法がe ::= e + e | num

于 2013-12-11T15:11:57.200 に答える
5

プログラムを修正する前に、問題をどのように特定したかを確認してください。特定の文には構文ツリーが 1 つだけあると想定していましたが、そのうちの 2 つが得られました。本質的に、Prolog はバグを見つけるのに役立ちました!

これは、Prolog で非常に役立つデバッグ戦略です。すべての回答を見てください。

次は、文法をどのようにエンコードしたかという具体的な方法です。実際、あなたは非常に賢いことをしました: あなたは本質的に左再帰文法をエンコードしました - それでもあなたのプログラムは固定長のリストで終了します! これは、各再帰内で、中間に演算子として機能する要素が少なくとも 1 つ必要であることを示しているためです。したがって、再帰ごとに少なくとも 1 つの要素が必要です。それは結構です。ただし、この戦略は本質的に非常に非効率的です。ルールを適用するたびに、考えられるすべてのパーティションを考慮する必要があります。

もう 1 つの欠点は、構文ツリーから文を生成できなくなったことです。つまり、定義を次のように使用する場合:

?- parse(S, add(add(integer(1),integer(2)),integer(3))).

理由は 2 つあります。1 つ目は、目標T = add(...,...)が遅すぎることです。append/3目標の前の最初に置くだけです。しかし、もっと興味深いのは、 nowappend/3が終了しないことです。関連する障害スライスは次のとおりです (詳細については、リンクを参照してください)。

parse([num(X)], integer(X)) :- false .
parse(Tkns, T) :-
  ( T = add(T1,T2),
     append(E1, [plus|E2], Tkns), false, 
     parse(E1, T1) ,
      parse(E2, T2) ,
  ;  false、T =multiply(T1,T2)、
      append(E1, [star|E2], Tkns)、
      parse(E1, T1)、
      parse(E2, T2)、     
  ）。

@DanielLyonsは、形式言語からのあらゆる種類の正当化を必要とする「伝統的な」ソリューションをすでに提供しています。しかし、私はあなたがあなたのプログラムでエンコードしたあなたの文法に固執します-DCGに翻訳された-読み取り：

expr(integer(X)) --> [num(X)].
expr(add(L,R)) --> expr(L)、[プラス]、expr(R)。
expr(multiply(L,R)) --> expr(L), [star], expr(R).

この文法を使用?- phrase(expr(T),[num(1),plus,num(2),plus,num(3)]).すると終了しません。関連するスライスは次のとおりです。

expr(integer(X)) --> {false} , [num(X)] .
expr(add(L,R)) --> expr(L), {false} , [プラス], expr(R) .
expr(multiply(L,R)) --> {false} expr(L), [star], expr(R) .

ですから、変更しなければならないのはこの小さな部分です。ルールは、1 つの端末シンボルが必要であることを「認識」していることに注意してください。残念ながら、端末の表示が遅すぎます。再帰の前に発生する場合のみ! しかし、そうではありません。

これを修正する一般的な方法があります。別の引数のペアを追加して、長さをエンコードします。

parse(T, L) :-
   フレーズ（expr（T、L、[]）、L）。

expr(integer(X), [_|S],S) --> [num(X)].
expr(add(L,R), [_|S0],S) --> expr(L, S0,S1), [プラス], expr(R, S1,S).
expr(multiply(L,R), [_|S0],S) --> expr(L, S0,S1), [star], expr(R, S1,S).

これは非常に一般的な方法であり、文法があいまいな場合、または文法があいまいであるかどうかわからない場合に特に役立ちます。Prolog に考えさせてください。

于 2013-12-11T06:59:57.423 に答える
1

正しいアプローチは DCG を使用することですが、例の文法は左再帰的であり、機能しません。これは次のとおりです。

expression(T+E) --> term(T), [plus], expression(E).
expression(T-E) --> term(T), [minus], expression(E).
expression(T)   --> term(T).

term(F*T) --> factor(F), [star], term(T).
term(F/T) --> factor(F), [div], term(T).
term(F)   --> factor(F).

factor(N) --> num(N).
factor(E) --> ['('], expression(E), [')'].

num(N) --> [num(N)], { number(N) }.

左再帰から右再帰への変換と同様に、これとサンプルの文法との関係は明らかです。左端の派生に関するオートマトンのクラスの詳細を思い出すことはできませんが、文法があいまいである場合にのみ機能すると思いますが、これはそうではないと思います。本物のコンピューター科学者が来て、その点を明らかにしてくれることを願っています。

Prolog が使用するもの以外に AST を作成しても意味がありません。プロダクションの左側にある括弧内のコードは、AST 構築コードです (たとえばT+E、最初のexpression//1ルール内)。これが望ましくない場合は、それに応じてコードを調整してください。

ここから、parse/2API の提示は非常に簡単です。

parse(L, T) :- phrase(expression(T), L).

Prolog 独自の構造を使用しているため、結果は実際よりもはるかに印象的ではなくなります。

?- parse([num(4), star, num(8), div, '(', num(3), plus, num(1), ')'], T).
T = 4* (8/ (3+1)) ;
false.

使用したい場合は、より AST-y の出力を表示できますwrite_canonical/2。

?- parse([num(4), star, num(8), div, '(', num(3), plus, num(1), ')'], T),
   write_canonical(T).
*(4,/(8,+(3,1)))
T = 4* (8/ (3+1)) a

パーツ*(4,/(8,+(3,1)))は の結果ですwrite_canonical/1。そして、それを直接評価することができますis/2:

?- parse([num(4), star, num(8), div, '(', num(3), plus, num(1), ')'], T),
   Result is T.
T = 4* (8/ (3+1)),
Result = 8 ;
false.
于 2013-12-11T06:02:07.433 に答える