INSTITUT DE LA FRANCOPHONIE POUR L’INFORMATIQUE

Vers une grammaire ´
electronique du
vietnamien
´
MEMOIRE
pr´esent´ee et soutenue publiquement le 22 d´ecembre 2005

pour l’obtention du

DEPA de l’Institut de la Francophonie pour l’Informatique
(Sp´
ecialit´
e Informatique)

par

LE Hong Phuong

Encadrants :

Laurent ROMARY
Thi Minh Huyen NGUYEN

Directeur de Recherche INRIA
Equipe Langue et Dialogue, LORIA
Equipe Langue et Dialogue, LORIA

Laboratoire Lorrain de Recherche en Informatique et ses Applications — UMR 7503

Mis en page avec la classe thloria.


i

Remerciements
Je tiens tout d’abord à remercier Monsieur Laurent ROMARY, Directeur de Recherche
INRIA de l’équipe Langue et Dialogue du LORIA, pour m’avoir accueilli au sein de
l’équipe en me proposant ce stage.
Je suis reconnaissant à Madame Thi Minh Huyen NGUYEN pour son encadrement,
ses bons conseils, son soutien dévoué, sa patience ainsi que sa touche finale apportée à ce
mémoire.
Je tiens à remercier Madame Isabelle BLANCHARD pour tout ce qu’elle a fait pour
préparer mon arrivée et ma vie à Nancy.
Je remercie également toute l’équipe de recherche Langue et Dialogue : chercheurs,
enseignants, techniciens, doctorants, post-doctorants qui font du LORIA un environnement idéal de travail. Je remercie particulièrement Monsieur Azim ROUSSANALY pour
ses conseils et sa coopération tout au long du travail.
J’adresse un grand merci à Monsieur Mathias ROSSIGNOL pour sa correction du
fran¸cais de ce rapport.
Enfin, j’exprime mon entière reconnaissance à ma famille et mes amis pour leur soutien
et leurs encouragements.


ii


Table des matières
Table des figures


vi

Liste des tableaux

viii

1 Introduction

3

1.1 Problématique et objectif du stage . . . . . . . . . . . . . . . . . . . . . .

3

1.2 Environnement de travail . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.3 Travaux concernés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.4 Aper¸cu du mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2 La grammaire d’arbres adjoints

7


2.1 Système formel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.1.1

Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.1.2

Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.1.3

Arbres dérivés et arbres de dérivation . . . . . . . . . . . . . . . . . 12

2.1.4

Contraintes sur l’adjonction . . . . . . . . . . . . . . . . . . . . . . 13

2.1.5

Propriétés formelles . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.6


Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2 Usage et motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1

Pourquoi TAG ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2.2

Domaine de localité étendu

2.2.3

Dépendances à longue distance . . . . . . . . . . . . . . . . . . . . 21

2.2.4

Traitement des exceptions . . . . . . . . . . . . . . . . . . . . . . . 23

2.2.5

Traitement des mots composés et des expressions semi-figées . . . . 23

. . . . . . . . . . . . . . . . . . . . . . 20

2.3 Aspects informatiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.1

Analyseur syntaxique . . . . . . . . . . . . . . . . . . . . . . . . . . 24


2.3.2

Représentation du lexique . . . . . . . . . . . . . . . . . . . . . . . 24
iii


3 Une grammaire électronique du vietnamien

28

3.1 Principes linguistiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1.1

Principes de bonne formation des arbres élémentaires . . . . . . . . 28

3.1.2

Les principes de propagation des traits syntaxiques . . . . . . . . . 29

3.2 Catégories et traits utilisés . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1

Catégories des nœuds . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.2.2

Traits associés aux nœuds des arbres élémentaires . . . . . . . . . . 31

3.3 Familles à tête verbale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.1


Arbres intransitifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.3.2

Arbres transitifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.3.3

Complément phrastique . . . . . . . . . . . . . . . . . . . . . . . . 33

3.3.4

Arbres ditransitifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.3.5

Arbres ditransitifs à préposition relative . . . . . . . . . . . . . . . 34

3.3.6

Arbres impératifs à complément verbal . . . . . . . . . . . . . . . . 36

3.3.7

Arbres impératifs à complément adjectival . . . . . . . . . . . . . . 36

3.3.8

Complément de direction . . . . . . . . . . . . . . . . . . . . . . . . 37


3.3.9

Verbes de déplacement avec complément nominal . . . . . . . . . . 38

3.3.10 Verbes de mouvement avec complément adjectif . . . . . . . . . . . 38
3.3.11 Arbres ditransitifs avec un verbe de déplacement . . . . . . . . . . . 39
3.3.12 Complément modal . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.13 Complément adjectival . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4 Familles à tête adverbiale

. . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.4.1

Adverbes à gauche . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.4.2

Adverbes à droite . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.5 Familles des compléments facultatifs du syntagme verbal . . . . . . . . . . 42
3.5.1

Complément suffixal avec l’adposition . . . . . . . . . . . . . . . . . 42

3.5.2

Complément suffixal sans adposition . . . . . . . . . . . . . . . . . 42


3.5.3

Complément causal . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.5.4

Complément objectif . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.5.5

Complément de comparaison égale . . . . . . . . . . . . . . . . . . 44

3.5.6

Complément de manière . . . . . . . . . . . . . . . . . . . . . . . . 44

4 Implémentation et traitement informatique

47

4.1 Les choix d’implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2 Introduction au format TAGML2 . . . . . . . . . . . . . . . . . . . . . . . 48
iv


4.2.1

Description des entrées lexicales . . . . . . . . . . . . . . . . . . . . 48

