AC プログラムのソース コードは、C 文法 (CFG で説明) に従って解析でき、最終的に多くの AST に変換できます。そのようなツールが存在するかどうかを検討しています。最初に、具体的な文字列値を持たないトークンを含む多くの AST をランダムに生成し、CFG に従ってトークンの型だけを生成することで、逆のことを行うことができます。正規表現のトークンの定義に従ってトークン。
最初のステップは、反復的な非端末置換のように見えると想像できます。これはランダムであり、特定の反復回数によって制限される可能性があります。2 番目のステップは、正規表現に従ってランダムな文字列を生成するだけです。
これを行うことができるツールはありますか？
「データ生成言語」DGLはこれを行い、出力される文法のプロダクションの確率を重み付けする機能が追加されています。
一般に、再帰的降下パーサーは、言語を解析/認識するのではなく、生成する一連の再帰的手続きにまったく直接的に書き直すことができます。
正規化された形式の文法モデルがある場合 (すべてのルールは次のようになります):
LHS = RHS1 RHS2 ... RHSn ;
および言語の prettyprinter (たとえば、AST からテキストへの変換ツール) を使用すると、これらのいずれかを非常に簡単に構築できます。
ユニットツリーとして目標シンボルから始めるだけです。
Repeat until no nonterminals are left:
Pick a nonterminal N in the tree;
Expand by adding children for the right hand side of any rule
whose left-hand side matches the nonterminal N
値 (変数名、数値、文字列など) を運ぶ端末では、ランダムなコンテンツを生成する必要があります。
上記のアルゴリズムの複雑な点は、明確に終了しないことです。実際にやりたいことは、ツリーのサイズの制限を選択し、すべての非終端記号がなくなるか、制限を超えるまでアルゴリズムを実行することです。後者の場合、バックトラックし、最後の置換を元に戻し、別のことを試してください。これにより、決定されたサイズの AST に対する制限付きの深さ優先検索が行われます。
次に、結果をきれいに印刷します。正しく取得するのが難しいのは、かなりプリンターの部分です。
[prettyprinter を含め、これらすべてのものを自分で作成できますが、かなりの作業量です。私は、このすべての機構を言語でパラメーター化された方法で直接含むツールを作成します。私の経歴を参照してください]。
整形式の AST であっても厄介な問題は、AST が無意味である可能性があることです。整数 X の宣言を生成し、文字列リテラル値をそれに割り当てますが、それが許可されていない言語の場合です。おそらくいくつかの単純な問題を排除できますが、言語のセマンティクスは信じられないほど複雑になる可能性があります。例として C++ を検討してください。意味的に意味のあるプログラムになるようにすることは非常に困難です。本質的に、結果のテキストを解析し、名前と型の解決/チェックを実行する必要があります。C++ の場合、完全な C++ フロント エンドが必要です。