Como faço para gerar frases de uma gramática formal?

Question

O que é uma maneira comum de gerar frases de uma gramática?

Eu quero um algoritmo que é uma espécie de oposto de um analisador. Isto é, dado uma gramática formal livre de contexto (dizem LL), eu quero gerar uma sentença arbitrária em conformidade com que a gramática. Eu uso frase aqui para significar qualquer corpo válida de texto, para que ele possa realmente ser um programa todo (mesmo que não faz qualquer sentido, contanto que ele é syntactially correto).

Exemplo secundária:

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

Exemplo gerado programa :

import jkhbhhuob
import aaaaa888_

namespace u8nFGubgykb
{ class ui0op_np { ... }
}

Answer 1

Eu não sei que há um algoritmo de "comum" para fazer isso. Aleatório geração programa é usado em programação genética para que você possa olhar para um sistema GP gramática base e ver como eles lidam com geração programa. Eu faria um algoritmo de geração de regra recursiva como o pseudo-có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);
  }
}

Isso pressupõe que você leu em todas as partes em alguma estrutura de dados. Também seria necessário para lidar com as repetições (aleatoriamente gerar o número de vezes que eles ocorrem) e regras opcionais (jogar uma moeda para ver se eles estão lá ou não).

---

Edit: Ah, e se a regra tem mais de uma opção, você apenas escolher uma das opções para ir com, e processá-lo da mesma maneira. Então, se alguma regra foi. (Literal | Variável), você escolheria aleatoriamente entre os dois

Answer 2

Aqui está um exemplo Python usando o 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()))

O exemplo é adaptado a partir do livro . As frases geradas são sintaticamente correto, mas ainda jargão total.

Answer 3

A sua solução deve seguir a estrutura indutiva da gramática. Como você gerar um discurso aleatório para cada um dos seguintes?

• símbolo Terminal
• símbolo não-terminal
• Seqüência de lados direitos
• Escolha de lados direitos
• fechamento Estrela de lados direitos

Isso tudo será muito mais clara se você escrever para baixo a estrutura de dados que você usa para representar uma gramática. A estrutura do seu conjunto de funções de gerador mutuamente recursiva irá espelhar essa estrutura de dados muito de perto.

Lidar com recursividade infinita é um pouco arriscada. A maneira mais fácil é gerar um fluxo de enunciados e manter um corte profundo. Ou se você estiver usando uma linguagem de preguiçoso como Haskell você pode gerar todas declarações e descolar como muitos outros finitos como desejar (um problema mais complicado do que a pergunta original, mas muito divertido).

Answer 4

Em cima da minha cabeça:

Eu trabalharia de forma recursiva (basicamente o oposto de um analisador decente recursiva), utilizando algumas heurísticas sobre o que fazer com faixas ((...): provavelmente escolher aleatoriamente) opcionais (?: ver [], abaixo), repetições ( '' distribuição de Poisson?). Literais ("...") são simples escrito na saída, e subtokens ( `<...> ') gerar uma recursão.

Isto não deve ser muito difícil, a menos que você quiser garantir algum tipo de cobertura completa. Mesmo assim, apenas gerando um bando de dados seria uma ajuda ...

---

[*] Você precisa incluir opcionais menos de 50% do tempo para evitar regressão infinita durante o processamento de regras como

 nonterm:  otherstuff <nonterm>?

Boa captura por plinto .

Da mesma forma com repetições, jogue um distribuições que converge fortemente.

---

Você precisa analisar a gramática de entrada primeiro se ele é apresentado de uma forma BNF como aqui. coisa mais simples a fazer seria usar um (name, string) mapeamento, em seguida, começar com o mais alto nível de token (que se poderia supor meios o primeiro ...).

Isto dá-lhe:

( "programa", " NEWLINE? ")

( "importações", ( "importar" NEWLINE) *)

...

O que você comece com "programa", hit "" para que se repetem ... em voltar, hist "NEWLINE?", Então lançar os dados e escrever ou não, hit "" tão RECUR ... em troca, você está feito.

---

I encontrar o meu eu suspeitar que isso tenha sido feito antes. Se você só precisa a saída, eu pesquisar na web ... Talvez http: / /portal.acm.org/citation.cfm?doid=966137.966142 , embora o grande número de geradores de analisador lá fora atravancam o espaço de busca ... Tente neste artigo , também.

BTW-- Você universidade local provavelmente tem inscrições on-line para essas revistas, para que possa obtê-los gratuitamente por ligar na biblioteca.

Answer 5

O problema que você terá é que a natureza recursiva do gráfico é tal que você pode gerar gramáticas corretas de tamanho infinito. Você provavelmente vai querer fazer algo como criar um hash de tipos de nó em sua gramática com contagens e limites de quantas vezes você está permitindo-se a bater esse nó. primeira pesquisa, em seguida, profundidade ao conteúdo do seu coração.

Answer 6

Minha primeira sugestão seria uma busca em largura. Basta configurar um gráfico de regras e procurar por eles. Você vai começar a cuspir programas a partir dos menores possíveis, e lentamente ficando maior. Você provavelmente vai encontrar, no entanto, que a sua gramática vai cuspir exponencialmente mais programas para um determinado número de regras e você provavelmente não vai passar por 30 ou mais fichas em um programa usando um DFS.

O problema com uma primeira busca em profundidade é que o segundo você tem uma regra deixou-recursiva, sua pesquisa vai ficar preso em um loop infinito.

Outro grande problema é que os programas sintaticamente corretas são um longo caminho a partir de programas semanticamente corretos. Gerando o último tipo é provável completamente inviável em todos, mas o mais básico casos.

Answer 7

Como de costume, eu vou aconselhar contra reinventar a roda. Eu escrevi um destes para ARM assembler, mas estou no registro como lamentando-lo ( Software: prática e experiência Abril de 2007):

“Em retrospecto, um gerador de expressão off-the-shelf deveria ter sido usado para gerar instruções de montagem ARM aleatória para comparação. Em vez de um script Perl foi construído de forma incremental, tendo cada definição de instruções ARM e gerando casos. Uma vantagem, no entanto, do incremento in-house abordagem foi que simples substituições detectados erros simples, ea caça bug poderia proceder de forma incremental.”

Eu tenho medo que eu não me lembro o que me fez mudar de idéia, e eu duvido que seria relevante para as suas necessidades específicas, mas eu sugiro olhar mais difícil para uma solução pré-existente. Ele requer menos disciplina para material da escrita assim mesmo, mas sempre leva mais tempo do que o esperado.

Answer 8

Não é uma resposta, mas verificar a entrada da Wikipedia sobre geração de gramática: http://en.wikipedia.org/wiki/Context-free_grammar_generation_algorithms

descreveu alguns algoritmos comuns utilizados.

Answer 9

Embora a idéia é bom (I ter pensado nisso muitas vezes antes), a realidade é que, sem alguns dados da amostra e / ou toneladas de restrições gerador / limites do esforço, é bastante um grande trabalho.

Um pôde apenas encontrar escrevendo amostras com a mão mais fácil. :)