Discussion:Grammaire formelle

Bonjour,

Concernant la première section, 2ème paragraphe :

Je me demandais quelle était la source pour ces définitions. En général, je vois plutôt le terme "lettres" ou "caractères" lorsque les symboles correspondent à un seul signe graphique, et le terme "symbole" dans les autres cas. Jamais les termes "unité lexicale" ou "lexème". Ceux-ci ne sont pas, à ma connaissance, utilisés pour désigner des éléments de l'alphabet, mais exclusivement des "mots", c'est-à-dire : des objets produits à partir de cet alphabet et d'une grammaire associée. Je crains donc qu'il n'y ait contresens, ou extrapolation à partir d'un exemple (d'un livre/article...) non représentatif.

Cordialement, Monsieur Moussu

Dans l'exemple de l'analyse syntaxique (qui est celui auquel fait allusion ma phrase), les symboles de l'alphabet sont bien les lexèmes. Ce sont certes des suites de plusieurs caractères, mais ce sont eux les symboles terminaux de la grammaire, et donc les symboles de l'alphabet.

Pour la même raison, je ne suis pas du tout d'accord avec une partie de tes modifications :

1. L'alphabet n'est pas un ensemble de symboles, parce que ça ne veut rien dire, on n'a pas défini ce que c'était qu'un symbole, à part justement un élément de l'alphabet.
2. Le monoïde libre sur un alphabet ne contient que les suites finies, pas les suites au sens général (indexées par les entiers), encore moins les suites indexées par les ordinaux.
3. Il n'y a pas besoin de « règles de production » pour définir un langage. Un langage, c'est un sous-ensemble quelconque, et il se trouve juste que certains langages peuvent être définis, par exemple, par des grammaires.

Pour ce qui est des sources, il me semble que ce que je dis est la terminologie standard de la théorie des langages. Pour essayer d'être cohérent à la fois avec la terminologie des programmeurs et celle des chercheurs en infos et des matheux, il me semble que le compromis classique est le vocabulaire de la traduction française du Dragon Book.

En passant, dans Wikipédia, il vaut mieux éviter les balises HTML quand elle ne sont pas strictement nécessaires.

MM (pas Utilisateur:MM) 27 avr 2005 à 14:42 (CEST)

Je reprends par point et dans le désordre :

1. point 2 - C'est vrai en pratique. En théorie, rien n'interdit d'indexer la suite sur N (si ce n'est qu'un tel mot est inanalysable, bien sûr...)
2. point 3 - Exact ! Autant pour moi. J'ai trop anticipé. Je re-corrige sur-le-champ.
3. point 1 - & symboles/lexèmes : on a besoin d'un "axiome", de toutes manières.

Mais je crois que je vois la source de nos différends. Ton approche est purement informatique et tu présentes les termes dans le cadre de la théorie des compilateurs. Or, les grammaires formelles sont également utilisées par (et Chomsky les a initialement formalisées en vue de) l'analyse "linguistique". En compilation, "lexème" représente le produit de l'analyse lexicale. Il correspond, linguistiquement, à un "mot". Le terme est utilisé comme équivalent de symbole (ou lettre, ou toute autre dénomination des éléments de l'alphabet) pour l'analyse syntaxique dans le cadre de la construction d'un compilateur, parce qu'il représente l'entrée du deuxième niveau d'analyse. Mais en toute rigueur, c'est un cas d'espèce. Disons un glissement fonctionnel. Comme souvent, les termes changent de signification en changeant de domaine. Il faudrait donc préciser le contexte de la définition pour éviter les ambiguïtés.

NB : Certaines des précisions que j'ai ajoutées (sous-ensemble pour partie, par exemple) ne sont pas formellement indispensables (et sont mêmes redondantes). Elle sont juste faites pour améliorer la lisibilité pour les non-mathématiciens (j'en connais plein en linguistique :o)

PS : pour les balises HTML, je les ai utilisées parce qu'elles sojnt mentionnées dans l'aide de la Wikipedia. Quel problème posent-elles ??

PPS : je pense ajouter une définition des différents types de grammaires en fonction de la nature des règles utilisées.
Monsieur Moussu

J'ai essayé de faire une version de compromis qui reprend celles de tes modifications avec lesquelles je suis d'accord, et seulement celles-là. Sur le point 2, j'insiste, il y a une théorie des langages de mots infinis, mais ce n'est pas celle dont on parle ici ; en tout cas, l'ensemble des suites infinies de symboles n'est certainement pas appelé monoïde libre, ni noté $A^{*}$ (plutôt $A^{\omega }$). Je n'ai pas compris ta réponse sur le point 1, mais je reformule ce que je disais : on prend un ensemble, on lui donne le nom d'alphabet, et par définition, on appelle symboles les éléments de l'alphabet. Enfin, pour le HTML, il y a des âneries dans l'aide ;-). Plus sérieusement, la syntaxe wiki permet d'unifier « naturellement » la présentation et la structure des articles, et de les convertir à un autre format. Si l'on veut faire quelque chose qu'elle ne suffit pas à obtenir, on peut utiliser directement le HTML, mais il vaut mieux éviter quand on peut s'en passer sans dommage. MM (pas Utilisateur:MM) 28 avr 2005 à 09:35 (CEST)

