Les différence principale entre l'expression régulière et la grammaire sans contexte est que le les expressions régulières aident à décrire toutes les chaînes d'un langage régulier tandis que la grammaire sans contexte aide à définir toutes les chaînes possibles d'un langage sans contexte.

La grammaire désigne les règles syntaxiques pour la conversation dans les langues naturelles. L'informatique utilise dans une large mesure la théorie des langages formels. En 1956, Noam Chomsky a donné un modèle mathématique de grammaire pour l'écriture des langages informatiques. Lorsqu'il est possible de dériver un ensemble de toutes les chaînes d'une grammaire, on dit que le langage est généré à partir de cette grammaire. Deux types de grammaire sont la grammaire régulière et la grammaire sans contexte. Tout langage qui peut être décrit par une expression régulière est un langage régulier. La grammaire sans contexte est une généralisation de l'expression régulière. Il est possible d'utiliser des expressions régulières pour écrire des langages réguliers et une grammaire sans contexte pour écrire une grammaire sans contexte.

Expression régulière, grammaire sans contexte

Qu'est-ce que l'expression régulière

La grammaire régulière génère des langages réguliers. Cette grammaire a un seul non-terminal du côté gauche et un seul côté droit constitué d'un seul terminal ou d'un seul terminal suivi d'un seul non-terminal. Il peut avoir une règle de production comme suit.

X -> un ou X -> un Y

Où X, Y N (non terminal) et a ϵ T (terminal)

Les expressions régulières aident à écrire une grammaire régulière pour décrire les langages réguliers.

Une expression régulière représente un certain ensemble de chaînes de manière algébrique. Certaines règles importantes à suivre lors de l'écriture d'une expression régulière sont les suivantes.

1. Les symboles terminaux, le symbole nul et le symbole vide sont des expressions régulières.
2. L'union de deux expressions régulières est une expression régulière.
3. La concaténation de deux expressions régulières est une expression régulière.
4. L'itération ou la fermeture est une expression régulière.

L'expression régulière pour l'ensemble {0, 1, 2} est la suivante.

R = 0 + 1+2

L'ensemble {abb, a, b, bba} peut être représenté par l'expression régulière suivante.

R = abb + a +b + bba

Considérons l'ensemble, {ϵ, 0, 00, 000, …}

Le est la chaîne vide. L'expression régulière est R = 0*. Cela représente la fermeture du symbole, y compris le symbole vide.

Dans l'ensemble {1, 11, 111, 1111, …..}

L'expression régulière est R = 1 ^+. Ce + dénote la fermeture d'un symbole à l'exclusion du symbole vide.

Qu'est-ce que la grammaire sans contexte

Dans la théorie des langages formels, le langage sans contexte (CFL) est un langage généré par la grammaire sans contexte. Quatre paramètres définissent la grammaire sans contexte (G).

G= {V,, S, P}

V: Ensemble de symboles variables ou non terminaux.

∑: Ensemble de symboles de bornes

S: symbole de démarrage

P: Règle de production

Context Free Grammar a le format suivant pour la règle de production.

A -> a où a = {V, ∑ }* et A ϵ V

Un exemple de grammaire sans contexte est le suivant. Chaque production se compose d'un symbole non terminal et d'une expression régulière.

Pour générer un langage qui génère un nombre égal de a et de b est au format d'un b . La grammaire sans contexte est la suivante.

G = {(S, A), (a, b), (S ->aAb, A -> aAb |)}

Considérant le symbole de départ,

S – > a A b

En appliquant A -> aAb

→ a a A b b

En appliquant à nouveau A -> aAb,

→ a a a A b b b

En appliquant A -> ϵ (Ce symbole dénote une chaîne vide)

→ a a a b b b

→ un ³ b ³

Lorsque l'on considère la sortie, le nombre de a est égal au nombre de b. Il a un b former.

Relation entre l'expression régulière et la grammaire sans contexte

Différence entre l'expression régulière et la grammaire sans contexte

Définition

Une expression régulière est un concept de la théorie du langage formel qui est une séquence de caractères définissant un modèle de recherche. La grammaire sans contexte est un type de grammaire formelle dans la théorie des langages formels, qui est un ensemble de règles de production qui décrivent toutes les chaînes possibles dans un langage formel donné.

Usage

Les expressions régulières aident à représenter certains ensembles de chaînes de manière algébrique. Il aide à représenter les langages réguliers. La grammaire sans contexte aide à définir toutes les chaînes possibles d'un langage sans contexte.

Conclusion

Une expression régulière est une méthode de correspondance de modèle. C'est une méthode flexible pour fournir un moyen flexible et concis de faire correspondre des chaînes de texte. Il définit toutes les chaînes dans le langage normal. D'autre part, la grammaire sans contexte permet de définir toutes les chaînes appartenant à un langage sans contexte. La différence entre l'expression régulière et la grammaire sans contexte est que les expressions régulières aident à décrire toutes les chaînes d'un langage régulier, tandis que la grammaire sans contexte aide à définir toutes les chaînes possibles d'un langage sans contexte.

Référence:

1. « Expressions régulières ». Www.tutorialspoint.com, Tutorials Point, 8 janvier 2018, disponible ici.2. « Introduction à la grammaire sans contexte ». Www.tutorialspoint.com, Tutorials Point, 8 janvier 2018, disponible ici.

Image de courtoisie:

1. "Toolbaricon RegEx" de M0tty - Travail personnel (CC BY-SA 4.0) via Commons Wikimedia