3

DCG形式の文脈自由文法から非決定性プッシュダウンオートマトンのデルタ関数を取得する必要があります。これを行うためのアルゴリズムは非常に単純です。

文法のすべてのルールについて、デルタ関数にA --> B遷移を追加します。[q1, lambda, A] --> [B]

文法のすべてのルールについて、デルタ関数にE --> c遷移を追加します。[q1, c, c] --> [lambda]

[q0, lambda, z0] --> [q1, S*z0]遷移と[q1, lambda, z0] --> [q2, z0]デルタ関数を追加します。

すべての大文字は非終端記号であり、すべての小文字は終端記号です。lambdaは空の文字列、Sは文法の最初の記号、*は連結演算子、z0はスタックの最上位の記号です。

これは文法を意味します

S --> A*b | B | y
A --> w*x | x
B --> A*b

デルタ関数を使用してプッシュダウンオートマトンを生成します

[q0, lambda, z0] --> [q1, S*z0]
[q1, lambda, S] --> [q1, A*b]
[q1, lambda, S] --> [q1, B]
[q1, lambda, S] --> [q1, y]
[q1, lambda, A] --> [q1, w*x]
[q1, lambda, A] --> [q1, x]
[q1, lambda, B] --> [q1, A*b]
[q1, b, b] --> [q1, lambda]
[q1, w, w] --> [q1, lambda]
[q1, x, x] --> [q1, lambda]
[q1, y, y] --> [q1, lambda]
[q1, lambda, z0] --> [q2, z0]

私はこのアルゴリズムをPrologに実装する必要があり（ユーザーから文法を取得してデルタ関数を返す）、論理プログラミング言語を使用するのはこれが初めてであるため、混乱しています。

文法を述語形式に変換してから、すべての述語を「反復」し、すでに「トラバース」した述語をリストに追加して、このリストを処理してデルタ関数を返すことができると思いました。しかし、これは物事を行うためのある種の本当に複雑な命令型の方法であり、これにPrologを使用することは無意味だと思います。

この問題にはもっと洗練された解決策があるかもしれないので、そのような解決策が存在するかどうか知りたいです。

4

1 に答える 1

2

ここで可能なコーディング

g2nfa(Grammar, Delta) :-
    maplist(transitions, Grammar, DeltaT),
    append(DeltaT, DeltaF),
    Initial = (q0, lambda, z0 --> q1, 'S'*z0),
    Final = (q1, lambda, z0 --> q2, z0),
    append([[Initial], DeltaF, [Final]], Delta).

transitions(Sym --> Alternatives, Transitions) :-
    phrase(transition(Sym, Alternatives), Transitions).

transition(Sym, A|As) --> state(Sym, A), !, transition(Sym, As).
transition(Sym, A) --> state(Sym, A).
state(Sym, A) --> [(q1, lambda, Sym --> q1, A)].

test :-
    g2nfa([( 'S' --> 'A'*b | 'B' | y ),
           ( 'A' --> w*x | x ),
           ( 'B' --> 'A'*b )
          ], T), maplist(writeln, T).

それはあなたの要件を満たしているようです

?- test.
q0,lambda,z0-->q1,S*z0
q1,lambda,S-->q1,A*b
q1,lambda,S-->q1,B
q1,lambda,S-->q1,y
q1,lambda,A-->q1,w*x
q1,lambda,A-->q1,x
q1,lambda,B-->q1,A*b
q1,lambda,z0-->q2,z0
true.

構文の詳細を理解することができます。2番目の書き換えルール（文法のすべてのルールE-> cについて、遷移[q1、c、c]->λをデルタ関数に追加します。）がサンプルに適用されていないことに注意してください。

于 2012-06-16T14:04:04.343 に答える