8
votes

Convertir une expression régulière en CFG

Comment puis-je convertir une langue régulière en sa grammaire sans correspondance équivalente? Est-il nécessaire de construire la DFA correspondant à cette expression régulière ou existe-t-il une règle pour une telle conversion?

Par exemple, considérez l'expression régulière suivante

01 + 10 (11) ^*
Comment puis-je décrire la grammaire correspondant à la valeur ci-dessus?

regex grammar automata

1 commentaires

Vous vous demandez s'il existe des implémentations de bibliothèque open source utiles pour cette tâche en maintenant

3 Réponses :

6
votes

Je suppose que vous voulez dire la convertir en une grammaire formelle avec des règles de la forme V-> w, où v est un non mortminal et W est une chaîne de bornes / non-mines. Pour commencer, vous pouvez simplement dire (mélanger la syntaxe CFG et Regex): xxx pré>

où S est le symbole de démarrage. Maintenant, brisons-le un peu (et ajoutons de la clarté de clarté): p> xxx pré>

La clé est de convertir * code> ES et + es à la récursion. Premièrement, nous convertirons l'étoile kleène en un plus en insérant une règle intermédiaire qui accepte la chaîne vide: p> xxx pré>

enfin, nous convertirons + Code> Notation à la récursivité: P>

S -> 0 A 1 0 B
A -> 1
A -> A 1
B -> (empty)
B -> C
C -> 11
C -> C 11

0 commentaires

14
votes

changer A + B sur la grammaire p>

 A -> 01
 A -> 10B
 B -> (empty)
 B -> 11B

changer A * à p>
```
G -> AB
```
changer AB sur p>
```
G -> (empty)
G -> A G
```
- Utilisez des états sous forme de symboles non mortels li>
- Utilisez la langue en tant que jeu de symboles de terminaux li>
- Ajouter une transition P -> AQ pour toute transition P -> Q sur la lettre A dans l'automate d'origine li>
- Utilisez l'état initial comme symbole initial dans la grammaire li> ul> ul>

3 commentaires

Pourquoi B -> 11 au lieu de B -> B11 ?

Pourquoi changez-vous A + B dans g -> A et g -> b ? Ne + signifie-t-il "une ou plusieurs de l'expression précédente" dans Regex?
@Leonoverweel dans la théorie de la langue formelle A + B est utilisé pour désigner la somme, dans la notation de langages de programmation A | B est utilisé à la place.

2 votes En réalité, différentes grammaires CFG peuvent produire la même langue. Donc, étant donné une expression régulière (langue régulière), sa cartographie de la CFG n'est pas unique. Certainement, vous pouvez construire un CFG qui entraîne une expression régulière donnée. Les réponses ci-dessus ont montré une certaine manière pour y parvenir. J'espère que cela vous donne une idée de haut niveau. 0 commentaires

Articles qui pourrait vous intéresser : Je cherche une regex qui ne permet pas plus que le caractère étoile consécutif La fonction check_time vérifie le format de l'heure d'une horloge de 12 heures Comment convertir 10 chiffres avec ce format XXX-XXX-XXXX au format formel américain qui ressemble à (XXX) XXX-XXXX en utilisant Python3 Regex sub php: vérifie si une variable a / manque de caractères particuliers