Cours.article
7
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
7
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Modèles de Langage et Analyse SyntaxiqueCours 2 - SyntaxeAntoine Rozenknopantoine.rozenknop@lipn.univ-paris13.fr7 octobre 201016Plan1 Introduction 12 Grammaires formelles 12.1 Définitions : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.2 Hiérarchie des grammaires formelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2.1 type 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2.2 type 3 : grammaires régulières = grammaires rationnelles . . . . . . . . . . . . . . 22.2.3 type 2 : grammaires hors-contexte = grammaires algébriques . . . . . . . . . . . . 32.2.4 type 1 : grammaires contextuelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2.5 type 0 : grammaire non-contrainte . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Forme Normale de Chomsky 51 IntroductionDans les exemples vus jusqu’ici on s’est limité à des règles de réécritures qui avaient toutes la forme :X !Y ... Y1 noù X est un symbole non-terminal de la grammaire, et Y ... Y sont soit des symboles non-terminaux,1 nsoit des symboles terminaux.Il s’agit en fait d’un type bien particulier de grammaires de réécriture, appelées grammaires hors-contexte, pour lequel on maîtrise des algorithmes d’analyse efficaces, comme on va le voir (plus tard!). Ilen existe d’autres types.Le pionnier en matière de grammaire de réécritures est Noam Chomsky. Dans la suite, on va voir :– ...
Voir
Modèles de Langage et Analyse Syntaxique Cours 2 Syntaxe
Antoine Rozenknop antoine.rozenknop@lipn.univparis13.fr 7 octobre 2010
1
Plan
1 Introduction1 2 Grammairesformelles 1 2.1 Définitions: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 2.2 Hiérarchiedes grammaires formelles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 2.2.1 type4 .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 2.2.2 type3 : grammaires régulières = grammaires rationnelles. . . . . . . . . . . . . .2 2.2.3 type2 : grammaires horscontexte = grammaires algébriques. . . . . . . . . . . .3 2.2.4 type1 : grammaires contextuelles .. . . . . . . . . . . . . . . . . . . . . . . . . . .4 2.2.5 type0 : grammaire noncontrainte. . . . . . . . . . . . . . . . . . . . . . . . . . .5 3 FormeNormale de Chomsky5
1 Introduction
Dans les exemples vus jusqu’ici on s’est limité à des règles de réécritures qui avaient toutes la forme : X→Y1. . .Yn où X est un symbolenonterminalde la grammaire, et Y1. . .Ynsont soit des symboles nonterminaux, soit des symboles terminaux. Il s’agit en fait d’un type bien particulier de grammaires de réécriture, appeléesgrammaires hors contexte!). Il, pour lequel on maîtrise des algorithmes d’analyse efficaces, comme on va le voir (plus tard en existe d’autres types. Le pionnier en matière de grammaire de réécritures est Noam Chomsky. Dans la suite, on va voir : – laclassification des grammaires formelles issue de ses travaux; – cequ’est laforme normale de Chomsky; – commenton peut transformer une grammaire horscontexte quelconque pour obtenir une grammaire équivalente sous forme normale de Chomsky. L’intérêt de cette transformation, qui n’est pas évident au premier abord, apparaîtra clairement lors qu’on s’intéressera aux algorithmes d’analyse syntaxique des grammaires horscontexte. Mais chaque chose en son temps!
2 Grammairesformelles 2.1 Définitions: Grammaire formelle –V: Vocabulaire –VT: Vocabulaire terminal (ensemble de symboles terminaux) –VN: Vocabulaire nonterminlal (ensemble de symboles nonterminaux) –P: Axiome (élément de VN) (un symbole nonterminal) –R: ensemble de règles de récritures de la forme :α→βavec ∗ –α,β∈V –α6=∅
Définition 1.Une grammaire formelleGest un quadruplet (VN, VT, R, P).
Dérivation Définition 2.Une chaîneu1se réécriten une chaîneu2(u1⇒u2) si et seulement si il existe des chaînes de symbolesv1,v2,α,βtels que : 1.u1=v1α v2 u2=v1β v2 2.α=βou(α→β)∈R ∗ Définition 3.Une chaîneu1se dériveen une chaîneu2(u1⇒u2) si unesuccessionde réécritures permet d’obteniru2à partir deu1. Définition 4.Une dérivation est une succession de réécritures.
Langage Définition 5.On appellelangage engendré par Gl’ensemble de toutes les suites de symboles qui dérivent de l’axiome de G : ∗ ∗ L(G)={x/x∈PV et⇒x} Définition 6.On appellelangage sur VTl’ensemble (potentiellement infini) des chaînes delongueurs finiesformées avec des éléments du vocabulaire terminal VT.
Décidabilité Définition 7.Un langage estdécidablesi pour toute phrase on peut savoir au bout d’untemps finisi elle appartient ou nom au langage.
2.2 Hiérarchiedes grammaires formelles La hiérarchie des grammaires formelles décrite par N. Chomsky classe les grammaires de réécriture selon la forme que peut prendre leurs règles. On les donne en ordre inverse, c’estàdire de la forme la plus restrictive à la moins restrictive.
2.2.1 type4 Dans une grammaire de type 4,les parties droites de toutes les règles sont des terminaux. Les éléments de R ont donc la forme :
X→αavec X∈VN α∈VT*
Une telle grammaire ne fait qu’énumérerles phrases de son langage sur VT.
2.2.2 type3 : grammaires régulières = grammaires rationnelles Définition 8.Dans une grammairerégulière à gauche, les règles ont l’une des formes suivantes : X→X, YY a∈VN avec X→a a∈VT Définition 9.Dans une grammairerégulière à droite, les règles ont l’une des formes suivantes : X→a YX, Y∈VN avec X→a a∈VT
Exemple de grammaire régulière à droite P→Pa P→B B→b B→b B
n m Cette grammaire engendre les chaînesa b. ab aab abb aaabbbbbb ...
Utilité en TAL Les grammaires régulières sont utilisées dans : – lareprésentation compacte deslexiques – laconstruction decorrecteurs orthographiquesou de lexiquesrobustesaux erreurs – desgrammaires locales: motscomposés, séquences acceptables de chiffres (nombres,dates) – desgrammaires pour desdomaines très restreints(annonces de vols dans les aéroports)
Limitations Les grammaires de type 3 ne peuvent traiter : n n – leschaînesa bde typea1. . . anb1. . . bn(“respectivement”) n n – leschaînesa bde typea1. . . anbn. . . b1(expressionsparenthésées, structures enchâssées) : En anglais : The dog the stick the fire burned beat bit the cat En français : Le chat que le voisin que le maire que le préfet qui a été condamné a félicité a attrapé est blanc. – leschaînesabac soit. . .soit. . .ni. . .ni. . . – lerejeten fin de phrase des prépositions (en anglais) ou des particules séparables (en allemand) : The girl that I do not want to be caught with. – Lesdépendances à longue distance(interrogatives, clivées.. .) Jean veut savoir quelle fille Marie croit que Paul a vue.
2.2.3 type2 : grammaires horscontexte = grammaires algébriques Définition 10.Une grammaire de type 2, ditehorscontexteoualgébrique, est une grammaire de réécriture dont les parties gauches des règles contiennent un unique nonterminal : X∈VN X→αavec ∗ α∈V
Exemple de grammaire horscontexte P→a Pb P→a b P→
n n Cette grammaire engendre les chaînesa b. “” “ab” “aabb” “aaabbb” ...
Utilité en TAL Les grammaires horscontexte sont adaptées pour : n n – leschaînesa bde typea1. . . anbn. . . b1(expressions parenthésées, structures enchâssées) P→SN SV peut analyser : SN→SN ( P ) The dog the stick the fire burned beat bit the cat P SN SV SN P SN SV SN P SN VN ( () ) The dogthe stickthe fireburned beatbit the cat – leschaînesabac soit. . .soit. . .(X→soit Y soit Y) ni. . .ni. . .(X→ni Y ni Y)
Limitations – Lesgrammaires horscontexte traitent avec difficulté lerejeten fin de phrase des prépositions (en anglais) ou des particules séparables (en allemand).
Solution : dupliquer les règles pour chaque préposition ou particule – Ellesne peuvent traiter lesdépendances à longue distance, le pro. .)(interrogatives, clivées. blème étant par exemple de contraindre un accord selon un syntagme qui sort du contexte de cet accord : Jean veut savoir quelle fille Marie croit que Paul a vue. n m n m – Niles rares langues qui ont des structures de typea bc d n n – Niles chaînesa bde typea1. . . anb1. . . bn(“respectivement”) Henri et Sophie sont repectivement indifférent et séduite par le film. Ces arguments ne sont pas vraiment décisifs pour mettre de côté ces grammaires pour le TAL, car en n m pratique, leset nesont jamais grands.
2.2.4 type1 : grammaires contextuelles Définition 11.Les grammaires de type 1, ditesgrammaires contextuellesse définissent par des règles du type : + α∈V ∗ α→βavecβ∈V |β| ≥ |α| (La partie gauche est non vide, et la partie droite doit contenir plus de symboles que la partie gauche)
Exemple : n n n La grammaire suivante engendre le langagea b c P→C Ba B C→B C P→a P B C
a B→a b b B→b b b C→b c c C→c c
Remarques – Cesgrammaires sontdécidables
le nombre de symboles ne peut que croître dans une dérivation.
Pour déterminer si une phrase de longueurnappartient au langage, il suffit de produire toutes les dérivations en s’arrêtant dès que le nombre de symboles produits dépassen, ce qui se fait en un temps fini. Cependant, un temps fini ne veut pas dire qu’il soit court! En pratique, cette génération exhaustive a une complexité exponentielle enn(le temps d’analyse est proportionnel à l’exponentielle du nombre de mots de la phrase à analyser). – Lesgrammaires sur lesquelles portent la majorité des recherches en TAL se situent entre le type 1 et le type 2.
2.2.5 type0 : grammaire noncontrainte Définition 12.Les grammaires de type 0 se définissent par des règles du type : ∗ α∈V α→βavec ∗ β∈V
Remarque :Ces grammaires ne sont pas décidables.
On a pu remarquer que toutes les grammaires qui ont été écrites pour des langues naturelles pouvaient être récrites en utilisant le formalisme des règles contextuelles.
3 FormeNormale de Chomsky
Noam Chomsky a défini un type particulier de grammaires horscontexte (type 2) : les grammaires horscontexte sousforme normale. En TAL, ces grammaires sont très pratiques pour faire de l’analyse 3 syntaxique : elles permettent l’utilisation d’algorithmes efficaces pour cette tâche, de complexité O(n).
Forme Normale de Chomsky (CNF) Définition 13.Une grammaire horscontexte est sousForme Normale de Chomskysi ses règles ont l’une des deux formes : X∈VN X→Y ZY∈VN avec X→a Z∈VN a∈VT Définition 14.Une grammaire horscontexte est sousCNF étenduesi ses règles peuvent également prendre les formes : X∈VN X→Y Z Y∈VN X→Yavec Z∈VN X→a a∈VT
Mise sous forme normale La plupart des grammaires horscontexte ne sont pas sous forme normale de Chomsky, que ce soient des grammaires du langage naturel ou de langages artificiels (langages de programmation par exemple), ce qui pourrait limiter l’intérêt des algorithmes efficaces que nous verrons plus loin. Heureusement, les grammaires de type 2 ont la propriété intéressante de pouvoir être mises sous forme normale, c’estàdire qu’il existe toujours une grammaire CNF équivalente. Définition 15.Deux grammaire sont diteséquivalentessi elles peuvent produire les mêmes chaînes de symboles terminaux. Dans le cas des grammaires horscontexte, on peut de plus facilement trouver un arbre d’analyse à partir d’un arbre créé avec la grammaire CNF équivalente. La mise sous forme normale se fait en 3 temps : 1. Suppressiondes règles de type :X→α tiβ(oùtiest un terminal etαet/ouβsont non vides) (a) Créerun nonterminalTi (b) Ajouterla règleTi→ti (c) Remplacerla règleX→α tiβparX→α Tiβ 2. Suppressiondes règles de type :X→Y (a) Pourchaque règleZ→α X β, ajouter une règleZ→βα Y. (b) SupprimerX→Y. 3. Suppressiondes règles de type :X→αY Z (a) Créerun nouveau nonterminalXi (b) Ajouterla règleXi→Z α (c) Remplacerla règleX→αY ZparX→Y Xi
La mise sous forme normale d’une grammaire augmenteconsidérablement le nombre de nonterminaux et de règles.
Exemple :
Forme initiale R1: P→SN SV R2: SN→Det N R3: SN→Det N SP R4: SP→Prep SN R5: SV→V R6: SV→V SN R7: SV→V SN SP L5: V→mange
Forme normale de Chomsky R1: P→SN SV R2: SN→Det N R3.1: X1→N SP R3.2: SN→Det X1 R4: SP→Prep SN R1.2: P→SN V R6: SV→V SN R7.2: X2→SN SP R7.1: SV→V X2 L5: V→mange
