如何从 BNF 生成随机程序

Question

我知道我的问题听起来有点含糊，但我在网上找不到任何教程。我不是要答案，而是要更多的解释。 BNF的一个例子：

<prog> ::= “int main() { <stat_list> return 0; }”
<stat_list>  ::= <stat>
         | <stat_list> <stat>
<stat>       ::= <cmpd_stat>
         | <if_stat>
         | <iter_stat>
         | <assgn_stat>
         | <decl_stat>
<cmpd_stat>  ::= { <stat_list> }
<if_stat>    ::= if ( <exp> ) <stat>
         | if ( <exp> ) <cmpd_stat>
         | if ( <exp> ) <stat> else <stat>
         | if ( <exp> ) <cmpd_stat> else <stat>
         | if ( <exp> ) <stat> else <cmpd_stat>
         | if ( <exp> ) <cmpd_stat> else <cmpd_stat>

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

Answer 1

NLTK has a package for grammars。通常用于句子分析，但没有什么能阻止您使用它来创建遵循该规则的 "program"。

我认为 NLTK 只允许你定义一个上下文无关文法，所以我留给你一个我做的小例子：

from nltk import CFG
from nltk.parse.generate import generate

#Define your grammar from string
#You can define it using other methods, but I only know this xD

grammar = CFG.fromstring(""" S -> NP VP
  VP -> V NP
  V -> "mata" | "roba"
  NP -> Det N | NP NP
  Det -> "un" | "el" | "con" | "a" | "una"
  N -> "bebé" | "ladrón" | "Obama" | "perrete" | "navastola" | "navaja" | "pistola" """)

''' This grammar creates sentences like:
        El bebé roba a Obama
        Baby steals Obama (in spanish)
'''
#With this we "create" all the possible combinations
grammar.productions()

#Here you can see all the productions (sentences) with 5 words
#created with this grammar
for production in generate(grammar, depth=5):
    print(' '.join(production))

Answer 2

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

首先，为您的语言构建一个递归解析器。 (See my SO answer on how to do just that)。 在阅读时暂停....我现在假设您了解如何做到这一点。

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

您想要做的是修改每个调用，以决定它 return "true" 如果在调用之前函数中仍有一些替代方法可用，则它的可能性很小。如果调用决定为 false，则控制权简单地传递给解析器的另一部分。如果调用判定为真，它实际上会调用；被调用方现在必须以 return 为真并生成相应源代码的方式进行操作。在某些时候，这将强制对令牌 reader 的调用为 return true；令牌 reader 被发出随机令牌的打印函数替换。当你这样做时实际发生的是，决定某事是否为真的电话现在简单地变成了电话；我们不再需要 return 状态，因为调用的函数必须 return 为真。这将我们的函数-returning-bools 更改为过程-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(); }

好的，现在让我们强制调用使用随机 return 真或假的抛硬币函数来决定它们是否会成功。任何形式的结构：

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

请注意，变量名和整数常量的标记识别器现在变成了打印随机变量的打印程序 names/constants。这实际上也只是将 "flip" 推入这些程序。

现在这可能会打印任意长的程序，因为 flip 可能会强制 s 重复调用自己。如果 flip 是 50-50，那么 1000 次递归中有 1 次递归的机会可能没问题。但是，您可能会根据到目前为止生成的输出的大小或任何递归的深度，决定让每个单独的翻转偏向于选择较短的短语。

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

没有简单的方法来解决这个问题，因为语言语义不保证 "easy"。只是表明解析程序（"technically easy"）和检查正确的语义（"arbitrarily hard"，考虑 C++），会导致生成不违反语言语义的随机程序的任何同样困难的问题。

如何从 BNF 生成随机程序

How to generate random programs from BNF

python

parsing

code-generation

bnf