7

文脈自由文法を Greibach Normal Form (GNF) に変換しています。主な変換 (Hopcroft & Ullman による) は、文法のインデックス付き変数に対する一連の反復です。それは本質的に「ステートレス」です。適切なインデックスに対する一連の折り畳みとして実装しました (実装はかなり簡単です)。

gnf :: Ord a => Set (Rule a) -> Set (Rule a)
gnf rl = foldl step1 rl [1..maxIndex rl]
 where step1 rl' k = foldl step2 rl' [1..k - 1]
        where step2 rl'' j = noLR k (subst rl'' k j)

maxIndex rlは、一連のルール内の最大変数インデックスを返します。subst rl kjは、右辺がjインデックスの変数で始まるルールによって、 kインデックスのルールで置換を実行します。gnfを実行した後、逆の順序で文法の最終パスを実行する必要があります。

問題はnoLRで、左再帰のkインデックス規則で文法を変換します。noLRが適用されるルール (またはkインデックス付きルール)ごとに一意の変数を生成する必要があるため、これは「ステートフル」関数です。だから私はステートフル関数を書いた

noLR :: Ord a => Int -> Set (Rule a) -> State [Sym a] (Set (Rule a))
noLR rl = do (n:ns) <- get; put ns;
             let rl' = ... remove left recursion rl n ...
              in return rl'

noLRがパラメーターとして取るnを更新するために、 noLRを一緒にシーケンスすることができます。ただし、上記の関数のstep2内でnoLRを実行する方法がわかりません。ステートフルな計算がいくつかの再帰関数内に埋め込まれているため、スキーマでlet ...を使用できないようです。

私がやりたいのは、 nの明示的なスレッド化と同様に、 nを何らかのタイプのグローバル変数にすることです。これは、 step2内で呼び出して更新できます。これが、もともと関数をeta -expansion (for n）。この種の効果を達成するために状態モナド内でgnfを構造化する方法を知っている人はいますか? フォールド内の最後の計算を除いて、他に何も「ステートフル」ではありません。私は「些細な」例で状態モナドを使用することに慣れているだけです。私はむしろ迷っています。

4

2 に答える 2

4

指定したタイプで noLR を使用するには、次の行に沿って gnf 関数を書き直す必要があります。

gnf :: Ord a => Set (Rule a) -> Set (Rule a)
gnf rl = evalState (foldM step1 rl [1..maxIndex rl]) ( ... generate the initial state [Sym a] here ...)
 where step1 rl' k = foldM step2 rl' [1..k - 1]
        where step2 rl'' j = noLR k (subst rl'' k j)

状態変数は計算全体に存在し、その事実をコードで明示する必要があります。

新しく生成された変数名が互いに衝突しないことだけが必要な場合は、インデックス k と j から新しいシンボル名を生成することで noLR を純粋にすることができます。 j == 16. ただし、入力文法にそのような記号名が既に含まれている場合は、問題が発生する可能性があります。

記号を文法内で一意にする必要がある場合は、それを言ってみませんか?

newSymbol :: Set (Rule a) -> Sym a
newSymbol rl = ... find a symbol name not used in rl ...

ただし、Set (ルール a) を newSymbol 操作をより効率的に実装できる別の型に置き換えない限り、これは明らかに効率的ではありません。

于 2010-11-23T22:48:59.983 に答える
3

noLR を純粋に書き直そうとします。ルールの名前とそのインデックス (または類似のもの) のみに依存するシンボルを生成するように書き直すことはできませんか?

noLR k j = noLR' k j $ newSymbol k j
    where newSymbol k j = ... -- some concatenation of k and j
          noLR' k j sym = ... -- your now pure function
于 2010-11-23T20:51:44.843 に答える