Ê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 GraphSearch.
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.
Publications associées (1)
Concepts associés (83)
Regular tree grammar
In theoretical computer science and formal language theory, a regular tree grammar is a formal grammar that describes a set of directed trees, or terms. A regular word grammar can be seen as a special kind of regular tree grammar, describing a set of single-path trees. A regular tree grammar G is defined by the tuple G = (N, Σ, Z, P), where N is a finite set of nonterminals, Σ is a ranked alphabet (i.e.
Grammaire formelle
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).
Linguistique
La linguistique est une discipline scientifique s’intéressant à l’étude du langage. Elle n'est pas prescriptive mais descriptive. La prescription correspond à la norme, c'est-à-dire ce qui est jugé correct linguistiquement par les grammairiens. À l'inverse, la linguistique se contente de décrire la langue telle qu'elle est et non telle qu'elle devrait être. On trouve des témoignages de réflexions sur le langage dès l'Antiquité avec des philosophes comme Platon.
Cours associés (6)
CS-320: Computer language processing
We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in
CS-452: Foundations of software
The course introduces the foundations on which programs and programming languages are built. It introduces syntax, types and semantics as building blocks that together define the properties of a progr
MATH-305: Introduction to partial differential equations
This is an introductory course on Elliptic Partial Differential Equations. The course will cover the theory of both classical and generalized (weak) solutions of elliptic PDEs.
Séances de cours associées (84)
Analyseur: CYK Algorithm
Explore les grammaires formelles, les algorithmes d'analyse, l'efficacité de l'algorithme CYK et la correction syntaxique dans le traitement du langage naturel.
Algorithme CYK
Introduit l'algorithme CYK pour une analyse syntaxique efficace à l'aide de l'analyse des graphiques et discute de sa complexité et de sa technique d'analyse ascendante.
Grammaires sans contexte
Couvre les grammaires sans contexte, leur équivalence avec les automates pushdown et la hiérarchie des types de grammaire.