4.2.2


La lexicalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.2.3

Les traits top et bottom

4.2.4

Les co-ancres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.2.5

Les équations de traits . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.2.6

Les libs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.2.7

Les familles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.2.8

Les traits d’arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

. . . . . . . . . . . . . . . . . . . . . . . . 50

4.3 Analyse du vietnamien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.3.1

Le logiciel LLP2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.3.2

Un analyseur LTAG pour le vietnamien . . . . . . . . . . . . . . . . 57

5 Conclusion et perspectives

62

5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Bibliographie

64

v


Table des figures
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8

2.9
2.10
2.11
2.12
2.13
2.14

Schéma général de l’adjonction . . . . . . . . . . . . . . .
Exemples d’arbres initiaux . . . . . . . . . . . . . . . . . .
Exemples d’arbres auxiliaires . . . . . . . . . . . . . . . . .
Exemple de substitution . . . . . . . . . . . . . . . . . . .
Exemple d’adjonction . . . . . . . . . . . . . . . . . . . . .
Arbre initial ou arbre auxiliaire . . . . . . . . . . . . . . .
Arbre dérivé et dérivations pour verre à vin / verre de vin
Historique de la dérivation . . . . . . . . . . . . . . . . . .
Grammaire TAG qui engendre an bn cn dn . . . . . . . . . .
Substitution avec structures de traits . . . . . . . . . . . .
Adjonction avec structures de traits . . . . . . . . . . . . .
Unification des traits . . . . . . . . . . . . . . . . . . . . .
Expression des dépendances à longue distance . . . . . . .
Factorisation morpho-syntaxique du système XTAG . . . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

9
9
9
10
10
11
11
12
14
18
19
19
22
25

3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8

3.9
3.10
3.11
3.12
3.13
3.14
3.15
3.16
3.17
3.18
3.19
3.20

Arbre déclaratif intransitif αnV . . . . . . . . . . . . . . . .
Arbre déclaratif transitif αn0 V n1 . . . . . . . . . . . . . . .
Arbre déclaratif avec complément phrastique αn0 V S . . . .
Arbre ditransitif αn0 V n1 n2 . . . . . . . . . . . . . . . . . . .
Arbre ditransitif à adposition relative au milieu αn0 V n1 On2
Arbre ditransitif à adposition relative avant αn0 V On1 n2 . .
Arbre impératif à complément verbal αn0 V n1 v . . . . . . . .
Arbre impératif à complément adjectival αn0 V n1 a . . . . . .
Arbre auxiliaire de complément de direction βvV . . . . . .
Processus d’adjonction d’un complément de mouvement . . .
Verbe de déplacement après un syntagme verbal . . . . . . .
Verbes de déplacement avec complément nominal αn0 V0 V1 n1
Verbes de mouvement avec complément adjectif αn0 V0 AV1 .
Arbre ditransitif avec un verbe de déplacement αn0 V0 n1 V1 n2
Complément modal αnV v . . . . . . . . . . . . . . . . . . .
Complément adjectival αn0 V a . . . . . . . . . . . . . . . . .
Adverbes à gauche du syntagme verbal βRv . . . . . . . . .

Adverbes à droite du syntagme verbal βvR . . . . . . . . . .
Complément suffixal avec l’adposition βvOn . . . . . . . . .
Complément suffixal sans adposition βvn . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

32
33
34
34
35
35
36
36

37
37
38
38
39
39
40
40
41
42
42
43

vi


vii
3.21
3.22
3.23
3.24
3.25
3.26
3.27
3.28
3.29
3.30
3.31

Complément

Complément
Complément
Complément
Complément
Complément
Complément
Complément
Complément
Complément
Complément

causal est un nom βvCn . . . . . . . . . . . .
causal est un syntagme verbal βv1 Cv2 . . . .
causal est un syntagme adjectival βvCa . . .
causal est une phrase βvCS . . . . . . . . . .
objectif est un nom βvOn . . . . . . . . . . .
objectif est un verbe avec adposition βv1 Ov2
objectif est un verbe sans adposition βv1 v2 .
de comparaison est un nom . . . . . . . . . .
de comparaison est un verbe . . . . . . . . .
modal est un adjectif . . . . . . . . . . . . . .
modal est un verbe . . . . . . . . . . . . . . .

4.1
4.2
4.3
4.4
4.5

Le schème d’analyse pour le vietnamien . . . . .

L’affichage d’arbres élémentaires . . . . . . . . .
Un résultat d’analyse d’une phrase vietnamienne
L’affichage d’arbres de dérivation d’analyse . . .
La lexicalisation des arbres élémentaires . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.

.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

43

44
44
45
45
46
46
46
46
46
46

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.

.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.

.
.
.
.

58
59
60
61
61


Liste des tableaux
3.1 Catégories du vietnamien . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Spécifications des catégories du vietnamien . . . . . . . . . . . . . . . . . . 30
3.3 Traits associés aux nœuds des arbres . . . . . . . . . . . . . . . . . . . . . 32

viii


Résumé
Au long du développement des ressources linguistiques, on peut distinguer entre des
grammaires qui sont dépendantes de programmes et celles qui sont utilisables pour des
applications diverses. Les formalismes de grammaire d’unification (unification-based formalisms) ont été utilisés pour développer des grammaires à large couverture pour l’anglais,
le fran¸cais, l’allemand, le chinois, le japonais, le coréen, etc. Néanmoins, il n’existe pas
une telle grammaire pour le vietnamien, une langue parlée par environ 85 millions de
personnes dans le monde entier.
Dans ce rapport, nous présentons d’abord la première grammaire LTAG (Lexicalized
Tree Adjoining Grammar, grammaire d’arbres adjoints lexicalisée et augmentée par des
structures de traits basées sur l’unification) pour le vietnamien, appelée vnLTAG, qui a

