7

私は Python で PEG パーサー ジェネレーターを実装していますが、Prolog を知っている人なら誰でも知っているはずの「カット」機能を除いて、これまでのところ成功しています。

カット ( !) 記号が解析された後は、同じレベルで代替オプションを試行すべきではないという考え方です。

expre = '(' ! list ')' | atom.

(が見られた後、解析が成功するか、2 番目のオプションを試さずに失敗する必要があることを意味します。

バックトラックを強制するために Python の (非常に効率的な) 例外システムを使用しているのでFailedCut、囲んでいる選択を中止する特別な例外を設定しようとしましたが、うまくいきませんでした。

この機能が他のパーサー ジェネレーターでどのように実装されているかについてのポインターは役に立ちます。

多分私が抱えていた問題は、地域性の欠如でした. ルールの左側の部分に対して生成されるコードは次のようになります。 

cut_seen = False
try:
    self.token('(')
    cut_seen = True 
    self.call('list')
    self.token(')')
except FailedParse as e:
    if cut_seen:
         raise FailedCut(e)
    raise

次に、choice( |) 演算子用に生成されたコードは、FailedCut. 局所性の欠如とは、キャッチする選択肢FailedCutが呼び出しの奥深くにある可能性があり、その結果、識別が困難すぎるということです。

シーケンス用に生成されたコードに、カットの囲まれた選択肢を知らせようとする代わりに、選択肢用に生成されたコードにそれらを認識させることができます。これにより、Prolog とは異なり、カットの範囲が非常にローカルになりますが、特定のトークン シーケンスが表示された後にオプションにコミットするという PEG パーサーで必要なものには十分なので、エラー レポートはその場所を参照します。他のオプションが利用可能だった可能性のある別の場所ではなく、ソースで。

ルール/述語用に生成されたコードがそれをキャッチFailedCutして通常の例外に変換する場合FailedParse、カットには適切なスコープがあることに気づきました。

@falseの質問を参照して、私がやりたいことの完全な例を次に示します。

start = expre ;

expre = named | term ;

named = word ':' ! term;

term = word ;

その文法では、 orwordを介して到達できますが、パーサーが.namedtermnamed:

ソリューション

公平を期すために、これまでの作品をhttps://bitbucket.org/apalala/grako/で公開しました。

最終的な解決策では、シーケンスは次のコンテキスト マネージャーで囲まれます。

@contextmanager
def _sequence(self):
    self._push_cut()
    try:
        yield
    except FailedParse as e:
        if self._cut():
            self.error(e, FailedCut)
        else:
            raise
    finally:
        self._pop_cut()

また、choice 関数のオプションは次のように囲みます。

@contextmanager
def _option(self):
    p = self._pos
    try:
        self._push_ast()
        try:
            yield
            ast = self.ast
        finally:
            self._pop_ast()
        self.ast.update(ast)
    except FailedCut as e:
        self._goto(p)
        raise e.nested
    except FailedParse:
        self._goto(p)

これは、次のオプションを試すために戻るのではなく、選択肢から抜け出すことを強制します。

カット自体は次のように実装されます。

def _cut(self):
    self._cut_stack[-1] = True

完全なソース コードはBitbucketで見つけることができます。

4

3 に答える 3

3

ISO Prolog の例外処理 (catch/3およびthrow/1) を使用する Prolog では、カットは次のように実装できます。

cut. % Simply succeeds
cut :-
   throw(cut). % on backtracking throws an exception

これには、適切な場所でその例外をキャッチする必要があります。たとえば、ユーザー定義の述語の各ゴール (非終端) を次のようにラップできるようになりました。

catchcut(Goal) :-
   catch(Goal,cut,fail).

の成功時にリソースを解放しないため、これはカットを実装する最も効率的な方法ではありません!が、目的には十分かもしれません。また、このメソッドは、ユーザー定義の の使用に干渉する可能性がありcatch/3ます。しかし、どのような場合でも、Prolog 言語全体をエミュレートしたいとは思わないでしょう。

また、Prolog の -grammars を直接使用することを検討してください。これを別の言語で実装する場合、明らかでない細字がたくさんあります。

于 2013-01-03T19:08:50.993 に答える
2

私の質問の最後に提案された解決策はうまくいきました： 

cut_seen = False
try:
    self.token('(')
    cut_seen = True 
    self.call('list')
    self.token(')')
except FailedParse as e:
    if cut_seen:
         raise FailedCut(e)
    raise

次に、選択肢またはオプションが評価されるたびに、コードは次のようになります。

p = self.pos
try:
   # code for the expression
except FailedCut:
    raise
except FailedParse:
    self.goto(p)

編集

実際の解決策では、「カット スタック」を保持する必要がありました。ソース コードはint Bitbucket です。

于 2013-01-11T21:30:43.350 に答える
1

ただ読んでください。

(パーサーの状態を変更するなどの)ディープcut_seenと、ローカル変数を使用した状態の保存と復元を提案しました。これは、スレッドのスタックを「cut_seenスタック」として使用します。

しかし、あなたには別の解決策があり、私はあなたがすでに大丈夫だと確信しています.

ところで: 素晴らしいコンパイラ – これは私が pyPEG で行っていることとは正反対なので、多くのことを学ぶことができます ;-)

于 2013-01-21T23:33:16.560 に答える