Définition du formalisme

Structures abstraites

Nos structures abstraites sont des arbres, dont les nœuds représentent les composants syntaxiques de l’énoncé, et les feuilles les éléments du lexique. Les arêtes sont étiquetées par des fonctions syntaxiques, dénotant la relation entre le sous-arbre qu’elles dominent et son nœud parent. Par convention, toutes les arêtes sortantes d’un même nœud portent des étiquettes différentes. Un inconvénient de ce choix est que les adjonctions deoivent se faire de manière récursive, plutôt que de permettre, par exemple, à de multiples adverbes de s’appliquer au même niveau. Cela facilite en revanche la visualisation de la forme générale des structures abstraites dans la grammaire d’approximation. En raison de cette convention, et comme l’ensemble des étiquettes d’arêtes apparaissant dans une grammaire est fixé, tous les arbres d’une grammaire sont de degré borné ; ce qui permet de les considérer comme des termes. Tous les nœuds internes de ces termes sont construits au moyen d’un même symbole (noté •) dont l’arité est égale au nombre d’étiquettes d’arête utilisées dans la grammaire. Par conséquent, chaque étiquette d’arête correspond à un entier positif inférieur ou égal à l’arité de • , et les sous-termes correspondant à des sous-arbres inexistants (c’est-à-dire dont la fonction syntaxique n’est pas remplie) sont remplacés par un symbole ⊥, d’arité nulle. Enfin, les éléments du lexique sont représentés par autant de symboles, également d’arité nulle. La figure 3.1 illustre cette correspondance, en présentant à gauche une structure abstraite sous forme d’arbre, et à droite le terme qui l’encode. Cette structure abstraite appartient à notre langage d’exemple, et correspond à l’expression « si vrai alors 1 + 1, sinon 0 ». L’ensemble des étiquettes d’arête susceptibles d’apparaître est alors : {si, alors,sinon, op, arg1, arg2} ; le symbole • des nœuds internes est donc d’arité 6 dans le terme à droite. L’ensemble des feuilles utilisées (les éléments du lexique) est décrit dans la prochaine section.

Entrées lexicales

L’ensemble des étiquettes utilisées pour les feuilles est répertorié dans un lexique, dont les entrées associent chaque étiquette à un ensemble de traits nommés propriétés de l’entrée lexicale. Ces propriétés seront utilisées pour contraindre la grammaticalité des structures abstraites : elles incluront dans le prochain chapitre (consacré aux descriptions linguistiques) des informations syntaxiques telles que les parties du discours, marques d’accord, souscatégorisation, restrictions de sélection, etc. Par hypothèse, un lexique contient un nombre fini d’entrées et de propriétés associées à chaque entrée. Un lexique minimal pour notre langage d’exemple est donné par la table 3.1, incluant des propriétés permettant de distinguer les types de valeurs (booléen, entier), les opérateurs et leur type (logique, arithmétique), ainsi que l’arité (unaire ou non) et les priorités (faible ou forte) de ces derniers. Nous donnons maintenant une définition formelle d’un lexique, construit à partir d’un ensemble fini de mots et d’un ensemble fini de propriétés. Définition 3.1. Étant donné un ensemble fini de symboles L appelés mots du lexique et un ensemble fini de symboles P appelés propriétés (lexicales), une entrée lexicale est une paire (l, Pl), où l ∈ L et Pl ∈ P(P). Un lexique L est simplement défini comme un ensemble (fini) d’entrées lexicales. 

Grammaire d’approximation

Afin de caractériser l’ensemble des structures abstraites valides – c’est-àdire qui dénotent des énoncés syntaxiquement corrects – nous nous appuierons dans un premier temps sur une grammaire régulière de termes. Les termes qu’elle décrit correspondent à des structures abstraites arborescentes, selon l’encodage décrit précédemment. Cette grammaire vise uniquement à spécifier la forme générale des structures abstraites, sans modéliser toutes les règles de bonne formation des énoncés. Le langage ainsi généré illustre simplement la structure récursive de la langue, et est une grossière sur-approximation de l’ensemble des structures abstraites bien formées ; il sera affiné par la suite par l’ajout de contraintes de bonne formation. Dans la suite, nous désignerons cette grammaire indifféremment sous le terme de grammaire d’approximation ou de grammaire support (en raison des contraintes et des règles de linéarisation qui viendront décorer ses productions par la suite). Cette approche hybride n’est pas sans rappeler celle de Boral et Schmitz [2012], qui filtre les arbres de dérivation d’une grammaire hors-contexte à l’aide de la logique dynamique propositionnelle sur les arbres. Les non-terminaux d’une grammaire d’approximation dénotent le type des structures abstraites qu’ils génèrent. En outre, plutôt que d’énumérer toutes les règles lexicales possibles, nous emploierons par souci de concision des propriétés issues du lexique en guise de symboles terminaux : implicitement, ces symboles dénotent n’importe quelle entrée du lexique possédant la propriété correspondante. La figure 3.3 fournit une grammaire d’approximation possible pour notre langage d’exemple en listant ses productions. Elle possède un unique symbole non-terminal E, désignant une expression (arithmétique ou logique). La première production (en haut à gauche) permet de construire des expressions conditionnelles (« si [condition] alors [expression 1], sinon [expression 2] »), la production suivante (à droite) permettant de combiner une ou deux expression(s) au moyen d’un opérateur (la notation « (E) » est explicitée à la fin de cette section), et les deux productions terminales (en bas) permettent de réécrire une expression comme une valeur entière ou booléenne respectivement.