Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Grammaire formelle
Résumé
Une grammaire formelle est un formalisme permettant de définir une syntaxe et donc un langage formel, c'est-à-dire un ensemble de mots admissibles sur un alphabet donné.
La notion de grammaire formelle est particulièrement utilisée en programmation logique, compilation (analyse syntaxique), en théorie de la calculabilité et dans le traitement des langues naturelles (tout particulièrement en ce qui concerne leur morphologie et leur syntaxe).
Un langage est un ensemble de mots, qui sont simplement des séquences de symboles choisis dans un ensemble (en général fini) appelé alphabet. Formellement, si est un ensemble, on note le monoïde libre sur , c'est-à-dire l'ensemble des suites finies d'éléments de , muni de l'opération de concaténation de deux mots. Un langage sur l'alphabet est par définition un sous-ensemble de .
Souvent, les « symboles » que l'on considère lorsqu'on définit un langage par une grammaire formelle sont constitués de plusieurs caractères, de sorte qu'ils correspondent plutôt à ce que l'on appelle des mots dans la langue courante. De même, les « mots » du langage correspondent plutôt à des phrases ou à des textes. Lorsqu'il y a ambiguïté, on parle de lettres ou de caractères pour les symboles de l'alphabet utilisé pour coder les informations ; et on réserve le mot symbole pour ceux de l'alphabet abstrait, qui sont les éléments de base du langage.
Par exemple :
A1 = { a, b, c, d, e } est un alphabet contenant 5 symboles, traditionnellement appelés lettres dans ce cas précis ;
A2 = { 2, 5, @, $, & } est un autre alphabet contenant 5 symboles ;
A3 = { Dét, Adj, Verbe, Nom, Coord, Prép } est un alphabet de 6 symboles pouvant décrire, par exemple, la structure syntaxique d'une phrase dans une langue naturelle.
Une grammaire formelle (ou, simplement, grammaire) est constituée des quatre objets suivants :
un ensemble fini de symboles, appelés symboles terminaux (qui sont les « lettres » du langage), notés conventionnellement par des minuscules ;
un ensemble fini de symboles, appelés non-terminaux, notés conventionnellement par des majuscules ;
un élément de l'ensemble des non-terminaux, appelé axiome, noté conventionnellement ;
un ensemble de règles de production, qui sont des paires formées d'un non-terminal et d'une suite de terminaux et de non-terminaux ; par exemple, .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.