CFGから生成するときに有効な次の端末の集合を決定する

Question

文脈自由文法からランダムな文を生成しようとしています。各ステップの間に、生成される次の非終端記号は、この質問に無関係ないくつかの確率的基準に従って決定される。文法とこれまでに生成された部分文があれば、文法に従って次のステップで生成できる非終端記号の集合をどのようにして決定するのですか？

以下は、BNFと部分的な世代における文法の例です。

<expr> ::= <term> "+" <expr> | <term> 
<term> ::= <term> "*" <factor> | <factor> 
<factor> ::= "(" <expr> ")" | <const> 
<const> ::= "0" | "1" | "2" | "3" | "4" 

これまでに生成された配列：(1 +とする。この場合、生成される次のトークンは、{"(", "0", "1", "2", "3", "4"}から来るはずです。

一般的な文法と部分的な生成を考慮してこの集合を決定するアルゴリズムがありますか、または各段階でこの集合を利用できるように文を生成しますか？

Answer 1

文を生成する通常の方法は、開始記号で始まり、最初に（または最後の）非終端記号を、この回答に完全には関連しないサンプリング基準を使用して反復することです。

文法が左から右に解析できる場合は、接頭辞を解析して、エラーのないアクションが存在する端末の1つを選択するだけです。そのためには、左から右へのアルゴリズムが適用可能な構文解析テーブルが必要です。アルゴリズムがLALR（k）の場合、最終的なエラーにつながる行為を減らすことに注意する必要があります。そのようなシナリオを避けるには、削減アクションを選択する場合は、対応する先読みシンボルにコミットしないでください。あなたがシフトを行うときにのみコミットします。 （ただし、リダクションアクションに対応する先読みを無視することはできません。先読みシンボルが一貫して選択されるように、セット全体を保持する必要があります）。