如何从 BNF 生成随机程序

Question

我知道我的问题听起来有点模糊，但我在网上找不到任何教程。我不是在寻求答案，而是在寻求更多解释。\nBNF 的示例：

\n\n

<prog> ::= \xe2\x80\x9cint main() { <stat_list> return 0; }\xe2\x80\x9d\n<stat_list>  ::= <stat>\n         | <stat_list> <stat>\n<stat>       ::= <cmpd_stat>\n         | <if_stat>\n         | <iter_stat>\n         | <assgn_stat>\n         | <decl_stat>\n<cmpd_stat>  ::= { <stat_list> }\n<if_stat>    ::= if ( <exp> ) <stat>\n         | if ( <exp> ) <cmpd_stat>\n         | if ( <exp> ) <stat> else <stat>\n         | if ( <exp> ) <cmpd_stat> else <stat>\n         | if ( <exp> ) <stat> else <cmpd_stat>\n         | if ( <exp> ) <cmpd_stat> else <cmpd_stat>\n

\n\n

将其转换为 python 以使我的程序使用上述条件创建随机程序的最简单方法是什么？任何有用网站链接的帮助将不胜感激。

\n

Answer 1

NLTK有一个语法包。通常用于句子分析，但没有什么可以阻止您使用它来创建遵循该规则的“程序”。

\n\n

我认为 NLTK 只让你定义上下文无关语法，所以我在这里给你留下一个我做的小例子：

\n\n

from nltk import CFG\nfrom nltk.parse.generate import generate\n\n#Define your grammar from string\n#You can define it using other methods, but I only know this xD\n\ngrammar = CFG.fromstring(""" S -> NP VP\n  VP -> V NP\n  V -> "mata" | "roba"\n  NP -> Det N | NP NP\n  Det -> "un" | "el" | "con" | "a" | "una"\n  N -> "beb\xc3\xa9" | "ladr\xc3\xb3n" | "Obama" | "perrete" | "navastola" | "navaja" | "pistola" """)\n\n\'\'\' This grammar creates sentences like:\n        El beb\xc3\xa9 roba a Obama\n        Baby steals Obama (in spanish)\n\'\'\'\n#With this we "create" all the possible combinations\ngrammar.productions()\n\n#Here you can see all the productions (sentences) with 5 words\n#created with this grammar\nfor production in generate(grammar, depth=5):\n    print(\' \'.join(production))\n

\n

Answer 2

您可以通过滥用解析器将其变成生成器来做到这一点。

首先，为您的语言构建一个递归解析器。（请参阅我关于如何做到这一点的答案）。 当您阅读该内容时请暂停......我现在假设您了解如何做到这一点。

您会注意到，这样的解析器充满了从一个语法规则的解析器函数到其他语法规则或原始标记匹配器的其他函数的调用。

您想要做的是修改每个调用，以决定如果在进行调用之前函数中仍然有一些替代方案可用，则它将以较低的概率返回“true”。如果调用判定为 false，控制权就会简单地传递到解析器的另一部分。如果调用判定为真，则它实际上进行调用；被调用者现在必须以返回 true 并生成相应源代码的方式进行操作。在某些时候，这将强制对令牌读取器的调用返回 true；令牌读取器被发出随机令牌的打印函数取代。当您这样做时，实际发生的情况是，决定某件事是否为真的调用现在变成了调用；我们不再需要返回状态，因为被调用的函数必须返回 true。这将我们的functions-returning-bools 更改为procedures-returning-void。请参阅下面的示例..

让我们尝试使用简单编程语言p的简单语法来尝试一个示例：

p = s ;
s = v '=' e ;
s = 'if' e 'then' s ;
e = v ;
e = v '+' n ;

好的，我们的p递归下降解析器 （我不是 Python 人员，所以这是伪代码）：

function p() { return s(); } // no alternatives
function s() { if v()
               then if match("=")
                    then return e()
                    else return false;
               else if match("if")
                    then if e()
                         then if match("then")
                              then return s()
                              else return false;
                         else return false;
                    else return false;
              }
 function e() { if v()
                then if match ("+")
                     then if n()
                     else return true
                else return false
              }
 function v() { return match_variable_name(); }
 function n() { return match_integer_constant(); }

好的，现在让我们使用随机返回 true 或 false 的硬币翻转函数来强制调用决定它们是否会成功。任何以下形式的构造：

          if <testsomething> then <action x> else <action y>

变成：

          if flip() then  { <testsomething> <action x> } else <action y>

以及以下形式的任何构造：

          if  <testsomething> then <action x> else return false

变成

          { <testsomething>; <action x> }

因为如果我们要生成可解析的程序，它就必须成功。

如果testsomething是对另一个语法规则的函数调用，我们就不管它。对原始标记匹配的函数调用变成打印语句：如果testsomething是“match(Q)”，则将其替换为“print(Q)”；这就是实际生成程序片段的内容。

procedure p() { s(); } // no choice, this has to succeed
procedure s() { if flip() // flip == true --> v must succeed
               then { v();
                      print("=") // because if no match, procedure fails
                      e();
                    }
               else { print("if")  // if we get here, must succeed
                      e();
                      print("then"); // because match("then") must succeed
                      s();
                    }
              }
 procedure e() { v(); // because there are no alternatives
                 if flip() then { print("+");
                                  n();
                                }
                 else { }
               }
 procedure v() { print_variable_name(); }
 procedure n() { print_integer_constant(); }

请注意，变量名称和整数常量的标记识别器现在变成打印随机变量名称/常量的打印过程。这本质上也只是将“翻转”推入这些程序中。

现在，这可能会打印任意长的程序，因为 Flip 可能会强制 s 重复调用自身。如果翻转是 50-50，则 10 次递归的机会是千分之一，所以可能没问题。但是，您可能会决定根据迄今为止生成的输出的大小或任何递归的深度来偏向每个单独的翻转以选择较短的短语。

现在，这在一般情况下不会产生语义正确的程序。那是因为我们的解析器是“上下文无关的”；生成的代码的某一部分不受其他部分强制的约束。例如，如果您的语言必须在使用变量之前声明它，则此方案不能保证在 randome-var-X 出现在表达式中之前生成 random-var-X 的声明。

没有简单的方法可以解决这个问题，因为语言语义并不能保证是“简单的”。只是为了表明解析程序（“技术上简单”）并检查正确的语义（“任意困难”，考虑 C++），会导致生成不违反语言语义的随机程序的任何同样困难的问题。