Algorithme pour générer un langage fini à partir d'une grammaire non contextuelle non récursive

Question

Je recherche un algorithme pour générer le langage fini complet à partir d'une grammaire non récurrente sans contexte. L'application est la génération d'un ensemble de scénarios possibles pour l'automatisation des tests.

Exemple grammaire EBNF (S est la règle de départ):

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"; 

devrait produire un ensemble de phrases telles que:

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

Exemples et la littérature que j'ai trouvé jusqu'à présent refered à la génération aléatoire d'exemples basés sur des grammaires récursives. Mais mon problème est plus simple. Tous les conseils, noms ou liens vers les publications sont les bienvenus.

Merci,

S.

Answer 1

Une façon de définir la grammaire dans un langage de programmation, puis écrire du code pour itérer sur toutes les possibilités. Votre grammaire est spécifiée en utilisant les variables et les trois constructions: lit(x) qui représente un littéral comme "local", alt(a, b, c, ...) qui représente un choix de l'une des alternatives a, b, c, ... et seq(a, b, ..., z) qui représente une séquence d'une chose de a, concaténés avec une chose de b et ainsi de suite.

Voici votre grammaire sous cette forme.

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) 

Et voici un code complet (Python) qui utilise des définitions choisies avec soin pour alt, seq et lit pour que chaque production règle une fonction qui génère toutes ses possibilités:

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

Vous pouvez récursive générer un arbre dont les branches représenteront des dérivations selon les règles de la grammaire et dont les feuilles représenteront des mots dans la langue de la grammaire. Récupérer la langue finie entière est alors aussi simple que de sauver des feuilles comme vous les générez.

Représentez chaque nœud comme une collection ordonnée de symboles (terminaux ou non-terminaux). Pour chaque non-terminal, descendez récursivement vers un nouvel ensemble de nœuds où chaque remplacement possible est effectué. Continuez jusqu'à ce que votre liste ne contienne que des symboles de terminal, puis affichez la concaténation des symboles correspondant à votre noeud. Votre noeud initial sera toujours [S]. Exemple:

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"] ***