été développée pendant notre stage de recherche au LORIA. La grammaire vise à modéliser la compétence écrite et elle est à la fois indépendante du domaine et de l’application.
Elle peut être utilisée pour l’étiquetage syntaxique, l’analyse et pour la génération du vietnamien. La grammaire que nous avons développée implémente le standard international
ISO/DIS 24610-1, un standard pour la représentation, l’archivage et l’échange des structures de traits dans les applications du traitement des langages naturels, pour l’annotation
et la production des données linguistiques.
Ensuite, nous présentons une procédure robuste d’analyse en utilisant vnLTAG et un
analyseur pour la grammaire qui est basé sur LLP2 – un analyseur syntaxique du LORIA
qui a été développé depuis quelques années. LLP2 est un logiciel d’analyse des grammaires
d’arbres adjoints qui utilise une représentation efficace de grammaires en se basant sur un
format standard XML (appelé TAGML). Pour construire un analyseur pour la grammaire
vietnamien, nous avons, d’une part, adapté et perfectionné presque tous les modules de
LLP2 et, d’autre part, développé quelques nouveaux modules avant de les intégrer au
LLP2.
Enfin, nous effectuons une évaluation pour l’analyseur en utilisant un jeu de phrases
de test. Le jeu vise à couvrir les phénomènes syntaxiques majeurs pour la langue, en se
basant sur un vocabulaire relativement petit. Quelques résultats initiaux sont présentés.
Mots-clés: vietnamien, grammaire, étiquetage, analyse, TAG, LTAG


Abstract
As far as electronic syntactic resources go, one can distinguish between programdependent and reusable grammars. The unification-based grammar formalisms have been
used to develop reusable broad-coverage grammars for English, French, German, Chinese,
Japanese, Korean, etc. However, there does not exist such a grammar for Vietnamese, a
language spoken by about 85 millions people around the world.
In this report, we present the first sizable grammar written for Vietnamese LTAG
developed during our internship at LORIA, named vnLTAG. The grammar is intended to
model writer competence and is both application and domain independent. It can be used
for syntactic tagging, parsing and for generation of Vietnamese. The grammar that we
have developed implements the international standard ISO/DIS 24610-1 that provides a
format to represent, store or exchange feature structures in natural language applications,
for both annotation and production of linguistic data.

We then present a robust parsing scheme using vnLTAG and a parser for the grammar
which is based on LLP2, a syntactic parser that has been developed at LORIA for years.
LLP2 is dedicated LTAG software which uses an effective representation of grammar based
on a standard XML format (called TAGML). To build a parser for Vietnamese grammar,
we have not only adapted and upgraded most of the modules of LLP2 but also developed
from scratch some new modules before integrating them into LLP2.
Finally, we perform an evaluation for the parser using a test suite. The test suite
aims at covering the major syntactic phenomena for the language, using a relatively small
vocabulary. Some initial results are given.
Keywords: Vietnamese, grammar, tagging, parsing, TAG, LTAG


Chapitre 1
Introduction
1.1

Problématique et objectif du stage

Le traitement automatique des langues connaˆıt aujourd’hui un grand développement
et ses applications vont en se diversifiant. La plupart d’entre elles, des plus simples (correction d’orthographe, indexation automatique, extraction de termes) aux plus ambitieuses
(résumé, traduction automatique, génération de textes), ont besoin d’un composant syntaxique.
Nous concevons le composant syntaxique comme un module commun pour des applications diverses, qui peut être constitué de fa¸con indépendante du domaine d’application,
et de la nature de l’application visée.
Les traitements automatiques nécessitent des dictionnaires et des grammaires électroniques d’une précision et d’une exhaustivité non imaginées jusque-là.
De nos jours, un nombre important de grammaires électroniques à large couverture
ont vu le jour pour des langues comme l’anglais, le fran¸cais ou l’allemand. On peut citer
pour l’anglais et le fran¸cais, quelques projets comme :
– le projet Alvey, basé sur HPSG (la grammaire syntagmatique guidée par les têtes –
Head-driven Phrase Structure Grammar ) en Grande-Bretagne ([17]),
– le projet ParGram de grammaires multilingues parallèles, basé sur LFG (la grammaire lexicale fonctionnelle – Lexical Functional Grammar ), chez Xerox ([14]),

– le projet XTAG, basé sur les TAG (la grammaire d’arbres adjoints – Tree Adjoining
Grammar ), à l’Université de Pennsylvanie ([16]),
– le projet FTAG, basé sur TAG, à l’Université Paris 7 ([3]),
– le projet Lingo, basé sur HPSG, au centre CSLI de Stanford ([15]),
Il n’en reste pas moins que pour le vietnamien, il n’existe pas à notre connaissance de
grammaire électronique à large couverture réalisée. Ce rapport s’intéresse à la construction
d’une telle grammaire pour le vietnamien dans le paradigme d’une grammaire fortement
lexicalisée. En effet, nous présentons une grammaire d’arbres adjoints lexicalisée de taille
moyenne pour le vietnamien.
Les grammaires fortement lexicalisées comme les grammaires d’arbres adjoints sont
issues d’une évolution de la réflexion en linguistique formelle et en théorie des langages,
d’une part, et autorisent un traitement informatique relativement efficace de l’analyse
3


4

