19

文法から文を生成する一般的な方法は何ですか?

パーサーとは正反対のアルゴリズムが必要です。つまり、形式的な文脈自由文法 (たとえば LL) が与えられた場合、その文法に準拠する任意の文を生成したいと考えています。ここで文とは、有効なテキスト本体を意味するために使用しているため、実際にはプログラム全体である可能性があります (意味をなさない場合でも、構文的に正しい限り)。

文法の例:

program   : <imports> NEWLINE? <namespace>
imports   : ("import" <identifier> NEWLINE)* 
namespace : "namespace " <identifier> NEWLINE "{" <classes> "}" 
identifier: (A-Za-z_) (A-Za-z0-9_)*
...

生成されたプログラムの例:

import jkhbhhuob
import aaaaa888_

namespace u8nFGubgykb
{ class ui0op_np { ... }
}
4

9 に答える 9

16

NLTKを使用した Python の例を次に示します。

from nltk import parse_cfg, ChartParser
from random import choice

def produce(grammar, symbol):
    words = []
    productions = grammar.productions(lhs = symbol)
    production = choice(productions)
    for sym in production.rhs():
        if isinstance(sym, str):
            words.append(sym)
        else:
            words.extend(produce(grammar, sym))
    return words

grammar = parse_cfg('''
S -> NP VP
PP -> P NP
NP -> Det N | Det N PP | 'I'
VP -> V NP | VP PP
V -> 'shot' | 'killed' | 'wounded'
Det -> 'an' | 'my' 
N -> 'elephant' | 'pajamas' | 'cat' | 'dog'
P -> 'in' | 'outside'
''')

parser = ChartParser(grammar)

gr = parser.grammar()
print ' '.join(produce(gr, gr.start()))

この例は本から改作されています。生成された文は構文的には正しいですが、それでも完全に意味不明です。

于 2010-07-20T16:11:00.447 に答える
4

これを行うための「一般的な」アルゴリズムがあることを知りません。ランダムなプログラム生成は遺伝的プログラミングで使用されるため、文法ベースの GP システムを探して、それらがプログラム生成をどのように処理するかを確認できます。疑似コードのような再帰的なルール生成アルゴリズムを実行します。

void GenerateRule(someRule)
{
  foreach (part in someRule.Parts)
  {
    if (part.IsLiteral) OutputLiteral(part);
    if (part.IsIdentifier) Output(GenerateIdentifier(part)));
    if (part.IsRule) GenerateRule(part.Rule);
  }
}

これは、すべてのパーツを何らかのデータ構造に読み込んだことを前提としています。また、繰り返し（発生する回数をランダムに生成する）とオプションのルール（コインを投げて、そこにあるかどうかを確認する）を処理する必要があります。

編集：ああ、ルールに複数のオプションがある場合は、オプションの1つを選択して、同じ方法で処理します。したがって、あるルールが (Literal|Variable) の場合、2 つからランダムに選択します。

于 2009-03-02T20:00:29.823 に答える
2

ソリューションは、文法の帰納的構造に従う必要があります。次のそれぞれについて、ランダムな発話をどのように生成しますか?

  • 端子記号
  • 非終端記号
  • 右辺の数列
  • 右辺の選択
  • 右側のスタークロージャー

文法を表すために使用するデータ構造を書き留めると、これはすべてより明確になります。相互に再帰的なジェネレーター関数のセットの構造は、そのデータ構造を非常によく反映しています。

無限再帰を扱うのは少し危険です。最も簡単な方法は、発話のストリームを生成し、深さのカットオフを維持することです。または、Haskell のような遅延言語を使用している場合は、すべての発話を生成し、有限のものを好きなだけ剥がすことができます (元の質問よりもトリッキーな問題ですが、非常に面白い)。

于 2009-03-02T23:22:49.663 に答える
2

私の頭の上から：

