6

この文法の左再帰に小さな問題があります。Prologで書こうとしているのですが、左再帰を外す方法がわかりません。

<expression> -> <simple_expression>
<simple_expression> -> <simple_expression> <binary_operator> <simple_expression>
<simple_expression> -> <function>
<function> -> <function> <atom>
<function> -> <atom>
<atom> -> <number> | <variable>

<binary_operator> -> + | - | * | /

expression(Expr) --> simple_expression(SExpr), { Expr = SExpr }.
simple_expression(SExpr) --> simple_expression(SExpr1), binary_operator(Op), simple_expression(SExpr2), { SExpr =.. [Op, SExpr1, SExpr2] }.
simple_expression(SExpr) --> function(Func), { SExpr = Func }.
function(Func) --> function(Func2), atom(At), { Func = [Func2, atom(At)] }.
function(Func) --> atom(At), { Func = At }.

みたいなことを書いたのですが、全然うまくいきません。このプログラムを機能させるために変更するにはどうすればよいですか?

4

4 に答える 4

1

あなたのプログラムの問題は、確かに左再帰です。削除する必要があります。削除しないと、無限ループに陥ります

すぐ左の再帰を削除するには、フォームの各ルールを置き換えます

A->A a1|A a2|....|b1|b2|....

と：

A -> b1 A'|b2 A'|....
A' -> ε | a1 A'| a2 A'|....

そのため、関数は

function -> atom, functionR.
funtionR -> [].

ウィキページ

于 2012-05-19T08:40:02.427 に答える
1

この問題は、後方連鎖を使用しているためにのみ発生します。前方連鎖では、左再帰文法規則を直接扱うことができます。次の形式の文法規則が提供されます。

NT ==> NT'

サイクルを形成しないでください。{}/1本体の非終端記号の後に補助計算を配置し、頭部の非終端記号に補助計算専用のパラメータがない場合は、補助計算を使用することもできます。つまり、ボトムアップ状態です。

以下は、前方連鎖でこのように完全に機能する左再帰文法の例です。

:- use_module(library(minimal/chart)).
:- use_module(library(experiment/ref)).

:- static 'D'/3.

expr(C) ==> expr(A), [+], term(B), {C is A+B}.
expr(C) ==> expr(A), [-], term(B), {C is A-B}.
expr(A) ==> term(A).

term(C) ==> term(A), [*], factor(B), {C is A*B}.
term(C) ==> term(A), [/], factor(B), {C is A/B}.
term(A) ==> factor(A).

factor(A) ==> [A], {integer(A)}.

チャート パーサーのソース コードへのリンクは次のとおりです。このリンクから、フォワード チェイナーのソース コードも見つけることができます。以下に、セッションの例を示します。

?- use_module(library(minimal/hypo)).

?- chart([1,+,2,*,3], N) => chart(expr(X), N).
X = 7

解析中、チャート パーサーはボトムアップ方式でチャートを埋めます。上記のプロダクションの各非ターミナル p/n には、ファクト p/n+2 があります。上記の例のチャートの結果は次のとおりです。

:- thread_local factor/3.
factor(3, 4, 5).
factor(2, 2, 3).
factor(1, 0, 1).

:- thread_local term/3.
term(3, 4, 5).
term(2, 2, 3).
term(6, 2, 5).
term(1, 0, 1).

:- thread_local expr/3.
expr(3, 4, 5).
expr(2, 2, 3).
expr(6, 2, 5).
expr(1, 0, 1).
expr(3, 0, 3).
expr(7, 0, 5).
于 2012-05-19T16:27:26.197 に答える
0

@thanosQR からの回答はかなり良いですが、DCG よりも一般的なコンテキストに適用され、解析ツリーの変更が必要です。事実上、解析の「結果」が削除されました。これは良くありません。

式の解析だけに興味がある場合は、ここに便利なものを投稿しました。

于 2012-05-19T09:27:57.743 に答える