¿Cómo genero oraciones a partir de una gramática formal?

https://stackoverflow.com/questions/603687

03-07-2019
|

Pregunta

¿Cuál es una forma común de generar oraciones a partir de una gramática?

Quiero un algoritmo que sea algo opuesto a un analizador sintáctico. Es decir, dada una gramática formal libre de contexto (digamos LL), quiero generar una oración arbitraria que se ajuste a esa gramática. Uso oración aquí para referirme a cualquier cuerpo de texto válido, por lo que en realidad puede ser un programa completo (incluso si no tiene ningún sentido & # 8212; siempre que sea sintácticamente correcto) .

Ejemplo de gramática:

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

Ejemplo generado programa :

import jkhbhhuob
import aaaaa888_

namespace u8nFGubgykb
{ class ui0op_np { ... }
}

Solución

No sé si hay un " común " algoritmo para hacer esto. La generación aleatoria de programas se utiliza en la programación genética para que pueda buscar un sistema GP basado en gramática y ver cómo manejan la generación de programas. Haría un algoritmo de generación de reglas recursivas como el pseudocódigo:

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);
  }
}

Esto supone que has leído todas las partes en alguna estructura de datos. También necesitaría manejar las repeticiones (generar aleatoriamente el número de veces que ocurren) y las reglas opcionales (lanzar una moneda para ver si están allí o no).

Editar: Ah, y si la regla tiene más de una opción, simplemente elegiría una de las opciones y la procesaría de la misma manera. Entonces, si alguna regla fuera (Literal | Variable), elegiría aleatoriamente entre las dos.

Otros consejos

Aquí hay un ejemplo de Python que usa 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()))

El ejemplo está adaptado del libro . Las oraciones generadas son sintácticamente correctas pero siguen siendo un galimatías total.

Su solución debe seguir la estructura inductiva de la gramática. ¿Cómo se genera un enunciado aleatorio para cada uno de los siguientes?

Símbolo de terminal
Símbolo no terminal
Secuencia de lados derechos
Elección de lados derechos
Cierre en estrella de los lados derechos

Todo esto será mucho más claro si escribe la estructura de datos que usa para representar una gramática. La estructura de su conjunto de funciones generadoras mutuamente recursivas reflejará esa estructura de datos muy de cerca.

Tratar con la recursión infinita es un poco incierto. La forma más fácil es generar una secuencia de enunciados y mantener un límite de profundidad. O si está utilizando un lenguaje vago como Haskell, puede generar todos enunciados y eliminar tantos finitos como desee (un problema más complicado que la pregunta original, pero muy entretenido).

Fuera de mi cabeza:

Trabajaría recursivamente (básicamente lo contrario de un analizador recursivo decente) usando algunas heurísticas sobre qué hacer con los rangos ((...): probablemente elegir al azar) opcionales (?: ver [], a continuación), repeticiones ('' ¿Distribución de Poisson?). Los literales ("...") son simples escritos en la salida, y los subtokens (`& Lt; ... & Gt; ') generan una recursión.

Esto no debería ser demasiado difícil a menos que desee garantizar algún tipo de cobertura completa. Incluso entonces, solo generar un grupo de datos sería una ayuda ...

[*] Debe incluir opciones menos del 50% del tiempo para evitar una regresión infinita al procesar reglas como

 nonterm:  otherstuff <nonterm>?

Buena captura por zócalo .

Del mismo modo con las repeticiones, arroje una distribución que converja fuertemente.

Tendrá que analizar primero la gramática de entrada si se presenta en forma BNF como aquí. Lo más simple sería usar un mapeo (name, string), luego comenzar con el token de nivel más alto (que podría suponer que significa el primero ...).

Esto te da:

(" programa " ;, " < importa > NEWLINE? < espacio de nombres > " )

(" importaciones " ;, (" import " < identificador > NEWLINE) *)

...

Comienza con " programa " ;, presione " < importa > " entonces repites ... al regresar, hist " NEWLINE? " ;, así que tira los dados y escribe o no, presiona " < namespace > " tan recurrente ... al regreso ya terminaste.

Me encuentro sospechando que esto se ha hecho antes. Si solo necesita la salida, buscaría en la web ... Quizás http: / /portal.acm.org/citation.cfm?doid=966137.966142 , aunque la gran cantidad de generadores de analizadores abarrotan el espacio de búsqueda ... Pruebe este documento también .

Por cierto, su universidad local probablemente tenga suscripciones en línea a estas revistas, por lo que puede obtenerlas de forma gratuita conectándose a la biblioteca.

El problema que tendrá es que la naturaleza recursiva del gráfico es tal que puede generar gramáticas correctas de tamaño infinito. Probablemente desee hacer algo como configurar un hash de tipos de nodos en su gramática con recuentos y límites de cuántas veces se está permitiendo golpear ese nodo. Luego, busque primero en profundidad el contenido de su corazón.

Mi primera sugerencia sería una primera búsqueda amplia. Simplemente configure un gráfico de reglas y busque a través de ellas. Comenzarás a escupir programas a partir de los más pequeños posibles, y lentamente crecerás. Sin embargo, es probable que descubras que tu gramática escupirá exponencialmente más programas para un número determinado de reglas y es probable que no obtengas más de 30 tokens en un programa usando un DFS.

El problema con una primera búsqueda en profundidad es que la segunda vez que tenga una regla recursiva a la izquierda, su búsqueda se atascará en un bucle infinito.

Otro gran problema es que los programas sintácticamente correctos están muy lejos de los programas semánticamente correctos. Es probable que la generación del último tipo sea completamente inviable en todos los casos, excepto en los más básicos.

Como de costumbre, yo & # 8217; voy a aconsejar no reinventar la rueda. & # 8217; he escrito uno de estos para el ensamblador ARM, pero & # 8217; estoy registrado como lamentando ( Software: práctica y experiencia abril de 2007):

& # 8220; En retrospectiva, un generador de expresiones listo para usar debería haberse usado para generar instrucciones de ensamblaje ARM aleatorias para la comparación. En cambio, se creó un script Perl de forma incremental, tomando cada definición de instrucción ARM y generando instancias. Sin embargo, una ventaja del enfoque interno incremental fue que las sustituciones simples detectaron errores simples, y la búsqueda de errores podía continuar de forma incremental. & # 8221;

I & # 8217; me temo que no & # 8217; no recuerdo lo que me hizo cambiar de opinión, y dudo que sea relevante para sus necesidades específicas, pero sugiero buscar más para un preexistente solución. Se requiere menos disciplina para escribir cosas como esta, pero siempre lleva más tiempo de lo esperado.

no es una respuesta, pero revisa la entrada de wikipedia sobre la generación de gramática: http://en.wikipedia.org/wiki/Context-free_grammar_generation_algorithms

describió algunos algoritmos comunes utilizados.

Si bien la idea es buena (lo he pensado muchas veces antes), la realidad es que sin algunos datos de muestra y / o toneladas de restricciones del generador / límites de esfuerzo, es un trabajo bastante grande.

Uno podría encontrar más fácil escribir muestras a mano. :)

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow