Comment générer des phrases à partir d'une grammaire formelle?

https://stackoverflow.com/questions/603687

03-07-2019
|

Question

Quel est le moyen courant de générer des phrases à partir d'une grammaire?

Je veux un algorithme qui est en quelque sorte l'opposé d'un analyseur syntaxique. Autrement dit, étant donné une grammaire formelle sans contexte (disons LL), je souhaite générer une phrase arbitraire conforme à cette grammaire. J'utilise phrase ici pour désigner tout corps de texte valide. Il peut donc s'agir d'un programme complet (même si cela n'a aucun sens & # 8212; tant que la syntaxe est correcte) .

Exemple de grammaire:

program   : <imports> NEWLINE? <namespace>
imports   : ("import" <identifier> NEWLINE)* 
namespace : "namespace " <identifier> NEWLINE "{" <classes> "}" 
identifier: (A-Za-z_) (A-Za-z0-9_)*
...

Exemple programme généré :

import jkhbhhuob
import aaaaa888_

namespace u8nFGubgykb
{ class ui0op_np { ... }
}

La solution

Je ne sais pas s'il existe un " commun " algorithme pour le faire. La génération de programme aléatoire est utilisée dans la programmation génétique afin que vous puissiez rechercher un système de généraliste basé sur la grammaire et voir comment ils gèrent la génération de programme. Je ferais un algorithme de génération de règles récursif comme le pseudo-code:

void GenerateRule(someRule)
{
  foreach (part in someRule.Parts)
  {
    if (part.IsLiteral) OutputLiteral(part);
    if (part.IsIdentifier) Output(GenerateIdentifier(part)));
    if (part.IsRule) GenerateRule(part.Rule);
  }
}

Cela suppose que vous ayez lu toutes les parties dans une structure de données. Vous devez également gérer les répétitions (générer aléatoirement le nombre de fois qu'elles se produisent) et les règles optionnelles (lancer une pièce pour voir si elles sont présentes ou non).

Éditer: Oh, et si la règle a plus d’une option, il vous suffira de choisir l’une des options à utiliser et de la traiter de la même manière. Donc, si une règle était (Literal | Variable), vous choisiriez au hasard entre les deux.

Autres conseils

Voici un exemple Python utilisant le NLTK :

from nltk import parse_cfg, ChartParser
from random import choice

def produce(grammar, symbol):
    words = []
    productions = grammar.productions(lhs = symbol)
    production = choice(productions)
    for sym in production.rhs():
        if isinstance(sym, str):
            words.append(sym)
        else:
            words.extend(produce(grammar, sym))
    return words

grammar = parse_cfg('''
S -> NP VP
PP -> P NP
NP -> Det N | Det N PP | 'I'
VP -> V NP | VP PP
V -> 'shot' | 'killed' | 'wounded'
Det -> 'an' | 'my' 
N -> 'elephant' | 'pajamas' | 'cat' | 'dog'
P -> 'in' | 'outside'
''')

parser = ChartParser(grammar)

gr = parser.grammar()
print ' '.join(produce(gr, gr.start()))

L'exemple est adapté du livre . Les phrases générées sont syntaxiquement correctes mais restent du charabia total.

Votre solution doit suivre la structure inductive de la grammaire. Comment générez-vous un énoncé aléatoire pour chacun des éléments suivants?

Symbole du terminal
Symbole non terminal
Séquence des côtés droits
Choix du côté droit
Fermeture en étoile du côté droit

Tout cela sera beaucoup plus clair si vous écrivez la structure de données que vous utilisez pour représenter une grammaire. La structure de votre ensemble de fonctions de générateur mutuellement récursives reflétera très étroitement cette structure de données.

Faire face à une récursion infinie est un peu risqué. Le moyen le plus simple est de générer un flux d'énoncés et de conserver une profondeur de coupe. Ou, si vous utilisez un langage paresseux comme Haskell, vous pouvez générer toutes toutes les expressions et en enlever autant que vous le souhaitez (un problème plus épineux que la question initiale, mais très amusant).

De mémoire:

Je travaillerais de manière récursive (fondamentalement à l'opposé d'un analyseur syntaxique décent récursif) en utilisant des heuristiques sur l'utilisation des plages ((...): choisir probablement au hasard) (?: voir [], ci-dessous), répétitions ('' distribution de Poisson?). Les littéraux ("...") sont simplement écrits dans la sortie et les sous-octets (`& Lt; ... & Gt; ') génèrent une récursivité.

Cela ne devrait pas être trop difficile, sauf si vous voulez garantir une sorte de couverture complète. Même dans ce cas, le simple fait de générer un groupe de données serait une aide ...

[*] Vous devez inclure des options moins de 50% du temps pour éviter une régression infinie lors du traitement de règles telles que

 nonterm:  otherstuff <nonterm>?

Bonne prise par socle .

De même avec les répétitions, jetez une distribution qui converge fortement.

Vous devrez d'abord analyser la grammaire en entrée si elle est présentée sous une forme BNF comme ici. La chose la plus simple à faire est d'utiliser un mappage (name, string), puis de commencer par le jeton de niveau le plus élevé (ce qui pourrait signifier le premier ...).

Cela vous donne:

(" programme " ;, " < importe > NEWLINE? < espace de noms > " )

(" importations " ;, (" import " < identificateur > NEWLINE) *)

...

Vous commencez avec & "; programme &"; appuyez sur & "; &" importe > & "; alors vous revenez ... en revenant, hist & "; NEWLINE? &"; lancez donc les dés et écrivez ou non, frappez & "; < espace de noms > " alors revenez ... au retour, vous avez terminé.

Je me doute moi-même que cela a déjà été fait. Si vous avez juste besoin de la sortie, je chercherai sur le Web ... Peut-être http: / /portal.acm.org/citation.cfm?doid=966137.966142 , bien que le nombre considérable de générateurs d’analyseurs encombrent l’espace de recherche ... Essayez ce papier , aussi. / p>

BTW-- Votre université locale a probablement des abonnements en ligne à ces revues. Vous pouvez donc les obtenir gratuitement en vous connectant à la bibliothèque.

Le problème que vous allez avoir est que la nature récursive du graphe est telle que vous pouvez générer des grammaires correctes de taille infinie. Vous voudrez probablement faire quelque chose comme configurer un hachage de types de nœuds dans votre grammaire avec des comptes et des limites du nombre de fois que vous vous autorisez à frapper ce nœud. Puis approfondissez d'abord le contenu de votre coeur.

Ma première suggestion serait une première recherche en profondeur. Il vous suffit de configurer un graphique de règles et de les parcourir. Vous commencerez à créer des programmes en commençant par les plus petits possibles et en les agrandissant lentement. Vous constaterez probablement, cependant, que votre grammaire crachera de manière exponentielle plus de programmes pour un nombre donné de règles et que vous ne dépasserez probablement pas une trentaine de jetons dans un programme utilisant un système de fichiers distribués.

Le problème avec une première recherche de profondeur est que, dès que vous avez une règle récursive à gauche, votre recherche restera bloquée dans une boucle infinie.

Un autre gros problème est que les programmes syntaxiquement corrects sont loin des programmes sémantiquement corrects. La génération de ce dernier type est probablement totalement irréalisable, sauf dans les cas les plus élémentaires.

Comme d'habitude, je & # 8217; je vais vous déconseiller de réinventer la roue. J'ai & # 8217; j'en ai écrit un pour l'assembleur ARM, mais je & # 8217; j'en suis au regret de le regretter ( Logiciel: pratique et expérience avril 2007):

& # 8220; Rétrospectivement, un générateur d'expression disponible dans le commerce aurait dû être utilisé pour générer des instructions d'assemblage ARM aléatoires à des fins de comparaison. Au lieu de cela, un script Perl a été créé de manière incrémentielle, en prenant chaque définition d'instruction ARM et en générant des instances. Toutefois, l’approche incrémentielle interne a eu pour avantage que les substitutions simples détectaient des bogues simples et que la recherche de bogues pouvait se faire progressivement. & # 8221;

Je & # 8217; Je crains de ne pas & # 8217; Je ne me souviens pas de ce qui m'a fait changer d'avis, et je doute que cela réponde à vos besoins spécifiques, mais je suggère de rechercher plus fort un poste préexistant. Solution. Il faut moins de discipline pour écrire ce genre de choses, mais cela prend toujours plus de temps que prévu.

Ce n’est pas une réponse, mais consultez l’entrée Wikipedia sur la génération de la grammaire: http://en.wikipedia.org/wiki/Context-free_grammar_generation_algorithms

il décrit quelques algorithmes communs utilisés.

Bien que l’idée soit intéressante (j’y ai souvent pensé auparavant), en réalité, sans quelques exemples de données et / ou des tonnes de contraintes de générateur / limites d’effort, c’est un très gros travail.

On trouvera peut-être plus facile d’écrire des échantillons à la main. :)

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow