開発したクエリ言語用のランダムクエリジェネレータを構築しようとしています。アイデアは、解析テーブルのルールに従ってランダムクエリを生成することです。これまでのところ、私が試したすべてのLLパーサージェネレーターは、再帰下降パーサーのみを生成します。生成されたパーサーを変更してみることができますが、ANTLRが小さな式言語用に生成したパーサーを見ると、クエリ言語用のパーサーは非常に大きくなります。
したがって、テーブル駆動型パーサーはより小さく、微調整が容易になると思います。テーブル駆動のLLパーサーを生成できるオープンソースツールはありますか？
あるいは、LR解析テーブルを「逆に」使用してランダムクエリを導出できますか？
はい、LRパーサーテーブルを使用してランダムクエリを生成できます。解析しているようにテーブルをトラバースするだけで、状態テーブルがトークンの遷移または削減を提供する場所であればどこでも、クエリのサイズが「十分に大きい」場合は削減を優先して、そのトークンをランダムに提案します。トークンシーケンスはクエリです。
ただし、このためにLRテーブルは必要ありません。同様の方法で、文法定義（一連のBNFルール）をトラバースできます。まず、すべてのルールを次の形式に正規化する必要があります。
LHS = RHS1 RHS2 ... RHSn ;
これは、元のルールの複雑なサブフレーズを表すために新しく生成された非終端記号を追加することにより、クリーネ閉包とプラス、および代替を取り除きます。これは簡単です。
非終端記号（最初はゴールシンボル）がある場合は、LHSが一致するルールを見つけ、ランダムに1つ選択して、そのルールを展開します。ルール内の自分の位置を「ドット」（LRパーサー生成の「アイテム」と同じ考え方）として追跡する必要があります。ルールとドットが与えられると、選択されたトークンは終端記号（提案、選択の余地はありません！）または非終端記号（この段落の方法を使用して非終端記号のトークンシーケンスを再帰的に生成します）のいずれかです。