Алгоритм генерации конечного языка из нерекурсивной контекстно-свободной грамматики

Question

Я ищу алгоритм для генерации полного конечного языка из нерекурсивной контекстно-свободной грамматики. Приложение представляет собой набор возможных сценариев автоматизации тестирования.

Пример грамматики в 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 в рандомизированном поколения примеров на основе рекурсивных грамматик. Но моя проблема более простая. Все приветствия, имена или ссылки на публикации приветствуются.

Спасибо,

С.

Answer 1

Один из способов заключается в определении грамматики на языке программирования, а затем написать код, чтобы перебрать все возможности. Ваша грамматика задается с помощью переменных и три конструкции: 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) 

А вот некоторые полный (Python) код, который использует тщательно подобранные определения для alt, seq и lit сделать каждое производство исключает функцию, которая создает все свои возможности:

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 

Answer 2

Вы можете рекурсивно сгенерируйте дерево, ветви которого будут представлять дифференцирования в соответствии с правилами грамматики и листья которых будут представлять слова на языке грамматики. Восстановление всего конечного языка так же просто, как сбережение листьев при их создании.

Представляют каждый узел в виде упорядоченного набора символов (терминалов или нетерминалов). Для каждого нетерминала рекурсивно спускайтесь к новому набору узлов, где производится всякая возможная замена. Продолжайте, пока ваш список не будет содержать только символы терминала, а затем выведите конкатенацию в последовательности символов, соответствующих вашему узлу. Ваш начальный узел всегда будет [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"] ***