Chapitre 1. Introduction

syntaxique, d’autre part. Le modèle des grammaires d’arbres adjoints fait partie des grammaires d’unification en ce qu’il s’appuie sur des représentations linguistiques déclaratives
et monotones, vise à une description directe des phénomènes de surface, et utilise des
structures de traits combinées par unification. Il est basé sur des définitions mathématiques rigoureuses et a des propriétés informatiques intéressantes.

1.2

Environnement de travail

Nous avons effectué notre stage au sein de l’équipe Langue et Dialogue du laboratoire
LORIA, une unité de recherche de l’INRIA.
L’Institut National de Recherche en Informatique et en Automatique (INRIA) a l’ambition d’être au plan mondial, un institut de recherche au cœur de la société de l’information.

L’INRIA, institut national de recherche en informatique et en automatique placé sous
la double tutelle des ministères de la recherche et de l’industrie, a pour vocation d’entreprendre des recherches fondamentales et appliquées dans les domaines des sciences et
technologies de l’information et de la communication (STIC). L’institut assure également
un fort transfert technologique en accordant une grande attention à la formation par la
recherche, à la diffusion de l’information scientifique et technique, à la valorisation, à
l’expertise et à la participation à des programmes internationaux. Jouant un rôle fédérateur au sein de la communauté scientifique de son domaine et au contact des acteurs
industriels, l’INRIA est un acteur majeur dans le développement des STIC en France.
L’INRIA est actif au sein d’instances de normalisation comme l’IETF, l’ISO ou le
W3C dont il a été le pilote européen de 1995 à fin 2002.
L’INRIA accueille dans ses 6 unités de recherche situées à Rocquencourt, Rennes, Sophia Antipolis, Grenoble, Nancy et Bordeaux, Lille, Saclay et sur d’autres sites à Paris,
Marseille, Lyon et Metz, 3500 personnes dont 2700 scientifiques, issus d’organismes partenaires de l’INRIA (CNRS, universités, grandes écoles) qui travaillent dans plus de 120
projets (ou équipes) de recherche communs.
Le LORIA, Laboratoire Lorrain de Recherche en Informatique et ses Applications1 ,
est une Unité Mixte de Recherche - UMR 7503 - commune à plusieurs établissements :
– CNRS, Centre National de Recherche Scientifique,
– INPL, Institut National Polytechnique de Lorraine,
– INRIA, Institut National de Recherche en Informatique et en Automatique,
– UHP, Université Henri Poincaré, Nancy 1,
– Nancy 2, Université Nancy 2.
La création de cette unité a été officialisée le 19 décembre 1997 par la signature du
contrat quadriennal avec le Ministère de l’Education Nationale, de la Recherche et de la
Technologie et par une convention entre les cinq partenaires. Cette unité, renouvelée en
2001, succède ainsi au CRIN (Centre de Recherche en Informatique de Nancy), et associe
les équipes communes entre celui-ci et l’Unité de Recherche INRIA Lorraine.
Le LORIA est un Laboratoire de plus de 450 personnes parmi lesquelles
1

http ://www.loria.fr



1.3. Travaux concernés

5

– 150 chercheurs et enseignants-chercheurs,
– un tiers de doctorants et post doctorants,
– des ingénieurs, techniciens et personnels administratifs,
organisé en équipes de recherche et services de soutien à la recherche.
L’objectif du projet Langue et Dialogue du LORIA est de définir des modèles et des
techniques permettant de mettre en œuvre à court, moyen ou long terme des systèmes de
dialogue homme machine finalisés reposant sur une forte composante langagière. Dans ce
cadre, notre activité se développe dans trois directions complémentaires :
– l’étude des mécanismes fondamentaux de la communication en langue naturelle seule
ou accompagnée d’une désignation gestuelle (dialogue multimodal). Cette recherche
s’effectue dans un contexte pluridisciplinaire alliant linguistique et informatique
principalement ;
– la réalisation de systèmes de dialogue effectifs dans le cadre notamment de collaborations industrielles. Cette activité nous permet par ailleurs de disposer d’une
plateforme d’expérimentation pour la validation des différents modèles que nous
concevons ;
– la définition d’outils et de méthodes génériques permettant d’étudier de fa¸con fine
des situations de dialogues réels, issus de la transcription d’expériences de simulation
ou d’observations directes. Ce travail s’appuie sur une expérience acquise depuis
plusieurs années sur la normalisation et la manipulation de ressources linguistiques
(en particulier des « corpus »).

1.3

Travaux concernés

Dans le cadre du stage, tout d’abord, nous avons fait des recherches au sujet du

formalisme de la grammaire d’arbres adjoints. Nous avons dirigé notre attention sur la
bibliographie et l’état de l’art du domaine syntaxique, où le formalisme TAG joue un rôle
important dans l’évolution du domaine de traitement automatique des langages naturels.
Ensuite, nous avons réaliséé à la fois des études sur la grammaire vietnamienne et sur
le développement d’un logiciel d’analyse de la grammaire d’arbres adjoints du fran¸cais (le
logiciel LLP2). En effet, ce logiciel a été développé au sein de l’équipe Langue et Dialogue
du LORIA depuis 1999, et certains de ses modules ne se conforment pas au standard
international pour la représentation, l’échange, et l’archivage des ressources linguistiques
en raison de la disponibilité récente du standard ISO en 2004.
Puis, nous avons développé les modules d’analyse pour le vietnamien et intégré ces
modules au logiciel LLP2. Nous avons également construit un jeu de phrases de test pour
l’analyseur en se basant sur la grammaire vietnamienne.
Enfin, nous avons effectué des évaluations de l’analyseur en donnant les résultats
obtenus.


