Ce cours est en fait une séance pratique sur le traitement des
langues naturelles. Le sujet est tellement vaste que nous ne
verrons qu'une infime portion de l'existant, par le biais de
petits exemples.
Analyse générale
Une analyse non déterministe usant de backtracking risque
assez facilement d'atteindre des temps d'exécution importants,
en particulier si on n'effectue non pas une recherche d'une
solution (c'est-à-dire d'un arbre syntaxique) mais une recherche
de toutes les solutions (de tous les arbres). Les méthodes
d'analyse vues mercredi évitent assez bien cet écueil en
simulant en quelque sorte un comportement déterministe.
Analyse LR
généralisée
Le générateur d'analyseurs syntaxiques bison
permet une analyse GLR
depuis la version 1.5. La directive %glr-parser
mise en préambule du fichier fourni à bison choisit
cette possibilité.
L'archive de travail contient
du code minimaliste pour travailler avec
bison :
corpus.l fait office de corpus de mots
anglais,simplistic.y de grammaire anglaise, etshared.[hc] de bibliothèque d'arbres partagés.
Compilez le code par un simple make et vérifiez son
bon fonctionnement par la commande echo 'She saw the cat
liked the neighbour .' | ./simplistic. Si tout se passe
bien, vous êtes en train de lire
np_0_1 -> She_0_1
rel_5_0 ->
np_2_2 -> the_2_1 cat_3_1
np_5_2 -> the_5_1 neighbour_6_1
vp_4_3 -> liked_4_1 np_5_2
s_2_5 -> np_2_2 vp_4_3
vp_1_6 -> saw_1_1 rel_5_0 s_2_5
s_0_7 -> np_0_1 vp_1_6
Le premier nombre indique l'indice de départ d'un nœud, tandis
que le second nombre indique la longueur d'entrée
couverte. Pourquoi lit-on rel-5-0
comme position pour le pronom relatif passé sous
silence ? Vous pouvez ajouter l'option
--trace à la commande ./simplistic pour
afficher les étapes suivies par bison.
Gestion des ambiguïtés
Saisissez à présent echo 'She saw a neighbour with a
telescope .' | ./simplistic. Quel est le
problème ? Jetez un œil au manuel
de bison et corrigez
simplistic.y en conséquence. Dessinez la forêt
partagée obtenue.
Modification de la grammaire
On souhaite à présent accepter des conjonctions de
coordination. L'analyseur lexical corpus.l prévoit
déjà leur utilisation. Il faut en revanche compléter la
grammaire de simplistic.y pour permettre ces
constructions.
Un exemple de phrase que l'on souhaite traiter est 'She saw
a cat and a neighbour lived next door .'. Cette phrase peut
avoir par exemple les quatre interprétations suivantes :
She [saw [[[a cat and a neighbour] lived] next door]].[She saw a cat] and [a neighbour lived next door].[She [saw [[a cat and a neighbour] lived]]] next door .[[She saw a cat] and [a neighbour lived]] next door .
Limites de nos arbres partagés
Certaines productions des arbres partagés générés jusqu'ici
étaient données plusieurs fois par bison. Le
fichier ubda.y présente une grammaire assez
classique dans les problèmes de complexité. Faites un make
plot pour visualiser le nombre de règles que génère notre
petite bibliothèque de forêts partagées pour cette grammaire.
Des solutions existent pour garantir une grammaire d'arbres
partagés de taille O(n3)
de la longueur de l'entrée [BL89].
Limites de nos grammaires algébriques
Imaginez devoir tenir compte de toutes les constructions
grammaticales possibles.
- La grammaire devient permissive, et finit par accepter
beaucoup de phrases agrammaticales. Donnez un
exemple de phrase anglaise syntaxiquement incorrecte acceptée par
simplistic.y.
- La grammaire grandit pour tenir les différents cas de
figure distincts. Chaque ajout d'une nouvelle construction
syntaxique ajoute de très nombreuses règles dans différentes
parties de la grammaire.
Au-delà des grammaires algébriques
L'inadéquation des grammaires algébriques pour la description
d'une langue naturelle complète est connue depuis leur
conception [Cho56]. Celui-ci y introduit la notion de
grammaire transformationnelle. Ces grammaires sont
des systèmes de réécriture assez libres d'une forme
syntagmatique à une autre. Il donne par exemple
des règles de transformation pour passer à la voie
passive :
NP1 Aux V NP2
→* NP2 Aux-be-en-V by
NP1,
qui transformerait « The man ate the
food. » en « The food was eaten by the man. ».
Les grammaires transformationnelles ont occupé le devant de la
scène linguistique pendant une assez longue période. Elles sont
maintenant un peu délaissées. La complexité de traitement
informatique de leurs règles était très importante (en fait
elles ont une puissance formelle équivalente `des machines de
Turing, ce qui rend l'appartenance d'une phrase au langage
indécidable en général), et certains problèmes linguistiques
étaient difficiles à mettre en œuvre.
Les formalismes grammaticaux explorés actuellement sont dits
faiblement contextuels (mildly context
sensitive en anglais). Ces formalismes permettent de générer
des sur-ensembles des grammaires algébriques, tout en gardant des
temps d'analyse polynomiaux. Ils sont généralement lexicalisés.
La lexicalisation
Une grammaire lexicalisée est une grammaire dans
laquelle chaque règle possède au moins un élément terminal,
appelé l'ancrage. La transformation d'une grammaire
en une grammaire lexicalisée équivalente est une
lexicalisation. La transformation d'une grammaire algébrique en
forme normale de Greibach, où chaque règle est de la forme
A→aα avec A∈N,
a∈Σ et
α∈V*, est un
exemple de lexicalisation.
La lexicalisation des grammaires est significative en
linguistique. Certains estiment que, pour la langue française,
il n'y a pas deux verbes entrant exactement dans les mêmes
structures syntaxiques, sauf pour quelques exceptions dont les
cris d'animaux. Avoir des règles différentes pour chaque
terminal permet un contrôle fin des structures dans lesquelles
ils peuvent entrer.
Lexicalisez partiellement simplistic.y afin de
rejeter l'exemple agrammatical trouvé précédemment.
Lexicalisation forte
On parle d'équivalence forte entre deux grammaires
formelles si elles génèrent la même structure syntaxique. En
général, cette structure est un arbre, et on parle donc
d'équivalence forte si l'ensemble des arbres syntaxiques générés
par une grammaire est identique à l'ensemble généré par l'autre.
Ceci est bien sûr défini par opposition à l'équivalence faible
vue lors du cours de rappels sur les
langages formels, qui ne regarde que l'égalité des ensembles
de chaînes de caractères générées par chaque
grammaire. L'équivalence forte est bien plus utile dans une
analyse de texte, puisqu'en préservant la structure syntaxique
elle facilite le travail d'analyse sémantique qui suit.
On parle donc de lexicalisation forte si la lexicalisation donne
une grammaire fortement équivalente la grammaire
originelle. Nous allons voir un exemple de méthode de lexicalisation
forte qui utilise des grammaires d'arbres.
Grammaires d'arbres par adjonction
Une grammaire d'arbres par substitution (TSG) est un
quadruplet ⟨Σ, N, I, S⟩ où
- Σ est un ensemble fini de symboles terminaux,
- N est un ensemble fini de symboles non
terminaux ; Σ∩N=∅,
- S est un non terminal de départ, et
- I est un ensemble fini d'arbres finis dont les
nœuds internes sont étiquetés par des non terminaux et les
feuilles (sur la frontière) le sont par des symboles terminaux ou non
terminaux. Tous les symboles non terminaux de la frontière sont
marqués pour la substitution par ↓. Les arbres de
I sont appelés des arbres initiaux, et par
convention sont dénotés par des αi.
La figure ci-contre représente une grammaire d'arbres
lexicalisée fortement équivalente à la grammaire algébrique
S → NP VP
VP → adv VP
VP → v
NP → n
Un arbre est dérivé si il est construit en remplaçant, dans un
arbre initial, un non terminal A↓ de la frontière par un
arbre, dérivé ou initial, ayant A pour racine. On peut
ainsi remplacer NP↓ par α3 dans
α1 ci-contre.
Construisez la dérivation dans cette grammaire d'arbres par
substitution générant la phrase « n adv adv v ».
Limites des grammaires d'arbres par substitution
Dans la grammaire d'arbres par substitution donnée précédemment,
un ancrage d'α2 est adv. On aurait
préféré éviter un tel ancrage pour un arbre ayant S pour
racine. Donnez une grammaire d'arbres par
substitution fortement équivalente où ce phénomène ne se produit
pas. Est-ce satisfaisant ?
En fait, toutes les grammaires algébriques ne peuvent pas être
fortement lexicalisées par des grammaires d'arbres par
substitution. Et comme vous venez de le voir, quand une telle
lexicalisation est possible, elle n'est pas toujours bien fondée
linguistiquement.
Grammaires d'arbres par adjonction
Une grammaire d'arbres par adjonction (TAG) est un
quintuplet ⟨Σ, N, I, A, S⟩ où
- ⟨Σ, N, I, S⟩ est une
grammaire d'arbres par substitution,
- A est un ensemble d'arbres auxiliaires
dont les nœuds internes sont étiquetés par des non
terminaux, et les feuilles des terminaux ou des non
terminaux. Les non terminaux de la frontière sont marqués pour
la substitution par ↓, excepté pour un non terminal, le
nœud bas, marqué par une astérisque * et qui
doit être étiqueté par le même non terminal que la racine de
l'arbre. Les arbres de A sont dénotés par
βi.
L'opération d'adjonction consiste à prendre un sous
arbre α' de racine B d'un arbre initial ou dérivé
α, de placer un arbre auxiliaire β de racine B
à cet emplacement dans α, et de placer α' à la place
de B* en bas de β.
Par exemple, l'adjonction de β1 à
l'emplacement de VP dans α6 ci-contre
permet de retrouver l'arbre α2 de la grammaire
par substitution. Donnez les étapes de la
dérivation d'un arbre produisant la phrase « n adv adv
v ».
Le résultat qui nous intéresse ici est que toute grammaire
algébrique non infiniment ambiguë est fortement équivalente à
une grammaire d'arbres par adjonction lexicalisée. De plus, la
lexicalisation forte d'une grammaire d'arbres par adjonction
peut être réalisée avec une grammaire d'arbres par adjonction.
L'analyse syntaxique pour les TAG peut être effectuée en
temps O(n6) par des méthodes inspirées
de CYK ou d'Earley. Le
formalisme des TAG est faiblement
contextuel.
Pour un résumé des résultats sur les grammaire d'arbres par
adjonction, voir le chapitre [JS96] du Handbook of Formal
Languages.
Utilisation des LTAG
La figure ci-dessous présente une grammaire d'arbres par
adjonction lexicalisée. Un arbre de dérivation dans cette
grammaire pour la phrase « She lives next door. »
et l'arbre résultant suivent.
Donnez l'arbre de dérivation et l'arbre résultat pour la phrase
« She lives next next door. ».
Grammaire XTAG de l'anglais
En guise de conclusion à cette séance de travaux pratiques,
nous allons utiliser un analyseur pour la langue anglaise
implémenté à partir d'une grammaire d'arbres par adjonction
lexicalisée [XTA01].
Écrivez une phrase anglaise dans un fichier de test, par exemple
echo "She lives next door ." > test. L'analyse de ce
texte et l'affichage des arbres syntaxiques se fait par la
commande runparser +n test | print_deriv -b | showtrees.
Vous pouvez afficher une portion de la
grammaire utilisée grâce à la commande xtag.show.word
english 'lives', qui affichera tous les arbres ayant
lives comme ancrage. Explorez les possibilités des
outils.
