random - 文脈自由文法からn個のステートメントを生成する

Question

ですから、車輪の再発明をしないために、文脈自由言語（yaccなどによって生成されたものなど）からランダムステートメントを生成することについて、すでに何が行われているのかを知りたいと思います。これらの文法は主に構文解析用ですが、おそらく誰かがパーサーをテストするために何らかの世代を行ったのでしょうか。ありがとう

Answer 1

このブログ投稿をチェックしてください。基本的に、各ルールアプリケーションで選択されたRHSをランダム化します。

Answer 2

ここには、構文解析よりも効果的なランダム文の生成にいくつかの制約が必要な理由を示す、古くてまだ興味深い記事があります。また、これらの追加の制約を提供する簡単な方法を提案し、完全なサンプルプログラムを提供します（.. .Fortran IVでは...しかし、ねえ、それは40年以上前のものです...！-）。

残念ながら、私はこのテーマに関する最近の作業（またはより現代的な言語での実装）を知りませんが、Fortranのほこりっぽいデッキを好きな言語にトランスコードすることは、これらの概念を自分で思いつくほど難しいことではありません。 -）-これは、私が大学時代に実際の紙ベースの図書館で熟読した一種のすでに古代のものであり、ACMのオンライン検索機能によってぼんやりと覚えていた参照を見つけることができたことに驚いています。とても急速に（kudos、ACM！-）。私はこのテーマについて独自の研究を行ったことがありません。

Answer 3

このようなランダムトークンのシーケンスの生成は、一種の簡単なものです。ゴールシンボルから始めて、塗りつぶされていない非終端記号のランダムな展開を選択します。深さ/サイズを制御できるように、生成された解析ツリーの任意のブランチを特定の分枝限定法で検索する必要があります。

しかし、少なくともパーサジェネレータが文脈自由言語の記述を直接受け入れる場合は、この方法でパーサをテストすることに大きな価値はありません。これは、GLR（プログラム変換システムであるDMSで使用しているもの）やEarleyパーサーなどの完全な文脈自由パーサージェネレーター/ツールを使用する場合に発生します。

別の問題があります。パーサーをテストする場合は、必要なものをフィードする必要があります。確かに、それはトークンではありません。次に、ターミナルリーフの有効な語彙素を生成する必要があります。それもそれほど難しいことではありませんが、スキャナーレススタイルで文法を書くこのアプローチについて純粋になりたいと思っていました。

しかし、最後の問題は、ほとんどの言語で文脈自由文法を見つけるのが難しいことです。したがって、ゴールドグラマーもデバッグする必要があります。どのようにそれをしますか？その段階に到達すると、あきらめてパーサーをデバッグし、人生を続ける可能性があります。

ランダムサブツリーの生成は、ランダムツリーでスプライスしてソースストリームを修正できる場合、エラー回復に役立ちます。DMSのパーサーに対してこれを簡略化した形式で実行します。つまり、エラー処理機構は1つだけです。