私は再帰的に（基本的に再帰的なまともなパーサーの反対）、範囲（(...)：おそらくランダムに選択）オプション（?：以下の[ ]を参照）、繰り返し（' 'ポアソン分布？）をどうするかについていくつかの発見的方法を使用します。リテラル ( "...") は単純に出力に書き込まれ、サブトークン (`<...>') は再帰を生成します。

ある種の完全なカバレッジを保証したい場合を除き、これはそれほど難しいことではありません。それでも、たくさんのデータを生成するだけで助けになります...

[*] 次のようなルールを処理するときの無限回帰を防ぐために、50% 未満の時間でオプションを含める必要があります。

 nonterm:  otherstuff <nonterm>?

台座でよく釣れます。

繰り返しでも同様に、強く収束する分布をスローします。

ここのように BNF 形式で提示されている場合は、最初に入力文法を解析する必要があります。最も簡単なことは、 mapping(name, string)を使用してから、最高レベルのトークンから開始することです (最初のトークンを意味すると思われるかもしれません...)。

これにより、以下が得られます。

("プログラム", "<インポート> NEWLINE? <名前空間>")

("インポート", ("インポート" <識別子> NEWLINE)*)

...

「program」で始めて、「<imports>」を押して繰り返します...戻ってきたら、「NEWLINE?」を押して、サイコロを振って書くかどうか、「<namespace>」を押して繰り返します...戻ったら完了です。

私は、これが以前に行われたのではないかと疑っています。出力だけが必要な場合は、Web を検索します...おそらくhttp://portal.acm.org/citation.cfm?doid=966137.966142ですが、膨大な数のパーサー ジェネレーターが検索スペースを乱雑にしています。 ..この紙も試してみてください。

ところで、あなたの地元の大学はおそらくこれらの雑誌をオンラインで購読しているので、図書館に接続すれば無料で入手できます。

于 2009-03-02T19:51:43.230 に答える
1

私の最初の提案は、幅優先検索です。ルールのグラフを設定し、それらを検索するだけです。可能な限り小さいものから始めて、ゆっくりと大きくなるプログラムを吐き出し始めます。ただし、文法が特定の数のルールに対して指数関数的に多くのプログラムを吐き出し、DFS を使用するプログラムで 30 程度を超えるトークンを取得できない可能性が高いことに気付くでしょう。

深さ優先検索の問題は、2 番目に左再帰ルールを使用すると、検索が無限ループに陥ってしまうことです。

もう 1 つの大きな問題は、構文的に正しいプログラムは、意味的に正しいプログラムとはかけ離れているということです。後者のタイプを生成することは、最も基本的なケースを除いて、まったく実行不可能です。

于 2009-03-02T19:46:27.080 に答える
1

問題は、グラフの再帰的な性質により、無限のサイズの正しい文法を生成できることです。おそらく、そのノードにヒットできる回数のカウントと制限を使用して、文法でノードタイプのハッシュを設定するようなことをしたいと思うでしょう。次に、心ゆくまで深さ優先検索を行います。

于 2009-03-02T20:02:47.273 に答える
1

いつものように、車輪の再発明はしないようにアドバイスします。私はARMアセンブラ用にこれらの1つを書きましたが、後悔していると記録されています( Software: Practice and Experience April 2007):

「振り返ってみると、市販の式ジェネレーターを使用して、比較のためにランダムな ARM アセンブリ命令を生成する必要がありました。代わりに、各 ARM 命令定義を取得してインスタンスを生成する Perl スクリプトが段階的に作成されました。しかし、漸進的な社内アプローチの利点は、単純な置換によって単純なバグが検出され、バグハンティングが段階的に進められることでした。」</p>

残念ながら、何が私の考えを変えたのか思い出せず、それがあなたの特定のニーズに関連しているとは思えませんが、既存の解決策をもっと探すことをお勧めします. このようなものを自分で作成するのにそれほど規律は必要ありませんが、常に予想以上に時間がかかります。

于 2009-04-29T17:49:43.227 に答える
0

答えではありませんが、文法生成に関するウィキペディアのエントリを確認してください: http://en.wikipedia.org/wiki/Context-free_grammar_generation_algorithms

使用されるいくつかの一般的なアルゴリズムについて説明しました。

于 2009-03-02T19:46:00.480 に答える
-1

アイデアは素晴らしいものですが (私はこれまで何度も考えてきました)、現実には、いくつかのサンプル データや大量のジェネレーターの制約/労力の制限がなければ、非常に大きな仕事になります。

サンプルを手で書く方が簡単だと思うかもしれません。:)

于 2009-03-02T19:46:56.627 に答える