langage formel (suite)

• La grammaire permet par concaténation de générer les phrases structuralement correctes dans un langage L. L’analyse syntaxique est le processus de perception fournissant la description structurale, par exemple sous forme d’un arbre :

forme dans laquelle un prédicat est la partie d’une proposition exprimant ce qui est dit à propos du sujet. La syntaxe est sujette à ambiguïté, comme dans le cas du premier exemple, où la proposition qu’il allait poursuivre en Australie peut grammaticalement être rattachée soit à c₁, soit à c₂. Son but est le regroupement des mots du langage d’abord en propositions, puis en phrases.

• La sémantique est la relation entre les éléments du langage et l’ensemble des significations qui lui sont attribuées, c’est-à-dire la spécification de la manière dont une machine abstraite interpréterait les éléments (bien formés syntaxiquement) du langage. Ainsi, un symbole est un élément auquel au moins une signification a été attribuée par une règle de sémantique comme une feuille à l’arbre de la syntaxe.

Dans les langages naturels, les ambiguïtés sémantiques sont fréquentes, comme pour le mot charme (enchantement ou arbre).

• La pragmatique est la relation entre un symbole et son utilisateur. Un élément du langage doit avoir une sémantique avant de devenir pragmatiquement significatif, c’est-à-dire avant qu’une règle de pragmatique puisse lui associer une action. En informatique, il s’agit de la phase de génération du code-objet, exécutable sur une machine.

L’informatique a été marquée dès 1960 par la méconnaissance de la sémantique et de la pragmatique aux dépens de l’analyse syntaxique, et donc par une emphase déséquilibrée sur la forme aux dépens du fond, contenu ou sens.

Métalangage et productions

Le premier outil de formalisation d’un langage est un métalangage permettant de le décrire. Dans un cours d’anglais, le français sert de métalangage, mais, dans un cours de français, le français est utilisé comme son propre métalangage. Si l’on reprend la proposition Le chat attrape le rat, on voit qu’elle est composée d’un 〈sujet〉 suivi d’un 〈prédicat〉. Les mots chat ou attrape appartiennent au vocabulaire terminal, tandis que les mots 〈sujet〉 ou 〈verbe〉 appartiennent au vocabulaire sous-jacent des symboles grammaticaux servant de variables métalinguistiques. L’arbre syntaxique peut alors être décrit au moyen d’un ensemble de règles, à l’aide du symbole « : : = », qui signifie peut être composé de, autant pour les langages naturels que pour l’algèbre des automates :

Les règles sont les instructions du métalangage et sont aussi appelées productions, car elles permettent de dériver une proposition en remplaçant les entités syntaxiques (à gauche) par l’une des chaînes d’éléments du vocabulaire (à droite). Les dérivations ne sont pas déterministes, en ce sens qu’il existe deux possibilités pour 〈nom〉 par exemple, et cet ensemble de règles permet donc de dériver aussi : le rat attrape le chat. Cette possibilité peut être exprimée au moyen du symbole | signifiant ou dans une règle unique : 〈nom〉 : : = chat | rat.

Une règle est dite récursive à gauche (respectivement à droite) si elle est de la forme y : : ϖ (respectivement y : : α y) avec α et ϖ dans V*. Pour l’exemple présenté au début, il est nécessaire de distinguer entre les diverses propositions (principale et subordonnées) d’une même phrase (de même un programme peut être découpé en sous-programmes), et cette facilité alourdit notoirement le formalisme des règles.

Grammaires à structure de phrase

Une grammaire définissable par des productions et des automates est dite à structure de phrase. Une production x : : = v, dont v est pris dans l’ensemble V* des suites finies sur le vocabulaire total V = X + T, induit une description z issue d’une description non terminale y et centrée sur v avec y et z dans V*, si et seulement s’il existe des séquences α et ω dans V* telles que y = α x ω et z = α v ω. Par exemple, si x = 〈nom〉, α = 〈article〉, ω = noir et v = chat, alors 〈article〉 〈nom〉 noir ⇒ 〈article〉 chat noir et y = 〈sujet〉.

La séquence « y » produit directement la séquence z dans la grammaire G s’il existe une production x : : = v de G induisant une description non terminale z issue de y et centrée sur v : y ⇒ z avec y, v, z dans V*, de sorte que z est une dérivation directe de y : par exemple 〈article〉 〈nom〉 noir ⇒ 〈article〉 chat noir. Ainsi, la description non terminale y se réduit directement à la description z. La séquence y engendre la séquence z dans la grammaire G s’il existe des séquences intermédiaires t₁, ... t₂ avec r > 1 telles que y ⇒ t₁, ... t_i ⇒ t_i + 1, ..., t_r = z : y  z. Cette relation est réflexive et transitive. Par exemple, en remplaçant x = 〈nom〉 par x₀ = 〈nom composé〉 et 〈nom composé〉 : : = 〈nom〉 〈subordonnée〉 〈virgule〉 et 〈subordonnée〉 : : = qui 〈verbe〉 〈objet〉, une dérivation de longueur deux est obtenue.

Les productions ne font rien de plus que de décrire l’ensemble des arbres syntaxiques possibles, et ceux-ci sont des arbres généalogiques pour une famille dont l’ancêtre commun est σ = phrase, où les descendants immédiats d’un symbole forment une définition équivalente de ce symbole et où seuls les symboles terminaux n’ont pas de descendance. Les dérivations du symbole initial sont appelées formes sententielles. Une phrase est une forme sententielle comprenant seulement des symboles terminaux. Une grammaire à structure de phrases est formellement un quadruple G = (V, P, σ, T), dans lequel V est le vocabulaire incluant le vocabulaire terminal T et l’ensemble X = V — T des symboles grammaticaux (vocabulaire du métalangage), P un ensemble fini non ordonné de règles ou productions x : : = v avec v dans V* et x dans (V — T)* = X*, et σ la variable métalinguistique initiale, par exemple 〈phrase〉 à partir de laquelle est généré l’arbre syntaxique.