6

1.4

Chapitre 1. Introduction

Aper¸cu du mémoire

Ce mémoire est divisé en quatre chapitres : une introduction générale, une introduction à la grammaire d’arbres adjoints, une proposition et une implémentation de cette
proposition.
Le premier chapitre présente des informations générales concernant le stage que nous
avons effectué.
Le deuxième chapitre introduit la grammaire d’arbres adjoints telle qu’elle est utilisée
classiquement de nos jours en linguistique informatique. Il comporte aussi un panorama

conséquent de l’évolution historique des traitements accordés au lexique depuis des années
soixante jusqu’aux propositions basées sur des règles lexicales propres à la grammaire
d’arbres adjoints.
Le troisième chapitre donne notre proposition d’une grammaire électronique pour le
vietnamien en se basant au formalisme LTAG.
Le quatrième chapitre a pour vocation d’implémenter la grammaire ainsi proposée.
Nous y présentons le format standard TAGML pour la description des ressources linguistiques pour le traitement informatique et les résultats obtenus.
Le dernier chapitre constitue la conclusion et les perspectives de ce travail. Par ailleurs,
nous proposons une méthodologie de développement grammatical pour le vietnamien dans
le futur.


Chapitre 2
La grammaire d’arbres adjoints
Ce chapitre introduit la grammaire d’arbres adjoints ([2], [4], [5]). La grammaire
d’arbres adjoints (en anglais Tree Adjoining Grammar, ou TAG) est un système de composition d’arbres destiné principalement à l’analyse syntaxique automatique de la langue
naturelle.
La grammaire d’arbres adjoints a été définie comme modèle mathématique au milieu
des années soixante-dix ([19]). Il s’agissait d’une extension des grammaires en chaˆıne utilisées pour formaliser les théories de Z. Harris (1962). Une des motivations principales
des ses auteurs était de définir un système linguistiquement motivé à la capacité générative plus contrainte que celle des grammaires transformationnelles. La définition de la
grammaire d’arbres adjoints comme modèle linguistique complet est récente et s’est fait
en plusieurs étapes, avec des travaux formels ([4],[20],[24]), syntaxiques ([3],[8],[6],[16]) et
sémantiques ([23]).
Ce modèle tire son nom de l’utilisation d’arbres élémentaires (et non de règles de
réécriture) comme unités de base associées aux items lexicaux, qu’il combine par deux
opérations : la substitution et l’adjonction, la seconde lui étant spécifique. Il repose sur
le codage lexical de nombreuses informations et systématise cette tandence en définissant
des grammaires entièrement « lexicalisées ».
Une grammaire d’arbres adjoints est un ensemble fini d’arbres élémentaires combinés
par deux opérations : la substitution et l’adjonction. Dans une grammaire d’arbres adjoints

lexicalisée, tout arbre élémentaire a au moins un de ses nœuds feuilles occupé par un item
lexical qui lui sert de « tête ». ([24]). On dit aussi que l’item lexical « ancre »cet arbre
élémentaire.
Nous commencerons par une présentation générale de la TAG. Puis nous examinons
des exemples de la grammaire fran¸caise pour illustrer les concepts abordés. Ensuite, nous
discutons l’usage et la motivation de la grammaire d’arbres adjoints. Finalement, nous
présentons les aspects informatiques d’un système TAG.
7


8

Chapitre 2. La grammaire d’arbres adjoints

2.1
2.1.1

Système formel
Définitions

Définition 2.1 (Grammaire d’arbres adjoints). Une grammaire d’arbres adjoints est
un système de composition d’arbres défini par :
1. le quintuple < ltVN , VT , S, I, A > où :
– VN est un ensemble fini de symboles, les non-terminaux ;
– VT est un ensemble fini de symboles, les terminaux ;
– S ∈ VN est l’axiome ;
– I est un ensemble d’arbres initiaux. Un arbre initial est un arbre dont les nœuds
non-feuilles sont étiquetés par des non-terminaux et dont les nœuds feuilles sont
étiquetés par des terminaux ou des non-terminaux. Les nœuds feuilles étiquetés
par des non-terminaux sont appelés nœuds de substitution et sont habituellement

marqués par le symbole ↓ ;
– A est un ensemble d’arbres auxiliaires. Un arbre auxiliaire est un arbre dont les
nœuds non-feuilles sont étiquetés par des non-terminaux. Tout arbre auxiliaire
possède un nœud pied. Un nœud pied est un nœud feuille étiqueté par un nonterminal de catégorie identique à la racine et marqué par le symbole ∗. Les autres
nœuds feuilles sont soit des nœuds de substitution soit étiquetés par des terminaux.
De plus, I ∪ A forme l’ensemble des arbres élémentaires. La composition de deux
arbres élémentaires donne pour résultat un arbre dérivé.
2. et les deux opérations de composition suivantes :
– La substitution est une opération qui consiste à remplacer un nœud de substitution
étiqueté par la catégorie X par un arbre élémentaire ou dérivé dont la racine est
étiquetée par X. La substitution de l’arbre α dans l’arbre β produit un nouvel
arbre dérivé, γ.
– L’adjonction est une opération qui consiste à insérer un arbre auxiliaire β dans
un arbre α de manière à produire le nouvel arbre γ. Soit le nœud n2 de α étiqueté
X et β dont le nœud racine est également étiqueté par X. γ est construit de la
manière suivante :
– Le sous-arbre t de α dominé par n est enlevé de α.
– L’arbre auxiliaire β est inséré sous n. La racine de β est identifiée avec n.
– Le sous-arbre t est inséré sous le nœud pied de β. La racine de t, qui est une
copie de n, est identifiée avec le nœud pied de β.
De plus, l’adjonction est interdite sur les nœuds de substitution. Autrement dit,
n ne peut être marqué pour la substitution.
L’adjonction est schématisée en Figure 2.1.
2

