從非遞歸上下文無關語法生成有限語言的算法

我正在尋找一種算法來從非遞歸上下文無關語法生成完整的有限語言。該應用程序是爲測試自動化生成一組可能的場景。在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

從非遞歸上下文無關語法生成有限語言的算法

回答

相關問題