Expressão regular para gramática livre de contexto

7

Alguém sabe se existe um algoritmo para escrever diretamente a gramática livre de contexto que gera uma determinada expressão regular?

Marco L.
fonte
5
Deseja o CFG que gera as cadeias de expressão regulares válidas como "a * (a | b)" ou deseja o CFG que gera cadeias de caracteres como "aaaaab", dada a expressão regular "a * (a | b)"?
precisa saber é o seguinte

Respostas:

9

Suponho que você deseja obter uma gramática que gere o mesmo idioma da expressão regular fornecida.

Você pode conseguir isso seguindo as seguintes etapas:

  1. Traduza a expressão regular em um NFA.
  2. Traduza o NFA em uma gramática regular (direita).

Ambas as traduções são padrão e são abordadas em livros básicos sobre idiomas e autômatos formais. Observe que qualquer gramática comum também é livre de contexto.

Rafael
fonte
Sim, melhor que a minha resposta.
Hendrik Jan
4

Sim. Dou a resposta de alto nível, sem muitos detalhes.

Primeiro você tem que analisar as expressões. Isso pode ser feito usando um analisador decente recursivo simples. Vários exemplos na web.

Em seguida, você deve adicionar regras "semânticas" ao analisador, ao retornar da recursão. Esses são padrões em qualquer curso formal de teoria da linguagem. E seS1 e S2 são não terminais que geram expressões E1 e E2 então podemos gerar E1+E2 de S e as regras SS1, SS2. Nós podemos gerar concatenaçãoE1E2 de S e a regra SS1S2. E1 de S e as regras SS1S, Sλ. Supondo que escolhemos novos termos não terminais de cada vez.

Hendrik Jan
fonte
1

Como uma resposta anterior, presumo que você deseja obter uma gramática que gere o mesmo idioma da expressão regular fornecida r.

Um algoritmo recursivo para construir uma gramática livre de contexto G com L(G)=L(r) é o seguinte:

  • E se r=, produza uma gramática sem regras de produção (ou SS se deve ter uma regra).
  • E se r=Λ, resultado SΛ.
  • E se r=a (a expressão é apenas uma letra), saída Sa.
  • E se r=ab (união, também anotada como + ou |): construa gramáticas separadas a e b com símbolos de início Sa e Sb, combine-os e adicione SSaSb.
  • E se r=lr (concatenação, também anotada como ): construa gramáticas separadas para l e r com símbolos de início Sl e Sr, combine-os e adicione SSlSr.
  • E se r=x (Estrela Kleene): construa uma gramática para x com símbolo de início Sx e adicione SSxSΛ.

Isso é essencialmente equivalente à resposta de Hendrik, mas com mais detalhes que podem ser úteis.

Jonas Kölker
fonte