Ce nœud est parfois appelé nœud site de l’adjonction.


2.1. Système formel
(β)


(α)

9

(γ)

X

=⇒

X

X

X∗
X
Fig. 2.1 – Schéma général de l’adjonction

2.1.2

Exemples

Arbres élémentaires
La figure 2.2 donne quelques exemples d’arbres élémentaires pour le fran¸cais. Les
arbres initiaux sont utilisés pour la représentation des noms propres ou communs, des
verbes intransitifs ou transitifs à complément nominal ou prépositionnel (Figure 2.2).
(α1 )
N


(α2 )
N

Jean

(α3 )

maison

(α4 )

S

N0 ↓

V

N0 ↓

dort

S

V

N1 ↓

aime

Fig. 2.2 – Exemples d’arbres initiaux


Les arbres auxiliaires sont utilisés pour la représentation des modifieurs (adjectifs,
adverbes, relatives), des verbes à complétives, des verbes modaux et des auxiliaires (Figure
2.3).
(β1 )
N
A

(β2 )
V
N∗

(β3 )
Adv

V∗

belle

beaucoup
(β4 )
V
V

V∗

peut
Fig. 2.3 – Exemples d’arbres auxiliaires

N0 ↓


S

V
veut

S1 ∗


10

Chapitre 2. La grammaire d’arbres adjoints

Les arbres élémentaires correspondent à des structures argumentales complètes : un
prédicat « ancre »un (ou plusieurs) arbre élémentaire comportant au moins un nœud pour
chacun de ses arguments (sous forme de nœuds à substitution ou de nœud pied). L’arbre
α4 comprend les nœuds N0 ou N1 pour le sujet et le complément de aime, l’arbre β3 les
nœuds N0 et S1 ∗ pour le sujet et le complément de veut.
Substitution et adjonction
Les arbres dérivés résultent de la combinaison (la substitution ou l’adjonction) de
plusieurs arbres élémentaires. L’arbre dérivé γ est toujours du même type (initial ou
auxiliaire) que l’arbres où a lieu l’adjonction ou la substitution.
Un exemple de substitution est l’insertion d’un groupe nominal en position sujet dans
un arbre phrastique (Figure 2.4).
(α1 )
N

(α3 )

Jean


N0 ↓

(γ)

=⇒

S

S

V

N0

V

dort

Jean

dort

Fig. 2.4 – Exemple de substitution
Le nœud feuille N0 de l’arbre α3 associé à dort est remplacé par l’arbre initial α1
correspondant à Jean.
Un exemple d’adjonction est l’insertion de l’arbre auxiliaire β2 , correspondant à l’adverbe beaucoup, au nœud intérieur V de l’arbre α3 (Figure 2.5).
(α3 )
N0 ↓


S

V
dort

(β2 )
V

=⇒

V ∗ Adv

(γ2 )

S

N0

V

beaucoup

V

Adv

dort

beaucoup


Fig. 2.5 – Exemple d’adjonction
Le nœud intérieur V de l’arbre initial α3 associé à dort est remplacé par l’arbre auxiliaire β2 correspondant à l’adverbe beaucoup. Le sous-arbre dominé par V dans α3 , ici
réduit au nœud feuille dort, est recopié sous le nœud pied V ∗.
Si le nœud où a lieu l’adjonction est un nœud racine, on obtient la même structure
résultante qu’avec l’opération de substitution, mais pas le même arbre de dérivation.
L’arbre élémentaire dominant dans l’arbre de dérivation est, dans un cas, celui qui re¸coit


11

2.1. Système formel

la substitution, et dans l’autre, celui qui re¸coit l’adjonction. Si l’on considère que les
relations de dominance dans l’arbre de dérivation reflètent des dépendances sémantiques,
on peut se servir de l’alternative entre substitution et adjonction pour faire la différence,
par exemple, entre les constructions N1 Prep N2 où c’est le premier nom qui domine
(sémantiquement) et celles où c’est le second.
Prenons l’exemple des deux expressions verre à vin et verre de vin. La première désigne
un type de verre, tandis que la seconde désigne une certaine quantité de vin. Cette différence sémantique se retrouve au niveau distributionnel : verre de vin a même distribution
que vin, tandis que verre à vin a la distribution de verre :
– J’ai bu du vin / un verre de vin / ? ? un verre à vin.
– J’ai cassé un verre / ? ? un verre de vin / un verre à vin.
On choisit de représenter l’expression verre à N par un arbre initial (1) et verre de N
par un arbre auxiliaire (2) (Figure 2.6).
(2) - verre de
N

(1) - verre à
N
N

verre

SP

N

vin

SP

verre de

N↓

à

(3) - vin
N

N∗

Fig. 2.6 – Arbre initial ou arbre auxiliaire
L’arbre associé à verre de N s’adjoint au nœud racine de l’arbre (3) correspondant à
vin, tandis que l’arbre de verre à N re¸coit, lui, à la substitution à son nœud feuille N
de l’arbre de vin. La structure syntagmatique associée aux deux séquences verre à vin
et verre de vin est la même, ce que montrent bien les arbres dérivés. En revanche, les
relations de dépendance, manifestes dans les schémas de dérivation, sont inversées : la
séquence verre à vin est dérivée à partir de l’arbre initial associé à verre à N, tandis que
la séquence verre de vin est dérivée à partir de l’arbre associé à vin, qui re¸coit l’adjonction
de l’arbre associé à verre de N (Figure 2.7).

