私はCFG Gと終端記号aを入力とするアルゴリズムを設計しようとしており、S（Gの開始規則）が始まる文脈形式とともに。すなわち、S => *aαとなるような（T U N）*中の文字列αが存在すれば、それ以外の場合はnoを出力する。例えば、文法がS - > [S] | SS | ε、a =]の場合、答えはノーです。私はコードを探していません、私は擬似コードでこのトピックにどのようにアプローチすべきかを理解しようとしています。文脈自由文法のアルゴリズム
Xには、aで始まる文字列を派生させる方法が3つあります。
X -> a...X -> A...とAがaで始まる文字列を導出し、フォームのルールがありますあります。X -> B A...とBは、εを導出し、A...はaで始まる文字列を導出します。あなたはどちらの形式S -> ...のそれで始まる文法のすべてのルールを見て、適用されたアルゴリズムを構築し、それならばRHSは、端末または両方のチェック2と3で始まる場合は1をチェックするためにこれらを使用することができます非終端記号で始まります。各チェックは、ブール値を返す（おそらく再帰的な）関数に対応しています。
興味深い1つの詳細は、文法のサイクルを処理する必要性です。 A -> A aのような単一の規則だけでなく、A -> B...,B -> C...、C -> A...のような単一の規則。注意しないと、相互に再帰的なチェックは無限に繰り返されます。私はあなたにそれをお伝えします。奥行きの最初の探索がグラフ内のサイクルを永遠に回避する方法について考えてみましょう。
もう1つの詳細は、特定の非終端記号Bがεを導出するかどうかを判断する方法です。あなたは自分自身でそれを動かすことができるはずですが、他のすべてが失敗した場合は、「nullable non-terminal」を参照してください。あなたはよく知られている小さなアルゴリズムを見つけるでしょう。
チェックのいずれかが肯定的である場合は、はいを返します。それ以外のルールの網羅的な適用は決して見つけられませんでした。戻りません。
予測が停止するまでEarley parserのプレディクタを実行し、問題のターミナルで始まるルールが生成されるかどうかを確認できます。
最初の入力として問題の端末を受け入れるすべての非終端記号をマークし、既にマークされた非終端記号を受け入れるすべての非終端記号に最初の入力としてマークし、完了まで繰り返すマークされた非終端記号のセットに含まれています。