从非递归上下文无关语法生成有限语言的算法

我正在寻找一种算法来从非递归上下文无关语法生成完整的有限语言。该应用程序是为测试自动化生成一组可能的场景。在EBNF从非递归上下文无关语法生成有限语言的算法

实施例的语法（S是开始规则）：

S = Sender, Receiver; 
Sender = Human | Machine; 
Human = "user-type-1" | "user-type-2" 
Machine = Access, Protocol; 
Access = "internal" | "external"; 
Protocol = "soap" | "smtp"; 
Receiver = "local" | "remote";

应该产生一组类似的句子：

user-type-1 local 
internal soap local 
external smtp remote

实施例和文献我发现迄今refered到随机代基于递归语法的例子。但我的问题更简单。欢迎所有提示，名称或出版物链接。

感谢，

来源

2017-02-20 user186128

所以，你基本上想要在右侧的套件的笛卡尔积？ https://en.wikipedia.org/wiki/Cartesian_product – IVlad

U可以通过简单的递归方法生成所有句子。什么都有你尝试btw？ –

一种方法是定义在编程语言语法，然后写代码来遍历所有的可能性。你的语法使用变量和三项建设规定：lit(x)代表字面像"local"，alt(a, b, c, ...)它代表一种备选方案的选择a，b，c，...和seq(a, b, ..., z)代表的一两件事从a序列，级联从b等一件事。

这是你的语法形式。

Protocol = alt(lit("soap"), lit("smtp")) 
Receiver = alt(lit("local"), lit("remote")) 
Access = alt(lit("internal"), lit("external")) 
Human = alt(lit("user-type-1"), lit("user-type-2")) 
Machine = seq(Access, Protocol) 
Sender = alt(Human, Machine) 
S = seq(Sender, Receiver)

这里是一个使用精心挑选的定义为alt，seq和3210，使每个生产规则生成它的所有可能性的功能有一定满（Python）的代码：

import itertools 

def seq(*xs): 
    def r(): 
     for f in itertools.product(*[x() for x in xs]): 
      yield ' '.join(f) 
    return r 

def alt(*xs): 
    def r(): 
     for x in xs: 
      for f in x(): 
       yield f 
    return r 

def lit(x): 
    def r(): 
     yield x 
    return r 

Protocol = alt(lit("soap"), lit("smtp")) 
Receiver = alt(lit("local"), lit("remote")) 
Access = alt(lit("internal"), lit("external")) 
Human = alt(lit("user-type-1"), lit("user-type-2")) 
Machine = seq(Access, Protocol) 
Sender = alt(Human, Machine) 
S = seq(Sender, Receiver) 

for s in S(): 
    print s

来源

2017-02-20 16:53:59

你可以递归生成一棵树，树的分支将根据语法的规则表示派生词，并且叶子将用语言的语言表示词。恢复整个有限语言就像在生成叶子时一样简单。

将每个节点表示为有序的符号集合（终端或非终端）。对于每个非终结符，递归地下降到一组新的节点，在该节点处进行每个可能的替换。继续，直到您的列表仅包含终端符号，然后输出与您的节点对应的符号按顺序串联。您的初始节点将始终为[S]。例如：

S = Sender, Receiver; 
Sender = Human | Machine; 
Human = "user-type-1" | "user-type-2" 
Machine = Access, Protocol; 
Access = "internal" | "external"; 
Protocol = "soap" | "smtp"; 
Receiver = "local" | "remote"; 

[S] 
[Sender, ",", Receiver] 
    [Human, ",", Receiver] 
    ["user-type-1", ",", Receiver] 
    ["user-type-1", ",", "local"] *** 
    ["user-type-1", ",", "remote"] *** 
    ["user-type-2", ",", Receiver] 
    ["user-type-2", ",", "local"] *** 
    ["user-type-2", ",", "remote"] *** 
    [Machine, ",", Receiver] 
    [Access, ",", Protocol, ",", Receiver] 
    ["internal", ",", Protocol, ",", Receiver] 
    ["internal", ",", "soap", ",", Receiver] 
     ["internal", ",", "soap", ",", "local"] *** 
     ["internal", ",", "soap", ",", "remote"] *** 
    ["internal", ",", "smtp", ",", Receiver] 
     ["internal", ",", "smtp", ",", "local"] *** 
     ["internal", ",", "smtp", ",", "remote"] *** 
    ["external", ",", Protocol, ",", Receiver] 
    ["external", ",", "soap", ",", Receiver] 
     ["external", ",", "soap", ",", "local"] *** 
     ["external", ",", "soap", ",", "remote"] *** 
    ["external", ",", "smtp", ",", Receiver] 
     ["external", ",", "smtp", ",", "local"] *** 
     ["external", ",", "smtp", ",", "remote"] ***

来源

2017-02-27 22:00:20 Patrick87

从非递归上下文无关语法生成有限语言的算法

回答

相关问题