Arbre dérivé
N
N
verre

SP
à

Dérivations
(1)

(3)

(3)

(1)

N
vin

Fig. 2.7 – Arbre dérivé et dérivations pour verre à vin / verre de vin
Les deux opérations de combinaison présentent d’autres différences. La substitution
est toujours obligatoire, à un nœud non terminal marqué comme tel. L’adjonction est


12

Chapitre 2. La grammaire d’arbres adjoints

en général facultative mais peut-être marquée comme obligatoire ou comme interdite par

l’ajout de contraintes spécifiques (cf. 2.1.4). La substitution a lieu une fois ; l’adjonction est
un opération réitérable et créatrice d’enchâssements. Un arbre auxiliaire peut s’adjoindre
à lui-même (au nœud racine ou à tout nœud intérieur de même catégorie). L’opération
d’adjonction rend les grammaires TAG plus puissantes que les grammaires hors contexte
et les place dans le groupe des grammaires « légèrement »contextuelles.

2.1.3

Arbres dérivés et arbres de dérivation

Un arbre dérivé est obtenu par une suite d’opérations de combinaisons mettant en jeu
des arbres élémentaires ou dérivés. Cependant, pour un arbre dérivé donné, il n’est pas
possible de déterminer rétrospectivement la manière exacte dont il a été produit. Pour ce
faire, en TAG, on introduit l’arbre de dérivation, la structure associée à l’arbre de dérivé
qui est une trace explicite des opérations ayant servi à engendrer cet arbre dérivé.
Chacun des nœuds de l’arbre de dérivation représente un arbre élémentaire, les arcs
représentent la manière dont ces arbres sont combinés. A la racine de l’arbre de dérivation se trouve l’arbre initial (de racine phrastique) à partir duquel la phrase est dérivée.
Les autres nœuds portent des couples - arbre élémentaire et adresse du nœud de l’arbre
supérieur où cet arbre a été inséré.
Les adresses sont notées selon la convention de Gorn : 0 pour la racine et, pour les
autres nœuds, concaténation de l’adresse du nœud supérieur avec le rang du nœud. Les
nœuds immédiatement dominés par la racine ont les adresses 1, 2,. . .de gauche à droite ;
les nœuds immédiatement dominés par le nœud 1 ont les adresses 1.1, 1.2, etc. Pour
faciliter les calculs, les adresses sont celles des nœuds dans les arbres élémentaires et non
dans l’arbres dérivé.
Un arc plein indique que l’arbre fils a été adjoint sur l’arbre père ; un arc pointillé
indique que l’arbre fils a été substitué sur l’arbre père. L’adresse du nœud sur lequel a
eu lieu l’opération est indiquée sur l’arbre fils. Ainsi, en Figure 2.8, α1 est substitué à
l’adresse 1 de α3 .
(α1 )

N

(α3 )

Jean

N↓

(β5 )
V

S
V

V

dort
α3 (dort)
α1 (Jean)

[1]

(β2 )
V
V∗

semble

β5 (semble)


[2]

β2 (beaucoup)

[0]

Fig. 2.8 – Historique de la dérivation

V∗

Adv
beaucoup


2.1. Système formel

13

L’arbre de dérivation se construit comme illustré en Figure 2.8. La combinaison des
arbres engendre la phrase Jean semble dort beaucoup comme illustré en Figure 2.8. Dans
cet exemple, l’arbre α3 sert de point de départ à la dérivation, car son nœud racine est
étiqueté par l’axiome de la grammaire, S. L’arbre de dérivation indique que :
– α1 est substitué sur le nœud d’adresse 1 de α3 ,
– β5 est adjoint sur le nœud d’adresse 2 de α3 ,
– β2 est adjoint sur le nœud d’adresse 0 de β5 .
TAG interdit d’adjoindre deux arbres auxiliaires sur le même nœud. Cela permet de
préserver un arbre de dérivation non ambigu. A titre d’illustration, supposons que l’on
adjoigne β5 et β2 sur le nœud d’adresse 2 de α3 . L’arbre de dérivation résultant est
ambigu car il ne renseigne pas l’ordre dans lequel les opérations ont lieu. Ainsi cet arbre
de dérivation permet – dans ce cas-ci – d’engendrer deux arbres dérivés différents.

Une définition alternative de la dérivation TAG est proposée par ([27]) dans laquelle
il est possible d’opérer plusieurs adjonctions sur un même nœud, en ajoutant dans l’arbre
de dérivation l’ordre dans lequel les opérations sont réalisées3 . A notre connaissance, cette
variante demeure relativement peu utilisée dans les implémentations. Dans notre cadre,
nous utilisons la version standard de la dérivation.

2.1.4

Contraintes sur l’adjonction

