0

我正在开发一个老虎机迷你游戏应用程序。构成中奖的规则相当复杂（n of a kind，n of any kind，特定顺序），更复杂的是，此代码应该适用于 (n >= 3) 的老虎机卷轴。

所以，经过一番思考，我相信定义上下文无关语言是最有效和可扩展的方式。这样我就可以在 XML 文件中定义语法。

所以我的问题是，给定一串符号 S，我该如何测试 S 是否使用给定的上下文无关语言？我是否会简单地用尽规则，直到我没有有效的规则/符号，或者是否有已知的算法可以提供帮助。谢谢。

另外，像这样的语言似乎很不规则，对吗？我从来不擅长证明，所以我避免尝试。

对我的方法的任何评论也将不胜感激。

谢谢。

4

3 回答 3

0

上下文无关语法的一般情况很难评估。

但是，有一些方法可以在上下文无关语法的子集中解析语法。

例如：编译器经常使用SLR和LL语法来解析编程语言，它们也是上下文无关的语言。要使用这些，您的语法必须属于这些“家族”之一（请记住 - 每种上下文无关语言都有无限数量的语法）。

您可能想要使用的一些通常用于编译器的实用工具是java中的JavaCC和 C++ 中的bison。
（如果我没记错的话，Bison 是 SLR 解析器，JavaCC 是 LL Parser，但我可能是错的）

PS
对于具有插槽和符号的特定老虎机- 该语言绝对是规则的，因为其中最多有 k n 个“单词”，并且每种有限语言都是规则的。如果您正在为所有老虎机寻找语法，事情显然会变得复杂。nk

于 2012-08-13T14:28:40.517 回答
0

“...给定一串符号 S，我如何测试 S 是否使用给定的上下文无关语言？”

如果字符串w在 L(G) 中；寻找 G 的一系列产生式规则并由此推导出w的过程称为调用解析。所以，你必须创建一个解析树来搜索一些推导。为此，您需要执行详尽的广度优先搜索。出现了一个严重的问题：搜索过程可能永远不会终止。为了防止无休止的搜索，您必须将语法转换为所谓的范式。

“而且，这样的语言似乎很不规则，我说的对吗？”

不必要。每种常规语言都是无上下文的（因为它可以由 CTG 描述），但并非所有无上下文的语言都是常规的。

于 2012-08-13T14:29:59.330 回答
0

您最好的选择是使用适当的编程语言对其进行实际编码。CFG 是矫枉过正的，因为编写一些（如您所说）“相当复杂”的规则可能非常困难。例如，语法不适合谈论事物的数量。

例如，您将如何用这种语言编写“樱桃的数量大于任何其他物体的数量”？你给程序的人会怎么做？CFG 不能轻易地表达这些概念，而正则表达式无论如何也不能理智地做到这一点。

答案是语法不适合这项任务，除非老虎机试图造英语句子。

您还必须考虑当两个或更多“奖品序列”匹配时会发生什么！假设您想颁发最高奖，您需要一个有序的识别器列表。这并不是说除了任意函数​​之外，您不能使用（例如）正则表达式对识别器进行编码。我只是说一般的 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 回答