prolog - DCGを決定論的に変更する

Question

このグラマを決定論的に変更する方法

e --> [].
e --> "*".
e --> s_e.
e --> e, s_e.
s_e --> ("a",e);("b",e).

バックトラックを避けるためにカットをどこに置くべきかわかりません。

Answer 1

最後のルールは次のように書き直すことができます。

s_e --> "a", e.
s_e --> "b", e.

ここで、次のカットを配置することはおそらく理にかなっています。

s_e --> "a", !, e.
s_e --> "b", !, e.

（;）/ 2を使用して、元のコンパクトな形式でカットを配置することもできますが、上記の方が透明であることがわかります。上記は、s_eが同じ入力リストで複数回呼び出されない場合に有効です。

ただし、文法に欠陥があり、eは再帰的に残され、s_eは同じ入力リストで複数回呼び出されます。たとえば、文法が否定的な文に対してループすることを意味します。つまり、それらを拒否することはできません。また、肯定的な文に対してやり直した後、つまり入力が受け入れられたときに、文法がループします。

したがって、通常のProlog深度拳検索では左再帰を処理できないため、さらに左再帰を排除する必要があります。最も簡単なのは、新しい非終端記号を使用した正しい再帰で置き換えることです。つまり、eのプロダクションは次のように書くことができます。

 e --> s_e, rest_e.
 e --> "*", rest_e.
 e --> [].

 rest_e --> s_e, rest_e.
 rest_e --> "*", rest_e.
 rest_e --> [].

また、カットを配置することもできます。

 e --> s_e, !, rest_e.
 e --> "*", !, rest_e.
 e --> [].

 rest_e --> s_e, !, rest_e.
 rest_e --> "*", !, rest_e.
 rest_e --> [].

また、上記の文法は、複数の空のeプロダクションがs_eを介してe自体に入らないという意味でわずかに変更されています。また、sub eプロダクションは常に完全に解析されるという点で、より貪欲です。たとえば、次の文です。

 aaa

次のようにのみ解析されます：

 a(a(a))

そして、そうではありません：

 a(a)a

または：

 aa(a)

または：

 aaa

ただし、それ以外の場合は、DCGがボトムアップで実行され、左再帰に問題がない場合と同じ文を受け入れる必要があります。

よろしくお願いします