La grammaire d’arbres adjoints est enrichie d’un mécanisme supplémentaire permettant de contraindre l’adjonction. Jusqu’à présent, nous avons vu que d’une part, l’adjonction ne peut avoir lieu que sur un nœud de catégorie identique à celle de la racine et du
nœud pied de l’arbre auxiliaire à adjoindre et que d’autre part, il est interdit d’adjoindre
sur un nœud de substitution. TAG permet en outre d’associer à chaque nœud d’un arbre
une des trois contraintes supplémentaire suivantes :
– Contrainte d’adjonction obligatoire (AO). Le nœud auquel est associé cette contrainte
doit obligatoirement servir de site à une adjonction.
– Contrainte d’adjonction interdite (AI). Le nœud auquel est associé cette contrainte
ne peut servir de site à une adjonction.
– Contrainte d’adjonction sélective (AS). Le nœud auquel est associé cette contrainte
sélectionne un sous-ensemble d’arbres auxiliaires autorisés à s’adjoindre sur ce nœud.
Nous verrons ci-dessous que l’usage de TAG avec structures de traits permet de représenter les contraintes d’adjonction obligatoire et d’adjonction sélective, mais ne permet
pas de représenter la contrainte d’adjonction interdite. Dans la suite de ce texte, où nous
utilisons TAG augmenté de structures de traits, nous utiliserons la notation indicée NA
pour indiquer qu’un nœud est associé à la contrainte d’adjonction interdite.

2.1.5

Propriétés formelles

Langage TAG

Un arbre dérivé complet est un arbre dans lequel il n’est plus possible d’opérer de
substitutions et dont la racine est l’axiome de la grammaire. Soit G est une grammaire
3

Cette variante est motivée par des raisons linguistiques


14

Chapitre 2. La grammaire d’arbres adjoints

TAG. TG est l’ensemble de tous les arbres dérivés complets engendrés par G. Le langage
engendré par G, L(G), est l’ensemble des chaˆınes définies par le feuillage4 de chacun des
arbres de TG .
SNA

S

a

S

d

b

S∗N A

c


Fig. 2.9 – Grammaire TAG qui engendre an bn cn dn

Classe de langage de TAG
La classe de langages engendrée par une grammaire d’arbres adjoints (Tree Adjoining
Languages) comprend la classe des langages hors contexte5 ainsi que des langages qui
sont traditionnellement considérés comme des langages contextuels, comme le langage
an bn cn dn (Figure 2.9) et un fragment du langage copie6 .
On peut montrer qu’aucune TAG n’engendre le langage an bn cn dn en . Autrement dit
TAG n’engendre pas la totalité des langages contextuels. Pour cette raison, les langages
engendrés par les grammaires TAG appartiennent à une classe de langages appelés langages légèrement sensibles au contexte7 .
Lexicalisation d’une grammaire hors contexte
TAG est un résultat important en théorie des langages dans la mesure où il est démontré qu’il permet de lexicaliser fortement une grammaire hors contexte finiment ambigu¨e8
en préservant sa capacité générative forte.
Un formalisme fortement lexicalisé est un formalise constitué :
– d’un ensemble fini de structures finies dans lequel chaque structure est associée à
un élément lexical, et
– muni d’une ou plusieurs opérations de composition.
Les grammaires d’arbres adjoints et les grammaires catégorielles appartiennent à cette
classe de formalismes.
La lexicalisation d’un formalisme se définit comme suit : un formalisme F se lexicalise
par un formalisme F si pour toute grammaire G définie dans F on peut trouver une
4

En anglais yield
On peut montrer que les grammaires hors contexte engendrent le langage an bn mais pas le langage
an bn cn . Une grammaire hors contexte qui engendre an bn comprend les deux règles suivantes : S → a S b
et S → a b ([18]).
6
En anglais copy language
7

En anglais, Mildly context sensitive languages ([4]).
8
Une grammaire hors contexte infiniment ambigu¨e comprend par exemple la règle X → X, ce qui
permet d’engendrer des branches de profondeur quelconque et potentiellement infinie.
5


2.1. Système formel

15

grammaire G définie dans F telle que G est fortement lexicalisée et telle que les capacités
génératives fortes de G et de G sont identiques.
Pour lexicaliser une grammaire hors contexte G, le moyen classique est la mise en forme
normale de Greibach. Cependant, cette opération garantit uniquement une équivalence
faible entre G et G .
Une autre manière de lexicaliser une grammaire hors contexte est de procéder par
extension du domaine de localité des unités de la grammaire. Sous l’œil de la capacité
générative forte, on réinterprète une grammaire hors contexte comme un mécanisme qui
assemble des arbres partiels de profondeur 1.
Ainsi, les règles de grammaires suivantes :
S
VP
V

→ NP VP
→ V NP
→ mange

seront respectivement interprétées par les arbres suivants :

VP

S
NP

VP

V

V
NP

mange

Sous cet angle, une manière de lexicaliser une grammaire hors contexte en préservant sa capacité générative forte consiste à autoriser l’utilisation d’arbres de profondeur
quelconque (≥ 1) comme unité de base de la grammaire. Un tel système s’appelle une
grammaire de substitution d’arbres.
Définition 2.2 (Grammaire de substitution d’arbres). Une grammaire de substitution d’arbres est définie par le quadruple < VN , VT , S, A >, où :
– VN est le vocabulaire non-terminal,
– VT est le vocabulaire terminal,
– S ∈ VN est l’axiome,
– A est un ensemble d’arbres dont les nœuds feuilles sont étiquetés par des terminaux ou des non-terminaux, les nœuds feuilles étiquetés par des non-terminaux sont
appelés nœuds de substitution. Les nœuds non-feuilles sont étiquetés par des nonterminaux,
– et une opération de combinaison sur les arbres, la substitution, qui est définie de
manière identique à la substitution d’une TAG.
De plus, une grammaire de substitution d’arbres lexicalisée est une grammaire de
substitution d’arbres dans laquelle tout arbre comprend au moins un nœud feuille étiqueté
par un terminal.
Insuffisance des grammaires de substitution d’arbres pour la lexicalisation
d’une grammaire hors contexte