正式な文法から文章を生成するにはどうすればよいですか？

StackOverflow https://stackoverflow.com/questions/603687

質問

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

パーサーの反対のアルゴリズムが必要です。つまり、正式な文脈自由文法（たとえばLL）が与えられた場合、その文法に適合する任意の文を生成したいと思います。ここでは sentence を使用して有効なテキスト本文を意味するため、実際にはプログラム全体になる場合があります（意味がわからなくても<！>＃8212;構文的に正しい限り） 。

文法の例：

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 { ... }
}
役に立ちましたか？

解決

<！> quot; common <！> quot;があることはわかりません。これを行うためのアルゴリズム。遺伝的プログラミングではランダムプログラム生成が使用されるため、文法ベースの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つ選んで同じ方法で処理します。したがって、何らかのルールが（リテラル|変数）である場合、2つのうちのいずれかをランダムに選択します。

他のヒント

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()))

この例は、本からの抜粋です。生成された文は構文的には正しいが、まだ完全に意味不明です。

解決策は、文法の帰納的構造に従う必要があります。次のそれぞれに対してランダムな発話を生成するにはどうしますか？

  • 端子記号
  • 非終端記号
  • 右側のシーケンス
  • 右側の選択
  • 右側のスター閉鎖

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

無限再帰を伴う処理は少し危険です。最も簡単な方法は、発話のストリームを生成し、深度カットオフを維持することです。または、Haskellのような怠usingな言語を使用している場合、すべての発話を生成し、必要な限り多くの有限なものを剥がすことができます（元の質問よりも難しい問題ですが、非常に面白いです）。

頭の上から：

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

ある種の完全なカバレッジを保証したいのでなければ、これはそれほど難しくないはずです。それでも、データの束を生成するだけで助けになります...

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

 nonterm:  otherstuff <nonterm>?

台座。

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

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

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

  

（<！> quot; program <！> quot ;, <！> quot; <！> lt; imports <！> gt; NEWLINE？<！> lt; namespace <！> gt; <！> quot; ）

     

（<！> quot; imports <！> quot ;,（<！> quot; import <！> quot; <！> lt; identifier <！> gt; NEWLINE）*）

     

...

<！> quot; program <！> quot;で開始し、<！> quot; <！> lt; imports <！> gt; <！> quot;を押します。戻ってきたら、<！> quot; NEWLINE？<！> quot;を返します。サイコロを投げて、書くかどうか、<！> quot; <！> lt; namespace <！> gt;を押します。 <！> quot;繰り返します...戻ってきたら完了です。

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

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

問題は、グラフの再帰的な性質により、無限のサイズの正しい文法を生成できるということです。おそらく、文法でノードタイプのハッシュを設定し、そのノードにヒットできる回数と制限を設定することをお勧めします。次に、最初の検索を心の底まで掘り下げます。

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

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

別の大きな問題は、構文的に正しいプログラムは、意味的に正しいプログラムから遠いことです。後者のタイプを生成することは、ほとんどの基本的な場合を除いて、おそらく完全に実行不可能です。

いつものように、I <！>＃8217; mは車輪の再発明をしないようにアドバイスします。 I <！>＃8217;これらのいずれかをARMアセンブラ用に作成しましたが、後悔していると記録されています（ソフトウェア：実践と経験 2007年4月）：

<！>＃8220;振り返ってみると、市販の式ジェネレータを使用して、比較のためにランダムなARMアセンブリ命令を生成する必要がありました。代わりに、各ARM命令定義を取得してインスタンスを生成するPerlスクリプトがインクリメンタルに構築されました。ただし、社内での増分アプローチの利点は、単純な置換が単純なバグを検出し、バグハンティングがインクリメンタルに進行できることでした。<！>＃8221;

I <！>＃8217;心配しない<！>＃8217;何が私の考えを変えたのか思い出せず、それがあなたの特定のニーズに関連しているとは思わないが、既存の溶液。このようなものを自分で書くための規律はそれほど必要ありませんが、常に予想よりも時間がかかります。

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

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

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

手で簡単にサンプルを書くことができます。 ：）

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top