0

私はスロット マシンのミニゲーム アプリケーションに取り組んでいます。当選賞品を構成するルールはかなり複雑です (n 種類、n 種類、特定のシーケンス)。さらに複雑なことに、このコードは (n >= 3) のスロット マシンで機能する必要があります。リール。

したがって、いくつかの考えの後、私はコンテキストフリーの言語を定義することが最も効率的で拡張可能な方法であると信じています。これにより、XMLファイルで文法を定義できます。

だから私の質問は、記号Sの文字列が与えられた場合、Sが特定の文脈自由言語にあるかどうかをテストするにはどうすればよいですか? 有効なルール/シンボルがなくなるまでルールを使い果たすだけですか、それとも役立つ既知のアルゴリズムがありますか。ありがとう。

また、このような言語は非正規のように見えますが、正しいですか? 私は証明が得意ではなかったので、試してみるのを避けてきました。

Any comments on my approach would be appreciated as well.

ありがとう。

4

3 に答える 3

0

あなたの最善の策は、実際にこれを適切なプログラミング言語でコーディングすることです。あなたが言うように、「かなり複雑な」ルールをコーディングするのは非常に難しいので、CFGはやり過ぎです。たとえば、文法は物事の数について話すのにはあまり適していません。

たとえば、そのような言語で「さくらんぼの数は>他のオブジェクトの数」をどのようにコーディングしますか？あなたがプログラムを提供している人はどのようにそうするのでしょうか？CFGはそのような概念を簡単に表現することはできず、正規表現は一気に表現することはできません。

答えは、スロットマシンが英語の文章を作ろうとしない限り、文法はこのタスクには適切ではないということです。

また、2つ以上の「賞品シーケンス」が一致した場合に何が起こるかを考慮する必要があります。あなたが最高の賞品を配りたいと仮定すると、あなたは認識者の順序付けられたリストを必要とします。これは、任意の関数に加えて、（たとえば）正規表現を使用してレコグナイザーをコーディングできないということではありません。一般的なCFG解析はやり過ぎだと言っているだけです。なぜなら、CFGが正規言語（つまり正規表現）を超えるのは、任意の深さの解析ツリー（レベルN以上のネストされた括弧など）を考慮する機能であるためです。あなたが気にしていること。

これは、たとえば正規表現を許可したくないということではありません。パーサジェネレータを使用してチェリーバナナとナシを含む正規表現を認識することで、その作業を簡単に行うことができます。http：//en.wikipedia.org/wiki/Comparison_of_parser_generatorsを参照してください。再帰下降パーサー（特にトークンの長さが制限されている場合は、CFGを気にしないと仮定します）。

たとえば、これを擬似コードで実装する方法を次に示します（理想的には、静的に型チェックされた言語を使用し、リストを適切に操作します。これは頭から離れては考えられません）。

rules = []
function Rule(name, code) {
    this.name = name
    this.code = code

    rules.push(this)  # adds them in order
}

##########################

Rule("All the same", regex(.*))

Rule("No two-in-a-row", function(list, counts) {
    not regex(.{2}).match(list)
})

Rule("More cherries than anything else", function(list, counts) {
    counts[cherries]>counts[x] for all x in counts
      or
    sorted(counts.items())[0]==cherries
      or
    counts.greatest()==cherries
})

for token in [cherry, banana, ...]:
    Rule("At least 50% "+token, function(list, counts){
        counts[token] >= list.length/2
    })
于 2012-08-13T15:22:10.443 に答える
0

文脈自由文法の一般的なケースを評価するのは困難です。

ただし、文脈自由文法のサブセットで文法を解析する方法があります。

例: SLRおよびLL 文法は、多くの場合、コンパイラによってプログラミング言語を解析するために使用されます。プログラミング言語は、コンテキスト フリー言語でもあります。これらを使用するには、グラマーがこれらの「ファミリ」のいずれかに属している必要があります (覚えておいてください - 各文脈自由言語には無限の数のグラマーがあります)。

コンパイラに一般的に使用される実用的なツールには、Java のJavaCCとC++ のbisonがあります。
(私の記憶が正しければ、Bison は SLR パーサーで、JavaCC は LL パーサーですが、間違っている可能性があります)

PS スロットとシンボルを備え
た特定のスロットマシンの場合、言語は明らかに規則的です。これは、最大で k nの「単語」があり、すべての有限言語が規則的であるためです。すべてのスロット マシン用のグラマーを探していると、明らかに複雑になります。nk

于 2012-08-13T14:28:40.517 に答える
0

「...記号 S の文字列が与えられた場合、S が特定の文脈自由言語に含まれているかどうかをテストするにはどうすればよいでしょうか?」

文字列wが L(G) にある場合。wが導出される G の生成規則のシーケンスを見つけるプロセスは、構文解析を呼び出します。そのため、派生を検索するために解析ツリーを作成する必要があります。これを行うには、徹底的な幅優先検索を実行します。発生する重大な問題があります。検索プロセスが終了しない場合があります。無限の検索を防ぐには、文法を通常の形式と呼ばれるものに変換する必要があります。

「また、このような言語は非正規に見えますが、そうですか?」

必ずしも。すべての正規言語は文脈自由言語 (CTG で記述できるため) ですが、すべての文脈自由言語が正規表現であるとは限りません。

于 2012-08-13T14:29:59.330 に答える