Ah, encore deux choses que j'oubliais :

* pour ce qui est de faire un inventaire des différents types de grammaire, ça me paraît une très bonne idée.

* concernant l'emploi du terme lexème, je ne crois pas que nos points de vue soient contradictoires -- j'ai essayé de clarifier ma formulation du truc, modifie-la si tu as mieux...

MM (pas Utilisateur:MM) 29 avr 2005 à 16:04 (CEST)

Ok, bien noté pour les balises HTML ! Pour le mot "lexème", le but de ma remarque est juste d'éviter les télescopages avec l'acception usuelle du terme, en linguistique du moins. Cela dit, à la réflexion, il me semble que les choses seraient assez claires avec une reformulation plus ou moins du style : "une analyse lexicale produit des lexèmes en sortie. Ces lexèmes peuvent être utilisés comme éléments de l'alphabet en entrée de l'analyse syntaxique".

---

Bonjour, j'ai l'impression que l'article ne traite en fait que des grammaires syntagmatiques (phrase structure grammars en bon anglais) ; je serai pour renommer cet article en conséquence, en modifiant un peu l'introduction.
Sylvain Schmitz 12 décembre 2005 à 20:12 (CET)

Pour continuer la discussion, je viens de voir qu'il y a déjà des articles grammaire générative, grammaire générative et transformationnelle et grammaire universelle ! Un peu de ménage ne ferait pas de mal ; toutes les grammaires formelles ne sont pas génératives, mais les grammaires syntagmatiques, i.e. celles décrites par Noam Chomsky dans son vieil article de 1956 le sont ; les grammaires transformationnelles du même article ne sont pas à proprement parler génératives, ce sont de simples systèmes de réécriture, et elles méritent bien d'être qualifiées de grammaires formelles.
Sylvain Schmitz 12 décembre 2005 à 20:59 (CET)

Salut !

Je suis d'accord. Il y aurait lieu de clarifier tout ça. Je m'apprêtais justeùent à ajouter quelques précisions sur les grammaires régulières, hos-contexte, contextuelles et non contraintes dans le cadre de la théorie de Chomsky. J'attends que tu amorces le ménage pour voir comment insérer ça proprement.

NB : il y a déjà un article "grammaires hors-contexte". Le mieux sera sans doute de créer des articles sur le même modèle pour les autres GF.

Monsieur Moussu 16 décembre 2005 à 12:05 (CET)

---

Bonjour, il me semble que l'exemple de grammaire pour les opérations mathématiques usuelle est ambiguë, est-ce que ca nuit à sa généralité ? parce que telle qu'elle est écrite, A+ B *C peut etre compris comme expr + expr ou bien expr * expr. Aris

L'ambiguité est déconseillée, mais la combattre est difficile (voire les polynômes associatifs de Schützenberger). Si elle est indifférente pour l'acceptation d'un langage, elle nuit à son analyse et à sa traduction ; ici, formaliser un calcul de gauche à droite suppose des règles récursives à gauche seulement, dont l'exploitation informatique est délicate ; une acceptation sans ambiguité (ni analyse) utilisera plutôt des règles à récursivité finale.

--Lf69100 (d) 21 avril 2013 à 21:13 (CEST)

référence

je suggèrerais bien : "Notions sur les grammaires formelles" par Maurice Gross et André Lentin, avec une "Introduction" de Noam Chomsky, Collection Programmation, Gauthier-Villars, 1967. --Lf69100 (d) 21 avril 2013 à 21:13 (CEST)

forme normale de Floyd

Certains compilistes utilisent pour les grammaires non contextuelles les formes normales de Floyd, du style

A --> BC |D, où B est en principe un terminal.

forme qui facilite la représentation d'une grammaire par une liste de structure simple. --Lf69100 (d) 21 avril 2013 à 21:21 (CEST)

Définition de la grammaire formelle

La définition donnée dans la section grammaire est, il me semble, la définition d'une grammaire non contextuelle et pas celle d'une grammaire générale... Si je ne me trompe pas, une correction serait à apporter... The-cellist64 (discuter) 14 mars 2024 à 23:09 (CET)