9

AC 程序源代码可以根据 C 语法（在 CFG 中描述）进行解析，最终变成许多 AST。我正在考虑是否存在这样的工具：它可以通过首先随机生成许多 AST 来做相反的事情，其中​​包括没有具体字符串值的令牌，只有令牌的类型，根据 CFG，然后生成具体根据正则表达式中标记的定义进行标记。

我可以想象第一步看起来像是一个迭代的非终结符替换，它是随机的，并且可以受到一定数量的迭代次数的限制。第二步只是根据正则表达式随机生成字符串。

有什么工具可以做到这一点吗？

4

4 回答 4

5

“数据生成语言” DGL做到了这一点，增加了对输出语法中产生的概率进行加权的能力。

通常，递归下降解析器可以直接重写为一组递归过程来生成，而不是解析/识别语言。

于 2011-01-05T14:50:01.830 回答
1

给定一种语言的上下文无关文法，可以生成与文法匹配的随机字符串。

例如，nearley解析器生成器包括可以从语法生成字符串的“解解析器”的实现。

使用Prolog中的定句语法可以完成相同的任务。这里给出了一个使用定从句语法的句子生成器的例子。

于 2017-01-02T23:07:38.690 回答
0

如果你有一个规范化形式的语法模型（所有规则都是这样）：

 LHS = RHS1 RHS2 ...  RHSn ;

和语言漂亮的打印机（例如，AST 到文本转换工具），您可以很容易地构建其中之一。

只需从作为单元树的目标符号开始。

  Repeat until no nonterminals are left:
    Pick a nonterminal N in the tree;
       Expand by adding children for the right hand side of any rule
       whose left-hand side matches the nonterminal N

对于携带值的终端（例如，变量名、数字、字符串……），您必须生成随机内容。

上述算法的一个复杂之处在于它没有明确终止。你真正想要做的是在你的树的大小上选择一些限制，然后运行算法，直到所有的非终结符都消失或者你超过了限制。在后一种情况下，回溯，撤消最后的替换，然后尝试其他方法。这使您可以对确定大小的 AST 进行有界深度优先搜索。

然后漂亮地打印结果。它的漂亮打印机部分很难做对。

[你可以自己构建所有这些东西，包括漂亮的打印机，但这是相当多的工作。我以语言参数化的方式直接构建了包含所有这些机制的工具；见我的简历]。

即使是格式良好的 AST，一个令人讨厌的问题是它们可能是荒谬的。对于不允许这样做的语言，您可能会生成整数 X 的声明，并为其分配一个字符串文字值。您可能可以消除一些简单的问题，但语言语义可能非常复杂，以 C++ 为例。确保你最终得到一个语义上有意义的程序是非常困难的。本质上，您必须解析结果文本，并对其执行名称和类型解析/检查。对于 C++，您需要一个完整的 C++ 前端。

于 2017-01-03T00:19:56.370 回答
0

随机生成的问题在于，对于许多 CFG，输出字符串的预期长度是无限的（使用对应于非终结符号的生成函数和对应于语法规则的方程可以轻松计算预期长度） ; 你必须以某种方式控制产生式的相对概率以保证收敛；例如，有时，将非终结符的每个产生式规则与其 RHS 的长度成反比就足够了

关于这个主题的更多信息：Noam Chomsky, Marcel-Paul Sch\"{u}tzenberger, ``上下文无关语言的代数理论'', pp.\ 118-161 in P. Braffort 和 D. Hirschberg (eds.), Computer Programming and Formal Systems, North-Holland (1963)（参见关于 Chomsky–Schützenberger 枚举定理的维基百科条目）

于 2017-03-25T21:32:02.047 回答