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

le différence principale entre expression régulière et grammaire sans contexte est que le les expressions régulières aident à décrire toutes les chaînes d'un langage courant, 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 de conversation en langues naturelles. L'informatique utilise la théorie des langages formels dans une large mesure. En 1956, Noam Chomsky a donné un modèle mathématique de grammaire pour écrire 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. Toute langue pouvant être décrite par une expression régulière est une langue régulière. 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 normaux et une grammaire sans contexte pour écrire une grammaire sans contexte.

Zones clés couvertes

1. Qu'est-ce que l'expression régulière?
     - Définition, exemples
2. Qu'est-ce que la grammaire sans contexte?
     - Définition, exemples
3. Relation entre expression régulière et grammaire sans contexte
     - Schéma d'association
4. Différence entre expression régulière et grammaire sans contexte
     - Comparaison des différences clés

Mots clés

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 autre du côté droit consistant en un seul terminal ou un seul terminal suivi d'un seul non-terminal. Il peut avoir une règle de production comme suit.

X -> a ou X -> a Y

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

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

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

1. Les symboles terminaux, le symbole null 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 *. Ceci représente la fermeture du symbole incluant le symbole vide.

Dans l'ensemble 1, 11, 111, 1111,…

L'expression régulière est R = 1 ^+.  Ce + indique la fermeture d'un symbole excluant le symbole vide.

Qu'est-ce que la grammaire sans contexte?

Dans la théorie du langage formel, le langage sans contexte (LCF) 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 terminaux

S: symbole de départ

P: règle de production

La grammaire sans contexte a le format suivant pour la règle de production.

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

Voici un exemple de grammaire sans contexte. Chaque production consiste en un symbole non terminal et une expression régulière.

Pour générer un langage qui génère un nombre égal de a et 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ésigne une chaîne vide)

→ a a b b b

→ un ³ b ³

En considérant la sortie, le nombre de a est égal au nombre de b. Il a le unⁿ bⁿ forme.

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

• La grammaire sans contexte est une généralisation des expressions régulières.

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

Définition

Une expression régulière est un concept de la théorie des langages formels qui est une séquence de caractères définissant un modèle de recherche. La grammaire libre de contexte est un type de grammaire formelle dans la théorie du langage formel, qui est un ensemble de règles de production décrivant 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. Cela aide à représenter les langues ordinaires. 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. Il s'agit d'une méthode flexible permettant de fournir un moyen flexible et concis de faire correspondre des chaînes de texte. Il définit toutes les chaînes dans la langue normale. D'autre part, la grammaire sans contexte permet de définir toutes les chaînes appartenant à un langage sans contexte. La différence entre expression régulière et grammaire libre de contexte réside dans le fait que les expressions régulières permettent de 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, Point sur les tutoriels, 8 janvier 2018, disponible ici..
2. «Introduction à la grammaire sans contexte». Www.tutorialspoint.com, Point sur les tutoriels, 8 janvier 2018, disponible ici..

Courtoisie d'image:

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