基于yacc/bison/ANTLR语法生成随机但仍然有效的表达式

Question

可能吗？有没有可用的工具？

Answer 1

yacc 和 bison 将你的语法变成一个有限状态机。您应该能够随机遍历状态机以找到有效输入。

基本上，在每个状态下，您都可以将新令牌移到堆栈上并移动到新状态，或者根据一组有效的减少来减少堆栈中的顶部令牌。（有关其工作原理的详细信息，请参阅Bison 手册）。

您的随机生成器将遍历状态机，在每个状态下进行随机但有效的移位或减少。一旦到达最终状态，您就有了有效的输入。

对于人类可读的状态描述，您可以使用bison 的-v或--report=state选项。

恐怕我无法向您指出任何可以做到这一点的现有工具。